How a database actually runs your query

1 The execution model — running a plan tree

Recall from Session 8 that the optimiser hands the executor a query plan: a tree where each node is an operator (a small piece of machinery like "scan this table", "filter these rows", "join these two inputs"). Leaves read data; the root produces the final answer. Execution is the act of actually running that tree to produce rows.

The Volcano / iterator model

The dominant way to run a plan tree is the Volcano model (also called the iterator model or pipeline model), described by Goetz Graefe in the early 1990s. The idea is beautifully uniform: every operator exposes the same three methods, no matter what it does.

A tuple is just one row. Because every operator speaks this same little language, you can plug any operator on top of any other — a filter on top of a scan, a join on top of two filters — and it all just works. This is what Graefe meant by extensible: adding a new operator never breaks the others.

Pull-based, one tuple at a time

The opposite of pulling would be materialisation: each operator fully computes its entire output, stores it in a temporary table, and hands the whole thing up. That wastes huge amounts of memory for big tables. The Volcano model instead pipelines: a row is produced, flows all the way to the top, gets returned to the user, and only then does the next row get pulled. Memory stays tiny, and the very first row can come back almost instantly.

The request travels down (the next() calls); the tuple travels back up. Repeat until the scan says "no more rows."

// Every operator implements this same interface.
interface Operator {
    void  open();          // prepare state, open children
    Tuple next();          // return next tuple, or NULL when exhausted
    void  close();         // release resources, close children
}

// The driver loop the database runs at the very top:
function runQuery(rootOperator):
    rootOperator.open()
    while (tuple = rootOperator.next()) is not NULL:
        emitToClient(tuple)        // send this row to the user
    rootOperator.close()

2 Scan operators — getting rows off disk

Scan operators are the leaves of the plan tree — they're where actual data enters the pipeline. The two you'll meet constantly are the sequential scan and the index scan.

SeqScan — read the whole table

A SeqScan (sequential / full-table scan) reads every page of the table from start to finish and emits each row. Recall from earlier sessions that a table is stored as a set of fixed-size pages (blocks) on disk, each holding many rows. SeqScan walks them all.

class SeqScan implements Operator:
    function open():
        self.pageCursor = firstPageOf(self.table)
        self.rowCursor  = 0

    function next():
        while self.pageCursor is not NULL:
            if self.rowCursor < rowsIn(self.pageCursor):
                tuple = readRow(self.pageCursor, self.rowCursor)
                self.rowCursor += 1
                return tuple
            // page exhausted, move to the next one
            self.pageCursor = nextPage(self.pageCursor)
            self.rowCursor  = 0
        return NULL          // no more pages, table fully scanned

    function close():
        releasePages(self.table)

IndexScan — use a sorted shortcut

An IndexScan uses an index (typically a B+-tree, covered in our indexing sessions) to jump straight to the rows that match a condition, without reading the whole table. The index is a separate, sorted structure mapping column values to the locations of matching rows.

class IndexScan implements Operator:
    function open():
        // descend the B+-tree to the first key >= low bound
        self.cursor = index.seek(self.lowKey)   // e.g. age = 30

    function next():
        if self.cursor is atEnd or self.cursor.key > self.highKey:
            return NULL                       // passed age = 40, stop
        rowId  = self.cursor.value             // pointer to the actual row
        tuple  = fetchRow(rowId)               // follow pointer to the heap
        self.cursor = self.cursor.advance()    // next sorted entry
        return tuple

    function close():
        index.releaseCursor(self.cursor)

When is each chosen? Cost intuition

The optimiser (Session 8) picks based on selectivity — what fraction of the table matches. The key trade-off is sequential vs random I/O:

• SeqScan reads pages in order — fast, sequential disk reads — but reads everything. Cost ≈ number of pages in the table.
• IndexScan reads only matching rows, but each matching row may require a random jump to a different page (slow), plus the cost of walking the index.

3 Filter & Projection — the pipeline's gatekeepers

Filter and Projection map directly onto two pieces of SQL you already know: the WHERE clause and the SELECT list.

Filter — applying the WHERE predicate

A Filter operator (also called Selection, the σ in relational algebra) sits on top of a child operator. For each tuple the child gives it, it evaluates a boolean predicate (the WHERE condition). If the predicate is true, the tuple passes up; if false, it's dropped and the filter immediately asks its child for another.

