Query execution: the Volcano iterator model

Keep the course's running query in view:

SELECT name FROM emp WHERE salary > 75000 ORDER BY name;

By the time it reaches this lesson the string has already been turned into a tree. Week 8 lexed, parsed, and bound it into a typed query tree and a logical plan: projection(name) over selection(salary > 75000) over scan(emp), with a sort for the ORDER BY. Week 11 will turn that logical plan into a physical plan, choosing a sequential scan or an index scan on salary and deciding whether the sort can be skipped. This week sits between them in the pipeline but is taught first, because you cannot reason about which plan is cheapest until you know how a plan actually runs.

So the layer above (the optimizer) hands this layer a finished physical plan: a tree of concrete operators. This layer hands down a stream of page requests. When the scan at the bottom of the tree needs data, it asks the access method (weeks 6 and 7) for tuples, which asks the buffer pool (weeks 4 and 5) for pages by id, which asks the storage manager (weeks 2 and 3) to read bytes off disk. The whole stack is the spine from week 1. Our job here is the middle of journey 1: the executor.

The problem: do not build a table you were never asked for

The executor receives a tree of physical operators and must produce tuples. The most obvious way to run a tree is to evaluate it bottom up. Run the scan, write all of its output to a temporary table. Run the filter over that table, write its output to another temporary table. Run the projection, write a third. Hand the last table to the client. This is the materialization model, and it is perfectly correct.

It has two costs that sink it. The first is memory and I/O. Each operator writes its whole output and the next operator rereads it. A five-operator plan over a billion-row table writes and rereads a billion rows four times to produce results nobody asked to keep. The second cost is uniformity. If the join operator hard-codes the fact that its input is a temporary file on disk, you cannot feed it the output of an index scan or another join without rewriting it. Operators stop composing.

The mechanism: open, next, close

In the iterator model every operator, leaf or internal, implements the same three procedures. Graefe frames them as the four parts of a loop over a result set: initialization, the increment, the termination test, and the final housekeeping [Graefe 1994, Section III.B].

• open(): set up state, recursively open the inputs, allocate any buffers or hash tables this operator needs.
• next(): return the next output tuple, or an end-of-stream marker when there are no more. Call next() on an input only when more input is needed.
• close(): release state and recursively close the inputs.

Execution is demand-driven and top-down by control, bottom-up by data. The consumer at the root calls next(). That call recurses down to the leaves. One tuple bubbles back up per call. The PostgreSQL executor states the same contract: each node, when called, produces the next tuple in its output sequence or NULL if none remain, and a non-leaf node calls its child nodes in turn to obtain input [PostgreSQL executor README]. Parents pull. Children never push.

Two design choices in that picture deserve a name. First, an operator never learns what kind of operator feeds it. It just calls next() on an input pointer. Graefe calls these anonymous inputs or streams, and they are the reason any operator nests inside any other [Graefe 1994, Section III.B]. Second, all of an iterator's per-instance data lives in a state record, with no static variables. That invariant is what lets the same operator code (say, sort) appear several times in one plan: each occurrence gets its own state record [Graefe 1994, Section III.B].

Watch one tuple bubble up

The simulator below runs our query's plan: SeqScan(emp) feeding Filter(salary > 75000) feeding Projection(name). Click Step (or Play) to issue one next() at the root and watch it travel down and a tuple travel back up. Each operator shows the tuple it currently holds, and a counter tallies how many next() calls each operator has fielded. Filter and Projection never hold more than one tuple, which is the whole point.

Single-tuple iterator stepper press Step to pull one tuple through the plan

One interface, many operators

The reason a handful of operators cover so much SQL is that Volcano splits each operator into an algorithm shell and its support functions. The shell is the open / next / close loop. The support functions do all the item-level work: evaluate a predicate, hash a key, compare two records, compute a projected column. The shell is empty without them; a support function is just a function pointer plus a typeless argument, and because all interpretation of data items is imported this way, Volcano needs no type system for instances and is data-model independent [Graefe 1994, Sections III.A, IV].

That split is why three of our operators are really one. Volcano's filter operator carries three optional support functions: a predicate (selection), a transform (projection), and an apply function called once per record for side effects (updates, printing). So Filter and Project in the course are the same physical operator with a different support function plugged in [Graefe 1994, Section III.B.1]. The SeqScan is the file-scan iterator. And the entire join family (join, semi-join, outer joins, intersection, union, difference, aggregation, duplicate elimination) is one operator, one-to-one match, because they all reduce to the same step: separate the matching from the non-matching subsets of two inputs and emit a selected, possibly transformed subset [Graefe 1994, Section III.B.2].

# the iterator contract, as pseudocode. Every operator looks like this.
class Filter(Iterator):
    def open(self):
        self.child.open()                 # recurse down
    def next(self):
        while True:
            row = self.child.next()        # pull one tuple from the anonymous input
            if row is EOF:
                return EOF
            if self.predicate(row):       # support function, imported
                return row                 # pass it up; O(1) state, one row held
            # else drop it and loop: pull again
    def close(self):
        self.child.close()                 # recurse down

Where the pipeline has to stop

Not every operator can stream. A pipeline breaker must consume its entire input before it can emit a single output tuple. Our running query has one: the ORDER BY name sort. Sort cannot know which tuple is smallest until it has seen the last input tuple, so it pulls every tuple from below, buffers them (spilling to disk via external merge sort if they exceed memory), and only then starts returning them in order. The build side of a hash join is the other classic breaker: the hash table must be fully built before any probe can match [CMU 15-445 joins].

