Physical operators — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 3: Turning requests into execution

Prerequisites: Lesson 14 and the preceding foundations.

Learning outcomes

Trace scans, joins, sorting, and aggregation through their physical state and output behavior.
Calculate memory requirements and external passes when data exceeds a budget.
Choose among nested-loop, hash, and merge strategies using cardinality, ordering, skew, and spill costs.

A small answer can require a large computation

A query returns the ten customers with the highest spending. Producing those ten rows may require scanning payments, joining account data, grouping millions of records, and ranking the groups. The size of the answer does not bound the work required to discover it.

Physical operators implement logical operations using concrete algorithms, state, and resource budgets. The optimizer chooses among them, but the executor must preserve semantics when memory is insufficient, inputs are skewed, or the query is cancelled. A fast in-memory algorithm without a safe external path is incomplete for an engine that accepts larger workloads.

Scans and filters

A sequential scan visits data in its physical organization. It can exploit contiguous access and prefetching. An index scan follows a search structure and retrieves matching candidates. A bitmap-like strategy can collect matching locations and visit pages in a more favorable order. The best choice depends on selectivity, clustering, visibility checks, and required order.

If a predicate matches most rows, scanning the table can be cheaper than performing many scattered index-driven accesses. An index is not automatically the fastest route just because it exists. Conversely, a selective lookup should not read a huge table when a narrow access path can find the row.

Filters evaluate predicates on candidates. Projection avoids carrying unused fields further. In a vectorized engine, these operations can process batches and represent selected positions without immediately materializing full rows. The control-flow choices appear in Lesson 17; the algorithmic work remains tied to input cardinality and width.

Nested-loop joins

A nested-loop join takes an outer row and searches the inner input for matches. Without an index or other aid, comparing every pair has O(NM) candidate work. With an indexed inner lookup, it can be effective when the outer input is small and each lookup is selective.

For an illustrative 100 outer rows and an inner primary-key index, 100 lookups may be inexpensive. For ten million outer rows whose keys cause random misses, the same strategy can become costly. The algorithm label is unchanged while the access pattern and resource demand differ dramatically.

The operator must preserve duplicate matches and outer-join behavior. If one outer row matches several inner rows, it emits each required combination. A left join also emits a null-extended row if no match exists. Cancellation and errors must release held buffers and transaction resources.

Hash joins

A hash join builds a hash table from one input and probes it with the other. It is commonly useful for equality joins. Expected work is approximately linear in input size under suitable hashing and memory assumptions, but skew and large duplicate groups can increase cost.

for row in build_input:
    hash_table[key(row)].append(row)
for row in probe_input:
    for candidate in hash_table[key(row)]:
        if full_join_predicate(row, candidate):
            emit_combination(row, candidate)

The pseudocode retains all rows per key because duplicate semantics matter. It omits null handling and outer-join bookkeeping, which a real operator must implement. A residual predicate may reject candidates sharing the equality hash key. Hash equality alone is not the full join condition.

Build-side choice matters. The smaller logical input may still have a wider row representation. Hash overhead, buckets, alignment, and retained payload can exceed raw input bytes. An estimate that ignores this overhead can unexpectedly spill or exhaust memory.

Partitioned and external hash joins

When the build state does not fit, the engine can partition both inputs by a hash and process corresponding partitions. If a partition is still too large, it may be repartitioned or handled using another strategy. Temporary storage becomes part of the query’s resource budget.

Skew can defeat naive partitioning. If one key has millions of rows, hashing that key again does not split its equal-key group while preserving ordinary join semantics. The engine needs skew-aware handling, heavy-key separation, or a fallback. A huge duplicate match group may legitimately produce an enormous result, so no algorithm can make output proportional to a tiny input assumption.

Spill files need bounded naming, cleanup, integrity, and failure handling. A full temporary device should produce a controlled query error rather than corrupt durable database state. Background cleanup must not delete files still owned by another live query.

Merge joins

A merge join consumes inputs ordered by join key. It advances through their key ranges, producing matches when keys align. If inputs are already ordered through indexes or earlier operations, it can avoid building a large hash table.

