16

In a Postgres 9.1 database, I have a table table1 with ~1.5M rows and a column label (simplified names for the sake of this question).

There is a functional trigram-index on lower(unaccent(label)) (unaccent() has been made immutable to allow its use in the index).

The following query is quite fast:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword%')));
 count 
-------
     1
(1 row)

Time: 394,295 ms

But the following query is slower:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword and some more%')));
 count 
-------
     1
(1 row)

Time: 1405,749 ms

And adding more words is even slower, even though the search is stricter.

I tried a simple trick to run a subquery for the first word and then a query with the full search string, but (sadly) the query planner saw through my machinations:

EXPLAIN ANALYZE
SELECT * FROM (
   SELECT id, title, label from table1
   WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(unaccent(label)) like lower(unaccent('%someword and some more%'));
Bitmap Heap Scan on table1  (cost=16216.01..16220.04 rows=1 width=212) (actual time=1824.017..1824.019 rows=1 loops=1)
  Recheck Cond: ((lower(unaccent((label)::text)) ~~ '%someword%'::text) AND (lower(unaccent((label)::text)) ~~ '%someword and some more%'::text))
  ->  Bitmap Index Scan on table1_label_hun_gin_trgm  (cost=0.00..16216.01 rows=1 width=0) (actual time=1823.900..1823.900 rows=1 loops=1)
        Index Cond: ((lower(unaccent((label)::text)) ~~ '%someword%'::text) AND (lower(unaccent((label)::text)) ~~ '%someword and some more%'::text))
Total runtime: 1824.064 ms

My ultimate problem is that the search string comes from a web interface which may send quite long strings and thus be quite slow and may also constitute a DOS vector.

So my questions are:

  • How to speed up the query?
  • Is there a way to break it into subqueries so that it is faster?
  • Maybe a later version of Postgres is better? (I tried 9.4 and it does not seem faster: still the same effect. Maybe a later version?)
  • Maybe a different indexing strategy is needed?
  • 1
    It must be mentioned that unaccent() is also provided by an additional module and Postgres does not support indexes on the function by default since it's not IMMUTABLE. You must have altered something and you should mention what you did exactly in your question. My standing advice: stackoverflow.com/a/11007216/939860. Also, trigram indexes support case-insensitive matching out of the box. You can simplify to: WHERE f_unaccent(label) ILIKE f_unaccent('%someword%') - with a matching index. Details: stackoverflow.com/a/28636000/939860. – Erwin Brandstetter Aug 20 '15 at 4:22
  • I simply declared unaccent immutable. I added this to the question. – P.Péter Aug 24 '15 at 13:24
  • Be aware that the hack is overwritten when you update the unaccent module. One of the reasons why I suggest a function wrapper instead. – Erwin Brandstetter Sep 15 '15 at 22:06
34
+100

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.

  • 13
    Worth mentioning that you were the one to write the patch. And preliminary performance tests are impressive. This really deserves more upvotes (also for the explanation and workaround with the current version). – Erwin Brandstetter Sep 12 '15 at 20:21
  • I would be more interested in at least a reference to the machinery you used to implement the patch that wasn't there in 9.1. But, I agree w/ Erwin bad ass answer. – Evan Carroll Dec 25 '17 at 16:51
3

I have found a way to scam the query planner, it is a quite simple hack:

SELECT *
FROM (
   select id, title, label
   from   table1
   where  lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

EXPLAIN output:

Bitmap Heap Scan on table1  (cost=6749.11..7332.71 rows=1 width=212) (actual time=256.607..256.609 rows=1 loops=1)
  Recheck Cond: (lower(unaccent((label_hun)::text)) ~~ '%someword%'::text)
  Filter: (lower(lower(unaccent((label)::text))) ~~ '%someword and some more%'::text)
  ->  Bitmap Index Scan on table1_label_hun_gin_trgm  (cost=0.00..6749.11 rows=147 width=0) (actual time=256.499..256.499 rows=1 loops=1)
        Index Cond: (lower(unaccent((label)::text)) ~~ '%someword%'::text)
Total runtime: 256.653 ms

So, as there is no index for lower(lower(unaccent(label))), this would create a sequential scan, so it gets turned into a simple filter. What is more, a simple AND will also do the same:

SELECT id, title, label
FROM table1
WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
AND   lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

Of course, this is a heuristic that may not work well, if the cut-out part used in the index scan is very common. But in our database, there is not really that much repetition, if I use about 10-15 characters.

There are two small questions remaining:

  • Why can't postgres figure out that something like this would be beneficial?
  • What does postgres do in the 0..256.499 time range (see analyze output)?
  • 1
    In the time range between 0 and 256.499 it is building the bitmap. At 256.499 it produces its first output, which is the bitmap. Which is also its last output, as it only produces a single output--a single completed bitmap. – jjanes Aug 19 '15 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.