LIMIT waits for the whole join

Claim: Performance

A LIMIT stops early only when rows arrive in the order the ORDER BY asks for, which takes an index in that order. An index covers one table, so when the leading ORDER BY key reads columns from two joined tables, no index can produce that order. Postgres builds the whole join, sorts it, and only then keeps the first rows.

Example

SELECT o.id, o.created_at, s.shipped_at, p.name, p.price
FROM user_orders o
JOIN products p ON p.id = o.product_id
LEFT JOIN shipments s ON s.order_id = o.id
WHERE o.user_id = $1
ORDER BY coalesce(s.shipped_at, o.created_at) DESC, o.id
LIMIT 50;

The plan reads:

Limit  (rows=50)
  ->  Sort  (rows=2668)
        Sort Key: (COALESCE(s.shipped_at, o.created_at)) DESC, o.id
        ->  Nested Loop Left Join  (rows=2668)
              ->  Hash Join  (rows=2668)
                    ->  Seq Scan on products p
                    ->  Hash
                          ->  Bitmap Heap Scan on user_orders o
              ->  Index Scan using shipments_order_id_key on shipments s

The user has 2,668 orders. Every one is joined to its product and its shipment, and 2,618 of those joined rows are thrown away. To join 2,668 orders to their products, the planner reads all of products in a hash join. No index on user_orders or on shipments helps, because neither table holds the sort key alone.

How to fix it

Sort and limit the tables the sort key reads in a subquery, then join the rest to the rows it keeps:

SELECT top.id, top.created_at, top.shipped_at, p.name, p.price
FROM (
  SELECT o.id, o.created_at, o.product_id, s.shipped_at
  FROM user_orders o
  LEFT JOIN shipments s ON s.order_id = o.id
  WHERE o.user_id = $1
  ORDER BY coalesce(s.shipped_at, o.created_at) DESC, o.id
  LIMIT 50
) top
JOIN products p ON p.id = top.product_id
ORDER BY coalesce(top.shipped_at, top.created_at) DESC, top.id;

Only 50 products are joined, each by primary key. The rewrite returns the same rows only when each row the subquery keeps finds exactly one match in the rest. Here a NOT NULL foreign key from user_orders.product_id to products guarantees it. An inner join that can drop a row, or a join that can match several, changes the result.

When the sort key always reads the same tables, store it in one: a sorted_at column on user_orders, kept current by the code that writes shipments, makes an index on (user_id, sorted_at DESC, id) serve the whole ORDER BY, and the LIMIT stops after 50 rows.

Either way, measure both versions on real data before switching.

Detection

Query Doctor reports this Finding from the explain plan when all of these hold:

• A Limit sits directly over a Sort, and the Sort reads a join.
• The sort’s leading key names columns from at least two of the relations the join reads.
• The join builds at least four times the rows the LIMIT keeps, by the plan’s row estimates.
• The rows the LIMIT throws away carry at least a quarter of the query’s estimated cost. A sort run inside a loop counts once per run, so a small sort repeated for every outer row can qualify where the same sort run once does not.

A LIMIT fed by an index scan has no Sort node, and a sort key from one table can be served by an index, so neither is reported.