class Filter implements Operator:
    function open():
        self.child.open()

    function next():
        while (tuple = self.child.next()) is not NULL:
            if evaluate(self.predicate, tuple) is TRUE:
                return tuple      // passed the test
            // else: drop it and loop to fetch the next child tuple
        return NULL              // child exhausted

    function close():
        self.child.close()

Projection — choosing and computing columns

A Projection operator (the π in relational algebra) reshapes each tuple: it keeps only the requested columns and can compute new ones. Crucially, a filter changes how many rows flow; a projection changes what each row looks like but never adds or removes rows.

class Projection implements Operator:
    function open():
        self.child.open()

    function next():
        tuple = self.child.next()
        if tuple is NULL: return NULL
        return {
            name:   tuple.name,
            annual: evaluate(tuple.salary * 12, tuple)   // computed column
        }

    function close():
        self.child.close()

Expression evaluation

Both operators rely on expression evaluation: turning something like salary > 50000 or salary * 12 into a value for a given tuple. Internally an expression is a small tree — and yes, it's evaluated by the same recursive pattern as the plan tree.

        >
       / \
   salary  50000

function evaluate(node, tuple):
    if node is Constant:  return node.value          // 50000
    if node is Column:    return tuple[node.name]      // look up salary in the row
    if node is Operator:                            // e.g. >, *, AND
        left  = evaluate(node.left,  tuple)
        right = evaluate(node.right, tuple)
        return apply(node.op, left, right)             // 60000 > 50000 -> TRUE

4 Nested loop join — the simplest join

A join combines rows from two tables based on a matching condition (e.g. Employees.dept_id = Departments.id). The nested loop join is the simplest algorithm and the foundation for the rest. There are three flavours.

Naive (tuple-at-a-time) nested loop join

For every tuple in the outer table, scan every tuple in the inner table and emit the pairs that satisfy the join condition.

class NestedLoopJoin implements Operator:
    function open():
        self.outer.open()
        self.inner.open()
        self.outerTuple = self.outer.next()   // grab first outer row

    function next():
        while self.outerTuple is not NULL:
            while (innerTuple = self.inner.next()) is not NULL:
                if joinMatches(self.outerTuple, innerTuple):
                    return combine(self.outerTuple, innerTuple)
            // inner exhausted: advance outer, rewind inner
            self.outerTuple = self.outer.next()
            self.inner.close(); self.inner.open()   // restart inner scan
        return NULL

    function close():
        self.outer.close(); self.inner.close()

If the outer table has M rows and the inner has N rows, this compares roughly M × N pairs — O(M·N) time. Worse, if we re-read the inner table from disk every time, the I/O cost is brutal.

Block nested loop join

The big waste above is re-reading the inner table once per outer row. The block nested loop join fixes this by reading the outer table a block of pages at a time: load as many outer rows as fit in memory, then scan the inner table once for that whole block. This cuts inner re-scans from "once per outer row" to "once per outer block" — a massive I/O reduction. (Same O(M·N) comparisons, but far fewer disk reads.)

Index nested loop join

If there's an index on the inner table's join column, we don't scan the inner table at all. For each outer row, we do an IndexScan (Topic 2) to jump straight to matching inner rows. This turns the inner "loop" into a fast lookup.

class IndexNestedLoopJoin implements Operator:
    function next():
        while TRUE:
            if self.innerCursor has moreMatches:
                inner = self.innerCursor.next()
                return combine(self.outerTuple, inner)
            self.outerTuple = self.outer.next()
            if self.outerTuple is NULL: return NULL
            // probe the index instead of scanning the whole inner table
            self.innerCursor = innerIndex.lookup(self.outerTuple.joinKey)

★ Putting it all together

You now know how a database turns a plan into running machinery. Here's the one-paragraph story connecting all four topics:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• DBMS Session 9 — Query Execution (your course handout for this session).

Papers, docs & deep dives

• CMU 15-445 — Database Systems (course site) — the gold-standard free course; its query execution and join lectures cover exactly this material with slides and recorded videos.
• Graefe — "Volcano: An Extensible and Parallel Query Evaluation System" (IEEE TKDE, 1994) — the original paper that defined the open/next/close iterator model we used all session.
• Silberschatz, Korth & Sudarshan — Database System Concepts — the standard textbook; the "Query Processing" chapter walks through scans, selection, projection, and join algorithms in depth.
• PostgreSQL docs — Using EXPLAIN — see real plan trees with Seq Scan, Index Scan, and Nested Loop nodes in a production database, with cost and row estimates.
• CMU 15-445 lecture notes (Fall 2023) — concise written notes on the processing model, access methods, and join algorithms to complement the videos.