A table has 50 million rows and a query asks for the 10 newest by timestamp with ORDER BY plus a small LIMIT. If no index provides that order, what does a good execution engine do instead of fully sorting 50 million rows, and what are the limits of that technique?
answer
- Heap of size N, worst row at the root
- Loser rejected in one comparison
- Memory O(N) → never spills
- Still scans the whole input
- OFFSET+LIMIT is the real N — deep paging kills it
basics
~20 sIt runs a top-N heap sort: keep a bounded heap of only N rows, compare each incoming row against the heap's worst element, and discard immediately if it loses. Memory is O(N) instead of O(input), so no spill — but the whole input is still scanned, and the trick dies once N gets large.
solid answer
~1 minThe engine uses **top-N heapsort**. It maintains a heap of at most N entries ordered so the *worst* qualifying row sits at the root. Each input row is compared against that root: if it is worse, it is discarded with a single comparison and never stored; if it is better, it replaces the root and the heap is fixed up in O(log N). At the end the heap is drained in order. The payoffs are memory O(N) rather than O(input) — so a top-N never spills for small N — and CPU O(rows · log N) with a very cheap reject path. The limits matter as much as the technique: - The **entire input is still scanned**; you save the sort, not the read. - The planner must *know* N at plan time, so it needs the limit and offset to be visible; a large `OFFSET` counts against N because the engine must materialize offset+limit rows. - Above a threshold the heap stops fitting in memory and the engine falls back to a full external sort. - It cannot be used where the full ordering is required downstream, e.g. a sort feeding a merge join. The better fix for a hot path is an index on the ordering column, which turns the query into reading the first 10 index entries.
code
text · 3 linesLIMIT 10
-> SORT (key=created_at DESC, method=top-N heapsort, memory=29 kB)
-> SEQ SCAN events (rows=50,000,000)go deeper
Know that a small row limit lets the engine keep only that many rows in a heap instead of sorting everything, so memory stays tiny.
Explain the heap orientation and the one-comparison reject path, give the O(rows · log N) cost, and note that the scan cost is unchanged.
Bring in the failure modes — offset-driven pagination, N above the memory threshold, sorts whose parent needs the full order — and argue for an ordered index or keyset pagination on hot paths.
Treat it as an API design constraint: pagination contracts that expose deep offsets force full sorts at scale, so the ordering key, its tiebreaker, and the seek-based contract are decisions to make before the table gets large.
## The observation behind top-N If a query wants only the first N rows of an ordering, the relative order of the losers is irrelevant. Fully sorting 50 million rows to throw away 49,999,990 of them wastes almost all of the work. So execution engines special-case the pattern "sort feeding a small row limit" into a **top-N heap sort** (SQL Server calls the equivalent operator a TOP N Sort; PostgreSQL reports `Sort Method: top-N heapsort`). ## The algorithm Maintain a binary heap holding at most N rows, oriented so the **worst currently-qualifying row** is at the root. For `ORDER BY created_at DESC LIMIT 10`, that means the *oldest* of the ten newest seen so far sits on top. For each input row: 1. If the heap holds fewer than N rows, insert it — O(log N). 2. Otherwise compare against the root. If the new row is not better than the root, **discard it immediately** — one comparison, no allocation, no copy. 3. If it is better, replace the root and sift down — O(log N). When input ends, pop the heap repeatedly to produce the N rows in order. Worst case is O(rows · log N) comparisons, but the common case is far cheaper: after the heap warms up, most rows lose on the very first comparison, so the loop is essentially one compare and a branch per row. ## Why it changes the performance profile **Memory becomes O(N).** Ten rows fit in a few kilobytes regardless of table size, so a top-N sort never spills to temp files. This is the difference between a query that degrades gracefully as the table grows and one that falls off a cliff the day its sort no longer fits its budget. **Tuple copies collapse.** A full sort must materialize every input tuple in sort space; top-N stores at most N. **But I/O does not improve.** The scan still touches every row that passes the WHERE clause. Top-N converts an `O(R log R)` sort into an `O(R log N)` filter — it does not make the query sublinear. A query that reads 50 million rows to return 10 is still reading 50 million rows. ## When the engine cannot or will not use it - **N is not known at plan time.** The optimizer must see the row limit above the sort. If the limit is applied only after an operator the engine cannot push through — or is computed in a way the planner cannot fold — the sort has to produce everything. - **Large offsets.** Skipping rows still requires producing them in order, so the heap must hold `offset + limit` entries. Deep pagination therefore degrades back toward a full sort, which is the standard argument for keyset (seek) pagination over offset pagination. - **N is too large.** Once the heap exceeds the operator's memory budget, keeping it is no better than sorting; engines apply a threshold and fall back to a full external merge sort. - **Downstream needs the full order.** A sort that exists to feed a merge join or a sort-based aggregate must sort everything, because the parent consumes the whole stream. - **Ties at the boundary.** With duplicate sort-key values at the cut-off, which rows survive is arbitrary unless the ordering is made deterministic by adding a unique tiebreaker column. Two runs of the same query can legitimately return different rows. ## The alternative that beats it If this query is on a hot path, the real fix is an **ordered access path**: an index on the ordering column (with any equality-filter columns as leading key parts) lets the engine walk the index in order and stop after N entries. That is O(N) work, not O(rows), and it removes the sort operator from the plan entirely. Top-N heapsort is the engine's damage control when no such index exists — a good plan for an unindexed request, but still a full scan. A useful diagnostic habit: when you see a top-N sort over a large scan in a plan, read it as "the engine saved you from a spill but nobody gave it an index". When you see a plain external sort under a small limit, ask why the limit was not visible to the planner.
- Why does a large OFFSET defeat this optimization?To skip rows the engine must still produce them in the requested order, so the bounded heap has to hold offset + limit entries, not just limit. At OFFSET 100000 LIMIT 10 the heap holds 100,010 rows, which may exceed the memory budget and fall back to a full sort. Keyset pagination — filtering on the last seen sort-key value instead of counting rows — keeps the effective N tiny and lets an index seek directly to the right place.
Picking the ten tallest people in a stadium: you keep ten in a line and only compare each newcomer to the shortest of your ten — no need to rank everyone else.
saying these in an interview costs you the question
- Claiming top-N makes the query cheap because "it only reads 10 rows" — the scan is unchanged
- Thinking the heap holds the best row at the root rather than the worst qualifying one
- Assuming a top-N sort can still spill to disk for small N
- Believing a large OFFSET is free because the rows are discarded
- Expecting stable results across runs when the sort key has ties at the cut-off and no unique tiebreaker exists