Execution engines — 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 16 and the preceding foundations.

Learning outcomes

Compare iterator, vectorized, compiled, parallel, and asynchronous execution paths.
Calculate the amortization threshold for batching or compilation and identify first-result costs.
Explain SIMD, intermediate materialization, scheduling, and memory bandwidth as separate limits.

The same algorithm can have different instruction costs

Two engines both filter a column and sum matching values. One calls a virtual method for every row and constructs a small object for each intermediate result. Another processes a batch of compact values with a tight loop. A third compiles the query into specialized machine code. Their logical work is similar, but branching, dispatch, allocation, and memory access differ.

An execution engine determines how operators exchange data and how work maps to CPU resources. Its design affects throughput, first-result latency, compilation overhead, memory use, and cancellation. No representation is best for every query length and workload.

Iterator execution

A traditional iterator exposes methods such as open, next, and close. A parent repeatedly asks a child for another row. This composes operators naturally and supports streaming. A filter can request rows until one passes and return it upward.

filter.next():
    repeat:
        row = child.next()
        if row == END:
            return END
        if predicate(row):
            return row

The pseudocode clarifies control flow. Per-row calls and branches can become substantial when the useful work per row is tiny. The representation may also materialize tuples at boundaries, adding copying or allocation. On the other hand, it can produce the first result quickly and avoids the need to fill a large batch before returning.

Execution should distinguish end-of-stream from errors and cancellation. Resources acquired during open must be released on every termination path. A compositional interface is valuable only when ownership and cleanup compose as reliably as normal results.

Vectorized batches

A vectorized engine exchanges batches of values or columns. It amortizes call overhead and can operate on compact arrays. A selection vector can identify surviving row positions without immediately copying every field into a new row representation.

Batch size is a tradeoff. Larger batches improve amortization and may help instruction-level efficiency. They also retain more memory, delay first output, and can reduce fairness if one callback processes too much work. Smaller batches improve responsiveness while increasing per-batch overhead.

Null masks, variable-width values, and expression complexity affect vectorization. A batch of integers can be straightforward; strings may require offsets and indirect data access. A highly selective predicate can make compaction or sparse selection management important. Vectorized does not mean every operation becomes one hardware instruction.

SIMD and branching

Single instruction, multiple data, or SIMD, applies one instruction to several data lanes. It can accelerate comparisons and arithmetic over suitable representations. The benefit depends on CPU support, alignment, data types, and control flow.

Branch-heavy logic can disrupt efficient execution. A filter can sometimes use masks rather than unpredictable branches. But evaluating every expensive expression unconditionally may waste work compared with short-circuiting. A data-dependent expression can therefore favor different strategies at different selectivities.

Memory bandwidth can become the ceiling after CPU overhead is reduced. Once a scan consumes data as quickly as the memory system supplies it, adding more arithmetic optimization may do little. Parallel scans can saturate the same shared bandwidth, so per-core speedups do not multiply indefinitely.

Compilation and specialization

A compiled engine can generate code specialized to a query’s schema, expressions, and operator pipeline. This can remove generic dispatch and combine stages into tight loops. It introduces compilation latency, code-cache management, and additional implementation complexity.

An illustrative 2-millisecond compilation cost spread over one million processed rows is 2 nanoseconds per row. Spread over ten rows, it is 200 microseconds per row. These are amortization calculations, not measured execution costs. They explain why compilation can be attractive for long scans and unattractive for a one-off short lookup.

Caching generated code can amortize compilation across repeated queries. The cache must account for schema dependencies, parameter handling, memory use, and security. Excessively many distinct query shapes can create code churn. A fallback interpreter or mixed execution strategy can help short or uncommon queries.

Push, pull, and pipeline boundaries

Pull execution asks upstream operators for data. Push execution sends produced data downstream. Both can implement streaming and batching. Blocking operators such as full sorts create boundaries where data must be retained or reorganized.

Pipelining avoids materializing every intermediate result. A scan can feed a filter and projection directly. Materialization can still be useful when data will be reused, when adaptation needs cardinality evidence, or when workers require a shared stable representation. Avoiding all materialization is not a universal goal.

A pipeline also needs backpressure. If downstream output is blocked by a slow client, upstream operators must stop producing or retain only bounded state. Otherwise a fast scan can turn network delay into unbounded memory growth. Execution interfaces should make readiness and ownership explicit.

Parallel and asynchronous execution

Parallel execution divides work among simultaneous workers. A scan can split ranges; aggregation can combine partial state. The design must handle skew, duplicate work, cancellation, and shared resource limits. More workers can reduce elapsed time while increasing total CPU and memory consumption.

