Implementing fast and deterministic sort order in PostgreSQL with pg_trgm

Question

We have implemented a similarity search with pg_trgm in a PostgreSQL 13 database using a gist index with searchable_column. The table and index have the following setup:

CREATE TABLE things (
    id uuid PRIMARY KEY,
    searchable_column text
);

CREATE INDEX search_index ON things
USING GIST (searchable_column gist_trgm_ops);

This setup is very fast event with large record sets using queries like:

SELECT *
FROM things
WHERE searchable_column %> 'search term'
ORDER BY searchable_column <->> 'search term'

However, as there are a lot of rows in the table, pagination is necessary. Furthermore, pagination needs a deterministic ordering for the records. This is a problem as if there are a lot of records with the same word similarity score, sorting can take a very long time when using queries like:

SELECT *
FROM things
WHERE searchable_column %> 'search term'
ORDER BY searchable_column <->> 'search term', id

We tried to fix this by using a btree_gist but it does not work if the btree part is after the gist part:

CREATE INDEX search_index ON things
USING GIST (searchable_column gist_trgm_ops, id);

Using separate indexes also didn't have an effect so is there another way to make sorting fast in this query or completely different way to make the ordering deterministic?

EDIT: Here is some EXPLAIN ANALYZE for things table with one million rows with identical searchable_column = 'search term' and unique UUID id. It gives exactly the same result with both of the indexes above.

-- Reproducible with following:
CREATE TABLE things (
    id uuid PRIMARY KEY DEFAULT uuid_generate_v4(),
    searchable_column text
);

CREATE INDEX search_index ON things
USING GIST (searchable_column gist_trgm_ops);

INSERT INTO things (searchable_column) 
SELECT 'search term'
FROM generate_series(1, 1000000);


EXPLAIN ANALYZE
SELECT *
FROM things
WHERE searchable_column %> 'search term'
ORDER BY searchable_column <->> 'search term'
LIMIT 50;
                                                               QUERY PLAN                                                               
----------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.41..5.96 rows=50 width=32) (actual time=3.413..5.768 rows=50 loops=1)
   ->  Index Scan using search_index on things  (cost=0.41..110972.41 rows=1000000 width=32) (actual time=3.411..5.745 rows=50 loops=1)
         Index Cond: (searchable_column %> 'search term'::text)
         Order By: (searchable_column <->> 'search term'::text)
 Planning Time: 0.210 ms
 Execution Time: 5.975 ms
(6 rows)


EXPLAIN ANALYZE
SELECT *
FROM things
WHERE searchable_column %> 'search term'
ORDER BY searchable_column <->> 'search term', id
LIMIT 50;
                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=28444.40..28450.24 rows=50 width=32) (actual time=2032.197..2036.939 rows=50 loops=1)
   ->  Gather Merge  (cost=28444.40..125673.49 rows=833334 width=32) (actual time=2032.195..2036.932 rows=50 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Sort  (cost=27444.38..28486.05 rows=416667 width=32) (actual time=2021.904..2021.907 rows=39 loops=3)
               Sort Key: ((searchable_column <->> 'search term'::text)), id
               Sort Method: top-N heapsort  Memory: 31kB
               Worker 0:  Sort Method: top-N heapsort  Memory: 31kB
               Worker 1:  Sort Method: top-N heapsort  Memory: 31kB
               ->  Parallel Seq Scan on things  (cost=0.00..13603.00 rows=416667 width=32) (actual time=0.043..1965.472 rows=333333 loops=3)
                     Filter: (searchable_column %> 'search term'::text)
 Planning Time: 0.313 ms
 Execution Time: 2037.016 ms
(13 rows)

Answer 1

As I said in the comments, I don't find that gist_trgm_ops scales very well in the first place, and it is very context specific. Your example where every string is identical to every other string, is sure not very realistic. And my go-to examples, using hash digests of random numbers, surely is not realistic for you, either. So your mileage may very.

I thought the optimal plan here (with more realistic data) might be to use an incremental sort, where it gets the rows already sorted by distance (from the GiST index), and then only within the groups with tied distances it needs to re-sort by id. The planner does that fine if you use a btree index to obtain order, but it does not if you use a KNN scan to obtain order. However if you write the query a bit awkwardly with a sub-select returning the distance as an aliased derived column, you can nudge it to run that way:

EXPLAIN ANALYZE
SELECT * from (select *, searchable_column <->> 'search term' dist
FROM things
WHERE searchable_column %> 'search term'
ORDER BY searchable_column <->> 'search term') foo 
order by dist,id
LIMIT 50;

---------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=20.25..212.08 rows=50 width=33) (actual time=215.309..215.317 rows=50 loops=1)
   ->  Incremental Sort  (cost=20.25..3987.15 rows=1034 width=33) (actual time=215.307..215.311 rows=50 loops=1)
         Sort Key: ((things.searchable_column <->> 'search term'::text)), things.id
         Presorted Key: ((things.searchable_column <->> 'search term'::text))
         Full-sort Groups: 1  Sort Method: quicksort  Average Memory: 30kB  Peak Memory: 30kB
         Pre-sorted Groups: 1  Sort Method: top-N heapsort  Average Memory: 30kB  Peak Memory: 30kB
         ->  Index Scan using search_index on things  (cost=0.41..3935.68 rows=1034 width=33) (actual time=1.157..214.978 rows=1000 loops=1)
               Index Cond: (searchable_column %> 'search term'::text)
               Order By: (searchable_column <->> 'search term'::text)
 Planning Time: 0.476 ms
 Execution Time: 215.509 ms

In this case, I used a mixed dataset with 1e6 random hash digest rows and 1e3 rows with duplicates of 'search term'.

In my hands, I had to set enable_sort=off to get this plan as it preferred a different plan which in which it used the index only for the %> and not the <->>, and then just sorted all rows surviving %> and applied the limit to them. If I set pg_trgm.word_similarity_threshold = 0 then I got the incremental sort even without having to set enable_sort=off. But how this applies to your real case, I don't know.

In some real world conditions, I generally find it faster to use the GIN index than the GiST index, with judicious settings of the similarity threshold.