Duplicate groups require careful buffering or revisiting. If three left rows and four right rows share a key, an ordinary inner join produces twelve combinations. The operator must account for this even if it streams most nonduplicate keys. Outer and inequality joins introduce additional rules.

Sorting the inputs can cost more than the merge saves. However, a required final order or reuse of the ordering elsewhere can make the total plan attractive. Optimizers compare properties of the whole plan, not isolated operator times.

External sorting

Sorting larger-than-memory input commonly begins by sorting memory-sized runs, writing them to temporary storage, and merging runs. The number of merge passes depends on available memory, input/output buffers, file limits, and fan-in.

For an illustrative 1 GiB input and 64 MiB of usable run memory, there are at least sixteen initial runs before accounting for overhead. If the merge can read all sixteen concurrently with appropriate buffers, one merge pass can produce the sorted output. Smaller fan-in requires additional passes, increasing I/O.

The initial run size is not simply the configured memory value divided by raw tuple width. Sort keys, row references, allocator overhead, and representation matter. A top-k strategy can reduce state when only a small prefix is needed, but it may still need to examine all input to know which rows belong in that prefix.

Aggregation

Hash aggregation maintains state per group. Ordered aggregation can complete a group when the input advances beyond its key. Memory depends on distinct-group count and aggregate-state size, not just input row count.

A billion rows grouped into ten categories may have small final state. Ten million distinct identifiers can require much more memory even with fewer input rows. Approximate aggregates can reduce state for suitable use cases, but they change result guarantees and must be labeled accordingly.

Parallel aggregation needs a valid combine operation. For average, each worker can retain sum and count; the final result divides total sum by total count. Averaging worker averages without weighting is wrong when workers process different numbers of rows. Null and numeric-overflow semantics also need preservation.

Blocking, streaming, and cancellation

A blocking operator must consume substantial input before producing useful output, as in a full sort. A streaming operator can emit results progressively. This affects time to first row, retained memory, and cancellation responsiveness even when total execution time is similar.

Pipelines can propagate backpressure from a slow consumer. An upstream scan should not keep producing unbounded materialized rows when the output cannot drain. Cancellation must reach all workers, close temporary files, and release reservations. Some cleanup can be deferred safely, but the ownership must remain explicit.

A database can prioritize interactive work by limiting large operators or placing them in separate resource groups. That changes admission and fairness rather than the algorithm’s semantic result. The policy should be visible enough that an operator can explain why a query is queued or spilling.

A physical operator has an explicit interface

A useful operator contract states its input schema, required order, output schema, duplicate and null behavior, memory budget, and termination protocol. In a pull-style interface, a parent requests the next row or batch. In a push-style interface, a child offers output subject to downstream capacity. Either form needs a way to distinguish end of input, an error, and a temporary wait. A zero-row batch is not necessarily end of input unless the interface says so.

Ownership belongs in that contract. If an operator returns a view into a reusable input batch, the parent cannot retain it after the next call unless it takes ownership or copies required values. A hash join building state must retain stable keys and payload, not pointers into a scan buffer that will be overwritten. Many execution bugs are lifetime errors caused by treating a convenient row reference as permanently valid.

An operator also needs an account for memory it has reserved but not yet used, memory retained by emitted output, and temporary state during conversion or spilling. A simple current-allocation counter can underestimate peak transitions. Query-level cancellation must release or transfer every reservation, even if one worker fails while others are still producing output.

Compare nested loops and hashing with explicit assumptions

Assume an outer relation has 1,000 rows and the inner relation has one million. Each outer key has one matching inner row accessible through a hot index. If an indexed lookup costs an illustrative 5 microseconds, lookup work is about 5 milliseconds before output and other operators. Building a hash table over all million inner rows can easily do more work than those thousand lookups. Expected linear complexity alone does not establish the faster plan.

Now increase the outer relation to ten million rows and suppose the inner lookups frequently miss cache, costing 200 microseconds each. The simple sum is 2,000 seconds of lookup residence if performed sequentially. Some waits may overlap, but device capacity and concurrency impose limits. A scan-based hash join that reads the inner once and probes in batches can become much more attractive. The input sizes and physical access pattern changed the comparison.

