0

I've come across many questions/answers for Greatest/Top N per group type problems that explain how to solve the problem - generally some variation of row_number() or CROSS JOIN LATERAL, but I'm struggling to understand the theory behind the why for this example.

The particular example I'm working with is this:

SELECT "orders".* 
FROM "orders" 
WHERE user_id IN (?, ?, ?, ?, ?)
ORDER BY "orders"."created_at" LIMIT 50

Essentially, I want to find the 50 most recent orders amongst a group users. Each user may have thousands of orders.

I have two indexes - (user_id) and (user_id, created_at). Only the first index is ever used with this query.

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.

So my question is, 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?

EDIT: More context

This is the lateral join query that does use the index

SELECT o.*
FROM company_users cu
CROSS JOIN LATERAL (
   SELECT *
   FROM orders o
   WHERE o.user_id = company_users.user_id
   ORDER  BY created_at DESC LIMIT 50
   ) cu
WHERE  cu.company_id = ? 
ORDER BY created_at DESC LIMIT 50

Doing a nested select like this doesn't use the index - even though it does a nested loop just like the lateral join does:

SELECT "orders".* 
FROM "orders" 
WHERE user_id IN (SELECT user_id FROM company_users WHERE company_id = ?)
ORDER BY "orders"."created_at" LIMIT 50
2
  • 1
    The "why" isn't really answerable: this is a specific case of skip-scanning, which has not been implemented by those who coded the optimizer. Why they didn't do so would only be answerable by them, you may want to join the pgsql-hackers list postgresql.org/list/pgsql-hackers and ask a question there. Feb 4 at 12:12
  • 1
    Why? Because you haven't implemented it yet.
    – jjanes
    Feb 4 at 14:28

1 Answer 1

1

The problem is that scanning that index would not return the rows in created_at order, so all matching rows would have to be fetched. The optimizer doesn't think that such an index scan would be helpful, because PostgreSQL wouldn't be able to use the index to search for the IN condition in index order, thus returning the results in ORDER BY order.

You can try reversing the order of the columns in the index. That would be more promising, but I cannot tell if it would help in your case. If that doesn't help, you need a workaround like your lateral join.

6
  • A skip-scan would go in the right order, which is what OP is asking for. The lateral join is effectively a skip-scan. But this is not implemented yet. Feb 5 at 14:23
  • @Charlieface a skip-scan would only produce them in order piecewise, which is not enough. You would either need to "Merge Append" those pieces so they can stop early globally, or need to apply the LIMIT separately to each piece and then re-sort them and re-LIMIT them. Presumably the latter of these is what the unshown LATERAL is doing.
    – jjanes
    Feb 5 at 16:56
  • @Laurenz-Albe Do you mean using (created_at, user_id)? Or (user_id, created_at DESC) - FWIW, neither really improves the query. created_at first means it needs to scan ~500k rows in my example query. I've updated the original question with the LATERAL join I'm doing that works. I guess where some of my confusion is coming from is that even with a nested select that causes it to do a nested loop on orders it still won't choose to use that index.
    – Seanvm
    Feb 6 at 2:03
  • If your lateral join doesn't use the index on (user_id, created_at), something is seriously amiss. Perhaps you should ANALYZE the table to collect new statistics, or the data types don't match. The EXPLAIN (ANALYZE, BUFFERS) output would show more. Feb 6 at 7:34
  • The lateral join does use that index as expected. My main confusion was around why with the original query it can't use the index. I also noted that with a sub-select it will do a nested loop like the lateral join does, but not use the index. As the other posters pointed out though it seems that is just something the query planner just hasn't been designed to do..
    – Seanvm
    Feb 7 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.