Choose an ordering structure
A query needs data in some order: the next job by priority, the top 100 customers, a fully sorted output for a merge join or a file layout. Sorting is the expensive default: it must read everything before it can output anything. How much order do you actually need, and what is the cheapest way to get it?
You will end with the cheapest way to produce the order the query needs, and the parameter that sets its cost.
Decide
How much order does the query need?
Why
A heap answers only "what is next", and that is often all the question needs. Restricting the question costs no accuracy, so it is the cheapest escape there is.
Does the input already have an order you can use?
A clustered index, a bucketed or sorted table, an upstream operator's sorted output, or data that arrives nearly sorted.
Why
An existing order turns a sort into a scan or a merge. This has the most leverage of any question here, and it is the one query optimizers most often get wrong.
Does the data fit in memory?
Is the data spread across machines?
Where you can land
Heap
Use it when only the next element is ever needed.
What it costs: it answers nothing except "what is next".
Bounded heap
Use it when only the top k are needed.
Keep a heap of k items and discard anything worse than its smallest: bounded memory, exact answer.
Before you build it: check the query plan to see that your engine actually uses a top-k operator and is not compiling the query as a full sort followed by a limit.
Reuse the existing order
Use it when the input is already sorted or nearly so.
What it costs: precomputed order is paid at write time and locks the data to one order; a dataset can be physically sorted by only one key.
In-memory sort
Use it when all of the data fits in memory.
What it costs: nothing can be output until all input is read.
External merge sort
Use it when the data is larger than memory, on one machine.
Sort memory-sized runs, then merge them. The number to compute is the fan-in, how many runs merge at once, not the number of passes: fan-in ≈ memory ÷ the medium's efficient read size. 8 GB of memory with 1 MB reads merges about 8,000 runs at once.
What it costs: a bigger fan-in shrinks each run's buffer; below the efficient read size, sequential reads turn random.
Distributed (range-partitioned) sort
Use it when the data is spread across machines.
Sample the keys, choose boundaries, send each range to one machine, sort each range locally.
Before you build it: the real problem is choosing the boundaries, and the real risk is skew. A sort finishes when its slowest task does, so one bad boundary sets the whole stage's duration. Check the sample size against how many distinct keys you have before blaming the shuffle.
If it is a sliding window
Classify the aggregate before choosing a structure
Over a sliding window, the aggregate's algebra sets the memory cost:
- Invertible (sum, count, mean): subtract the element leaving the window; constant state.
- Associative but not invertible (max, min): you cannot subtract a max; use a monotonic deque or split the window into panes.
- Holistic (median, distinct count, top-k): state grows with the window, or use a sketch. There is no exact solution with bounded state.