Interview questions
Plans and the properties they need
1Why can two queries that return identical results differ in cost by 10,000 times?
A query says what result is wanted, not how to compute it. The engine can realize it with many different plans, and the sorts, shuffles and hash tables each plan must add differ enormously in cost.
Read moreA query is a specification
2What is an enforcer in a query plan?
An operator the engine inserts, such as a sort, a shuffle, a hash build or a deduplication, because another operator requires a property of its input (an order, a partitioning, uniqueness) that nothing upstream provides.
Read moreRequires, provides and enforcers
3Why can ORDER BY not return its first row early, while LIMIT 10 can?
The very last input row might sort first, so a sort must see its whole input before emitting anything. An unordered LIMIT can stop after any 10 rows.
4Why is concurrency not a problem inside query execution?
A query runs against a fixed snapshot of the data, so executing it is a pure function: retrying a task or reordering work never changes the answer.
Read moreTwo constraints disappear
5What is the basic trade-off between hash-based and sort-based operators?
Hashing is O(n) but leaves nothing reusable behind. Sorting is O(n log n) but leaves an order that later operators, such as a merge join, a grouping or an ORDER BY, can use for free.
Read moreThe core tension: hash or sort
6How many passes does an external sort need, and when does it need a third?
1 + ⌈log_F(N / M)⌉, where M is memory, B the I/O buffer size and F = M / B the merge fan-in. A third pass is needed only above N = M² / B: with 16 GB of memory and 8 MB buffers, about 32 TB per node. The same threshold applies to hash joins.
Read moreOut-of-core: the threshold
7When does broadcasting the smaller table beat shuffling both sides of a join, in network cost?
Broadcasting copies the small table to all P workers; shuffling moves both tables once. Broadcast wins on network when the large table is more than P times bigger than the small one. In practice memory, P copies of the small table, usually sets the limit first.
SQL semantics and what operators cost
8Why does projection in SQL not need to see all rows first, while projection in relational textbooks does?
SQL works with bags and keeps duplicates, so projecting columns is a per-row operation. Textbook projection works with sets and removes duplicates, which requires seeing everything.
Read moreSQL is bag algebra, not set algebra
9Why is NOT IN slower and riskier than NOT EXISTS?
If the subquery returns a single NULL, x NOT IN (…) is UNKNOWN for every row, and the query returns nothing. To get that right the engine needs a special three-outcome join rather than a plain anti-join. NOT EXISTS has no such trap.
Read moreThe join family
10What bug does a condition on the right-hand table in WHERE cause for a LEFT JOIN?
Unmatched rows have NULLs in the right-hand columns, so the condition is UNKNOWN for them and they are filtered out: the outer join silently behaves like an inner join. Put such conditions in the ON clause.
Read moreThe join family
11SQL has two kinds of equality. What are they, and where is each used?
Comparison equality, =, uses three-valued logic, so NULL = NULL is unknown; joins and WHERE use it. Grouping equality, IS NOT DISTINCT FROM, treats NULLs as equal; GROUP BY, DISTINCT and set operators use it.
Read moreSQL has two equalities
12What are distributive, algebraic and holistic aggregate functions?
Distributive functions combine partial results directly (SUM, COUNT, MAX). Algebraic ones combine through a fixed-size tuple (AVG through a sum and a count). Holistic ones have no bounded intermediate state (MEDIAN, exact COUNT DISTINCT). The class decides whether work can be split before data moves.
Read moreThe algebra of aggregate functions
13What decides the cost of a query with many window functions?
The number of distinct (PARTITION BY, ORDER BY) specifications, since each needs its own sort, not the number of functions.
Read moreWindow functions
14Why is keyset pagination faster than OFFSET, especially on late pages?
OFFSET m produces and throws away m rows before returning k, so each page costs O(m + k) and late pages keep getting slower. Keyset pagination replaces the offset with a predicate, WHERE key > last_seen, so each page costs O(k).
Read moreThe bounded-answer trick
15Why must the recursive part of a recursive query be monotonic?
Engines evaluate recursion semi-naively: each round joins only the rows that were new in the previous round. That shortcut is correct only if the recursive step never removes or changes rows it already produced.
Read moreRecursive queries
Joins
16A naive join scans table S once for every row of R. What are the three ways to avoid that?
Build an index on the spot (hash join), use one that already exists (indexed nested-loop join), or impose an order on both sides (sort-merge join).
Read moreA join is a decision about where the index comes from
17Which two assumptions does a hash join rely on?
That the join condition is an equality, and that keys are roughly evenly spread, so no single key overwhelms a partition.
Read moreThe core tension
18What is a hybrid hash join, and why does its cost rise as a ramp rather than a cliff?
It keeps one partition of the build side in memory and spills only the rest, so when the build side is m and memory M, only the fraction (m − M) / m goes to disk. Cost grows in proportion to the overflow instead of jumping when memory runs out.
Read moreHybrid hash: a ramp, not a cliff
19A join uses a Bloom filter built at run time to drop rows early. Why does the answer stay exact?
A Bloom filter has no false negatives, so it never drops a row that would match. Its false positives pass through to the exact join, which rejects them: they cost some work, not correctness.
Read moreSideways information passing
20Why does an as-of join (the latest row at or before a given time) deserve its own operator?
It is a "take the maximum" inside a join. Written in plain relational form, it builds O(n · m) candidate pairs and then picks one per row, and no optimizer rewrites that into the linear merge a dedicated operator does.
Read moreAs-of joins
21Why can skew on both sides of a join not be fixed by partitioning?
For a key with f_R rows on one side and f_S on the other, the output is f_R × f_S rows: genuinely quadratic work that must be produced somewhere. Only changing the question, for example aggregating one side first, helps.
Aggregation
22Why is COUNT(DISTINCT x) so much more expensive on a cluster than SUM(x)?
SUM is distributive: each worker sends one small partial sum per group. An exact distinct count is holistic: no fixed-size partial result exists, so the raw values themselves must be moved and deduplicated.
Read moreTwo-phase aggregation
23How much does partial (pre-shuffle) aggregation save, and when should it be turned off?
Its reduction ratio is about N / (P · G): the average rows per group on each of P workers, for N rows and G groups. Above about 10 it removes most of the shuffle; near 1 it is pure hashing overhead. Good engines sample the first rows and decide at run time.
Read moreThe core tension, as one ratio
24Why does skew in the group key not hurt SUM … GROUP BY, but cripple COUNT(DISTINCT) … GROUP BY?
Partial aggregation collapses the hot group to one row per worker before the shuffle. A holistic function cannot be collapsed, so every raw row of the hot group lands on a single reducer.
Read moreTwo-phase aggregation
25When memory fills during a hash aggregation, what are the options for spilling?
Spill raw rows (always correct, expensive); spill partial aggregates and merge them later (only for distributive and algebraic functions, with far less I/O); or keep the hot groups in memory and spill only the cold ones.
26How can skew make an aggregation cheaper?
Aggregation cost follows the number of distinct groups, not rows. With skew, a small set of hot groups held in memory absorbs most rows, so far less has to spill.
27What does using a sketch actually do to an aggregate?
It turns a holistic aggregate into an algebraic one: a fixed-size, mergeable state, about 12 KB for HyperLogLog. The approximation is the price of unlocking partial aggregation, a single shuffle, spilling partial state, and immunity to skew.
Read moreWhat a sketch actually does
28How does HyperLogLog's error relate to its memory?
The standard error is 1.04 / √m for m registers. 16,384 six-bit registers (12 KB) give 0.81%; 0.1% needs about a million registers (about 800 KB): roughly 66 times the memory for 8 times less error.
Read moreThe error formula
29Can you estimate COUNT DISTINCT from a 1% sample?
No. Rare values dominate the answer, and a sample mostly misses them. Sampling works for SUM and AVG, but not for COUNT DISTINCT, MIN or MAX.
Read moreWhat a sketch actually does
30Why can two runs of the same percentile query return different answers?
Merging t-digests is lossy and depends on the shape of the merge tree, which changes from run to run. HyperLogLog merges (register-wise maximum) are exactly reproducible, and KLL's error is bounded. Check which you use when a metric must be reproducible.
Read moreMergeability is not uniform
31Why can the same SUM over floating-point values differ between runs?
Floating-point addition is not associative, and partition counts, task completion order and merge trees all change the order of additions. Use compensated summation, decimals, or a fixed order.
Read moreFloating-point summation
32When is sort-based aggregation a better choice than hash-based?
When the output must be ordered by the group key anyway, when the input is already grouped, or when the function is an exact holistic one such as a median: sort by group and value, then read positions.
Read moreSort-based aggregation
Sorting
33What does an external sort cost in I/O, and how many passes does it take?
About 4N of I/O (read the input, write sorted runs, read them back, write the output), in two passes as long as N ≤ M² / B. With 16 GB of memory and 8 MB buffers that is up to 32 TB per node, so two passes is nearly always enough.
Read moreExternal merge sort
34When merging sorted runs, should you always maximize the number merged at once?
No. An F-way merge costs log F comparisons per record; at F = 1,000 that is about ten, comparable to the in-memory sort itself. Removing a pass saves I/O but spends CPU.
Read moreExternal merge sort
35Why is replacement selection rarely used for run generation any more?
Its heap has poor cache locality, and halving the number of runs rarely changes a pass count that is already two. It survives as a way to adapt to nearly sorted input.
36Why is range partitioning better than hash partitioning for a distributed sort?
With range partitioning, each worker sorts its own range, and the global result is just the ranges concatenated. Hash partitioning co-locates equal keys but gives no order between partitions, so the sorted parts do not compose.
Read moreSample-based range-partitioned sort
37Does range partitioning fix a hot key?
No. It fixes skew in how values are distributed, but a single key with more than N / P rows is a point mass that no choice of boundaries can split.
Read moreThree failure modes
38What is a normalized key, and why do sort implementations use one?
A byte string whose memcmp order equals the intended order of a multi-column key. Each comparison becomes one branch-free, vectorizable operation, typically 2–10× faster, and it makes radix sorting possible.
Read moreRadix sort and normalized keys
39How does an engine avoid a sort?
By tracking order as a property of each intermediate result. A prefix of an existing order is free; an equality predicate makes a column constant, so it drops out of the required order; an input sorted on part of the key needs only a segmented sort; and an operator that only needs rows grouped needs less than a full sort.
Read moreSort avoidance
40Why does OFFSET pagination get slow on late pages?
The engine must produce and discard every row before the offset, so its work and state grow with the page number. Keyset pagination replaces the offset with a predicate on the last key seen.
Read moreThe bounded-answer trickWhat query processing forbids
Deduplication
41In two-stage deduplication, why may the local stage flush its state early but the final stage must not?
A local stage that forgets keys only lets extra duplicates through, which the final stage removes. A final stage that forgets a key emits it twice, and nothing downstream corrects that.
Read moreThe state parameter
42How wide should a hash digest of a row be when used for deduplication?
128 bits. With 64 bits, the chance of at least one collision is about 2.7% at a billion rows and about 93% at ten billion, and a collision silently drops a row.
Read moreUse 128 bits
43Why is a Bloom filter safe in front of a join but unsafe for deduplication?
In front of a join, a false positive passes a row to an exact join that rejects it: extra work. In deduplication, a false positive marks a new row as already seen, so it is dropped, and nothing checks it: lost data.