A query filters on a range of one column and sorts by that same column in descending order. How can a B+tree index satisfy that ordering without a separate sort step, what property of the leaf level makes a descending walk possible, and when does the engine sort anyway?

## Why an index can replace a sort at all A B+tree keeps its entries sorted by key, and its leaf pages are chained in key order. Walking that chain therefore produces keys in sorted order without any sorting work. If a query's required ordering matches the index's key order, the query planner can eliminate the sort operator from the plan altogether. The saving is bigger than "one less step": - **Memory.** A sort needs a workspace proportional to its input. If the input exceeds the memory allowance, it spills to temporary files on disk and performs an external merge — writes and reads that have nothing to do with the data the user asked for. - **Latency to first row.** A sort is a **blocking** operator: it cannot emit anything until it has seen all of its input, because the last row read might sort first. An ordered index scan is **pipelined**: it emits the first qualifying row as soon as it finds it. That second point is decisive for queries that only want the first N rows. "Give me the 20 most recent orders" over an ordered index scan touches a handful of pages and stops. The same query as a scan-and-sort reads and sorts every qualifying row first, then discards all but 20. ## Descending order and the leaf chain Ascending output is the natural direction: descend to the range's lower bound and walk forward. Descending output requires the reverse: position at the upper bound and walk backwards. That is possible because leaf pages are linked to their neighbours, and in many implementations that linkage is **doubly linked** — each leaf knows both its right and its left sibling. A backwards scan positions at the last qualifying entry, emits entries within the page from the end towards the beginning, then follows the left-sibling link and repeats. This is why an index defined in ascending order can serve a descending sort perfectly well, and why creating a second, descending index on a single column is usually pointless. Where leaves are singly linked, engines achieve the same result by other means — for example by re-descending the tree to reach the preceding page, or by a scan strategy that collects and reverses. These have slightly different costs but the same observable outcome. One real asymmetry to be aware of: backward scans can interact worse with storage-level readahead, which is tuned for forward sequential access, so a very large descending scan may be somewhat slower per page than the equivalent forward scan. ## When the sort cannot be eliminated **Ordering does not match the index's order.** For a single column, ascending and descending are both reachable from one index by choosing the scan direction. For an ordering across multiple columns with *mixed* directions — one ascending and the next descending — a single-direction walk of the leaf chain does not produce that sequence. Only an index that declares those per-column directions can serve it without a sort. **Ordering is on something the index does not store.** If the required ordering is over an expression, or over a column in a different table, or over a computed value, the stored key order does not correspond to it and a sort is required. **The ordered path is more expensive than sorting.** This is the common and less obvious case. If the index does not contain every column the query needs, each qualifying entry requires a separate fetch of the row, and those fetches land in effectively random positions. For a selective range that is cheap. For a broad one, many random fetches cost more than one sequential pass over the table plus a sort — even though the sort is extra work — because sequential I/O is so much cheaper per row. The planner compares the two costs using its cardinality estimate, which is why the same query can use the ordered path for a narrow range and a scan-plus-sort for a wide one. **Grouping or aggregation reorders anyway.** If the plan must aggregate or hash-join above the scan, the ordering produced by the scan may be destroyed before it reaches the sort requirement, so preserving it buys nothing. ## Reading a plan The symptom to look for is an explicit sort operator sitting above an index scan on the very column being ordered — a sign that either the ordering does not match (check mixed directions), or the planner decided the ordered path was too expensive, or the plan's estimated row count is wrong. The presence of a row limit above a blocking sort is the highest-value version of this finding, because that is where the pipelined alternative saves the most. ## Summary Order comes free from the structure; direction comes from which way you walk the chained leaves; and the planner will still choose to sort whenever the ordered walk would cost more than sorting, or cannot produce the ordering asked for.