8.1 Query Executor: Scan, Join, Aggregate, and Resource Boundaries

The same SQL can scan a table or use an index, and join through nested loops, hashing, or merging. The executor implements these choices as operators and data flow. This lesson follows scans, joins, and aggregates to identify which steps stream results, which first accumulate state, and what happens when memory runs out.

Learning Objectives

• Distinguish between logical plan and physical plan;
• Understand the concepts of iterator, materialization, and vectorized execution;
• Compare sequential, index, and bitmap scans;
• Correctly analyze nested-loop, hash, and merge joins;
• Identify memory budget, spill, blocking, and pipeline breaker.

From SQL to Execution Plan

SQL text
  -> parse tree
  -> name/type resolution and semantic checks
  -> logical rewrite/normalization
  -> physical alternatives and cost search
  -> executable plan
  -> result protocol

Some systems integrate rewrite into the optimizer, while others first generate a bound relational tree. Support for view expansion, subquery decorrelation, and predicate inference also varies. It's not accurate to claim that all products strictly follow the same four-stage process.

Iterator model

The classic Volcano iterator defines an operator as:

open()
next() -> next tuple or end
close()

The parent invokes the child next(), forming a pull pipeline:

Limit
└─ Project
   └─ Filter
      └─ Index Scan

The advantage is composability and streaming; the cost is per-tuple function calls, branching, and poor instruction locality. Modern engines can use batch-at-a-time/vectorized, push-based, or compiled pipelines.

Streaming and Blocking Operators

• Filter, project, and most scan operators produce output immediately after reading a tuple;
• Full sort operators typically need to read the entire input before producing any output;
• Hash join build side must first construct a hash table;
• Hash aggregate usually requires seeing sufficient input before it can complete grouping;
• Materialize or cache operators store input for later reuse.

Blocking operators act as pipeline breakers, increasing startup latency and introducing memory or spill risks. LIMIT can stop an ordered scan early. Above a full sort, it may still require reading all candidate input.

Sequential scan

A sequential scan traverses relation pages or segments and applies the filter to visible tuples:

SELECT customer_id, name
FROM customers
WHERE level >= 15;

This SQL runs on the Lesson 1.2 SQLite fixture and matches Customer A and Customer B, without a guaranteed order. Check the actual plan to determine its access path. A sequential scan may outperform an index scan when:

• The table is small;
• The predicate has a high hit rate;
• The output requires most of the columns or a large number of rows;
• Sequential/readahead bandwidth is more efficient than numerous random heap fetches;
• Parallel scanning is available;
• Cache residency or the correlation between index order and heap layout makes index access less attractive.

The statement "a full table scan is the dumbest but always correct" is overly simplistic: while a scan is a valid physical execution path, the predicate expression may still throw an error, and factors such as snapshot consistency, permission boundaries, or data corruption can affect execution.

Index scan and index-only scan

CREATE INDEX idx_customers_level_id
ON customers (level, customer_id);

An index scan first retrieves matching index entries and then accesses the base table rows. If the heap pages pointed to by these entries are scattered across the storage, the cost of random page fetches increases.

For an index-only scan to be possible, the following conditions must be met:

• The columns required by the query must be available within the index entry;
• The engine must be able to verify version visibility using index and visibility metadata;
• The query plan must determine that the benefit outweighs the cost.

PostgreSQL may still perform a heap fetch even when query columns are covered, due to the visibility map not marking the corresponding heap pages all-visible. In contrast, InnoDB's "back-to-table" lookup in secondary indexes typically relies on a primary key lookup, reflecting a different physical model.

Bitmap scan

PostgreSQL bitmap index scans can combine multiple index results into a page/tuple bitmap, then access the data in heap-page order:

Bitmap Heap Scan
└─ BitmapAnd
   ├─ Bitmap Index Scan(status)
   └─ Bitmap Index Scan(reward)

This approach aggregates numerous tuple-locator accesses into page-level operations, reducing redundant or scattered heap page visits. However, it does not guarantee strictly contiguous I/O on physical storage. When memory is insufficient, bitmap representations can become lossy (only recording page-level information) and the resulting heap scan must reevaluate the predicate conditions.

