Return to Question

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 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)


postgres=# EXPLAIN ANALYZE
postgres-# SELECT *
postgres-# FROM things
postgres-# WHERE searchable_column %> 'search term'
postgres-# ORDER BY searchable_column <->> 'search term', id
postgres-# 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)

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)

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 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)


postgres=# EXPLAIN ANALYZE
postgres-# SELECT *
postgres-# FROM things
postgres-# WHERE searchable_column %> 'search term'
postgres-# ORDER BY searchable_column <->> 'search term', id
postgres-# 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)

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);

Is there a way to make sorting fast in this query or another way to make the ordering deterministic?

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?