Execution Engine

For each row of the outer input, scan the entire inner input and emit the pairs that satisfy the join predicate. Comparisons are O(n*m), and the naive form re-reads the inner input once per outer row, so I/O is the real problem.

Each sort or grouping operator gets a limited memory budget. If the rows it must hold exceed that budget, the engine writes partial results into temporary files and reads them back later. Spilling replaces memory work with disk I/O, so latency jumps sharply.

Phase one (build): read the smaller input fully and hash its join-key values into an in-memory hash table. Phase two (probe): stream the larger input, hash each row's key, look it up, and emit matches. It is chosen for equality joins over large inputs with no useful index.

Each operator call returns a batch — commonly around 1024 rows held column-wise — instead of one row. Per-call dispatch is amortized over the batch, and the inner loops become tight, branch-free, cache-resident and SIMD-friendly, so far more cycles go into real work.

Every plan operator implements open/next/close. The root's next() pulls one row from its child, which pulls from its child, down to the scans. It is simple and streams rows early, but costs an indirect call per row per operator, so big scans spend most cycles on machinery rather than data.

A streaming operator can emit an output row after seeing one input row — filters, projections, index lookups, nested-loop joins. A blocking operator must consume its entire input first — sorts, hash-join builds, hash aggregation, distinct, some window functions. Blocking costs memory, risks spilling to disk, and delays the first row until all input is read.

Both inputs must arrive sorted on the join key. Two cursors then walk them once in parallel: advance whichever side holds the smaller key, and emit rows when the keys are equal. One pass over each input; the expensive part is getting the inputs sorted.

Instead of scanning the inner input, it performs an index lookup on the inner table for each outer row's join key. Cost becomes outer rows times the cost of one lookup (an index descent plus row fetches) rather than outer rows times the whole inner table, so it scales with the outer side, not the product.

It uses external merge sort: fill memory, sort that chunk, write it out as a sorted run, repeat; then merge the runs with a heap, taking the smallest current row across runs. Cost is roughly two I/Os per row per pass, and passes grow when runs exceed the merge fan-in.

Hashing builds one in-memory entry per distinct key and needs memory proportional to the number of groups, but no ordering. Sorting needs no per-group memory but costs an O(n log n) sort, yet is free when input is already ordered and it delivers ordered output. Planners choose by estimated group count versus memory budget.

The build side's size determines the hash table's memory footprint, so the smaller input keeps it in memory. Choice is made from estimated rows, not actual. A large underestimate produces a hash table far bigger than its memory grant, forcing spilling to disk, or leaves the engine probing a huge table against a tiny one — either way, a plan that looked cheap runs for a very long time.

It spills: the sort writes sorted runs to temporary storage and merges them later; the hash build partitions the input to disk and processes partitions in turn. The query stays correct but does extra passes of I/O. Diagnose via spill counters and temp-file usage; fix the cardinality estimate, the memory grant, or the plan.

Its cost is the outer row count times a per-lookup constant, and the optimizer chose it believing the outer side would produce few rows. If the real outer count is far larger, cost grows linearly with no fallback: millions of random index probes instead of one sequential scan plus a hash join.

A hash function maps a value to a bucket and destroys ordering and locality: values that are close numerically land in unrelated buckets. So a hash table can answer "which rows have exactly this key?" but never "which rows are less than, or within a range of, this key." Range joins need other algorithms.

The order comes from an ordered access path — typically scanning a B-tree index whose leading columns are the join key, or the output of an earlier order-preserving operator. Reading in index order costs nothing extra, while an explicit sort costs O(N log N) plus temp-storage I/O when it does not fit in memory.

Instead of one outer row at a time, it buffers a block of outer rows that fits in memory and scans the inner input once per block, comparing each inner row against every buffered outer row. Inner scans drop from the outer row count to the number of blocks; the comparison count stays the same.

It runs a top-N heap sort: keep a bounded heap of only N rows, compare each incoming row against the heap's worst element, and discard immediately if it loses. Memory is O(N) instead of O(input), so no spill — but the whole input is still scanned, and the trick dies once N gets large.

When the build side exceeds memory, the engine hash-partitions both inputs into matching partitions written to temporary storage, then joins one partition pair at a time in memory. That is grace hash join. The hybrid variant keeps the first partition in memory and joins it during partitioning, so part of the work avoids disk entirely.

Pull: the consumer calls next() on its child and rows come back as return values. Push: the producer drives the loop and hands each tuple or batch to its parent's consume() method. Push fuses operators into one tight loop, suits code generation and multi-consumer plans; pull makes early termination and multi-input operators easier.

Because the intermediate is consumed more than once, or must be frozen. Buffering it turns repeated re-execution of a subtree into repeated cheap reads, lets one result feed several consumers, stabilizes a result that would otherwise change while the statement modifies the same rows, and shields an expensive or non-deterministic subplan from repeated evaluation.

Equal keys on both sides form groups whose full cross product must be emitted. The algorithm marks the start of the inner group and rewinds to that mark for every row of the outer group, so inner rows are read once per outer duplicate. Output for that key is the product of the two group sizes.

Get the executed plan with actual row counts and per-operator memory. Look for a sort or hash aggregate that switched from in-memory to external/batched with large temp bytes, and for actual rows far above estimates. Then cut rows and columns feeding it, supply order via an index, refresh statistics, and only then raise the memory budget for that job.

Merge join wins when the order is already there or cheap: both sides indexed or clustered on the join key, memory too small to hold a build side, an ordering needed downstream, or a large-versus-large join whose hash build would spill anyway. Hash join wins for one-shot joins on unordered inputs with a build side that fits.

Budget from total memory minus the buffer cache, divided by realistic peak concurrency and the number of memory-hungry operators per query — not per query in isolation. Too low means constant spilling and IO; too high means a few concurrent reports exhaust memory, evict the cache, or crash the process.

Decide by workload and engineering budget. Compilation fuses operators into register-resident loops and wins on long, compute-heavy analytical queries, but costs milliseconds of compile time per query plus hard debugging. Vectorized interpretation gets most of the win with precompiled primitives, no warm-up, and far less complexity — the safer default.

Budget from the top down: total RAM minus OS and buffer pool leaves a working-memory pool; divide by realistic peak concurrency times operators-per-plan to get a conservative default. Then differentiate by workload — small default for OLTP, elevated per-role or per-session for batch — and treat spilling as acceptable degradation, not failure.