An index nested-loop join can also cache repeated parameter results when semantics permit. If ten million outer rows contain only one thousand distinct keys, repeated lookup work can be reduced with memoization. That cache consumes memory and must respect snapshot and parameter semantics. The optimizer should estimate distinct probe keys, not only total outer rows, when evaluating such a strategy.

These are constructed cost comparisons, not timings for a particular engine. They demonstrate why physical choice depends on cardinality, key repetition, cache locality, and output size together. A one-line claim that hash joins or index joins are always faster misses those conditions.

Null and residual handling in a hash join

For an ordinary equality join, null keys do not compare equal under SQL’s usual predicate semantics. A build row with a null join key therefore cannot simply be grouped with other nulls and emitted as a match. An outer join may still need to preserve that row as unmatched. A null-safe equality operator, if explicitly requested by the dialect, requires a different rule.

A hash value is only a routing hint. Distinct keys can collide, so the executor compares actual keys after finding the bucket. A further residual predicate can reject rows with equal keys, such as a time-window restriction. For a left outer join, the operator emits a null-extended outer row only if no candidate satisfies the full join condition. Finding a bucket is not proof of a match.

Tracking matched build rows can support right or full outer joins. The tracking structure consumes memory and must be safe under parallel probes. After probing ends, unmatched rows are emitted according to the join semantics. An early cancellation or partial input failure cannot be treated as proof that remaining rows are unmatched, because unseen probe rows might have matched them.

Anti-joins and null-aware anti-joins add further state. A generic equality hash table can be reused as a building block, but the join operator must implement the exact logical contract established by the front end. Reusing code is useful only when semantic differences are explicit.

Skew creates both execution imbalance and unavoidable output

Suppose one million left rows and one million right rows share the same equality key. Their ordinary inner join produces one trillion pairs. At even 16 bytes per output pair, the raw output is 16 TB in decimal units. No join algorithm can return that complete result with work proportional only to the two million input rows. Output size is a lower bound on the required work.

A semijoin or preaggregation can produce much less output when that is what the query means, but the executor cannot silently substitute those semantics. The planner should use keys, constraints, and frequency estimates to predict large match groups and avoid unintentional explosions. Resource limits can stop a runaway query safely while preserving the distinction between a query error and a changed result.

Skew can also cause imbalance when output is modest. Hash partitioning sends all equal keys to one partition, so one worker can dominate completion while others finish early. Splitting a heavy group may require replicating one side, subdividing the Cartesian product, or choosing another algorithm. Each choice has memory and communication costs. Rehashing with a different seed does not divide one equal-key group into independent equality classes.

For merge joins, a large duplicate group may require buffering one side or repeatedly revisiting it. If that group exceeds memory, the operator needs a spill strategy. The usually streaming algorithm can therefore become blocking around one key. Average group size is insufficient for a tail-latency or memory guarantee.

External sorting as an I/O accounting problem

Take the constructed 1 GiB input with 64 MiB of usable run memory. Sixteen initial runs are produced if overhead is ignored. Reading input and writing those runs moves 2 GiB. A final sixteen-way merge reads another 1 GiB and can stream directly to its consumer. That gives about 3 GiB of read/write traffic across input and temporary storage boundaries, or 4 GiB if the final sorted result is also materialized to storage. Boundaries must be stated to compare the totals correctly.

If fan-in is only four, an intermediate merge combines sixteen runs into four, reading and writing another 2 GiB before the final merge. Small memory therefore increases not only CPU work but the number of full-data passes. Buffers for every input run, an output buffer, comparison keys, and heap state all consume memory; fan-in is not unlimited merely because many files can be opened.

A stable sort must preserve the required ordering among equivalent keys if the interface promises that property. SQL without a complete tie order may permit several outputs, but client pagination may require a unique tie-breaker. Collations and null ordering must remain identical between run generation and merging. A mismatch creates a result that is locally sorted within runs and globally wrong.

Temporary files need disk-space accounting and cleanup after process failure. Query failure because temporary storage is full should not affect durable table integrity. Reusing file names or directories without ownership checks can create security and cleanup hazards. External algorithms are production features only when their failure paths are as explicit as their fast path.