Breakers are where a query's memory budget is set, because that is where a whole input (or a hash table, or sorted runs) must live. In PostgreSQL that budget is work_mem, the per-operation memory before a sort or hash spills to temporary disk files [PG resource config]. External sort, the hash build, and grace partitioning are the subject of week 10; here just hold the distinction: Filter and Projection are streaming with O(1) state, Sort and the hash build are breakers.

Streaming operators versus pipeline breakers.

Operator	State held	Streams or breaks
SeqScan, IndexScan	one cursor	streams
Filter, Projection	one tuple	streams
Index nested loop, merge step	one tuple per side	streams
Sort (ORDER BY)	whole input or sorted runs	breaks
Hash join build side	whole hash table	breaks
Aggregation, DISTINCT	one entry per group, or whole sort	breaks

The cost of the simplest join

Our running query has no join, but most queries do, and the join is where the iterator model first meets real I/O cost. A join of R and S is conceptually the Cartesian product filtered by a predicate. Done literally that is |R| times |S| comparisons. The nested loop join is the most direct way to run it as iterators, and its three variants show how much the same logical join can cost depending on the physical choice.

Let R (the outer) have M pages holding m tuples, and S (the inner) have N pages. The naive nested loop rereads all of S once per outer tuple:

naive nested loop:  M + (m × N)

The m × N term is the killer. The block nested loop rereads S once per outer block instead of per tuple, giving the outer scan B - 2 buffer frames (one for an inner page, one for output):

block nested loop:  M + (ceil(M / (B - 2)) × N)

The index nested loop replaces the inner scan with an index probe at roughly constant cost C per outer tuple:

index nested loop:  M + (m × C)

On the standard CMU example (M = 1000, m = 100000, N = 500, B = 100, 0.1 ms per I/O) the naive form is about 1.4 hours, the block form about 6.5 seconds, and the right index turns it into a few hundred milliseconds [CMU 15-445 joins]. Same logical join, four orders of magnitude apart. The simulator below lets you feel the block term move as you change the buffer count.

Nested loop cost calculator drag the sliders and watch the three variants diverge

Deeper: who owns the tuple in the buffer, and why Volcano avoids temp files

When next() returns a record it returns a status plus a Next-Record structure: an RID and an address of the record pinned in the buffer pool. The ownership invariant is that each pinned record is owned by exactly one operator at a time. On receiving a record an operator may hold it (in a hash table), unfix it (when a predicate fails), or pass it on; operators that build new records, such as a join, fix their output and unfix their inputs [Graefe 1994, Section III.B]. This is the pin-count machinery from week 4 seen from the executor's side.

Volcano deliberately does not pass intermediate results through temporary files between operators, as some textbooks suggest, because that carries a substantial performance penalty. Intermediate streams live on virtual devices whose pages exist only in the buffer and vanish when unpinned, so the same buffer machinery serves both permanent and intermediate data while keeping it in memory [Graefe 1994, Sections III.A, III.B]. The one place data does hit disk is a pipeline breaker that overflows memory, which is the spill behavior of week 10.

Paper viva: Volcano

This week's assigned paper is Graefe's "Volcano: An Extensible and Parallel Query Evaluation System" (IEEE TKDE 6(1), 1994). The examiner will not ask you to recite it. They will ask you to defend why the design is shaped the way it is. Try to answer each before opening the model answer.

Model answer

The three procedures are open, next, and close. open initializes the operator's state (for example allocates a hash table) and recursively opens all of its inputs, so every iterator in a query is initiated recursively. next produces and returns one result record at a time, calling next on its inputs only when it needs more input, and signals end-of-stream when its source is exhausted; this is lazy, demand-driven evaluation. close releases resources and recursively shuts down the inputs. The consumer initiates the work: the root operator's next is called repeatedly, and each operator pulls from below only on demand. So control flows top-down and data flows bottom-up over the same call stack [Graefe 1994, Section III.B].

Model answer

Because an operator only ever calls open / next / close on its input, it never needs to know what produces that input. Graefe calls these anonymous inputs or streams. Uniformity buys three things. Composability: any operators nest in any combination, so the optimizer can reorder and stack them freely. Extensibility: a new operator is added without touching existing ones, because they depend only on the interface. Orthogonal parallelism: a single special operator (exchange) can be inserted anywhere to parallelize a subtree, with no change to the operators around it. The state record makes this concrete: all of an iterator's arguments and runtime state live in its state record with no static variables, and operators are linked by input pointers stored in those records. That is why the same algorithm, such as sort, can appear several times in one plan, each instance with its own state record [Graefe 1994, Sections III.B, IV, VI].

Model answer

A support function is an imported function entry point plus a typeless argument that performs all item-level work: predicates, hashing, comparison, projection, and side effects. Volcano's iterators are empty algorithm shells without them. Because all interpretation of data items is imported this way, Volcano needs no instance type system and works for any data type or model; adding a new abstract data type does not change the Volcano code at all [Graefe 1994, Sections III.A, IV]. The course operators map directly. SeqScan is the file-scan iterator. Filter is the filter operator's predicate function and Project is its transform function, so Volcano fuses selection, projection, and side effects into one filter operator. Join is the one-to-one match operator, with hybrid hash and sort-merge implementations whose build, probe, and flush phases map onto open (build) and next (probe then flush) [Graefe 1994, Sections III.B.1, III.B.2].

Check yourself