PostgreSQL Query with LIMIT Takes Long to Execute When Fewer Rows Are Left (Last Page of Pagination)

Question

I'm facing a strange issue with my PostgreSQL query related to pagination. I have a simple pagination setup, but whenever the number of rows left to retrieve is less than the LIMIT specified in the query, the query takes about 30 seconds to execute. In contrast, when the number of rows returned matches the LIMIT, the query runs instantly. This delay typically occurs on the last page of the pagination.

To isolate the issue, I've simplified the query by removing the OFFSET and only keeping the LIMIT, but the problem persists.

Here is the query:

select "t"."uuid"
from "transactions" as "t"
where "t"."user_uuid" in
('6b1339ca-0438-4e4b-99c9-33a6bca8abdc',
'428d503a-e64e-4bd3-808c-e4ea3432b1e9',
'6bf2b3cb-1e49-4ebc-9c24-40a54287b6ae',
'33b41527-cf68-4ddf-b7d3-a82a0bf83221',
'3112ce32-44fc-4dec-b3a9-c19dcfbfd532')
order by "timestamp" desc limit 25;

for this example there are 89 transactions. If I put the limit below 89 the query performs fast. Here is the query and the query plan

Here is the fast query plan with the limit set to 25

Limit  (cost=0.44..15784.41 rows=25 width=20) (actual time=0.054..0.583 rows=25 loops=1)
  ->  Index Scan Backward using idx_transactions_timestamp on transactions t  (cost=0.44..11255867.32 rows=17828 width=20) (actual time=0.053..0.579 rows=25 loops=1)
        Filter: (user_uuid = ANY ('{6b1339ca-0438-4e4b-99c9-33a6bca8abdc,428d503a-e64e-4bd3-808c-e4ea3432b1e9,6bf2b3cb-1e49-4ebc-9c24-40a54287b6ae,33b41527-cf68-4ddf-b7d3-a82a0bf83221,3112ce32-44fc-4dec-b3a9-c19dcfbfd532}'::uuid[]))
        Rows Removed by Filter: 148
Planning Time: 0.157 ms
Execution Time: 0.608 ms

Here is the slow query and plan with the limit set to 100

Limit  (cost=0.44..63136.33 rows=100 width=20) (actual time=0.051..28690.472 rows=91 loops=1)
  ->  Index Scan Backward using idx_transactions_timestamp on transactions t  (cost=0.44..11255867.32 rows=17828 width=20) (actual time=0.050..28690.459 rows=91 loops=1)
        Filter: (user_uuid = ANY ('{6b1339ca-0438-4e4b-99c9-33a6bca8abdc,428d503a-e64e-4bd3-808c-e4ea3432b1e9,6bf2b3cb-1e49-4ebc-9c24-40a54287b6ae,33b41527-cf68-4ddf-b7d3-a82a0bf83221,3112ce32-44fc-4dec-b3a9-c19dcfbfd532}'::uuid[]))
        Rows Removed by Filter: 23562639
Planning Time: 0.158 ms
Execution Time: 28690.509 ms

If i push the limit even higher to 200, it becomes fast again

Limit  (cost=68401.22..68401.72 rows=200 width=20) (actual time=0.621..0.643 rows=91 loops=1)
  ->  Sort  (cost=68401.22..68445.79 rows=17828 width=20) (actual time=0.620..0.635 rows=91 loops=1)
        Sort Key: "timestamp" DESC
        Sort Method: quicksort  Memory: 32kB
        ->  Bitmap Heap Scan on transactions t  (cost=620.99..67630.71 rows=17828 width=20) (actual time=0.173..0.603 rows=91 loops=1)
              Recheck Cond: (user_uuid = ANY ('{6b1339ca-0438-4e4b-99c9-33a6bca8abdc,428d503a-e64e-4bd3-808c-e4ea3432b1e9,6bf2b3cb-1e49-4ebc-9c24-40a54287b6ae,33b41527-cf68-4ddf-b7d3-a82a0bf83221,3112ce32-44fc-4dec-b3a9-c19dcfbfd532}'::uuid[]))
              Heap Blocks: exact=66
              ->  Bitmap Index Scan on idx_transactions_user_uuid  (cost=0.00..616.54 rows=17828 width=0) (actual time=0.072..0.073 rows=438 loops=1)
                    Index Cond: (user_uuid = ANY ('{6b1339ca-0438-4e4b-99c9-33a6bca8abdc,428d503a-e64e-4bd3-808c-e4ea3432b1e9,6bf2b3cb-1e49-4ebc-9c24-40a54287b6ae,33b41527-cf68-4ddf-b7d3-a82a0bf83221,3112ce32-44fc-4dec-b3a9-c19dcfbfd532}'::uuid[]))
Planning Time: 0.157 ms
Execution Time: 0.728 ms

Some things that might be useful

• If I remove the limit, or if I remove the order by the query is fast
• I have an index on the transactions.timestamp
• Ive tried to rearrange the query using a CTE but, it didn't seem to help: https://dba.stackexchange.com/a/130280

I'm pretty much at a loss of what to do next. I would appreciate anyone who has any ideas.

Answer 1

The upper end of the "timestamp" column contains at least 25, but less than 100, things which meet your IN-list condition. So finding 25 is easy, but then it has to read past another 23 million non-matching rows before it can round out the 100 matching ones. PostgreSQL doesn't know about this desert in the middle of the index, so it doesn't plan accordingly.

The answer you cite is very old. Since then, PostgreSQL has gained the ability to optimize through a CTE construct. To get the same optimization fence to apply on newer versions, you need to add the MATERIALIZED keyword:

WITH t AS MATERIALIZED ( ...

Your n_distinct isn't too bad, I expected it to be worse. But I still can't figure out how it comes out with the estimate. If it thinks every rare uuid has 12925576 / 1611 = 800 copies, then it should expect the provided 5-list to match 4000 rows, but it is actually expecting over 4 times as many. I don't know how to explain that. Maybe one of the hardcoded value is in the MCV list, and so is believed to be common, not rare. But since only 91 are actually found, this belief is wrong, so maybe your stats are of adequate size, but are just out of date? This is supported by the observation that the bitmap index scan finds 438 rows but only 91 of them end up being visible in to the bitmap table scan, which means the index is full of a lot of obsolete pointers. So a VACUUM ANALYZE would likely fix the problem. But if they can easily get out of date once they can do it again, so it might not be a permanent solution. The CTE might be the more robust option.