Postgresql – Slow query times for similarity searches with pg_trgm indices

We added two pg_trgm indices to a table, to enable fuzzy searching by either email address or name, as we need to find users by name, or email addresses which have been misspelled during signup (e.g. "@gmail.con"). ANALYZE was run after index creation.

However, doing a ranked search on either of these indices is very slow in the vast majority of cases. i.e. with an increased timeout, a query might return in 60 seconds, on very rare occasions as fast as 15 seconds, but usually queries will time out.

pg_trgm.similarity_threshold is the default value of 0.3, but bumping this up to 0.8 didn't seem to make a difference.

This particular table has over 25 million rows, and is constantly queried, updated, and inserted into (the mean time for each is under 2ms). The setup is PostgreSQL 9.6.6 running on an RDS db.m4.large instance with general purpose SSD storage, and more-or-less default parameters. The pg_trgm extension is version 1.3.

Queries:

• SELECT *
  FROM users
  WHERE email % 'chris@example.com'
  ORDER BY email <-> 'chris@example.com' LIMIT 10;
  

• SELECT *
  FROM users
  WHERE (first_name || ' ' || last_name) % 'chris orr'
  ORDER BY (first_name || ' ' || last_name) <-> 'chris orr' LIMIT 10;
  

These queries do not need to be run very often (dozens of times a day), but they should be based on the current table state, and ideally return within around 10 seconds.

Schema:

=> \d+ users
                                          Table "public.users"
          Column   |            Type             | Collation | Nullable | Default | Storage  
-------------------+-----------------------------+-----------+----------+---------+----------
 id                | uuid                        |           | not null |         | plain    
 email             | citext                      |           | not null |         | extended 
 email_is_verified | boolean                     |           | not null |         | plain    
 first_name        | text                        |           | not null |         | extended 
 last_name         | text                        |           | not null |         | extended 
 created_at        | timestamp without time zone |           |          | now()   | plain    
 updated_at        | timestamp without time zone |           |          | now()   | plain    
 …                 | boolean                     |           | not null | false   | plain    
 …                 | character varying(60)       |           |          |         | extended 
 …                 | character varying(6)        |           |          |         | extended 
 …                 | character varying(6)        |           |          |         | extended 
 …                 | boolean                     |           |          |         | plain    
Indexes:
  "users_pkey" PRIMARY KEY, btree (id)
  "users_email_key" UNIQUE, btree (email)
  "users_search_email_idx" gist (email gist_trgm_ops)
  "users_search_name_idx" gist (((first_name || ' '::text) || last_name) gist_trgm_ops)
  "users_updated_at_idx" btree (updated_at)
Triggers:
  update_users BEFORE UPDATE ON users FOR EACH ROW EXECUTE PROCEDURE update_modified_column()
Options: autovacuum_analyze_scale_factor=0.01, autovacuum_vacuum_scale_factor=0.05

(I'm aware that we should probably also add unaccent() to users_search_name_idx and the name query…)

Explains:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM users WHERE (first_name || ' ' || last_name) % 'chris orr' ORDER BY (first_name || ' ' || last_name) <-> 'chris orr' LIMIT 10;:

Limit  (cost=0.42..40.28 rows=10 width=152) (actual time=58671.973..58676.193 rows=10 loops=1)
  Buffers: shared hit=66227 read=231821
  ->  Index Scan using users_search_name_idx on users  (cost=0.42..100264.13 rows=25153 width=152) (actual time=58671.970..58676.180 rows=10 loops=1)
        Index Cond: (((first_name || ' '::text) || last_name) % 'chris orr'::text)
        Order By: (((first_name || ' '::text) || last_name) <-> 'chris orr'::text"
        Buffers: shared hit=66227 read=231821
Planning time: 0.125 ms
Execution time: 58676.265 ms

The email search is more likely to time out than the name search, but that's presumably because the email addresses are so similar (e.g. a lot of @gmail.com addresses).

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM users WHERE email % 'chris@example.com' ORDER BY email <-> 'chris@example.com' LIMIT 10;:

Limit  (cost=0.42..40.43 rows=10 width=152) (actual time=58851.719..62181.128 rows=10 loops=1)
  Buffers: shared hit=83 read=428918
  ->  Index Scan using users_search_email_idx on users  (cost=0.42..100646.36 rows=25153 width=152) (actual time=58851.716..62181.113 rows=10 loops=1)
        Index Cond: ((email)::text % 'chris@example.com'::text)
        Order By: ((email)::text <-> 'chris@example.com'::text)
        Buffers: shared hit=83 read=428918
Planning time: 0.100 ms
Execution time: 62181.186 ms

What could be a reason for the slow query times? Something to do with the number of buffers being read? I couldn't find much information about optimising this particular kind of query, and the queries are very similar to those in the pg_trgm documentation anyway.

Is this something that we could optimize, or implement better in Postgres, or would looking to something like Elasticsearch be a better fit for this particular use case?