Asynchronous execution overlaps waiting, such as storage reads, with other useful work. It does not imply parallel CPU execution. A single worker can manage many pending reads and resume operators when their dependencies complete. Those pending operations still retain buffers and metadata.

Parallelism and async I/O can interact. Many workers each issuing many reads can overwhelm a device queue. A shared budget should bound aggregate demand rather than assuming every operator’s local limit is safe when multiplied. Admission and resource governance belong in the execution design.

Follow one batch through a real execution shape

Consider a hypothetical purchase table with one hundred million rows. The query computes total completed revenue for one region. Its needed inputs are a one-byte status code, a four-byte region identifier, and an eight-byte amount stored in integer cents. Ignore compression and auxiliary metadata initially so the costs remain visible. A column-oriented representation reads approximately thirteen bytes per row, or 1.3 billion bytes for the full scan. A row representation containing another two hundred unused bytes may bring many more bytes through the memory hierarchy even though the projection discards them.

A batch holds 1,024 row positions. The scanner produces three arrays plus validity masks. A first predicate compares status values and writes a selection vector of passing positions. A second predicate examines region identifiers only for those positions. The aggregation reads amounts for the final survivors. Assuming every value is non-null simplifies this first trace; a production implementation must preserve the SQL distinction between false and unknown and must implement the aggregate’s null rules.

Suppose 25% of rows are completed and 4% of completed rows are in the chosen region. Each batch starts with 1,024 positions, retains an expected 256 after the first filter, and about ten after the second. These are averages rather than guaranteed batch cardinalities. Clustering can produce almost-empty or almost-full batches even when the global percentages are unchanged. The aggregate can accumulate into one local integer state without allocating a projected tuple per survivor.

execute_batch(status, region, amount, valid):
    selected = empty_position_vector()
    for position in batch_positions:
        if valid.status[position] and status[position] == COMPLETED:
            selected.append(position)

    for position in selected:
        if valid.region[position] and region[position] == target_region:
            if valid.amount[position]:
                sum_state = checked_add(sum_state, amount[position])
                nonnull_count = nonnull_count + 1

The accumulator is explicitly checked because overflow behavior is part of the numeric contract. The final result is null if SQL requires it and no non-null input was accumulated. Returning zero unconditionally would silently change SUM semantics on an empty result. Specialization is safe only while it preserves such details.

A selection vector is useful because copying complete records after each predicate would spend bandwidth on intermediates that disappear at the next stage. Conversely, a dense batch with almost every row selected can make indirection wasteful. Engines can use a dense representation, a bitmap, or an explicit position list according to the batch’s state. This is a representation decision within execution, distinct from choosing an index during planning.

Quantify batching without inventing a benchmark

Assume an abstract operator call costs forty nanoseconds and useful per-row processing costs eight nanoseconds. Row-at-a-time execution spends forty-eight nanoseconds per row in this deliberately simplified model. At a batch size of 1,024, one forty-nanosecond call amortizes to approximately 0.039 nanoseconds per row, giving roughly 8.039 nanoseconds before additional batch-management costs. The model predicts a large reduction in dispatch overhead, not a measured sixfold product speedup.

Real batch processing pays for selection creation, null handling, cache misses, and the representation of variable-length values. If those add twelve nanoseconds per row, the modeled total becomes about twenty nanoseconds. If the data source is storage-limited at a thousand nanoseconds per row, saving tens of nanoseconds in dispatch barely changes elapsed time. An execution improvement matters in proportion to the work it removes from the current critical path.

Batch fill time also matters. If a streaming source yields only five hundred records per second, waiting to fill 1,024 records takes about 2.048 seconds from an empty batch under a constant arrival model. A timeout or partial-batch rule is necessary when first-result latency matters. A database scan over already available data has different fill behavior from a live stream. The same batch-size setting should not be interpreted identically across those sources.

Memory budgets multiply across operators and workers. Four arrays totaling thirty-two bytes per position require 32 KiB for 1,024 positions. Thirty-two workers retaining four such batches each account for 4 MiB of array payload before masks, variable-width buffers, allocator overhead, and hash-table state. That amount may be modest in RAM but meaningful for private CPU caches. The optimal batch is not simply the largest that fits in main memory.

Pipeline fusion and its semantic boundaries

A compiled pipeline can combine scan, filter, expression evaluation, and hash-table insertion into one generated loop. This avoids constructing a generic intermediate object between each operator. The useful abstraction is a pipeline breaker: an operation whose output depends on retaining or reorganizing a substantial input. A global sort is an obvious breaker. A hash join’s build side also creates state before the probe side can use the completed hash table, although more advanced execution may overlap carefully defined stages.

