Query execution: joins, aggregation, vectorization

Why it matters

The nodes in an EXPLAIN plan are these algorithms. Knowing their costs lets you explain why a query spilled to disk, why a nested loop was disastrous or why a different join order changed memory use. Research and performance roles go further, into how engines minimize per-tuple overhead on modern CPUs.

Core ideas

Joins. For R ⋈ S with M and N pages and B buffer pages:

• Block nested loop reads R once and S once per block of R: about M + ⌈M/(B−2)⌉·N I/Os, fine when one input is tiny.
• Index nested loop probes an index on S for each R tuple; good when R is small after filtering and the index is selective.
• Sort-merge sorts both inputs (unless already sorted) and merges them; attractive when inputs arrive sorted or the output must be sorted.
• Hash join builds a hash table on the smaller input and probes it with the other. If the build side does not fit, Grace hash join first partitions both inputs with the same hash function, so matching tuples land in matching partitions, for about 3(M + N) I/Os. Hashing needs equality predicates; other join conditions need nested loops or sorting.

Sorting and aggregation. External merge sort writes sorted runs of B pages, then merges B−1 runs at a time: about 1 + ⌈log_(B−1)⌈N/B⌉⌉ passes, each reading and writing N pages. Aggregation either sorts and scans groups or hashes on the group key; hashing is usually faster unless sorted output is needed anyway.

Processing models. In the iterator model every operator offers next() and pulls one tuple at a time: simple and composable, but every tuple pays function-call and interpretation overhead. The materialization model passes whole results, which suits OLTP queries with small outputs. Vectorized engines pass batches of hundreds to a few thousand values per column, amortizing overhead and enabling tight loops and SIMD. Compiling engines generate code per pipeline, fusing operators so a tuple stays in registers from the scan up to the next pipeline breaker, an operator such as a hash build, sort or full aggregation that must consume all its input before producing output.

index NLJ:  for r in R: for s in index_lookup(S, r.k): emit(r, s)
hash join:  build H on S.k; for r in R: for s in H.get(r.k): emit(r, s)

Skew. If one key holds a large share of rows, one hash partition or one worker gets most of the work. Engines detect heavy hitters and process them separately, or broadcast the matching rows of the other input.

Common misconceptions

• "Hash join is always best." It needs an equality predicate and memory for the build side; a selective index or sorted inputs can make other joins cheaper.
• "Nested-loop joins are always bad." With a tiny outer input and an index on the inner input they are often cheapest; the danger is choosing one on an underestimate.
• "Vectorized and compiled execution are rival fads." Both remove interpretation overhead; a controlled comparison found compilation stronger on computation-heavy pipelines and vectorization better at hiding memory stalls, and some systems combine them.
• "Spilling only happens on huge tables." It happens whenever an operator exceeds its memory budget, often because of a misestimate.

How to approach it

Do the cost arithmetic for each join on one example until it is automatic. Then implement: BusTub's query execution project covers scans, aggregation, hash join, external sort and an optimizer rule. Finally, read the 15-721 notes on vectorized execution and compilation, and keep conclusions modest: the better model depends on the workload.