Top-k changes retained state, not always scanned work

For an unsorted input of one hundred million rows, a top-ten operator can keep a heap of ten candidates rather than sort the entire input. Each new qualifying row is compared with the current threshold and may replace the worst candidate. Retained state is small, while every qualifying input row still needs to be considered unless another access path proves it cannot win.

If computing the ranking expression is expensive, the heap does not remove that cost. If rows contain large payloads, the operator can retain keys and stable row references, then fetch payload for winners. That saves memory only if the reference lifetime and snapshot remain valid. Late materialization connects operator design back to storage layout.

A matching ordered index can stop early after finding enough qualifying rows. Residual predicates can force inspection of many more candidates. For example, if only one in a thousand ordered rows passes a permission or status filter, obtaining ten results might examine around ten thousand rows under a simple independent model. Correlated distributions can make that much better or worse.

Aggregation state can be small or unbounded

SUM and COUNT have fixed-size state per group under their numeric representation. An aggregate collecting every value into an array grows with input cardinality. Exact median requires retaining or externally organizing substantial information unless the value domain permits a special structure. A memory planner should know each aggregate’s state-growth behavior rather than assume one constant budget per group.

For ten million groups with an illustrative 64-byte aggregate entry, payload state alone is 640 MB. Hash buckets, allocator overhead, keys, and output buffers increase it. A 512 MB query budget cannot safely hold that state merely because the input itself is streamed. Partitioned aggregation can spill groups by key and process them later, with special handling for aggregates whose partial state is itself large.

Ordered aggregation can finish a group when ordering proves no more rows for that key will arrive. If a later stage breaks order, that proof no longer holds. The optimizer must propagate actual physical properties, and the executor must not assume order from a source that only happened to produce it in a previous run.

Cancellation is a protocol across the plan

A root operator receiving cancellation marks shared query state and stops requesting new work. Parallel workers check at safe points, stop producing output, and report terminal state. In-flight I/O retains its buffers until completion. Temporary files and memory reservations are released exactly once, even when cancellation races with a normal completion or another worker’s error.

Some operations require rollback rather than immediate termination. A mutation can have installed provisional changes that the transaction manager must undo or hide. A read can retain a snapshot whose release enables cleanup. Canceling only the network response while leaving execution running can consume resources long after the caller disappears. Conversely, freeing execution memory before workers stop can cause use-after-free faults.

This is why an executor is more than a collection of algorithms. It coordinates lifetimes, budgets, errors, and progress across a graph. The fastest implementation of one join routine is insufficient if it cannot coexist safely with spills, slow consumers, cancellation, and transactional visibility.

Visualize retained state and external work

hash join:
  build input -> [hash table: keys + rows + match metadata]
  probe input ---------------------> lookup -> residual check -> output
  memory pressure -> partition build and probe -> temporary partitions
                                           -> process matching partitions

external sort, 1 GiB / 64 MiB example:
  input -> 16 sorted runs -> [merge buffers + priority structure]
                              -> final ordered stream
  smaller fan-in -> intermediate merged runs -> another read/merge pass

The diagram labels retained state rather than assuming it equals raw input bytes. Hash buckets and match metadata add memory; sort buffers and comparison references reduce usable run space. Temporary partitions or runs add I/O and space whose lifetime continues until the consuming operator finishes or cleanup takes ownership.

A plan producing output incrementally can still contain blocking suboperators. The hash build must be ready before ordinary probes find matches, and a global unsorted top-k must inspect enough input to prove its winners. Time to first row, total completion time, and peak retained state therefore need separate analysis. The diagram is a constructed execution model and does not imply one engine uses precisely these internal buffers.

Case connection and design conclusion

PostgreSQL’s executor documentation describes plan-node execution, while its explain facilities expose selected physical strategies. The scenarios in this lesson show why the same logical join can use different algorithms under different cardinality, width, order, and memory conditions.

A physical operator design states its input requirements, output semantics, state size, blocking behavior, external fallback, and cleanup obligations. Lesson 16 supplies the estimates and cost comparisons used to choose among those operators before actual execution reveals the true input.

Sources and further reading

Course index · Lesson plan