Bitmap scan paths are most effective when intermediate selectivity is involved. For very few rows, a direct index scan is typically more efficient. For the majority of rows, a sequential scan remains the preferred approach.

Nested-loop join

for outer_row in outer:
    for inner_row in parameterized_inner(outer_row.key):
        if join_predicate:
            emit

Without an access path, repeated scanning of the inner table can be costly; with an index supporting parameterized lookup, it's suitable for small outer tables or highly selective probes.

The complexity cannot be captured solely by outer × log(inner): each probe may return multiple rows, cache hits vary, predicate evaluation differs, and random I/O patterns are not uniform.

NLJ can also be used for non-equality joins and lateral correlations, making it the most general join framework.

Hash join

The conceptual flow of an equi-join:

build:
  for row in build_input:
    hash_table.get_or_create(hash(row.key)).append(row)

probe:
  for row in probe_input:
    for candidate in hash_table.get(hash(row.key), []):
      if equality(candidate.key, row.key):
        emit pair

Hash buckets must store multiple candidates and cannot use hash_table[key] = row to overwrite duplicates. After hash collisions, rows must still be compared using database equality semantics. This pseudocode shows an ordinary equijoin and omits NULL, outer-join, and resource handling. Under SQL =, NULL keys must not be emitted as equal matching pairs.

The optimizer typically favors the input with the smaller estimated size for the build side, but factors like row width, data skew, parallel exchange requirements, outer-join semantics, and available memory can alter this decision.

Spill/batching

When the build input exceeds available memory, the engine can partition both inputs using a secondary hash: matching keys are grouped into the same partition, and the build and probe operations proceed in batches. However, this is not a cost-free "graceful degradation":

• Temporary I/O overhead increases;
• Highly skewed keys may still cause a single partition to overflow;
• Repartitioning and recursive batching introduce additional passes;
• Concurrent hash nodes or workers amplify memory and disk pressure;
• Spill tail latency may spike dramatically.

Merge join

When both sides are sorted on compatible join keys:

compare current key groups
smaller side advances
equal groups produce all matching pairs

Duplicate groups must produce Cartesian matches. Merge joins are suitable for operators and order semantics that are merge-joinable, and not all < or BETWEEN can automatically use the same algorithm; specific operator classes and support are determined by the engine.

Input ordering can come from an index scan, an upstream sort, or an existing pathkey. If both sides require spilling to disk, a hash join might be cheaper; if the parent also requires ordering, the sort cost may be reused.

Aggregation

Hash aggregate

group_key -> aggregate states. Suitable when group keys can fit in memory or when the engine can efficiently partition and spill data. High cardinality, wide state, or skew introduces additional risks.

Sort/group aggregate

The input is sorted by group keys, and accumulation occurs within each group. This approach is highly attractive when an existing order is available; otherwise, it incurs the cost of sorting and potential spilling.

Streaming aggregate

If the input is already ordered by grouping key, only the current group's state needs to be retained, keeping memory usage very low.

COUNT(DISTINCT), ordered aggregates, and large user-defined states alter the operator requirements.

Resource ownership

Query memory is not simply "one query using a fixed pool":

• Multiple sort/hash nodes can exist simultaneously;
• Parallel workers each maintain their own state;
• Pipelined nodes can overlap in lifetime;
• Materialization and spooling generate temporary files;
• Result buffering and client backpressure also consume resources.

Add budgets for simultaneously active nodes, then account for worker and session concurrency, counting genuinely shared state once. PostgreSQL hash nodes also use hash_mem_multiplier; not every node necessarily reaches its limit at the same time. Raising work_mem blindly can turn a spill into an OOM failure. See PostgreSQL resource configuration.

Lesson Summary

An execution plan is a combination of operators and data flow. The choice of scan depends on selectivity, coverage, and locality; the choice of join depends on cardinality, order, memory usage, and predicate conditions. Spill occurs at the resource boundary and is not a transparent detail. The next lesson explains how the optimizer uses statistics and cost to select among these alternatives.