Top-N Heapsort and LIMIT Plans #

An admin page lists the 50 most recent orders with ORDER BY placed_at DESC LIMIT 50, and its plan shows Sort Method: top-N heapsort Memory: 32kB over 40 million rows — fast and cheap. Page 2,000 of the same list, LIMIT 50 OFFSET 99950, shows Sort Method: external merge Disk: 1804208kB. The only change is the offset, and it turned a bounded sort into a full one.

Sort nodes in general are analysed in sort and hash node analysis; the relationship to window queries is in window functions and top-N plans. This page covers the bounded sort itself.

The Algorithmic Condition #

When a Limit node sits directly above a Sort — possibly with nodes between them that cannot change the number or order of rows — the planner passes the sort a bound: offset + count. With a bound N, the executor uses one of two strategies:

Two things break the bound:

Whether a sort is used at all competes with an ordered index scan, which needs no sort and stops after N rows — ideal unless the rows needed are rare in index order, the trap covered in startup cost vs total cost under LIMIT.

Keeping 50 rows versus sorting 40 million Left, the top-N heapsort for LIMIT 50: a heap of 50 rows, each input row compared with the worst kept row, memory measured in kilobytes. Right, the full sort for OFFSET 99950: the bound of 100 thousand rows exceeds work_mem, so the whole input is sorted externally before the page is returned. LIMIT 50 → top-N heapsort bound N = 50 heap holds 50 rows Memory: 32kB input read once, never fully sorted LIMIT 50 OFFSET 99950 → full sort bound N = 100,000 exceeds work_mem as a heap Sort Method: external merge all 40M rows sorted on disk the bound is offset + limit, so every page deeper costs more

Annotated EXPLAIN Evidence #

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, customer_id, total, placed_at
FROM orders WHERE status = 'shipped'
ORDER BY total DESC
LIMIT 50;
Limit  (actual time=8204.1..8204.2 rows=50 loops=1)
  ->  Sort  (actual time=8204.1..8204.1 rows=50 loops=1)
        Sort Key: total DESC
        Sort Method: top-N heapsort  Memory: 32kB           -- bounded: only 50 rows kept
        ->  Seq Scan on orders  (actual rows=40012004 loops=1)
              Filter: (status = 'shipped'::text)
Execution Time: 8204.6 ms
-- cost is the scan; the sort itself is trivial

Deep page:

... ORDER BY total DESC LIMIT 50 OFFSET 99950;
Limit  (actual time=41204.8..41205.0 rows=50 loops=1)
  ->  Sort  (actual time=41180.2..41204.2 rows=100000 loops=1)
        Sort Key: total DESC
        Sort Method: external merge  Disk: 1804208kB         -- bound too large for a heap
        ->  Seq Scan on orders  (actual rows=40012004 loops=1)
Execution Time: 41810.6 ms

A bound lost to an intervening node:

Limit  (actual rows=50 loops=1)
  ->  Unique  (actual rows=50 loops=1)
        ->  Sort  (actual rows=40012004 loops=1)
              Sort Key: customer_id, total DESC
              Sort Method: external merge  Disk: 1402110kB
-- SELECT DISTINCT … LIMIT 50: the Unique node blocks the bound, so the sort is full
Three Sort Method lines to recognise Three lines are annotated. Sort Method top-N heapsort with 32 kilobytes shows a bounded sort. Sort Method external merge with 1.8 gigabytes under a deep offset shows the bound was too large. A full external sort beneath a Unique node under Limit shows the bound could not pass through. Sort Method: top-N heapsort Memory: 32kB bounded: N kept in a heap OFFSET 99950 → Sort Method: external merge bound too big: full sort Limit → Unique → Sort (external merge) Unique blocks the bound top-N heapsort means the LIMIT reached the sort

Step-by-Step Resolution #

  1. Read Sort Method under every Limit. top-N heapsort is healthy; quicksort or external merge under a Limit means the bound was too large or was blocked.

  2. Replace deep OFFSET with keyset pagination. Remember the last row’s sort key and continue from it, keeping N at the page size:

    SELECT id, customer_id, total, placed_at
