Bound the answer, bound the state
What it is
A bounded heap of size k turns ORDER BY … LIMIT k into O(n log k) time and O(k) memory. That means the operator never spills, whatever the input size. That is the real prize: an unbounded-memory operator becomes a bounded-memory operator with no loss of exactness. (Compare with Probabilistic and sketch structures: trading correctness for space, where bounded memory is bought by approximation.) Here it is bought by restricting the question rather than the answer, which is strictly better when available. Whenever you see an operator with bounded state and exact output, look for a restriction on the question.
From Core Data Structures › Heaps
Every bound you can put on the answer (k rows, one group, an error tolerance) converts into a bound on state. Unbounded answers are what cost memory.
From Query Processing › Sets, pivots, recursion
Top-N has an elegant second step. Once the heap is full, the k-th value is a predicate. The query contained no filter. But execution has created sort_key > current_kth, and this synthetic predicate can be fed straight back into row-group skipping. Engines that do this can abandon whole files in the middle of a scan. The effect compounds: each qualifying row tightens the threshold, a tighter threshold skips more, and skipping finds the good rows sooner. This positive feedback converges quickly when the data is clustered on the sort key and does nothing when it is not.
From Query Planning & Optimization › Projection and Top-N
Where it appears
In 4 mechanisms. Each says what the mechanism is about, then how this principle shows up there, in its own words.
- Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
(Compare with Probabilistic and sketch structures: trading correctness for space, where bounded memory is bought by approximation.) Here it is bought by restricting the question rather than the answer, which is strictly better when available.
Read it inHeaps and priority queues
- Query Processing
Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?
Every bound you can put on the answer (k rows, one group, an error tolerance) converts into a bound on state.
Read it inSet operators, pivots and recursion
- Query Planning & Optimization
How does a system choose a plan for a question when the facts that decide the best plan are unknown until the plan has run?
Once the heap is full, the k-th value is a predicate.
Read it inProjection pushdown and Top-N pushdown
- Specialized Processing Models
What do you build when a query predicate cannot be reduced to a range over an ordered key?
Text search is the discipline of not evaluating most of a query you could never afford to evaluate, for a question that has no correct answer.
Read it inFinding is cheap, scoring is the cost; the inverted index
Related
Made on the same pages most often.