Problem and applicable scenarios
You own an OLAP engine's GROUP BY. Input size and cardinality are unstable, so aggregate state may exceed memory. Explain how to avoid a sudden failure or performance cliff at the boundary, and how you would verify the design.
This fits data-engineering, query-execution, and database-kernel interviews. Assume exact aggregation is a blocking operator whose output requires reading all input; do not assume the input is sorted by group key.
What the interviewer is evaluating
- Whether you can explain why hash aggregation is usually the in-memory baseline and why it is not trivially spillable.
- Whether memory management, page layout, parallel combining, and I/O backpressure form one execution model in your answer.
- Whether you distinguish estimate-then-switch plans from runtime-adaptive behavior and their failure boundaries.
- Whether you can prove throughput, peak memory, and tail latency with reproducible experiments instead of product-name recall.
Clarifying questions before answering
- What are the upper bounds for group-key cardinality and aggregate state? Without a bound, a spill path is mandatory.
- What storage medium and query latency are acceptable? Local NVMe, network disks, and object storage require different I/O assumptions.
- Must the result be exact? An approximate sketch changes the problem constraints.
- May the output be reordered? If yes, sort aggregation is a candidate; if no, preserve hash-path semantics.
A 30-second answer framework
“I treat GROUP BY as a blocking operator and establish a baseline from per-group state and a memory budget. With room available I use parallel hash aggregation. As the budget is approached, I do not restart the query or abruptly switch to a separate disk algorithm; I let the same paged state spill gradually between memory and storage. A buffer manager handles eviction and reload, threads move through sink, combine, finalize, and output. I increase cardinality in controlled tests, measure peak memory, spill volume, throughput, and failures, and retain sort aggregation for low-cardinality or already sorted input.”
Step-by-step deep dive
1. Build a state budget first
Estimate the key, accumulator, hash metadata, and alignment cost per group, then multiply by expected cardinality. Include page directories, temporary buffers, and thread-local state. Estimating only input bytes misses the state explosion caused by high cardinality.
2. Use one paged representation
Place aggregate state in addressable pages. In memory, use a CPU-friendly layout; under pressure, let one buffer manager evict pages to storage and reload them later. Reconstruct page addresses or offsets on reload. This avoids serializing the entire operator into a second format and avoids restarting when one more row crosses the estimate.
3. Control parallel phases and backpressure
Organize parallel execution as sink, combine, finalize, and get-data: threads build local state, combine page references, and finalize output once. Spilling must obey buffer-manager and I/O-queue backpressure; otherwise more threads create random-write amplification. Track skewed keys and split oversized pages or cap per-group state when needed.
4. Compare alternatives
If input is sorted by group key, streaming aggregation keeps little state. For low cardinality and stable state, in-memory hashing is fastest. Sort aggregation is suitable when sorting is acceptable, ordered output is required, or hash state is badly skewed. An estimate-driven runtime switch can make one extra group trigger an unpredictable cliff.
5. Design reproducible verification
Keep input width fixed and increase unique groups until state crosses the budget. Record per-stage throughput, peak RSS, bytes read and written, spilled pages, reloads, and p95 latency. Repeat hot- and cold-cache runs and inject I/O throttling. Check correctness against an independent sort-aggregation result; timing alone is insufficient.
High-quality sample answer
I would first confirm that this is exact, blocking aggregation and that group state can exceed memory. The baseline is a parallel hash table, but I would store state in a unified paged buffer manager: when memory is tight, cold pages are evicted to storage and later reloaded into the same logical structure. Threads cooperate through sink, combine, finalize, and get-data, while an I/O queue applies backpressure so concurrency does not saturate storage. Sorted input can use streaming aggregation; low cardinality can stay fully in memory. I would then run cardinality-ramp tests with hot and cold caches, checking exact results, peak memory, spill volume, and p95 latency to show graceful degradation across the budget.
Common mistakes
- Symptom: “When memory is low, write it to disk.” Why it fails: no page layout, reload, concurrency, or backpressure is defined. Fix: describe the unified buffer manager and phase boundaries.
- Symptom: Estimate cardinality and restart after exceeding the limit. Why it fails: estimation error turns boundary data into a cliff. Fix: use gradual runtime spilling without a query restart.
- Symptom: Claim hash aggregation always beats sorting. Why it fails: sorted input, low cardinality, and skew change the trade-off. Fix: state when the alternative wins.
- Symptom: Report only average throughput. Why it fails: spilling first changes tail latency and failure rate. Fix: include peak memory, I/O, p95, and correctness.
Follow-up questions and answers
What if storage latency suddenly rises?
Reduce the rate at which new threads enter sink, expose queue watermarks, and keep hot pages resident. If the SLO still cannot be met, return a resource-exhausted result instead of unbounded memory growth.
What if one group key owns most of the state?
Split that key's state into mergeable shards, cap page size, and merge shards during finalize. If the aggregate is not decomposable, explicitly reduce parallelism or reject the plan.
When would you choose sort aggregation?
Choose it when input is guaranteed sorted, ordered output is required, or random hash-state access costs more than sorting and sequential scans. Mention that sort's temporary runs may spill too.
How do you prove there is no performance cliff?
Ramp cardinality on one dataset and plot size against latency. Around the memory budget, look for a smooth slope rather than a step change, and compare against an abrupt disk-algorithm switch under the same hardware, cache, and I/O limits.
What if the result page also exceeds memory?
Let downstream consume get-data as a stream, or write final pages to a temporary relation for sequential reads. Do not rebuild an unbounded result array merely to return it.