Trigram search gets much slower as search string gets longer
In PostgreSQL 9.6 there will be a new version of pg_trgm, 1.2, which will be much better about this.  With a little effort, you can also get this new version to work under PostgreSQL 9.4 (you have to apply the patch, and compile the extension module yourself and install it).

What the oldest version does is search for each trigram in the query and take the union of them, and then apply a filter. What the new version will do is pick the rarest trigram in the query and search for just that one, and then filter on the rest later.  

The machinery to do this does not exist in 9.1.  In 9.4 that machinery was added, but pg_trgm wasn't adapted to make use of it at that time.

You would still have a potential DOS issue, as the malicious person can craft a query which has only common trigrams.  like '%and%', or even '%a%'



If you can't upgrade to pg_trgm 1.2, then another way to trick the planner would be:

WHERE (lower(unaccent(label)) like lower(unaccent('%someword%'))) 
AND   (lower(unaccent(label||'')) like 
      lower(unaccent('%someword and some more%')));


By concatenating the empty string to label, you trick the planner into thinking it can't use the index on that part of the where clause.  So it uses the index on just the %someword%, and applies a filter to just those rows.



Also, if you are always searching for entire words, you could use a function to tokenize the string into an array of words, and use a regular built-in GIN index (not pg_trgm) on that array-returning function.