Optimizing postgres sorting by word_similarity

Question

I have a table with 2M rows of hotel names in Postgresql 12. I am building a typeahead so users can quickly find the hotel by name. I have played around with different Postgres options including FTS, trigrams, and levenshtein distance.

word_similarity in pg_trgm gives me the best results, but whenever I need to sort by the similarity score, things get too slow (without sorting the query finishes in milliseconds):

SELECT name, word_similarity('trade center new york mariott', name) AS sml from hotels_hotel where 'trade center new york mariott' %> name ORDER BY sml DESC LIMIT 5;

                                          name                                          |    sml
----------------------------------------------------------------------------------------+------------
 Courtyard by Marriott New York Downtown Manhattan/World Trade Center Area              | 0.53846157
 Fairfield Inn & Suites by Marriott New York Downtown Manhattan/World Trade Center Area | 0.53846157
 Residence Inn by Marriott New York Downtown Manhattan/World Trade Center Area          | 0.53846157
 AC Hotel by Marriott New York Times Square                                             |    0.53125
 Courtyard by Marriott World Trade Center, Abu Dhabi                                    |  0.5263158
(5 rows)

Time: 9602.969 ms (00:09.603)

EXPLAIN (ANALYZE, BUFFERS, VERBOSE, COSTS) SELECT name, word_similarity('trade center new york mariott', name) AS sml from hotels_hotel where 'trade center new york mariott' %> name ORDER BY sml DESC LIMIT 5;
                                                                                          QUERY PLAN                                                                                          
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=65390.53..65391.11 rows=5 width=27) (actual time=9619.113..9625.482 rows=5 loops=1)
   Output: name, (word_similarity('trade center new york mariott'::text, (name)::text))
   Buffers: shared hit=1746167
   ->  Gather Merge  (cost=65390.53..65589.11 rows=1702 width=27) (actual time=9619.109..9625.474 rows=5 loops=1)
         Output: name, (word_similarity('trade center new york mariott'::text, (name)::text))
         Workers Planned: 2
         Workers Launched: 2
         Buffers: shared hit=1746167
         ->  Sort  (cost=64390.50..64392.63 rows=851 width=27) (actual time=9612.578..9612.580 rows=4 loops=3)
               Output: name, (word_similarity('trade center new york mariott'::text, (name)::text))
               Sort Key: (word_similarity('trade center new york mariott'::text, (hotels_hotel.name)::text)) DESC
               Sort Method: top-N heapsort  Memory: 25kB
               Worker 0:  Sort Method: top-N heapsort  Memory: 25kB
               Worker 1:  Sort Method: top-N heapsort  Memory: 25kB
               Buffers: shared hit=1746167
               Worker 0: actual time=9610.098..9610.100 rows=5 loops=1
                 Buffers: shared hit=581861
               Worker 1: actual time=9609.314..9609.317 rows=5 loops=1
                 Buffers: shared hit=579828
               ->  Parallel Index Only Scan using hotels_hotel_name_a9005e17 on public.hotels_hotel  (cost=0.43..64376.37 rows=851 width=27) (actual time=4.040..9606.166 rows=15070 loops=3)
                     Output: name, word_similarity('trade center new york mariott'::text, (name)::text)
                     Filter: ('trade center new york mariott'::text %> (hotels_hotel.name)::text)
                     Rows Removed by Filter: 666002
                     Heap Fetches: 2
                     Buffers: shared hit=1746113
                     Worker 0: actual time=0.281..9603.591 rows=14890 loops=1
                       Buffers: shared hit=581834
                     Worker 1: actual time=8.157..9602.811 rows=14678 loops=1
                       Buffers: shared hit=579801
 Planning Time: 0.396 ms
 Execution Time: 9625.576 ms
(31 rows)

Time: 9626.933 ms (00:09.627)

Is there any way I can optimize this query? Happy to build a huge index as I suppose is needed.

Why word_similarity is best for my use case:

• allows typos (notice I misspell marriott in my query)
• allows different ordering of the words

---

Edit 1

The explain analyze without sorting:

EXPLAIN ANALYZE SELECT name, word_similarity('trade center new york mariott', name) AS sml from hotels_hotel where 'trade center new york mariott' %> name LIMIT 5;
                                                      QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..1264.75 rows=5 width=27) (actual time=0.391..15.981 rows=5 loops=1)
   ->  Seq Scan on hotels_hotel  (cost=0.00..516777.29 rows=2043 width=27) (actual time=0.384..15.969 rows=5 loops=1)
         Filter: ('trade center new york mariott'::text %> (name)::text)
         Rows Removed by Filter: 292
 Planning Time: 0.285 ms
 Execution Time: 16.041 ms
(6 rows)

Time: 17.800 ms

Edit 2

The relevant indices present on the table:

CREATE INDEX autocomplete_gist ON public.hotels_hotel USING gist (name gist_trgm_ops)
CREATE INDEX autocomplete_name_idx ON public.hotels_hotel USING gin (name gin_trgm_ops)
CREATE INDEX hotels_hotel_name_a9005e17 ON public.hotels_hotel USING btree (name)
CREATE INDEX hotels_hotel_name_a9005e17_like ON public.hotels_hotel USING btree (name varchar_pattern_ops)
CREATE UNIQUE INDEX hotels_hotel_pkey ON public.hotels_hotel USING btree (id)
CREATE INDEX hotels_hotel_popularity_05985c85 ON public.hotels_hotel USING btree (popularity)

Edit 3

The new query:

EXPLAIN (ANALYZE, BUFFERS) SELECT name, word_similarity('trade center new york mariott', name) AS sml from hotels_hotel ORDER BY name <->> 'trade center new york mariott' LIMIT 5;
                                                                       QUERY PLAN

 Limit  (cost=0.41..5.65 rows=5 width=31) (actual time=3632.397..3633.554 rows=5 loops=1)
   Buffers: shared hit=1 read=32537
   I/O Timings: read=184.432
   ->  Index Scan using autocomplete_gist on hotels_hotel  (cost=0.41..2140836.75 rows=2043215 width=31) (actual time=3632.394..3633.548 rows=5 loops=1)
         Order By: ((name)::text <->> 'trade center new york mariott'::text)
         Buffers: shared hit=1 read=32537
         I/O Timings: read=184.432
 Planning Time: 0.250 ms
 Execution Time: 3679.847 ms

Answer 1

Use a GiST index:

CREATE INDEX ON hotels_hotel USING gist (name gist_trgm_ops);

and search like this:

SELECT name,
       word_similarity('trade center new york mariott', name) AS sml
FROM hotels_hotel
ORDER BY name <->> 'trade center new york mariott'
LIMIT 5;

That will get you the five closest matches.

Answer 2

You might have better luck with the GIN index rather than GiST.

GIN doesn't support KNN the way GiST does, so you instead you would have to apply the match operation with appropriate value of pg_trgm.word_similarity_threshold, then sort the row which survive that.

SELECT name, word_similarity('trade center new york mariott', name) AS sml from hotels_hotel 
WHERE name %> 'trade center new york mariott' 
ORDER BY name <->> 'trade center new york mariott' 
LIMIT 5;

The planner doesn't make very clever distinctions between the cost of GIN and GiST indexes, so you might need to just drop the GiST index to get it to use the GIN.