input pages
    |
    v
scan -> predicate -> projection -> partial aggregate
                                  |
                           materialized group states
                                  |
                                  v
                         merge -> order -> output

The arrows show data dependencies, not one thread per box. The first four stages may share one fused loop. The group states form an explicit materialization boundary. Ordering waits for its necessary input, and output serialization can become a separate bottleneck even after computation is fast.

Fusion can increase generated-code size and register pressure. A huge expression tree can exceed useful instruction-cache capacity or force intermediate values into memory. Reusing an interpreted operator can therefore outperform one enormous generated function on some workloads. Compilation also needs safe invalidation when a schema, collation, function definition, or access policy changes. A cached executable plan is a dependency-bearing artifact, not simply a string-to-machine-code dictionary.

Error semantics limit reordering. If an expression can divide by zero, access external state, or invoke a volatile function, moving it across a filter can change observable behavior. Even pure floating-point aggregation can produce different low-order bits after reassociation because floating-point addition is not associative. A parallel engine must document its numeric behavior rather than promise bitwise identity accidentally.

Parallel execution needs an ownership plan

Suppose a scan is divided into sixty-four ranges and scheduled on eight workers. Each worker takes a range, accumulates local groups, and publishes its completed state to a merge stage. Local aggregation avoids an atomic increment for every row. The merge performs fewer shared updates, but it must reconcile duplicate groups across workers and account for total memory.

Static division is simple when ranges contain equal work. Equal bytes do not guarantee equal processing: one range may contain long strings, expensive expressions, or skewed join matches. Dynamic task queues improve balance, but tasks that are too small pay excessive scheduling overhead. Work stealing can move computation toward idle workers while sacrificing data locality. The scheduler is choosing between balance and locality rather than obtaining both without cost.

Nested parallelism is another hazard. Eight query workers invoking a library that independently launches eight threads can create sixty-four runnable workers. With several concurrent queries, runnable work can overwhelm the machine even though each component appears reasonably bounded. The execution engine needs a shared accounting boundary for worker permits, memory, and I/O, or a composition rule that prevents accidental multiplication.

For a hypothetical eight-core machine, one query using all eight cores may complete twice as fast as with four because its remaining stages are partly serial. Two concurrent queries each using eight workers may instead compete for the same caches and memory bandwidth. Allocating four workers per query can improve overall response time and fairness. Per-query elapsed time and system-wide efficiency are different objectives.

Asynchronous state machines and cancellation

An asynchronous operator cannot leave an ordinary stack frame blocked indefinitely while holding an arbitrary latch. It stores enough continuation state to resume when an I/O completion arrives. That state includes buffer ownership, the next operator step, error status, and cancellation context. Pending work consumes memory even when it consumes no CPU.

resume_scan(state):
    if state.cancel_requested:
        release_owned_buffers(state)
        finish_cancelled(state)
    elif state.page_ready:
        process_available_page(state)
        schedule_next_bounded_step(state)
    elif not state.read_in_flight:
        reserve_io_permit()
        issue_read_with_completion(state)

This sketch omits the synchronization that arbitrates cancellation against completion. The important requirement is that one transition owns final cleanup. A callback arriving after cancellation must recognize that it may release an I/O reference but must not write into freed query state. Reference counting or a structured lifetime protocol can provide this guarantee; merely setting a cancelled boolean cannot.

Cancellation of an executing statement is distinct from reversing an already committed transaction. A query may also be cancelled after some result rows have been transmitted. The client protocol needs to distinguish a partial result followed by failure from a complete successful result. An execution design that ignores protocol completion can provide locally correct computation while causing callers to misinterpret truncated output.

Choosing an execution model from the workload

A prepared key lookup that reads one cached row may benefit little from a sophisticated vector pipeline. Its dominant costs can be admission, indexing, transaction metadata, protocol handling, and durability if it writes. A ten-billion-row aggregate can amortize compilation and benefit greatly from compact columns, partial aggregation, and wide execution. A subscription query executes incrementally over changes and needs yet another unit of work.

A practical design can combine a generic interpreter for low-startup-cost paths, batched operators for scans, and selected compiled expressions. The combination is justified by measured workload boundaries, not by accumulating every technique. Each additional execution path adds correctness obligations for nulls, types, errors, cancellation, and state lifetime.

