A paginated query filters on one column and sorts by another, and the plan shows an expensive sort step. How can a multi-column index remove that sort entirely, and what must be true about the index column order and the ASC/DESC directions for that to work?
answer
- Leaf level is a sorted linked list
- Equality columns, then ORDER BY columns, same sequence
- Range before sort column kills the ordering
- Backward scan = full reversal only
- Sort blocks; index walk streams under LIMIT
basics
~20 sPut the equality-filtered columns first and the sort columns immediately after, in the same order as the ORDER BY. Inside the pinned block the index is already in sort order, so the engine walks it and stops early. Mixed ASC/DESC only works if the index directions match or are exactly reversed.
solid answer
~60 sBuild the key as **equality-filter columns, then the ORDER BY columns in the same sequence**. For `WHERE tenant_id = ? ORDER BY created_at DESC LIMIT 20`, an index on `(tenant_id, created_at)` lets the engine seek to the tenant block and walk it backwards, emitting 20 rows and stopping. No sort node, and — crucially with `LIMIT` — bounded work regardless of table size. Two conditions must hold. First, the sort columns must form a contiguous run in the key immediately after columns pinned by equality; a range predicate or an unpinned column in between breaks the ordering. Second, the directions must be compatible: an index is scannable forward and backward, so `ORDER BY a ASC, b ASC` and `ORDER BY a DESC, b DESC` both work on an index `(a ASC, b ASC)`. Mixed `a ASC, b DESC` does not, unless you declare the index with matching per-column directions (`(a ASC, b DESC)`). The payoff is largest with `LIMIT`: a sort must consume the whole input before returning the first row, while an ordered index walk is incremental.
code
sql · 15 lines-- filter equality + sort: index gives both
SELECT id FROM events
WHERE tenant_id = :t
ORDER BY created_at DESC
LIMIT 20;
CREATE INDEX idx_events_tenant_created ON events (tenant_id, created_at);
-- mixed directions need per-column directions in the index
SELECT id FROM events
WHERE tenant_id = :t
ORDER BY priority ASC, created_at DESC;
CREATE INDEX idx_events_tenant_prio_created
ON events (tenant_id, priority ASC, created_at DESC);go deeper
Know that an index stores rows in key order, so sorting by the indexed column can be free, and that the filter columns belong before the sort columns in the key.
State the structural rule precisely and explain the forward/backward scan trick plus its limit for mixed ASC/DESC ordering.
Diagnose from the plan: identify the blocking sort, show the key shape that removes it, and reason about IN-lists, ranges before the sort column, and why LIMIT makes the fix decisive.
Tie it to pagination architecture — keyset pagination reuses the same ordered key, deep OFFSET remains linear, and index-order design becomes a contract between API paging semantics and the physical schema.
## Why an index can replace a sort A B+Tree index is not just a lookup structure — its leaf level is a linked list of entries in key order. Any scan of that leaf level therefore produces rows already sorted by the key columns. If the order the query asks for is a prefix of the order the index already has (within the region being scanned), the optimizer can drop the sort operator entirely and stream rows straight out of the index. This is a pipelining win as much as a CPU win. A sort is a **blocking** operator: it must read every input row before it can emit the first output row, and if the input exceeds the working memory budget it spills to disk. An ordered index scan is **incremental**: the first row is available after one tree descent. ## The structural requirement For `WHERE <equality predicates> ORDER BY s1, s2, …`, the index key must look like: `(equality columns…, s1, s2, …, [extra columns])` The equality columns collapse to a single value, so inside their block the entries are ordered by `s1`, then `s2`. That is precisely the requested order. What breaks it: - **A range predicate before the sort columns.** With key `(created_at, priority)` and `WHERE created_at > :t ORDER BY priority`, the scanned run spans many timestamps, and `priority` restarts its ordering within each — the rows come out unsorted by `priority`, so a sort is required. - **A gap.** Key `(tenant_id, region, created_at)` with `WHERE tenant_id = ? ORDER BY created_at` scans several region blocks, each internally ordered by `created_at` but not globally. Some engines can merge these runs cheaply; many just sort. - **Sorting by an expression.** `ORDER BY LOWER(name)` cannot be satisfied by an index on `name` for most collations. ## Direction compatibility Leaf pages are doubly linked, so an index can be walked forward or backward at essentially the same cost. That means one index `(a ASC, b ASC)` satisfies both `ORDER BY a ASC, b ASC` (forward) and `ORDER BY a DESC, b DESC` (backward) — the whole-tuple reversal. What it does **not** satisfy is a mixed request like `ORDER BY a ASC, b DESC`, because no single traversal direction produces that interleaving. The fix is to declare per-column directions at creation time: `CREATE INDEX … ON t (a ASC, b DESC)` — supported by mainstream engines — which then also serves the exact reverse, `a DESC, b ASC`. NULL placement is the fine print: an index has a fixed position for NULLs (first or last, per engine or per declaration), and a query asking for the opposite placement may still need a sort. State it as a caveat rather than guessing per-engine defaults. ## GROUP BY gets the same benefit Grouping needs rows with equal grouping keys brought together, which sorted input provides for free. With ordered index input, the engine can use a streaming/sorted aggregate: accumulate while the key is unchanged, emit on change, constant memory. Without it, it hashes (memory proportional to distinct groups) or sorts first. So an index on `(customer_id)` or `(status, customer_id)` can turn a hash aggregate into a group aggregate — the same structural rule applies, grouping columns must be a contiguous run after the equality-pinned ones. ## Interaction with pagination This is where it pays most. `ORDER BY created_at DESC LIMIT 20 OFFSET 0` on a matching index is a descent plus 20 entries. Without the index, the engine sorts the entire filtered set to return 20 rows. Deep offsets still degrade (the engine walks and discards `OFFSET` entries), which is the usual argument for keyset pagination — `WHERE (created_at, id) < (:last_ts, :last_id)` — a form that also relies on the very same index order, so the two techniques compose. ## Answering well Name the structure (`equality columns, then sort columns in ORDER BY sequence`), give the direction rule (forward/backward covers full reversal; mixed needs declared per-column directions), and finish with the sort-is-blocking-versus-scan-is-incremental point, because that is what makes it matter under `LIMIT`.
- The query is WHERE status IN ('A','B') ORDER BY created_at LIMIT 10 with an index on (status, created_at). Is the sort avoided?Not automatically. The IN list produces two separate seeks, each internally ordered by created_at, but the concatenation of the two runs is not globally ordered. Some engines can merge the runs incrementally and still avoid an explicit sort; others materialize and sort. If it matters, check the plan rather than assuming, and consider whether an index leading with created_at plus a residual status filter is cheaper for a small LIMIT.
- Why does adding LIMIT make the missing index so much more expensive, relatively speaking?A sort is a blocking operator: it must consume its entire input before emitting the first row, so LIMIT cannot reduce its input work — you pay for sorting every matching row to return ten. An ordered index scan is incremental, so the engine stops after ten entries. The gap between the two plans therefore grows with the size of the filtered set while the result stays tiny.
saying these in an interview costs you the question
- Assuming any index on the sort column removes the sort regardless of the filter columns
- Thinking a backward scan can satisfy mixed ASC/DESC ordering
- Putting the sort column before the equality-filter columns in the key
- Ignoring that a range predicate before the sort column destroys the ordering
- Believing LIMIT reduces the work of a sort node