What should I do so returning 200 rows is at least as fast as returning 1000 rows when performing partial match queries on an indexed column?

Question

I have a PostgreSQL 17 table table0. It has a single column col0 containing random strings of 2 to 16 characters. I would like to perform partial match queries, hence I created a GIN index with gin_trgm_ops. To my surprise, I found that I can select up to 1000 rows containing abc much faster than up to 200 rows containing abc. Reproducible setup:

Launch DB using Docker:

docker run \
    --name postgres-db \
    -e POSTGRES_DB=postgres \
    -e POSTGRES_USER=postgres \
    -e POSTGRES_PASSWORD=mysecretpassword \
    -p 5432:5432\
    -d postgres

I execute queries using DBeaver or by saving them to query.sql and then:

PGPASSWORD=mysecretpassword psql \
    -h localhost \
    -p 5432 \
    -U postgres \
    -d postgres \
    -v ON_ERROR_STOP=1 \
    -f query.sql

Set up table:

create table public.table0 (
    col0 varchar(25)
);

select setseed(0.12343);

insert into table0 (col0)
select substring(md5(random()::text), 1, (2 + (random() * 14))::int)
from generate_series(1, 12345678);

create extension pg_trgm;
create index col0_gin_trgm_idx on table0 using gin (col0 gin_trgm_ops);

vacuum (full, analyze) table0;

Check execution plan and runtime of selecting a 200 rows containing abc:

explain analyze
select * from table0 where col0 like '%abc%' limit 200;

Output:

                                                    QUERY PLAN                                                     
-------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..352.27 rows=200 width=9) (actual time=0.672..49.646 rows=200 loops=1)
   ->  Seq Scan on table0  (cost=0.00..216621.29 rows=122985 width=9) (actual time=0.671..49.599 rows=200 loops=1)
         Filter: ((col0)::text ~~ '%abc%'::text)
         Rows Removed by Filter: 114081
 Planning Time: 4.540 ms
 Execution Time: 50.960 ms
(6 rows)

Check execution plan and runtime of selecting up to a 1000 rows containing abc:

explain analyze
select * from table0 where col0 like '%abc%' limit 1000;

Output:

                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=848.36..1369.03 rows=1000 width=9) (actual time=17.373..26.987 rows=1000 loops=1)
   ->  Bitmap Heap Scan on table0  (cost=848.36..64883.21 rows=122985 width=9) (actual time=17.371..26.931 rows=1000 loops=1)
         Recheck Cond: ((col0)::text ~~ '%abc%'::text)
         Heap Blocks: exact=846
         ->  Bitmap Index Scan on col0_gin_trgm_idx  (cost=0.00..817.62 rows=122985 width=0) (actual time=14.689..14.690 rows=21318 loops=1)
               Index Cond: ((col0)::text ~~ '%abc%'::text)
 Planning Time: 2.165 ms
 Execution Time: 27.356 ms
(8 rows)
                                                            

As visible, when I use LIMIT 200, the engine is doing a Seq Scan on table0, but when I have LIMIT 1000, Bitmap Index Scan on col0_gin_trgm_idx is used. This superficially explains why the query using LIMIT 200 took 4.540+50.960= 55.5 milliseconds, while the LIMIT 1000 query took less, 2.165+27.356=29.521 milliseconds.

I read (see this or this) that ideally I should not try to force the use of indexes in a production environment. Naively, it seems that using the index to search for 200 rows containing abc would be faster than the sequential scan currently used, as using the index to search for 1000 rows is faster than searching for 200 rows using sequential scan.

In my real world scenario (Aurora PostgreSQL instance running on AWS RDS), this difference is limiting: when I need to select 25 rows from my table, it is much faster to select a 100 of them, and then just filter those 100 by other means than postgresql (or I can just modify the application so that selecting 100 rows instead of 25 is also ok).

I am wondering if I am doing something suboptimal with the indexing, or I am missing something.

What should I do so querying with LIMIT 200 is at least as fast as querying with LIMIT 1000?

I am primarily interested in methods advisable to use in a production environment. It is safe to assume that table0 will not need to be modified to edit its contents, ever.

Answer 1

I can't reproduce this with 100% reliability (which is strange because I would think the setseed would make it the same every time, but for me it does not). When the replication fails, it is because it uses the bitmap scan for both queries.

The problem seems to be with the row estimate (expected 122985 actual 21318, ratio of 5.8) The mis-estimate makes the seq scan with limit 1 seem faster, as it expects to find the first N rows after scanning less of the table.

I think the problem with the estimate is that the LIKE will usually not yield selectivity estimates of much less than than 1/statistics size, and that is just not accurate enough for the task at hand.

You could potentially fix this by doing:

alter table table0 alter column col0 set statistics 1000;

before the table gets analyzed, to improve the statistics. You might want to go above 1000.

This does seem like a pretty precarious solution though. I would contradict those other posts you linked to. If this small change in performance is enough to worry about, I think it would be best tackled by directly hinting the query to force it to use the plan you want (see pg_hint_plan)