This is related to a question I asked on dbs.stackexchange.com: https://dba.stackexchange.com/questions/335501/why-doesnt-postgres-apply-limit-on-groups-when-retrieving-n-results-per-group
But to reiterate - I have a query like this:
SELECT "orders".*
FROM "orders"
WHERE (user_id IN ?, ?, ?)
ORDER BY "orders"."created_at" LIMIT 50
I have two indexes - `(user_id)` and `(user_id, created_at)`. Only the first index is ever used with this query.
If I query for a specific user_id, as expected it uses the composite index. If I use an inner select and trick the query planner into doing a nested loop for each user, it no longer uses the composite index.
I can understand that the query planner would not know ahead of time which users would have those 50 newest orders.
I imagined that it would be clever enough to determine that only 50 results are needed, and that it could use the `(user_id, created_at)` index to get 50 orders for each user. Then sort and filter those few hundred results in memory.
Instead what I'm seeing is that it gets all orders for each user using the `user_id` index and then sorts/filters them all in memory.
Here is an example query plan:
Limit (cost=45271.94..45272.06 rows=50 width=57) (actual time=13.221..13.234 rows=50 loops=1)
Buffers: shared hit=12321
-> Sort (cost=45271.94..45302.75 rows=12326 width=57) (actual time=13.220..13.226 rows=50 loops=1)
Sort Key: orders.created_at
Sort Method: top-N heapsort Memory: 36kB
Buffers: shared hit=12321
-> Bitmap Heap Scan on orders orders (cost=180.85..44862.48 rows=12326 width=57) (actual time=3.268..11.485 rows=12300 loops=1)
Recheck Cond: (orders.user_id = ANY ('{11,1000,3000}'::bigint[]))
Heap Blocks: exact=12300
Buffers: shared hit=12321
-> Bitmap Index Scan on index_orders_on_user_id (cost=0.00..177.77 rows=12326 width=0) (actual time=1.257..1.258 rows=12300 loops=1)
Index Cond: (orders.user_id = ANY ('{11,1000,3000}'::bigint[]))
Buffers: shared hit=21
Planning:
Buffers: shared hit=6
Execution time: 13.263 ms
The table I'm querying has roughly 50,000,000 orders, with an even distribution of ~4000 orders per user.
I have found that I can speed this up significantly using CROSS JOIN LATERAL and it will use the composite index, but I'm struggling to understand WHY the CROSS JOIN LATERAL is needed here for it to use the index.
I can understand that the query planner would not know ahead of time which users would have those 50 newest orders.
I imagined that it would be clever enough to determine that only 50 results are needed, and that it could use the `(user_id, created_at)` index to get 50 orders for each user. Then sort and filter those few hundred results in memory.
Instead what I'm seeing is that it gets all orders for each user using the `user_id` index and then sorts/filters them all in memory.
Here is an example query plan:
Limit (cost=45271.94..45272.06 rows=50 width=57) (actual time=13.221..13.234 rows=50 loops=1)
Buffers: shared hit=12321
-> Sort (cost=45271.94..45302.75 rows=12326 width=57) (actual time=13.220..13.226 rows=50 loops=1)
Sort Key: orders.created_at
Sort Method: top-N heapsort Memory: 36kB
Buffers: shared hit=12321
-> Bitmap Heap Scan on orders orders (cost=180.85..44862.48 rows=12326 width=57) (actual time=3.268..11.485 rows=12300 loops=1)
Recheck Cond: (orders.user_id = ANY ('{11,1000,3000}'::bigint[]))
Heap Blocks: exact=12300
Buffers: shared hit=12321
-> Bitmap Index Scan on index_orders_on_user_id (cost=0.00..177.77 rows=12326 width=0) (actual time=1.257..1.258 rows=12300 loops=1)
Index Cond: (orders.user_id = ANY ('{11,1000,3000}'::bigint[]))
Buffers: shared hit=21
Planning:
Buffers: shared hit=6
Execution time: 13.263 ms
The table I'm querying has roughly 50,000,000 orders, with an even distribution of ~4000 orders per user.
I have found that I can speed this up significantly using CROSS JOIN LATERAL and it will use the composite index, but I'm struggling to understand WHY the CROSS JOIN LATERAL is needed here for it to use the index.
I've tried tweaking costs, disabling bitmap scans, etc, so it seems like this is a functional limitation rather than something to do with cost/statistics.
So my question is twofold:
So my question is twofold:
- why doesn't Postgres use the composite index, and then retrieve only the minimum necessary amount of rows (50 per user) using the query I posted above?
- If it is a functional limitation, is it lack of implementation, or is there a deeper incompatibility with how the query planner works that would prevent it from being able to do this?
Thanks!
