From what to how: why a query has many plans
Why does a query have a huge space of equal-answer plans, and which few ideas explain the cost of every plan?
A query is a specification, not an instruction
Every layer of a storage system below the query engine has an imperative interface. "Write this block." "Ship this record." "Commit this transaction." The caller says what to do and the system must do it faithfully and survive failures.
A SQL query is different. It is a specification of the answer. Omar does not say "scan orders, build a hash table, probe it". He says "give me the rows that look like this". That one change creates the whole subject of this mechanism. A relational expression has an equivalence class of physical realizations: many different plans that produce byte-identical results. Their costs differ by two to four orders of magnitude (100× to 10,000×). Omar's two versions are two members of one such class. The subject exists because the class is large.
Two constraints disappear
Two difficult constraints from lower layers stop mattering here. The relief is what makes everything here possible.
1. Concurrency is gone. By the time a query runs, the layers below have handed it a fixed snapshot (a frozen, consistent view of the data). Execution is therefore a pure function of immutable input: same input, same output, no matter how many times or in what order you compute it. This gives the engine great freedom. Operators can be reordered, re-run, started speculatively, partly thrown away, cached, or recomputed on a different machine. A retry costs money but never correctness. No lower layer had this freedom.
2. Durability is gone. Nothing in a query has to survive a crash. If the machine dies, the query simply starts again. So the engine may hold any amount of unlogged state in memory and throw it away at the end.
A new constraint appears: logical, not physical
What takes their place is a limit that is logical rather than physical. That makes it harder than anything below:
You cannot emit MAX(amount) early, because the very last row might be the largest. You cannot emit the first row of a globally sorted result early, because the last input row might sort first. This is not an engineering weakness that clever code will remove. It is information-theoretic: the last input can change the first output. Omar's ORDER BY shows nothing for 20 minutes for exactly this reason, while LIMIT 10 (with no order) can stop after ten rows because any ten rows are a correct answer. Everything expensive here descends from this one fact.
Requires, provides, and enforcers
Here is the organizing model for this whole mechanism:
The properties that matter are:
- Order: the rows are sorted on some list of keys.
- Partitioning: rows with the same key are located together (on the same executor).
- Distinctness: no duplicate rows.
- Materialization: the data is fully present (collected) rather than still arriving.
When what an operator requires is not what its input provides, the engine must insert an enforcer: a sort, a shuffle, a hash build, or a dedup step. A small example: a merge join (Join algorithms) needs both inputs sorted on the join key. If an input is not sorted, the engine inserts a sort in front of it. That sort is the enforcer.
Enforcers are where the time goes. The operators themselves (the comparisons, the additions, the predicate checks) are close to free by comparison.
This frame also explains when earlier investments pay off. A clustered table (stored sorted by a key) is a sort paid at write time. A bucketed table (stored pre-split by hash of a key) is a shuffle paid at write time. An index is an ordering paid at write time. A query is where those investments are either cashed in (the enforcer disappears because the property was already there) or wasted (the query needed a different property from the one you paid for in advance).
The core tension: hash or sort
How can an engine make equal things meet? To join, group, dedup or compare, rows with equal keys must be found together. There are exactly two mechanisms:
- Hash them into the same bucket.
- Sort them so that equal keys become adjacent.
Hashing costs O(n) and leaves nothing reusable behind. Sorting costs O(n log n), but it leaves an order that later operators can use for free. Every blocking operator here (join, aggregation, distinct, set operations, window functions) can be built with either mechanism. The choice is always the same question in a new form:
Small example. Suppose a query joins orders to customers on customer_id, then groups the result by customer_id. A hash join and then a hash aggregation each pay O(n) and each leave nothing behind. A sort-merge join sorts once, and its output is already sorted by customer_id, so the aggregation after it needs no second sort. If two operators use the order, sort wins. If only one does, hash wins. (Sorting develops this as "amortization across requirements".)
Two things that decide an operator's cost
Two properties determine how an operator behaves: how much state (remembered data) it must hold, and whether its output can be larger than its input.
| State O(1): streaming | State O(n): blocking | |
|---|---|---|
| Output ≤ input | filter, project, LIMIT without order | DISTINCT, group-by aggregate, sort, top-N (state is only O(k)) |
| Output can exceed input | unnest/flatten, lateral join, table function, one recursive step | join, grouping sets / CUBE, window with an unbounded frame |
(Notation: O(1) means a small constant amount, independent of input size. O(n) means state proportional to the input size. k is the number of rows in a LIMIT.)
Streaming operators are not merely cheap. They are negatively priced, because they shrink the input to everything after them. A filter that keeps 1% of the rows makes every later operator 100 times cheaper. Blocking operators are demands on memory, and memory is the scarce resource of this mechanism (not CPU, and not disk). The bottom-right cell is blocking and amplifying: the join. That is why join algorithms get their own Part (Join algorithms) and why joins dominate the research literature.
Out-of-core: the threshold that is the same for sort and for hash join
The most useful quantitative fact here is that two different out-of-core algorithms start to degrade at the same threshold. "Out-of-core" means the data does not fit in memory, so the algorithm works with disk.
External sort's merge and Grace hash join's partitioning are both limited by the same fan-out, one buffer per open run or partition, F = M/B. So both need a third pass at the same size, N > M²/B: 32 TB per instance at M = 16 GB and B = 8 MB. Sorting derives the pass count and why the "log" has been a constant 2 for thirty years; Grace hash join derives the partitioning bound.
The boundary condition. All of this assumes that partitions come out about equal. Under a Zipf key distribution they do not. In the limiting case, where a single key has more rows than fit in memory, divide and conquer has no move left: hashing one value always gives one bucket. That is the only structural dead end here, and it is why skew handling is a separate topic and not just a tuning knob. We return to it in Join algorithms.
Distributed execution: the same model with the network as the limit
Distributed execution uses the same model. We replace "requires state" by "requires a partitioning that the data does not have". An operator needs a shuffle exactly when its output for a key depends on rows that may live on another executor.
The escape is broadcast: send the whole small table to every executor, so the large table never moves. Broadcast moves m·P bytes (small side of size m, copied to P executors) instead of n+m (shuffling both sides of sizes n and m). It wins on network whenever the size ratio n/m exceeds the parallelism P.
But the binding limit is memory. The small side must sit fully in memory on every executor, so real broadcast thresholds are tens of megabytes, far below what the network arithmetic alone would allow. The shuffle's cost was not removed; it was moved into P copies of memory.
Broadcast also has an underrated second benefit: it preserves the large side's partitioning, so a later aggregation on the same key also loses its shuffle. Property preservation compounds down the plan. A local cost saving does not.
Approximation is the only degraded mode
In many systems there is a "fail-degraded" mode: the system keeps working in a weaker form (for example, a database that serves stale reads when replicas are down). Query processing has almost none. The only graceful-degradation mode of this mechanism is approximation. (There is one narrow exception, a recursion limit, in Relational operators.) The hard limits and the price of each escape are in What query processing forbids.