The engine’s diagnostic output should expose where rows are produced, filtered, materialized, spilled, and exchanged. It should distinguish compilation time from execution time and report worker count and memory peaks. Without these observations, a user may mistake a slow compile or blocked result stream for an inefficient scan and tune the wrong mechanism.

Late materialization and variable-width data

The batch example used fixed-width columns. A string column usually carries offsets or pointers to separately stored bytes. Filtering on a numeric column first can avoid decoding or copying strings for rejected rows. This is late materialization: delay reconstructing a full output record until a consumer actually needs it. The optimization saves work only if position mappings remain cheap and the required values can still be located efficiently.

Consider a table with ten million rows, each containing a forty-byte average description. An early projection copying every description moves about 400 MB of character payload. If a numeric filter retains 1%, copying descriptions after filtering moves approximately 4 MB. These figures omit offset arrays, allocation headers, compression, and cache effects. They isolate the avoided intermediate payload rather than estimate end-to-end elapsed time.

Dictionary encoding can replace repeated strings with small codes. Equality against one known category may compare codes without expanding strings, provided the encoding’s semantics preserve the requested comparison. Lexical ordering, locale-aware collation, and case folding cannot always use raw code order. A representation optimized for equality may need additional work for sorting or range comparisons.

Retaining references instead of copying creates lifetime obligations. If a batch points into a decoded page, the page must remain pinned until the last consumer releases those references. A downstream sort that retains values for much longer may need to copy them into its own stable arena. Avoided copying can therefore become retained-memory pressure. The engine must account for transitive ownership rather than count only each operator’s immediate arrays.

Resource cleanup is part of the operator algebra

An operator tree composes success paths elegantly, but exceptions can occur at any depth: allocation failure in an aggregate, corruption during a scan, cancellation during an exchange, or a client disconnect during output. Every acquired resource needs a well-defined owner and finalization path. A parent closing itself should propagate cleanup to children even if opening the entire tree never finished.

One practical model separates reservation from acquisition and uses scoped ownership objects. A sort reserves a bounded memory budget before building runs. If the reservation fails, it chooses a spill path or returns a controlled resource error. If the disk fills during spilling, temporary files are closed and registered for removal. Returning an error while leaving dozens of gigabytes of orphaned runs is an operational correctness failure even if table contents remain intact.

Progress accounting helps diagnose these paths. Rows examined, rows produced, bytes spilled, I/O wait, CPU time, and output-blocked time should be distinct. A filter reporting ten output rows might have scanned ten billion inputs. A query reporting little CPU could be waiting for a device or a slow recipient. Meaningful counters describe the engine’s actual units of work and avoid attributing all elapsed time to whichever operator appears last in the plan.

The implementation can begin with a simple iterator and add batching where profiling shows dispatch overhead. That progression preserves a reference path for semantic comparison. Every faster path must produce the same permitted results and errors under the selected numeric and isolation contracts. Performance engineering is successful when it removes work while retaining those contracts, not when it merely removes validation or cleanup.

Compare the control paths visually

Tuple path: next(row1) -> filter(row1) -> project(row1)
            next(row2) -> filter(row2) -> project(row2)
            next(row3) -> filter(row3) -> project(row3)

Batch path: next([row1,row2,row3,...])
                 -> compare arrays -> selected positions -> aggregate

The illustration contrasts dispatch granularity rather than claiming that a batch always fits one SIMD instruction. Both paths can implement the same relational operation. The batch path reduces calls and can expose compact arrays to hardware, while the tuple path can return an early survivor without waiting for batch fill. A compiled pipeline can further fuse the batch’s stages or specialize a row loop; compilation and batching are independent choices.

An amortization threshold follows from the saved work. If compilation costs two milliseconds and saves five nanoseconds per processed row, break-even occurs at four hundred thousand rows, ignoring code-cache reuse and secondary effects. Fewer rows favor the lower-startup path under those assumptions. A repeated prepared query can amortize compilation across executions, while a stream of unique tiny queries cannot. This threshold is a constructed calculation, not a universal engine setting.

Case connection and design conclusion

SQLite documents bytecode execution through its virtual machine. ClickHouse documents an architecture oriented toward efficient analytical processing. These provide contrasting implementation contexts for interpreting dispatch, batching, and representation. The lesson’s calculations and workload implications are architectural analysis rather than comparative benchmarks of those products.

An execution design should identify its unit of work, exchange representation, compilation policy, parallel boundaries, waiting model, and cleanup obligations. Lesson 18 then examines a larger boundary: whether application computation runs inside the engine, beside it in the same process, or across a network.

Sources and further reading

Course index · Lesson plan