FROM orders
WHERE status = 'shipped'
  AND (total, id) < ($last_total, $last_id)
ORDER BY total DESC, id DESC
LIMIT 50;

    The implementation details for ORMs are in offset vs keyset pagination plans.

  3. Add an index matching filter and order so no sort is needed at all:

    CREATE INDEX CONCURRENTLY orders_shipped_total_idx ON orders (total DESC, id DESC)
WHERE status = 'shipped';

  4. Move the limit below blocking nodes where semantics allow. For “50 distinct customers with the highest order”, use DISTINCT ON with a matching order, or a subquery that limits before joining.

  5. Watch the width of sorted rows. The heap holds whole rows; selecting wide columns raises memory per row and lowers the bound that fits. Sort ids first and join back for the wide columns.

  6. Check parallel plans. Under Gather Merge, each worker sorts its share; top-N bounds are applied per worker as well, which keeps memory bounded.

Cost of page N with OFFSET Page 1 uses a 32 kilobyte heap. Page 100, with an offset of about 5 thousand, uses a 2.6 megabyte heap. Page 2,000, with an offset of about 100 thousand, falls back to an external sort using 1.8 gigabytes of disk. A keyset page at any depth uses a 32 kilobyte heap or an index scan. page 1 (N=50) 32 kB heap page 100 (N=5,000) 2.6 MB heap page 2,000 (N=100,000) 1.8 GB on disk keyset, any page 32 kB values in kilobytes; the deep page dwarfs the others

Before and After #

-- BEFORE: OFFSET pagination, page 2,000
Limit → Sort (external merge  Disk: 1804208kB) → Seq Scan (40M rows)          Execution Time: 41810.6 ms

-- AFTER: keyset pagination + partial index on (total DESC, id DESC)
Limit → Index Scan using orders_shipped_total_idx  Index Cond: (ROW(total, id) < ROW(…))   Execution Time: 0.21 ms

Ties and stable ordering #

Top-N results are only well defined when the sort order is unique. With ORDER BY total DESC LIMIT 50, rows tied at the 50th total may be chosen arbitrarily, and a heapsort and a full sort can pick different tied rows. Pagination then repeats or skips rows across pages. Always end the ORDER BY with a unique column — usually the primary key — both for correctness and so that keyset conditions can use a row comparison like (total, id) < (…), which a composite B-tree index serves directly.

PostgreSQL 13 added FETCH FIRST … WITH TIES, which returns all rows tied with the last one. It is useful for leaderboards but makes the bound open-ended: the sort must continue past N while ties remain, which is still cheap for heapsort but can return more rows than the page size.

Common Pitfalls #

Deep OFFSET pagination. The bound grows with the page number. Diagnostic signal: sort method changes as users page deeper. Fix: keyset pagination.

DISTINCT or GROUP BY under LIMIT. The bound cannot pass through. Diagnostic signal: full sort below Unique or an aggregate. Fix: DISTINCT ON with matching order, or limit earlier.

Wide rows in the heap. Memory per row reduces the usable bound. Diagnostic signal: heapsort falling back to external sort at modest N. Fix: sort narrow keys, then join for wide columns.

Non-unique ordering. Tied rows move between pages. Diagnostic signal: duplicates or gaps across pages. Fix: add a unique tiebreaker column.

Frequently Asked Questions #

What is top-N heapsort in PostgreSQL? #

The sort method used when a LIMIT applies directly to a sort. The executor keeps only the best offset-plus-limit rows in a heap while reading its input, so memory stays small and the input is never fully sorted.

Why does OFFSET make my query slow? #

The sort bound is offset plus limit, so a deep page must keep or sort a very large number of rows, and the rows before the offset are produced and discarded. Beyond a point the bound exceeds work_mem and the plan falls back to a full sort.

Why is my ORDER BY LIMIT query still doing a full sort? #

Either the bound is too large for a heap in work_mem, or a node between the Limit and the Sort — such as Unique, an aggregate or a join — prevents the bound from reaching the sort.

Up: Window Functions and Top-N Plans