When a query plan shows a merge join with no sort step beneath it, where does the required ordering come from, and why is that usually cheaper than sorting the rows at query time?
answer
- B-tree leaves are already in key order
- interesting orders tracked by the optimizer
- sort is blocking + spills to temp
- non-covering index order = random row fetches
- index both sides on the join key
basics
~20 sThe order comes from an ordered access path — typically scanning a B-tree index whose leading columns are the join key, or the output of an earlier order-preserving operator. Reading in index order costs nothing extra, while an explicit sort costs O(N log N) plus temp-storage I/O when it does not fit in memory.
solid answer
~50 sB-tree index leaves are stored in key order, so an ordered scan of an index whose leading columns match the join key hands the merge join sorted rows for free. Other sources exist: a table clustered on the key, the sorted output of an upstream merge join, or a grouping operator that already sorted. An explicit sort, by contrast, must consume its entire input before emitting a first row — it is a blocking operator — costs O(N log N) comparisons, and spills runs to temporary storage once it exceeds its memory budget, adding a full write and read of the data. The catch is that ordered index access is not free in every sense: a non-covering index scan pays a base-row lookup per entry, which can cost more than a sequential scan plus a sort when the query touches most of the table. That is exactly the tradeoff the optimizer is costing.
code
text · 5 linesMerge Join Merge Join
-> Sort (key: a.k) -> Index Scan a_k_idx
-> Seq Scan a -> Index Scan b_k_idx
-> Sort (key: b.k)
-> Seq Scan bgo deeper
Say that B-tree indexes store keys in order, so scanning one gives sorted rows without a sort step.
Contrast inherited order with an explicit sort, and mention that sorts block and spill.
Bring in selectivity, clustering, and covering columns — explain when scan-plus-sort actually wins and how you would verify it in a plan.
Treat index and clustering design as the decision that makes repeated large joins linear-cost, and weigh the write-side cost of maintaining those orders.
## Two ways to get sorted input A merge join needs both sides ordered on the join key. That order can be produced (an explicit sort operator) or inherited (an access path that naturally emits rows in key order). Optimizers model this as interesting orders: an ordering some later operator would benefit from, tracked so a plan that already has it is not charged for a sort. ## Where inherited order comes from The common source is a B-tree index. Its leaf level is a key-ordered structure, so a range or full scan of the index yields entries in key order. If the index leading columns are exactly the join key, that ordering is directly usable. Other sources: a table physically clustered or index-organised on the key, the output of an upstream merge join or sorted grouping, and order-preserving parallel exchanges. What does not preserve order: scans that gather row locations and fetch them in physical order, unordered parallel scans, and hash-based operators. ## Why an explicit sort is expensive A sort is blocking: no output until the last input row is consumed, which stalls pipelining and delays the query's first row. Its CPU cost is O(N log N) comparisons. Its worse property is memory sensitivity — when the input exceeds the sort memory it becomes an external merge sort, writing sorted runs out and merging them back. That adds at least one full write plus one full read of the input, and with very little memory, several merge passes. Two sorts, one per side, double all of this. ## Why the ordered scan is not automatically better Ordered index access has its own cost. If the index does not contain every needed column, each entry requires fetching the base row, and those fetches follow key order rather than physical order — effectively random I/O. Once the query touches a large fraction of the table, sequential scan plus sort can beat index order comfortably. Selectivity and clustering (how well index order correlates with physical row order) decide it, and this is precisely what the optimizer weighs when choosing between a merge join over index scans and a hash join over sequential scans. ## Practical design lever This is the actionable part: if two large tables are joined repeatedly on the same key, indexing or clustering both on that key turns the merge join into two ordered scans and a linear merge, with almost no memory demand. That is why merge joins are common on foreign-key joins where both sides are indexed on the key, and rare on ad-hoc joins over columns nobody indexed. ## Reading a plan A merge join with two sort nodes underneath means the engine paid for the order; if the join is not producing an ordering the plan needs, another algorithm is often cheaper. A merge join over two ordered index scans is the shape you want. Half and half — one sorted side, one scan — is common and reasonable when only one table has a suitable index.
- Why might an optimizer prefer a sequential scan plus an explicit sort over an ordered index scan for the same table?When the scan touches a large fraction of the table and the index does not cover all needed columns, walking the index means one base-row fetch per entry in key order, which is effectively random I/O. A sequential scan reads pages in physical order and the sort then costs O(N log N) CPU, which is often cheaper overall.
saying these in an interview costs you the question
- Claiming any index scan produces sorted output — order-preserving access is a specific property, not a given
- Ignoring that a sort is blocking, so it delays the first row and cannot pipeline
- Assuming ordered index access always beats scan-plus-sort regardless of selectivity or clustering