How SQL Reaches Bytes on Disk — Building a Query Engine From Scratch

What This Article Traces

Type SELECT name FROM users WHERE age > 30 and results come back. This article traces everything that happens in between, without ever stopping at "and from here it's a black box."

The starting point is a plain string. The end point is a concrete instruction: read 8192 bytes at offset 34,988,032 of file descriptor 42, and interpret 48 of those bytes as a struct. Between them sit more than a dozen transformations, each with its own intermediate representation.

The running example is a slightly larger query that joins two tables: SELECT u.name, o.total FROM users AS u JOIN orders AS o ON u.id = o.user_id WHERE u.age > 30 AND o.total > 100 ORDER BY o.total DESC LIMIT 10. The demo below follows it through every stage.

SELECT u.name, o.total
FROM users AS u
JOIN orders AS o ON u.id = o.user_id
WHERE u.age > 30 AND o.total > 100
ORDER BY o.total DESC
LIMIT 10;

The overall structure looks like this. The upper half is the layer that understands the query; the lower half is the layer that touches data.

The dotted edges are references rather than data flow. The catalog and the statistics are consulted from outside the main top-to-bottom path. The plan cache skips part of that path: when the same SQL arrives a second time, a cached physical plan can be used right after binding, and the stages from the logical plan through optimization do not run again (chapter 9).

We will implement each stage in Python, leaning on PostgreSQL's vocabulary. Concrete names (pd_lower, t_hoff, clock-sweep) make it much easier to pick up the real source code afterwards.

The spine is the running example traced top to bottom, but we detour into GROUP BY aggregation, NULL and three-valued logic, what actually happens past work_mem, plan caching, and how parallel plans get costed. Each bears directly on why a query suddenly gets slow in production.

Index data structures themselves (B+ trees and LSM-trees) are covered in How Database Indexes Work, so this article concentrates on how indexes are used.

Chapter 1: Lexing — Cutting a String Into Tokens

The first job is turning a sequence of characters into tokens, the smallest meaningful units.

It looks trivial, but decisions have to be made. Is >= one token or two? Is age30 an identifier, or age followed by 30? The answer is maximal munch: from the current position, consume as much as possible. That makes >= one token and age30 one identifier.

from dataclasses import dataclass
 
KEYWORDS = {
    "SELECT", "FROM", "WHERE", "AND", "OR", "NOT",
    "JOIN", "ON", "AS", "ORDER", "BY", "ASC", "DESC", "LIMIT",
    "GROUP", "HAVING",
}
TWO_CHAR_OPS = (">=", "<=", "<>", "!=")
 
 
@dataclass(frozen=True)
class Token:
    kind: str   # KEYWORD / IDENT / NUMBER / STRING / OP / PUNCT / EOF
    text: str
    pos: int
 
 
def tokenize(sql: str) -> list[Token]:
    out: list[Token] = []
    i, n = 0, len(sql)
    while i < n:
        if sql[i].isspace():
            i += 1
            continue
 
        start, c = i, sql[i]
 
        if c.isalpha() or c == "_":
            while i < n and (sql[i].isalnum() or sql[i] == "_"):
                i += 1
            word = sql[start:i]
            kind = "KEYWORD" if word.upper() in KEYWORDS else "IDENT"
            out.append(Token(kind, word, start))
 
        elif c.isdigit():
            while i < n and sql[i].isdigit():
                i += 1
            # Only consume a dot when a digit follows it — otherwise we would
            # break qualified references such as "t.1".
            if i + 1 < n and sql[i] == "." and sql[i + 1].isdigit():
                i += 1
                while i < n and sql[i].isdigit():
                    i += 1
            out.append(Token("NUMBER", sql[start:i], start))
 
        elif c == "'":
            i += 1
            while i < n and sql[i] != "'":
                i += 1
            if i >= n:
                raise SyntaxError("unterminated string literal")
            i += 1                       # closing quote
            out.append(Token("STRING", sql[start:i], start))
 
        elif sql[i:i + 2] in TWO_CHAR_OPS:   # must be tried before 1-char ops
            out.append(Token("OP", sql[i:i + 2], start))
            i += 2
 
        elif c in "=<>+-*/%":
            out.append(Token("OP", c, start))
            i += 1
 
        elif c in ",().;":
            out.append(Token("PUNCT", c, start))
            i += 1
 
        else:
            raise SyntaxError(f"unexpected character {c!r} at position {i}")
 
    out.append(Token("EOF", "", n))
    return out

The order of the branches carries meaning. If the sql[i:i+2] in TWO_CHAR_OPS test does not come before the single-character operator test, >= splits into > and =.

The demo below runs this scanner one token at a time.

Where Keywords Are Recognized

The implementation above reads the whole word first and then consults the keyword table. Do it the other way around (scan for the literal string SELECT) and a column named selected_at splits into SELECT + ed_at. Munch first, classify second is the rule.

The SQL standard reserves more than 200 words, and implementations differ. PostgreSQL grades them into four categories, listed in kwlist.h: reserved; reserved but still usable as a function or type name; non-reserved but not usable as a function or type name; and fully non-reserved. That gradation is why words like value and name (both non-reserved) still work as column names.

Chapter 2: Parsing — Assembling Tokens Into a Tree

Next, the parser assembles the tokens into a tree. Plain recursive descent handles the skeleton of a statement (SELECT … FROM … WHERE …), but expressions (a + b * c > d AND e) need operator precedence. We use precedence climbing, also known as Pratt parsing.

AST Definitions

@dataclass
class ColRef:                       # an unresolved column reference
    table: str | None
    column: str
 
@dataclass
class Const:
    value: object
 
@dataclass
class BinOp:
    op: str
    left: object
    right: object
 
@dataclass
class FuncCall:
    name: str
    args: list
    star: bool = False       # the * in COUNT(*)
 
@dataclass
class TableRef:
    name: str
    alias: str | None
 
@dataclass
class JoinExpr:
    left: object
    right: object
    on: object
 
@dataclass
class SortKey:
    expr: object
    desc: bool
 
@dataclass
class Select:
    targets: list
    frm: object
    where: object | None
    group_by: list
    having: object | None
    order_by: list
    limit: int | None

The Parser

PRECEDENCE = {
    "OR": 1,
    "AND": 2,
    "=": 3, "<>": 3, "!=": 3, "<": 3, ">": 3, "<=": 3, ">=": 3,
    "+": 4, "-": 4,
    "*": 5, "/": 5,
}
 
 
class Parser:
    def __init__(self, tokens: list[Token]):
        self.toks, self.i = tokens, 0
 
    def peek(self) -> Token:
        return self.toks[self.i]
 
    def advance(self) -> Token:
        tok = self.toks[self.i]
        self.i += 1
        return tok
 
    def accept(self, text: str) -> Token | None:
        if self.peek().text.upper() == text.upper():
            return self.advance()
        return None
 
    def expect(self, text: str) -> Token:
        tok = self.accept(text)
        if tok is None:
            raise SyntaxError(f"expected {text!r}, found {self.peek().text!r}")
        return tok
 
    # ── statement skeleton: recursive descent ─────────
    def parse_select(self) -> Select:
        self.expect("SELECT")
        targets = [self.parse_expr()]
        while self.accept(","):
            targets.append(self.parse_expr())
 
        self.expect("FROM")
        frm = self.parse_from()
 
        where = self.parse_expr() if self.accept("WHERE") else None
 
        group_by = []
        if self.accept("GROUP"):
            self.expect("BY")
            group_by.append(self.parse_expr())
            while self.accept(","):
                group_by.append(self.parse_expr())
 
        having = self.parse_expr() if self.accept("HAVING") else None
 
        order_by = []
        if self.accept("ORDER"):
            self.expect("BY")
            while True:
                expr = self.parse_expr()
                desc = self.accept("DESC") is not None
                if not desc:
                    self.accept("ASC")
                order_by.append(SortKey(expr, desc))
                if not self.accept(","):
                    break
 
        limit = int(self.advance().text) if self.accept("LIMIT") else None
        return Select(targets, frm, where, group_by, having, order_by, limit)
 
    def parse_from(self):
        node = self.parse_table_ref()
        while self.accept("JOIN"):
            right = self.parse_table_ref()
            self.expect("ON")
            node = JoinExpr(node, right, self.parse_expr())
        return node
 
    def parse_table_ref(self) -> TableRef:
        name = self.advance().text
        if self.accept("AS"):
            return TableRef(name, self.advance().text)
        if self.peek().kind == "IDENT":          # AS-less alias
            return TableRef(name, self.advance().text)
        return TableRef(name, None)
 
    # ── expressions: precedence climbing ──────────────
    def parse_expr(self, min_prec: int = 0):
        left = self.parse_primary()
        while True:
            op = self.peek().text.upper()
            prec = PRECEDENCE.get(op, -1)
            if prec < 0 or prec < min_prec:
                return left
            self.advance()
            # Left associative: the right operand may only absorb
            # operators that bind more tightly than this one.
            right = self.parse_expr(prec + 1)
            left = BinOp(op, left, right)
 
    def parse_primary(self):
        tok = self.advance()
        if tok.kind == "NUMBER":
            return Const(float(tok.text) if "." in tok.text else int(tok.text))
        if tok.kind == "STRING":
            return Const(tok.text[1:-1])
        if tok.kind == "IDENT":
            if self.peek().text == "(":         # an aggregate function call
                self.advance()
                if self.accept("*"):
                    self.expect(")")
                    return FuncCall(tok.text.upper(), [], star=True)
                args = [self.parse_expr()]
                while self.accept(","):
                    args.append(self.parse_expr())
                self.expect(")")
                return FuncCall(tok.text.upper(), args)
            if self.peek().text == ".":
                self.advance()
                return ColRef(tok.text, self.advance().text)
            return ColRef(None, tok.text)
        if tok.text == "(":
            inner = self.parse_expr()
            self.expect(")")
            return inner
        raise SyntaxError(f"unexpected token {tok.text!r}")

The + 1 in parse_expr(prec + 1) is what creates left associativity. When the parser reaches a - b - c, it parses the right operand of the first - with min_prec = 5, so the second - (precedence 4) is not absorbed and we get (a - b) - c. Write parse_expr(prec) instead and you get right associativity, a - (b - c), which changes the result. Right-associative operators such as exponentiation use exactly that form.

An AST Is Only What Was Written

What we have now is a syntax tree. Whether a table named users exists, whether it has a column age, whether the comparison age > 30 is well typed — none of that has been checked. SELECT nonexistent FROM nowhere parses without complaint.

Chapter 3: Binding — Attaching Names to Entities

Meaning is attached during binding (also called semantic analysis), the first stage that consults the catalog, i.e. the system tables.

The Catalog

@dataclass
class Column:
    name: str
    type: str            # "int" / "text" / "numeric"
 
@dataclass
class Relation:
    name: str
    columns: list[Column]
    n_rows: int          # analogous to pg_class.reltuples
    n_pages: int         # analogous to pg_class.relpages
    oid: int = 0         # pg_class.oid
    relfilenode: int = 0 # on-disk file name; changes on VACUUM FULL etc.
 
CATALOG = {
    "users": Relation(
        "users",
        [Column("id", "int"), Column("name", "text"), Column("age", "int")],
        n_rows=100_000, n_pages=1_000, oid=16384, relfilenode=16384,
    ),
    "orders": Relation(
        "orders",
        [Column("id", "int"), Column("user_id", "int"), Column("total", "numeric")],
        n_rows=1_000_000, n_pages=10_000, oid=16390, relfilenode=16390,
    ),
}

Range Tables and Vars

After binding, a column reference is a position, not a name: PostgreSQL's Var(varno, varattno). varno indexes the range table (the list of relations that appeared in FROM), and varattno is the column number.

@dataclass(frozen=True)
class Var:
    rel: int        # index into the range table
    attno: int      # column number (0-based here; PostgreSQL is 1-based)
    type: str
    label: str      # for display only; never used at run time
 
 
COMPARISONS = {"=", "<>", "!=", "<", ">", "<=", ">="}
NUMERIC_TYPES = {"int", "numeric"}
 
 
class Binder:
    def __init__(self, catalog):
        self.catalog = catalog
        self.range_table: list[tuple[str, Relation]] = []
 
    def collect_from(self, node) -> None:
        if isinstance(node, TableRef):
            if node.name not in self.catalog:
                raise NameError(f'relation "{node.name}" does not exist')
            rel = self.catalog[node.name]
            self.range_table.append((node.alias or node.name, rel))
        elif isinstance(node, JoinExpr):
            self.collect_from(node.left)
            self.collect_from(node.right)
        else:
            raise TypeError(node)
 
    def bind_expr(self, expr) -> tuple[object, str]:
        if isinstance(expr, Const):
            if isinstance(expr.value, bool):
                return expr, "bool"
            if isinstance(expr.value, int):
                return expr, "int"
            if isinstance(expr.value, float):
                return expr, "numeric"
            return expr, "text"
 
        if isinstance(expr, ColRef):
            hits = []
            for rel_idx, (alias, rel) in enumerate(self.range_table):
                if expr.table is not None and expr.table != alias:
                    continue
                for attno, col in enumerate(rel.columns):
                    if col.name == expr.column:
                        hits.append(Var(rel_idx, attno, col.type,
                                        f"{alias}.{col.name}"))
            if not hits:
                raise NameError(f'column "{expr.column}" does not exist')
            if len(hits) > 1:
                raise NameError(f'column reference "{expr.column}" is ambiguous')
            return hits[0], hits[0].type
 
        if isinstance(expr, BinOp):
            left, lt = self.bind_expr(expr.left)
            right, rt = self.bind_expr(expr.right)
 
            if expr.op in ("AND", "OR"):
                if (lt, rt) != ("bool", "bool"):
                    raise TypeError(f"argument of {expr.op} must be boolean")
                return BinOp(expr.op, left, right), "bool"
 
            if lt != rt and not {lt, rt} <= NUMERIC_TYPES:
                raise TypeError(
                    f"operator does not exist: {lt} {expr.op} {rt}")
 
            result = "bool" if expr.op in COMPARISONS else lt
            return BinOp(expr.op, left, right), result
 
        if isinstance(expr, FuncCall):
            args = [self.bind_expr(a) for a in expr.args]
            bound = FuncCall(expr.name, [a for a, _ in args], expr.star)
            if expr.name == "COUNT":
                return bound, "int"                # COUNT is always integral
            if not args:
                raise TypeError(f"{expr.name} requires an argument")
            arg_type = args[0][1]
            if expr.name == "AVG":
                return bound, "numeric"            # averaging integers yields a fraction
            if expr.name in ("SUM", "MIN", "MAX"):
                # exact for MIN/MAX; SUM is simplified — PostgreSQL widens
                # sum(int4) to int8 and sum(int8) to numeric to avoid overflow
                return bound, arg_type
            raise NameError(f'function "{expr.name}" does not exist')
 
        raise TypeError(f"cannot bind {expr!r}")

Only now can these errors be produced:

• column "ago" does not exist — no such column in the catalog
• column reference "id" is ambiguous — both relations have an id
• operator does not exist: text > integer — type mismatch

The line lt != rt and not {lt, rt} <= NUMERIC_TYPES compresses implicit casting into a single condition. Real PostgreSQL is far more elaborate: it collects every candidate operator from pg_operator and ranks them using the conversion rules in pg_cast. That machinery is what promotes the 100 in o.total > 100 to numeric.

Binding Normalizes Away Surface Differences

After binding, u.age and (when unambiguous) plain age both become the same Var(0, 2, "int"). Once the table is aliased as u, the name users is hidden, so users.age is an error in PostgreSQL and in the binder above. Every later optimization works on this normalized form, so it never has to care how the query was written.

Chapter 4: The Logical Plan — Dropping Into Relational Algebra

The bound AST becomes a tree of relational algebra operators. From here on SQL syntax is irrelevant; all that remains is which set operations to apply, in what order.

@dataclass
class Scan:
    rel: int
    relation: Relation
    alias: str
    predicate: object | None = None    # evaluated while scanning
 
@dataclass
class Filter:
    child: object
    predicate: object
 
@dataclass
class Join:
    left: object
    right: object
    predicate: object
 
@dataclass
class Project:
    child: object
    exprs: list
 
@dataclass
class Sort:
    child: object
    keys: list
 
@dataclass
class Aggregate:
    child: object
    group_keys: list
    aggs: list           # [FuncCall("COUNT", [], star=True), …]
 
@dataclass
class Limit:
    child: object
    n: int

The translation rules are direct.

Several familiar SQL rules follow from this table. WHERE becomes a node below Aggregate, and HAVING one above it. That is why HAVING may reference aggregates and WHERE may not: WHERE sits at a position where aggregated values do not exist yet.

Applying these rules naively to the running example gives this tree:

Limit(10)
└─ Sort(o.total DESC)
   └─ Project(u.name, o.total)
      └─ Filter(u.age > 30 AND o.total > 100)
         └─ Join(u.id = o.user_id)
            ├─ Scan(users AS u)
            └─ Scan(orders AS o)

The nesting order mirrors SQL's evaluation order (FROM → WHERE → SELECT → ORDER BY → LIMIT). Because SELECT sits above WHERE, an alias defined in the select list cannot be referenced in WHERE, a familiar SQL restriction that follows directly from this shape.

The tree returns the correct result, but slowly: it joins all 1,000,000 orders with all 100,000 users before filtering anything.

Chapter 5: Rewriting — Changing Shape Without Changing Meaning

Optimization starts with transformations that are clearly profitable without computing any cost. They come from the equivalence laws of relational algebra.

Predicate Pushdown

$\sigma_{p}(R \bowtie S) \equiv \sigma_{p}(R) \bowtie S \quad (\text{when } p \text{ references only columns of } R)$

Push selection below the join. Fewer rows reach the join, which is almost always a win.

The key implementation trick is to split AND into conjuncts and push each one separately. As one lump, u.age > 30 AND o.total > 100 references both tables, so it cannot go below the join at all; split apart, each half can be pushed to its own table.

def conjuncts(expr) -> list:
    """Flatten a chain of ANDs into a list."""
    if isinstance(expr, BinOp) and expr.op == "AND":
        return conjuncts(expr.left) + conjuncts(expr.right)
    return [expr]
 
 
def and_all(preds: list):
    if not preds:
        return None
    node = preds[0]
    for p in preds[1:]:
        node = BinOp("AND", node, p)
    return node
 
 
def used_rels(expr) -> set[int]:
    """The set of range-table indexes an expression references."""
    if isinstance(expr, Var):
        return {expr.rel}
    if isinstance(expr, BinOp):
        return used_rels(expr.left) | used_rels(expr.right)
    return set()
 
 
def rels_of(node) -> set[int]:
    if isinstance(node, Scan):
        return {node.rel}
    if isinstance(node, Join):
        return rels_of(node.left) | rels_of(node.right)
    return rels_of(node.child)
 
 
def push_down(node, preds: list):
    """Push predicates as deep as they can go.
       Returns (rewritten subtree, predicates that could not be pushed)."""
    if isinstance(node, Scan):
        mine, stays = [], []
        for p in preds:
            (mine if used_rels(p) <= {node.rel} else stays).append(p)
        node.predicate = and_all(mine)
        return node, stays
 
    if isinstance(node, Join):
        node.left, preds = push_down(node.left, preds)
        node.right, preds = push_down(node.right, preds)
        here, stays = [], []
        scope = rels_of(node)
        for p in preds:
            (here if used_rels(p) <= scope else stays).append(p)
        return (Filter(node, and_all(here)) if here else node), stays
 
    raise TypeError(node)

Splitting WHERE with conjuncts() and feeding it to push_down() gives:

Limit(10)
└─ Sort(o.total DESC)
   └─ Project(u.name, o.total)
      └─ Join(u.id = o.user_id)
         ├─ Scan(users)   filter: age > 30
         └─ Scan(orders)  filter: total > 100

The join now sees 55,000 × 100,000 rows instead of 100,000 × 1,000,000 (chapter 6 shows where these estimates come from).

OR Cannot Be Pushed

WHERE u.age > 30 OR o.total > 100 cannot be split. OR is true when either side is true, so evaluating one side alone changes the answer. In practice this form can only be evaluated after the join, and it is a common cause of slow queries. The usual fixes are to rewrite it as a UNION (so each branch can be optimized independently) or to avoid the OR in the schema design.

Other Rewrites

• Column pruning — drop columns that nothing above the node references. The savings are largest in columnar stores, which is one reason to avoid SELECT *.
• Constant folding — compute an expression of constants once at plan time, the way WHERE x = 2 + 2 becomes WHERE x = 4. Only immutable functions qualify. An expression with a stable function, such as now() - interval '7 days' (now() is constant within a statement), is not folded at plan time, because a reused plan (chapter 9) would keep a stale value; in an index scan condition it is evaluated once at execution start. Volatile functions such as random() cannot even be reduced to a single evaluation (function volatility categories).
• Transitive predicate closure — derive b.x = 10 from a.x = b.x AND a.x = 10 so the constant can also be pushed onto b.
• Subquery decorrelation — turn a correlated subquery into a join. This is often one of the highest-impact rewrites.

Transitive closure is short enough to show. In practice, "why does only one of my two tables use its index?" is very often a question about whether this rewrite fired.

def transitive_closure(preds: list) -> list:
    """Build equivalence classes from x = y, then copy constant
       predicates across every member of the class."""
    classes: list[set] = []                     # sets of Vars known to be equal
    for p in preds:
        if (isinstance(p, BinOp) and p.op == "="
                and isinstance(p.left, Var) and isinstance(p.right, Var)):
            merged = {p.left, p.right}
            rest = []
            for c in classes:                   # fuse overlapping classes
                (merged.update(c) if merged & c else rest.append(c))
            classes = rest + [merged]
 
    derived = []
    for p in preds:
        if isinstance(p, BinOp) and isinstance(p.left, Var) and isinstance(p.right, Const):
            for c in classes:
                if p.left in c:
                    derived += [BinOp(p.op, v, p.right) for v in c if v != p.left]
    return preds + derived

Applied to a.x = b.x AND a.x = 10, this produces b.x = 10, which push_down() can then sink all the way to the scan of b. PostgreSQL calls this machinery equivalence classes, implemented in equivclass.c.

An example of decorrelation:

-- Correlated: naively evaluated once per outer row
SELECT u.name FROM users u
WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id AND o.total > 100);
 
-- Rewritten as a semi join: one hash table, built once
SELECT u.name FROM users u
SEMI JOIN orders o ON o.user_id = u.id AND o.total > 100;

SEMI JOIN is not valid SQL syntax, but it is a real operator inside the planner. It is what EXPLAIN shows as Hash Semi Join.

What Breaks Rewriting: Three-Valued Logic and Outer Joins

Everything above quietly assumed two things: that a predicate is either true or false, and that joins commute. SQL guarantees neither in general.

The first problem is NULL and three-valued logic. SQL has three truth values: TRUE, FALSE, and UNKNOWN. NULL > 30 is not FALSE; it is UNKNOWN.

AND    | T | F | U          OR     | T | F | U
-------+---+---+---        -------+---+---+---
   T   | T | F | U             T   | T | T | T
   F   | F | F | F             F   | T | F | U
   U   | U | F | U             U   | T | U | U

Two consequences matter in practice.

1. WHERE keeps a row only when the predicate is TRUE; UNKNOWN is discarded. So a predicate test should really read if pred(row) is True, and that is how it is spelled once chapter 15 rewires the scan to real storage.
2. CHECK constraints do the opposite and treat UNKNOWN as passing. The same expression flips its NULL behavior depending on where it is written.

This is also why NOT IN (… a list containing NULL) always returns nothing. x NOT IN (1, NULL) means x <> 1 AND x <> NULL, and the right conjunct is permanently UNKNOWN, so the whole thing can never be TRUE. Consequently the planner cannot safely convert NOT IN into an anti join, which is why it tends to be slower than NOT EXISTS.

The second problem is outer joins. Predicate pushdown is only unconditionally valid for inner joins.

-- Original: users with no orders survive the join
SELECT u.name, o.total
FROM users u LEFT JOIN orders o ON u.id = o.user_id
WHERE o.total > 100;          -- ← discards the NULL-extended side anyway
 
-- This predicate cannot be moved out of the join into WHERE
SELECT u.name, o.total
FROM users u LEFT JOIN orders o ON u.id = o.user_id AND o.total > 100;

In the first query o.total > 100 rejects NULLs, so the planner performs join strength reduction, turning the outer join into an inner join and regaining full freedom to reorder. In the second the predicate lives in the ON clause, so it does not reject NULL-extended rows. The join must stay an outer join, and the predicate cannot be moved out of the join into a filter on its result: that would drop users who have no matching order instead of NULL-extending them. Since it references only orders, it can still be applied to the orders scan before the join.

Outer joins also restrict join-order freedom: $(A \mathbin{⟕} B) \bowtie C$ and $A \mathbin{⟕} (B \bowtie C)$ generally differ. Chapter 8's dynamic program relies on the inner-join property that every split of a subset yields the same result, so it cannot be applied unchanged once outer joins appear. Representing joins as hyperedges instead of graph edges ("these relations must all be present before this join may run") is the idea behind DPhyp, which we meet in chapter 8.

Chapter 6: Statistics and Cardinality Estimation

The optimizer proper begins here, with the most fragile part of query optimization.

Comparing costs requires knowing how many rows each operator produces. That number is unknowable before execution, so it is estimated from statistics.

Histograms

ANALYZE samples a table and records the following in pg_statistic:

• Most common values (MCVs) and their frequencies — used for equality selectivity
• Equi-depth histogram bounds — used for range selectivity
• n_distinct — the number of distinct values (negative values express a fraction of the row count)
• Correlation — how closely the column order matches physical order, which drives random-I/O estimates for index scans

An equi-depth histogram places boundaries so that every bucket holds the same number of rows. Narrow buckets mean dense regions of the value distribution.

@dataclass
class ColumnStats:
    n_distinct: int
    bounds: list         # equi-depth boundaries: len(bounds) - 1 buckets
 
 
def selectivity_gt(stats: ColumnStats, value) -> float:
    """Selectivity of col > value, assuming uniformity inside each bucket."""
    bounds = stats.bounds
    nb = len(bounds) - 1                     # number of buckets
    if value < bounds[0]:
        return 1.0
    if value >= bounds[-1]:
        return 0.0
    for i in range(nb):
        lo, hi = bounds[i], bounds[i + 1]
        if lo <= value < hi:
            above_in_bucket = (hi - value) / (hi - lo)
            return (nb - i - 1) / nb + above_in_bucket / nb
    return 0.0

Suppose the deciles of users.age are:

age_stats = ColumnStats(
    n_distinct=63,
    bounds=[18, 22, 25, 27, 29, 31, 34, 38, 44, 53, 80],
)
selectivity_gt(age_stats, 30)     # → 0.55

Following the arithmetic: 30 lands in bucket 4, [29, 31). Buckets 5 through 9 are entirely above it, contributing $5/10 = 0.5$. Within bucket 4, $(31-30)/(31-29) = 0.5$ lies above, contributing $0.5 \times 0.1 = 0.05$. Total: $0.55$, or 55,000 rows.

Join Cardinality

The textbook estimate for an equi-join is the following, where $\mathrm{NDV}$ is the number of distinct values (the n_distinct seen above).

$|R \bowtie_{R.a = S.b} S| \approx \frac{|R| \cdot |S|}{\max(\mathrm{NDV}(R.a), \mathrm{NDV}(S.b))}$

def join_cardinality(left_rows, right_rows, ndv_left, ndv_right) -> float:
    """Equi-join estimate under the containment assumption: every value on the
       side with fewer distinct values also occurs on the other side."""
    return left_rows * right_rows / max(ndv_left, ndv_right)

With 55,000 users rows (after filtering), 100,000 orders rows (assuming 10% of orders pass total > 100), and NDV(users.id) = NDV(orders.user_id) = 100,000:

$\frac{55{,}000 \times 100{,}000}{100{,}000} = 55{,}000$

When Estimation Breaks

Three strong assumptions underpin all of this:

1. Uniformity — values are uniformly distributed inside each histogram bucket
2. Independence — selectivities of separate predicates are independent and can be multiplied
3. Containment — one join key's value domain is contained in the other's

None of them hold in practice, and independence fails most easily. Take WHERE city = 'Yokohama' AND prefecture = 'Kanagawa', where 1% of rows are in Yokohama and 5% are in Kanagawa. Assuming independence gives a selectivity of $0.01 \times 0.05 = 0.0005$, but the true value is $0.01$, because Yokohama determines the prefecture. That is a 20× underestimate.

The error also multiplies with every join level.

Leis et al., "How Good Are Query Optimizers, Really?" (PVLDB 9(3), 2015), compared the intermediate-result estimates of PostgreSQL 9.4, the research system HyPer and three commercial systems with the true cardinalities, using the 113 multi-join queries of their Join Order Benchmark over the real-world IMDB data set. All five systems routinely produced estimates off by a factor of 1,000 or more, and the errors grew exponentially with the number of joins. For PostgreSQL, 16% of the estimates for one join were off by a factor of 10 or more; the share rose to 32% with two joins and 52% with three. Their central conclusion is that cardinality estimation accuracy matters far more to final plan quality than cost model accuracy does.

Mitigations include:

• Multivariate statistics — collect statistics over correlated column groups. PostgreSQL offers CREATE STATISTICS (dependencies, ndistinct, mcv).
• Adaptive query execution — observe actual row counts at run time and switch plans. Oracle Adaptive Plans, SQL Server Adaptive Joins, Spark AQE.
• Learned estimators — train a model on execution history. Still mostly research, but reaching production.

Chapter 7: The Cost Model — What Actually Gets Counted

With row counts estimated, the planner can compute costs. A cost has no time unit; it is a dimensionless relative number that answers "if reading one page sequentially is 1.0, how much is everything else?"

import math
 
SEQ_PAGE_COST        = 1.0      # read one page sequentially
RANDOM_PAGE_COST     = 4.0      # read one page randomly
CPU_TUPLE_COST       = 0.01     # process one tuple
CPU_INDEX_TUPLE_COST = 0.005    # process one index entry
CPU_OPERATOR_COST    = 0.0025   # evaluate one operator or function

random_page_cost = 4.0 does not mean PostgreSQL believes a physical random read is only four times a sequential read. The documentation explicitly says the default is lower than raw hardware ratios because the majority of random reads, such as indexed reads, are assumed to be cached. On SSD-heavy or fully cached workloads, a common tuning step is to lower random_page_cost to match measurements, often to 1.1–2, and to set it equal to seq_page_cost only when random access is effectively no worse. That single constant moves the break-even point between index scans and sequential scans.

Scan Costs

def seq_scan_cost(rel: Relation, n_quals: int) -> float:
    """Read every block in order and evaluate n_quals conditions per tuple."""
    return (rel.n_pages * SEQ_PAGE_COST
            + rel.n_rows * CPU_TUPLE_COST
            + rel.n_rows * n_quals * CPU_OPERATOR_COST)

seq_scan_cost(CATALOG["users"],  1)   # 1,000 + 1,000 +   250 =  2,250
seq_scan_cost(CATALOG["orders"], 1)   # 10,000 + 10,000 + 2,500 = 22,500

This formula does not depend on selectivity: returning one row still costs a full scan. An index scan, by contrast, costs roughly in proportion to selectivity. Where those two lines cross is where the plan flips.

The Cost of an Index Scan

Now the other line. Fetching $n$ rows through an index looks like $n$ random reads, but several rows share a page, so it costs less. The more rows you fetch, the higher the chance the next one lands on a page you have already read.

Mackert and Lohman quantified this in 1989, and PostgreSQL uses their formula verbatim.

def index_pages_fetched(tuples_fetched, pages, index_pages,
                        total_table_pages, effective_cache_size=524_288):
    """Mackert-Lohman: pages actually fetched given a finite buffer.
       effective_cache_size defaults to 4 GB = 524,288 pages."""
    T = float(pages) if pages > 1 else 1.0
    # Every table in the query plus this index competes for cache;
    # pro-rate by this table's share
    total_pages = max(total_table_pages + index_pages, 1.0)
    b = max(1.0, math.ceil(effective_cache_size * T / total_pages))
 
    if T <= b:                                  # the table fits in cache
        pf = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched)
        return T if pf >= T else math.ceil(pf)
 
    lim = (2.0 * T * b) / (2.0 * T - b)         # where re-reads start
    if tuples_fetched <= lim:
        return math.ceil((2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched))
    return math.ceil(b + (tuples_fetched - lim) * (T - b) / T)

Fetch 5,000 rows from users (1,000 pages / 100,000 rows):

$\mathrm{PF} = \frac{2 \times 1{,}000 \times 5{,}000}{2 \times 1{,}000 + 5{,}000} = 1{,}428.6 \;\longrightarrow\; \text{clamped to } T = 1{,}000$

The estimate is at most one table's worth of pages, not 5,000 random reads. The "one page per row" intuition breaks down as row counts grow.

Correlation — The Same Index, 75× Apart

The other factor is the correlation between index order and the physical order of the heap (the file that stores the table's rows). PostgreSQL computes two endpoints and interpolates between them.

def index_scan_cost(rel, index_pages, selectivity, correlation=0.0,
                    random_page_cost=RANDOM_PAGE_COST, total_table_pages=11_000):
    tuples = rel.n_rows * selectivity
 
    # Index side: read the matching entries
    idx_pages = math.ceil(selectivity * index_pages)
    idx_cost = (idx_pages * random_page_cost
                + tuples * (CPU_INDEX_TUPLE_COST + CPU_OPERATOR_COST))
 
    # Heap side: interpolate the two endpoints by correlation squared
    pf = index_pages_fetched(tuples, rel.n_pages, index_pages, total_table_pages)
    max_io = pf * random_page_cost                       # correlation = 0
    seq_pages = math.ceil(selectivity * rel.n_pages)
    min_io = random_page_cost + max(seq_pages - 1, 0) * SEQ_PAGE_COST  # = 1
    heap_cost = max_io + correlation ** 2 * (min_io - max_io)
 
    return idx_cost + heap_cost + tuples * CPU_TUPLE_COST

Holding selectivity at 5% (5,000 rows) and varying only correlation:

Same index, same row count, a 75× difference from correlation alone. The benefit of CLUSTER, or of time-series data whose insertion order happens to be ascending, reaches the cost model through this one interpolation.

There is no rigorous derivation for using the square of the correlation as the weight. costsize.c says so itself:

We currently interpolate linearly between the estimates based on the correlation squared (XXX is that appropriate?).

Production cost models contain acknowledged guesswork.

Finding the Crossover

Take the users(age) index at 275 pages, correlation 0, and compare against the Seq Scan cost of 2,250.

The crossover sits around 0.8% with the HDD-era random_page_cost = 4.0. Drop it to the SSD-oriented 1.1 and, for the same table and the same index, the crossover climbs into the tens of percent. Once random reads are cheap, the Mackert–Lohman clamp means the index scan's I/O stops growing, while the Seq Scan keeps paying CPU cost for every row in the table.

(This model omits index descent cost and B+ tree height, so real PostgreSQL crosses over at a lower selectivity. The exact number matters less than the fact that one constant moves the boundary by orders of magnitude.)

Join Costs

How to read a single table is settled. The next question is how to match two inputs against each other, and every join algorithm gets its own formula.

@dataclass
class Plan:
    rows: float
    cost: float
    desc: str
 
 
def hash_join_cost(build: Plan, probe: Plan, out_rows: float) -> float:
    return (build.cost + probe.cost
            + build.rows * CPU_OPERATOR_COST     # building the hash table
            + probe.rows * CPU_OPERATOR_COST     # probing it
            + out_rows   * CPU_TUPLE_COST)       # producing output tuples
 
 
def sort_cost(input_cost: float, rows: float, limit: int | None = None) -> float:
    """Following PostgreSQL, one comparison costs 2 * cpu_operator_cost.
       A LIMIT turns this into a bounded heap, shrinking the logarithm."""
    comparison_cost = 2.0 * CPU_OPERATOR_COST
    keep = rows if limit is None else min(rows, limit)
    return input_cost + comparison_cost * rows * math.log2(max(keep, 2.0))
 
 
def merge_join_cost(left: Plan, right: Plan, out_rows: float) -> float:
    ls = sort_cost(left.cost, left.rows)
    rs = sort_cost(right.cost, right.rows)
    return (ls + rs
            + (left.rows + right.rows) * CPU_OPERATOR_COST
            + out_rows * CPU_TUPLE_COST)

(The bounded branch of sort_cost is simplified: PostgreSQL's cost_tuplesort uses $N \log_2 2K$ for a top-N heapsort. It is a constant-factor difference that does not change any ranking in this article, but keep it in mind when comparing these numbers against real EXPLAIN output.)

Three candidates for the join in the running example:

The 48.175 in the nested-loop row is the cost of one inner index lookup. Each user has about 10 orders, so we read 2 index pages and 10 heap pages randomly, plus CPU cost $10 \times (0.005 + 0.01 + 0.0025)$. That is $12 \times 4.0 + 0.175 = 48.175$, repeated 55,000 times, which puts it far above the other two candidates.

But make the outer side a single row (WHERE u.id = 42) and the same nested loop becomes the fastest option. No join algorithm is universally better; the ranking flips with row counts. That is why cost-based optimization is needed.

Choosing the Build Side

hash_join_cost looks symmetric in build and probe, but the build side should be the smaller one. The hash table has to fit in memory (work_mem in PostgreSQL). If it does not, execution degrades to a grace hash join, which partitions both sides by hash value, spills the partitions to temporary files, and processes them one at a time, adding I/O. The planner folds this in by increasing the batch count when the estimated build size exceeds work_mem.

Startup Cost and Total Cost

Cost has been one scalar so far, but EXPLAIN prints this:

Hash Join  (cost=2387.50..25687.50 rows=55000 width=36)

There are two numbers. The first is the startup cost: what must be paid before the first row can be returned. The second is the total cost: everything, through the last row.

They are tracked separately because a parent node does not always need every row. The cost of a partial retrieval follows from a formula written at the top of costsize.c:

@dataclass
class CostedPlan:
    rows: float
    startup_cost: float
    total_cost: float
 
 
def cost_for(plan: CostedPlan, tuples_to_fetch: float) -> float:
    """Cost of a partial retrieval. Startup is paid regardless, so it is not pro-rated."""
    frac = min(tuples_to_fetch, plan.rows) / plan.rows
    return plan.startup_cost + (plan.total_cost - plan.startup_cost) * frac

"Blocking" Means "High Startup Cost"

A hash join's startup cost includes the entire total cost of the build side, because no row can be emitted until the hash table is finished. An operator with that property (nothing comes out until the input has been drained) is called blocking; chapter 10 implements a few.

def hash_join_startup(build: Plan) -> float:
    """Startup runs until the build side is drained and hashed."""
    return build.cost + build.rows * CPU_OPERATOR_COST

For the hash join in the running example that is $2{,}250 + 55{,}000 \times 0.0025 = 2{,}387.5$, against a total of $25{,}687.5$. This pair of numbers is how the planner represents "blocking."

(PostgreSQL's initial_cost_hashjoin also charges cpu_tuple_cost per build row, giving $2{,}250 + 55{,}000 \times (0.0025 + 0.01) = 2{,}937.5$. We stay consistent with this chapter's simplified model here.)

Add a LIMIT and the Ranking Inverts

Chapter 9 will claim that LIMIT changes the algorithm chosen below it. These two numbers are enough to check that claim.

For all rows the hash join (25,688) beats the nested loop (2,651,875) by more than 100×. Ask for ten rows and the ranking flips, because the nested loop has essentially zero startup cost and only has to read as many outer rows as it needs.

The same arithmetic explains the classic incident "adding LIMIT 10 made the query 1,000× slower." The planner assumes ten outer rows will yield ten results and picks the zero-startup nested loop; if matching rows are actually rare, execution scans the outer side to the end. Cardinality misestimates are never more punishing than under a LIMIT.

Cursors (DECLARE … CURSOR) always use this partial-retrieval costing. Following cursor_tuple_fraction (default 0.1), they are planned as if only 10% of rows will be fetched, which is why the same SQL can get a different plan through a cursor.

Chapter 8: Join Order — Fighting the Search Space

With three or more relations, the order of joins matters more than the algorithm chosen for each one.

How Big Is the Space?

For $n$ relations there are $n!$ left-deep trees, and $\frac{(2n-2)!}{(n-1)!}$ bushy trees.

Exhaustive enumeration is impossible, but optimal substructure saves us. If a plan uses the join of $\{A, B, C\}$ as an intermediate result, the subtree that produces it can be replaced by the best plan for $\{A, B, C\}$ alone without making the whole plan worse (given a monotone cost function). So one best plan per subset suffices, and the state count collapses to $2^n$. That is the dynamic program System R introduced in 1979.

def dp_join_order(rels, cardinality, connected):
    """Fix the optimal plan for every subset, smallest first (DPsize)."""
    n = len(rels)
    best = {}
    for i in range(n):
        best[1 << i] = Plan(rows=rels[i].n_rows, cost=0.0, desc=rels[i].name)
 
    for size in range(2, n + 1):
        for mask in range(1, 1 << n):
            if bin(mask).count("1") != size:
                continue
            if not connected(mask):          # prune Cartesian products
                continue
            rows = cardinality(mask)
            for right in submasks(mask):     # enumerate proper subsets
                left = mask ^ right
                if left == 0 or right == 0:
                    continue
                if left not in best or right not in best:
                    continue
                if not has_join_edge(left, right):
                    continue
                cost = rows + best[left].cost + best[right].cost   # C_out
                if mask not in best or cost < best[mask].cost:
                    best[mask] = Plan(rows, cost,
                                      f"({best[left].desc} ⋈ {best[right].desc})")
    return best[(1 << n) - 1]
 
 
def submasks(mask: int):
    """The classic idiom for enumerating all non-empty proper submasks."""
    sub = (mask - 1) & mask
    while sub > 0:
        yield sub
        sub = (sub - 1) & mask

The submasks idiom (sub - 1) & mask walks the submasks of mask in descending order, and enumerating all submasks of all subsets is $O(3^n)$.

The cost function here is C_out, the sum of intermediate result sizes. It ignores scan and algorithm costs, yet it captures most of what makes one join order better than another.

The demo below runs it on a four-table join of users (u), orders (o), order_items (i), and products (p), with products filtered down to 10 rows.

The order as written, $((u \bowtie o) \bowtie i) \bowtie p$, costs 605,000; the optimal $((i \bowtie p) \bowtie o) \bowtie u$ costs 15,000, roughly 40× cheaper. The intuition "start from the most selective relation" turns out to have a precise cost-based justification.

Pruning Cartesian Products

The connected(mask) check inside the loop does much of the work. A subset that no join predicate connects can only be produced by a Cartesian product, which explodes row counts, so skipping such subsets shrinks the search space enormously. For a chain-shaped join graph, the candidate count drops to $O(n^3)$.

Pruning too aggressively has a cost, though. When one relation is tiny (a dimension table, say), the Cartesian product is sometimes genuinely faster. Many implementations allow cross products only as a fallback, when no connected subset can be formed.

When n Gets Large

PostgreSQL abandons dynamic programming once the number of relations being joined reaches geqo_threshold (default 12) and switches to a genetic algorithm (GEQO). Optimality is no longer guaranteed, but planning time stays bounded.

In practice, though, join_collapse_limit (default 8) bites first. Beyond eight relations written with explicit JOIN syntax, the planner stops flattening the FROM clause and keeps the written order. If you reproduce this chapter's DP on a real ten-table explicit-join query and nothing gets reordered, suspect this setting first. (Subquery flattening has its own knob, from_collapse_limit.)

Conversely, setting join_collapse_limit = 1 prevents any reordering of explicit JOINs, which is the standard way to pin a join order by hand, the last resort when the estimates cannot be fixed.

Other systems and papers take different approaches:

• DPccp / DPhyp (Moerkotte & Neumann) — enumerate only connected subgraphs of the join graph, never constructing useless subsets. DPccp, for simple join graphs, is the VLDB 2006 paper; DPhyp, which generalizes it to hypergraphs (outer joins and complex predicates), is "Dynamic Programming Strikes Back", SIGMOD 2008. Used by DuckDB and HyPer.
• Cascades / Volcano framework (Graefe) — top-down search driven by transformation rules and a memo structure. SQL Server, Apache Calcite, and CockroachDB follow this lineage. Unlike bottom-up DP, it can extend the search space just by adding rules.
• Interesting orders — treat sort order as part of the state. A sorted intermediate result can be reused by a later merge join or ORDER BY, so a locally more expensive plan can win globally. The idea already appears in the System R paper.

Chapter 9: The Physical Plan — Committing to Algorithms

Each logical operator maps to several physical ones.

The final physical plan:

Limit(10)                              rows=10       cost≈26,601
└─ Sort(o.total DESC) top-N heapsort   rows=10       cost≈26,601
   └─ HashJoin(u.id = o.user_id)       rows=55,000   cost≈25,688
      ├─ SeqScan(orders)               rows=100,000  cost≈22,500   [probe]
      │    Filter: total > 100
      └─ Hash                          rows=55,000
         └─ SeqScan(users)             rows=55,000   cost≈2,250    [build]
              Filter: age > 30

Sort became a top-N heapsort because of LIMIT 10. Sorting all 55,000 rows costs $0.005 \times 55{,}000 \times \log_2 55{,}000 \approx 4{,}330$; keeping a 10-element heap costs $0.005 \times 55{,}000 \times \log_2 10 \approx 914$. Memory drops from $O(n)$ to $O(10)$ as well.

In physical optimization, a parent node's requirement often changes the algorithm chosen below it. LIMIT pushes down "how many rows are needed"; ORDER BY pushes down "in what order."

Properties that constrain how a result is produced without changing what is computed are called physical properties. The canonical examples are sort order (PostgreSQL's PathKey) and data distribution (partitioning, in a distributed engine). Cascades-style optimizers make them part of the search state, remembering "the cheapest plan for this subset in this sort order" separately for each order. Chapter 8's interesting orders are the ancestor of that idea.

Reusing Plans — Prepared Statements and Generic Plans

Everything from chapter 1 to here is expensive. An application firing the same query thousands of times per second should not re-lex it every time, so implementations cache plans.

That introduces a trade-off. Caching a parameterized query means building a plan without knowing the parameter values, and chapter 6's selectivity_gt cannot compute anything without a value.

DEFAULT_INEQ_SEL = 0.3333333333333333    # selfuncs.h
DEFAULT_EQ_SEL   = 0.005
UNKNOWN = object()                       # an unbound parameter
 
 
def selectivity_gt(stats: ColumnStats, value) -> float:
    if value is UNKNOWN:
        return DEFAULT_INEQ_SEL          # no histogram lookup possible
    ...                                  # otherwise, as in chapter 6

Evaluating WHERE u.age > $1 against the very same histogram:

The generic plan is built for 33,333 rows: too small for $1 = 30, too large for $1 = 79.

PostgreSQL compromises by trying custom plans first. choose_custom_plan() in plancache.c:

1. always builds a custom plan for the first five executions
2. compares their average estimated cost against the one generic plan
3. keeps the generic plan thereafter if it is cheaper (and skips planning entirely)

This explains the pattern "it was fast for the first few calls and then suddenly 100× slower." To force one kind of plan, set plan_cache_mode to force_custom_plan or force_generic_plan.

Avoiding parameters is not a free escape. Interpolating values into the SQL string every time lets the planner estimate with the real values, but it defeats plan caching entirely and opens the door to SQL injection. Estimation accuracy and plan reuse are in tension by construction.

Chapter 10: The Execution Engine — The Volcano Iterator Model

The plan exists. Time to run it.

The Volcano model that Goetz Graefe introduced in 1990 (also called the iterator model, or pull-based execution) gives every operator the same three methods.

class Operator:
    def open(self) -> None: ...          # initialize state
    def next(self) -> dict | None: ...   # return one tuple, or None when done
    def close(self) -> None: ...         # release resources

The uniform interface is the model's main strength: any operator stacks on top of any other, so the planner is free to choose the shape of the tree.

Implementation

class SeqScanExec:
    def __init__(self, rows, predicate=None):
        self.rows, self.predicate = rows, predicate
        self.cursor = 0
 
    def open(self):
        self.cursor = 0
 
    def next(self):
        while self.cursor < len(self.rows):
            row = self.rows[self.cursor]
            self.cursor += 1
            if self.predicate is None or self.predicate(row):
                return row
        return None
 
    def close(self):
        pass
 
 
class NestedLoopJoinExec:
    def __init__(self, outer, inner, predicate):
        self.outer, self.inner, self.predicate = outer, inner, predicate
        self.outer_tuple = None
 
    def open(self):
        self.outer.open()
        self.inner.open()
        self.outer_tuple = None
 
    def next(self):
        while True:
            if self.outer_tuple is None:
                self.outer_tuple = self.outer.next()
                if self.outer_tuple is None:
                    return None
                self.inner.open()          # rewind the inner side (rescan)
            inner_tuple = self.inner.next()
            if inner_tuple is None:
                self.outer_tuple = None    # inner exhausted; advance the outer
                continue
            if self.predicate(self.outer_tuple, inner_tuple):
                return {**self.outer_tuple, **inner_tuple}
 
    def close(self):
        self.outer.close()
        self.inner.close()

The demo below follows the call chain one event at a time: next() descending from root to leaves, and tuples climbing back from leaves to root.

Blocking Operators

Not every operator can return one tuple at a time. Sort cannot return its first row until it has seen the last one. HashJoin cannot probe until the build side is fully consumed. These are the blocking operators (also called pipeline breakers) that chapter 7 met from the cost side, where their startup cost included the whole cost of the input they drain first. Here is what they look like as code.

from collections import defaultdict
 
class HashJoinExec:
    def __init__(self, build, probe, build_key, probe_key):
        self.build, self.probe = build, probe
        self.build_key, self.probe_key = build_key, probe_key
 
    def open(self):
        # ── build phase: drain the build side completely (blocking)
        self.build.open()
        self.table = defaultdict(list)
        while (row := self.build.next()) is not None:
            self.table[self.build_key(row)].append(row)
        self.build.close()
 
        # ── prepare the probe phase
        self.probe.open()
        self.matches = iter(())
        self.current = None
 
    def next(self):
        while True:
            m = next(self.matches, None)
            if m is not None:
                return {**m, **self.current}
            self.current = self.probe.next()
            if self.current is None:
                return None
            self.matches = iter(self.table.get(self.probe_key(self.current), ()))
 
    def close(self):
        self.probe.close()
        self.table = None

Where blocking operators sit determines how much a query has to read before it returns its first row. LIMIT 10 still reads every row when an ORDER BY is present, because Sort blocks. Without ORDER BY, LIMIT 10 stops calling next() after ten rows.

The Top-N Heap

ORDER BY … LIMIT n can be done with a heap of size $n$ instead of a full sort.

import heapq
import itertools
 
class TopNExec:
    def __init__(self, child, key, n, desc=True):
        self.child, self.key, self.n, self.desc = child, key, n, desc
 
    def open(self):
        self.child.open()
        heap = []                       # min-heap of (sort key, seq, row)
        seq = itertools.count()
        while (row := self.child.next()) is not None:
            k = self.key(row)
            if not self.desc:
                k = -k                  # flip the sign for ASC
            if len(heap) < self.n:
                heapq.heappush(heap, (k, next(seq), row))
            elif k > heap[0][0]:        # only replace the current worst
                heapq.heapreplace(heap, (k, next(seq), row))
        heap.sort(key=lambda x: x[0], reverse=True)
        self.out = iter([row for _, _, row in heap])
 
    def next(self):
        return next(self.out, None)
 
    def close(self):
        self.out = None

The next(seq) counter in the second tuple position prevents Python from falling through to comparing the row dictionaries on key ties, which would raise TypeError. It is the standard defensive idiom when using heapq with non-comparable payloads.

Expression Evaluation Does Not Walk a Tree

Every operator so far has treated predicate(row) as a plain Python function. Real implementations put one more layer here.

The obvious approach is to walk the bound expression tree recursively, once per row. Because the shape of that tree never changes at run time, PostgreSQL instead compiles it once at executor-init time, into a flat array of steps, and afterwards just runs a for loop over that array. That is what ExprState and the EEOP_* steps are.

Filter: (total > 100 AND user_id = 42) becomes roughly this:

 0  EEOP_SCAN_FETCHSOME       last_var=3     # deform only up to the highest attnum used
 1  EEOP_SCAN_VAR             attnum=3       # total
 2  EEOP_CONST                value=100
 3  EEOP_FUNCEXPR_STRICT      numeric_gt     # skip the call entirely if an arg is NULL
 4  EEOP_QUAL                 jumpdone=9     # FALSE and NULL both fail immediately
 5  EEOP_SCAN_VAR             attnum=2       # user_id
 6  EEOP_CONST                value=42
 7  EEOP_FUNCEXPR_STRICT      int4eq
 8  EEOP_QUAL                 jumpdone=9
 9  EEOP_DONE

(Opcode names move between releases. The listing uses the names through PostgreSQL 17; in 18 EEOP_DONE was split into EEOP_DONE_RETURN / EEOP_DONE_NO_RETURN, and two-argument strict functions became EEOP_FUNCEXPR_STRICT_2. Also, attnum is stored zero-based in the step struct (varattno - 1); only last_var is a real 1-based attribute number. The shape is what matters.)

Three things this article has discussed elsewhere are embedded in that array, in machine form.

The last_var on EEOP_SCAN_FETCHSOME limits chapter 15's deform_tuple, which this step invokes, to the highest attribute number the expression references. Columns can only be extracted front to back, so if nothing beyond attnum 3 is used, attribute 4 onwards is never touched. That is one reason SELECT * on a 40-column table is slower than naming three columns: the executor pays for the longer loop before a single byte reaches the network (per-column output-function calls and transfer volume then pile on top of it).

The _STRICT suffix is chapter 5's three-valued logic, made mechanical. A strict function returns NULL whenever an argument is NULL, so the step short-circuits to NULL without calling the function at all.

EEOP_QUAL turns the rule "WHERE only passes TRUE" into an instruction. Whether the previous result was FALSE or NULL, it jumps to the end and fails the row. An AND written inside an expression uses EEOP_BOOL_AND_STEP_* instead. That one must distinguish FALSE from UNKNOWN, so it threads an anynull flag through the steps: FIRST clears the flag, the middle steps set it on NULL and bail out early on FALSE, and LAST turns "no FALSE but at least one NULL" into NULL. Splitting those roles across three opcodes (FIRST / middle / LAST) instead of branching at run time is a deliberate performance special case.

This flat array is also what PostgreSQL's JIT compiles: an interpreter loop with an indirect branch per step becomes straight-line native code. When chapter 12 says PostgreSQL's JIT targets expression evaluation and tuple deforming, this array is what it means.

Chapter 11: When Memory Runs Out — External Sort and Hash Aggregation

Every operator in the previous chapter assumed its intermediate results fit in memory. When they do not, the two canonical cases, sorting and aggregation, fail in completely different ways.

External Merge Sort

Chapter 7 introduced work_mem as the line a hash table has to stay under. For sorting, crossing that line looks like this:

def sort_external(rows, key, work_mem_rows, tmp):
    """Run generation, then merge. The skeleton of tuplesort.c."""
    runs, buf = [], []
    for row in rows:
        buf.append(row)
        if len(buf) == work_mem_rows:      # work_mem is exhausted
            buf.sort(key=key)
            runs.append(tmp.spill(buf))    # write the sorted chunk to a temp file
            buf = []
    if buf:
        buf.sort(key=key)
        runs.append(tmp.spill(buf))
 
    # Keep one row per run in a heap; pop the smallest and refill from that run
    return heapq.merge(*(tmp.read(r) for r in runs), key=key)

One merge pass would suffice if every run could be merged at once, but each run being merged (a "tape" in PostgreSQL's code) needs its own read buffer. PostgreSQL budgets 32 blocks (MERGE_BUFFER_SIZE = 256 KB) plus per-tape overhead for each one, so at work_mem = 4MB roughly 15 runs can be merged simultaneously (tuplesort_merge_order()). More runs than that require additional merge passes.

$\text{passes} = \lceil \log_M r \rceil \qquad (r = \text{runs},\; M = \text{merge order})$

PostgreSQL's cost_tuplesort writes exactly that:

$\text{startup} = c\,N \log_2 N \;+\; 2\,\text{npages} \cdot \lceil \log_M r \rceil \times (0.75\,c_{\text{seq}} + 0.25\,c_{\text{rand}})$

The comment on that last weighting admits it is a guess:

The disk traffic is assumed to be 3/4ths sequential and 1/4th random accesses (XXX can't we refine that guess?)

Two sizes, assuming 60 bytes per row:

• 55,000 rows ≈ 3.3 MB — fits the default 4 MB work_mem, so it is an in-memory quicksort and touches no disk at all.
• 5,500,000 rows ≈ 330 MB — $r \approx 330{,}000{,}000 / (4 \times 1{,}048{,}576) \approx 79$ runs and $M \approx 15$, so $\lceil \log_{15} 79 \rceil = 2$ passes.
  • $\text{npages} = \lceil 330{,}000{,}000 / 8192 \rceil = 40{,}284$
  • $\text{npageaccesses} = 2 \times 40{,}284 \times 2 = 161{,}136$
  • disk $= 161{,}136 \times 1.75 \approx 282{,}000$
  • CPU $= 0.005 \times 5{,}500{,}000 \times \log_2 5{,}500{,}000 \approx 616{,}000$

So in this cost model, spilling to disk adds only about 46% on top of the comparison cost. Sorting degrades gracefully past work_mem. Hashing is what falls off a cliff: a hash join has to repartition and rewrite both inputs, and a hash aggregate, which only ever has one, repartitions that one recursively.

Also, temp files bypass the buffer pool entirely. Chapter 14's shared_buffers is for tables and indexes; sort spills are read and written directly under base/pgsql_tmp/. That is how "there is plenty of RAM but the sort is slow" happens.

Actual behavior shows up in EXPLAIN ANALYZE, where chapter 9's three sort variants appear verbatim as strings:

Sort Method: top-N heapsort  Memory: 25kB
Sort Method: quicksort       Memory: 3400kB
Sort Method: external merge  Disk: 341000kB

Aggregation — Hash or Sort

Chapter 9's operator table listed Aggregate → Hash Aggregate / Sorted Aggregate. Here are both: hash aggregation blocks, and sorted aggregation does not.

class HashAggExec:
    """Blocking: keeps per-group state in a hash table."""
 
    def __init__(self, child, group_keys, init, accum, final):
        self.child, self.group_keys = child, group_keys
        self.init, self.accum, self.final = init, accum, final
 
    def open(self):
        self.child.open()
        table = {}
        while (row := self.child.next()) is not None:      # ← drains everything
            k = tuple(row[c] for c in self.group_keys)
            # Never write `table.get(k) or self.init()`: the moment an
            # accumulator's state goes falsy (0, False) it would reset.
            state = table[k] if k in table else self.init()
            table[k] = self.accum(state, row)
        self.out = iter([(k, self.final(s)) for k, s in table.items()])
 
    def next(self):
        return next(self.out, None)
 
    def close(self):
        self.child.close()
 
 
class SortedAggExec:
    """Non-blocking: emits a row the instant the key changes. Input must be sorted."""
 
    def __init__(self, child, group_keys, init, accum, final):
        self.child, self.group_keys = child, group_keys
        self.init, self.accum, self.final = init, accum, final
 
    def open(self):
        self.child.open()
        self.cur_key, self.state = None, None
 
    def next(self):
        while True:
            row = self.child.next()
            if row is None:
                if self.cur_key is None:
                    return None
                out = (self.cur_key, self.final(self.state))    # the last group
                self.cur_key = None
                return out
 
            k = tuple(row[c] for c in self.group_keys)
            if self.cur_key is None:
                self.cur_key = k
                self.state = self.accum(self.init(), row)
            elif k == self.cur_key:
                self.state = self.accum(self.state, row)
            else:
                out = (self.cur_key, self.final(self.state))    # key changed
                self.cur_key = k
                self.state = self.accum(self.init(), row)
                return out
 
    def close(self):
        self.child.close()

In PostgreSQL's cost model, their total costs are exactly the same. From cost_agg in costsize.c:

Note: in this cost model, AGG_SORTED and AGG_HASHED have exactly the same total CPU cost, but AGG_SORTED has lower startup cost.

Work it out for SELECT user_id, count(*) FROM orders GROUP BY user_id. The input is SeqScan(orders) (1,000,000 rows at cost 20,000), and the group count is NDV(user_id) = 100,000.

The totals are identical at 23,500; only the startup cost (22,500 versus 0) separates them, which is exactly the distinction chapter 7 introduced.

But "input already sorted" only counts when the order is free. Sorting on purpose costs

$20{,}000 + 0.005 \times 10^6 \times \log_2 10^6 \approx 119{,}700$

which loses to HashAgg's 23,500 by more than 5×. So the aggregation strategy is decided by whether an existing index or a lower merge join happens to supply the order. This is where chapter 8's interesting orders pay off in practice.

HashAgg has its own weakness: the hash table can overflow. The budget is work_mem × hash_mem_multiplier (default 2.0 since PostgreSQL 15), not plain work_mem, and a hash join's hash table gets the same budget. On spill, cost_agg charges random_page_cost per written page and seq_page_cost per page read back, then doubles both. The comment reads: "HashAgg has somewhat worse IO behavior than Sort on typical hardware/OS combinations." Once again, sorting is the one whose cost grows more gently when it spills.

The demo below puts the two failure modes side by side. Try moving the work_mem slider. The demo feeds the same input as this chapter's sort example (5,500,000 rows, 330 MB, grouped on 1,000,000 distinct keys) to both operators, not the 1,000,000-row / 100,000-group example in the table above:

Measured behavior appears on the HashAggregate node in EXPLAIN ANALYZE (the numbers below are an illustrative example). Batches of 2 or more means the hash table spilled, and only then is Disk Usage printed:

HashAggregate  (actual rows=100000 loops=1)
  Batches: 5  Memory Usage: 6273kB  Disk Usage: 21456kB

Chapter 12: Beyond Volcano — Vectorization, Code Generation, and Parallelism

The Volcano model we have been building has a performance problem: returning one row costs one function call per operator. Ten million rows times five operators is fifty million calls. At tens of nanoseconds each, that alone is seconds. Worse, virtual calls defeat branch prediction, so the overhead can exceed the actual work (one comparison).

There are three ways out of that constraint: change the granularity (vectorization), erase the open/next/close contract altogether (code generation), and clone the tree and run copies side by side (parallelism).

Vectorization and Code Generation

Vectorized execution makes next() return a batch of roughly 1,024 rows instead of one tuple. Call counts drop by three orders of magnitude, and the inside of a batch becomes a tight loop where SIMD and loop unrolling pay off. MonetDB/X100 (CIDR 2005) started this line; DuckDB and ClickHouse follow it.

Code generation goes further and eliminates the operator tree, fusing operators into tight loops. Neumann's "Efficiently Compiling Efficient Query Plans for Modern Hardware" (VLDB 2011) formalized the push-based pipeline: split the plan at pipeline breakers and compile each pipeline into one loop. Intermediate tuples are never materialized; values stay in registers.

PostgreSQL's LLVM-based JIT is easy to confuse with whole-plan code generation, but it does not eliminate the operator tree. It compiles only expression evaluation and tuple deforming (the EEOP_* array from chapter 10) into native code.

Parallel Execution — Where to Put the Gather

The third way is to run parts of the operator tree in several processes at once. Every plan so far has been serial. A parallel plan collects the workers' rows in a Gather node, and the cost arithmetic shows that whether parallelism makes the plan cheaper depends on where that node goes.

First, the worker count. PostgreSQL derives it logarithmically from table size: the first worker comes once the table reaches min_parallel_table_scan_size (default 8 MB = 1,024 pages), and another is added on every tripling.

users is 1,000 pages: 24 pages short, so it never goes parallel. orders at 10,000 pages would earn 3 workers, but max_parallel_workers_per_gather (default 2) caps it at 2.

Next, the divisor. The leader participates too, so the divisor is not simply the worker count. But the more workers there are, the busier the leader gets collecting their output, so its contribution is discounted by 0.3 per worker. Once that discount leaves nothing (4 workers or more), the leader is not counted at all.

$\text{divisor} = 2 + (1.0 - 0.3 \times 2) = 2.4$

And only CPU cost is divided. The same total number of pages still has to be read, so the I/O term survives intact.

$\text{Parallel Seq Scan(orders)} = \underbrace{10{,}000}_{\text{I/O, undivided}} + \frac{10{,}000 + 2{,}500}{2.4} = 15{,}208.3$

That would be a clear win, but shipping rows from workers to the leader is not free. parallel_tuple_cost defaults to 0.1, ten times cpu_tuple_cost, and starting the workers costs parallel_setup_cost = 1,000.

Put the Gather directly above the scan and you lose:

$15{,}208.3 + \underbrace{1{,}000}_{\text{setup}} + \underbrace{0.1 \times 100{,}000}_{\text{tuple transfer}} = 26{,}208 \;>\; 22{,}500\ \text{(serial)}$

Put it above the join and you win, because only 55,000 rows cross the queue instead of 100,000.

Gather  (cost=3387.50..24429.00 rows=55000 width=36)
  Workers Planned: 2
  ->  Hash Join  (cost=2387.50..17929.00 rows=22917 width=36)
        Hash Cond: (o.user_id = u.id)
        ->  Parallel Seq Scan on orders o  (cost=0.00..15208.33 rows=41667 width=20)
              Filter: (total > '100'::numeric)
        ->  Hash  (cost=2250.00..2250.00 rows=55000 width=24)
              ->  Seq Scan on users u  (cost=0.00..2250.00 rows=55000 width=24)
                    Filter: (age > 30)

The small rows= values under Gather are not a mistake: they are per-worker counts (100,000 / 2.4 = 41,667 and 55,000 / 2.4 = 22,917). This often trips up readers of their first parallel plan.

Two rules follow.

1. The Gather wants to be as high in the tree as possible, because every row crossing the boundary costs 40 cpu_operator_cost units. That is why PostgreSQL builds partial paths bottom-up and only caps them with a Gather at the top, and why Gather Merge exists: preserving order on the way up means the Sort need not sit above the Gather.

2. The inner side of a join is not divided: in the plan above, every worker builds its own copy of the users hash table (PostgreSQL 11+ can share one via Parallel Hash). So the hash budget is charged per node per process, and the leader executes the plan too: 2 workers + the leader = 3 processes × 1 hash node × 8 MB (the previous chapter's work_mem 4 MB × hash_mem_multiplier 2.0) = 24 MB. A plan with several hash nodes multiplies further. That multiplication is what makes the folk remedy for a spill ("just raise work_mem") dangerous.

Not everything can live below a Gather, either. Operations that write or lock rows, executions that might be suspended partway (DECLARE … CURSOR, PL/pgSQL's FOR … IN query LOOP), and PARALLEL UNSAFE functions all force serial execution. (SERIALIZABLE isolation did too, through PostgreSQL 11; that restriction was lifted in 12.) A non-zero max_parallel_workers_per_gather is necessary but not sufficient.

The running example of this article would in fact go parallel on a default PostgreSQL (24,429 < 25,688). Presenting the serial plan everywhere else is a simplification that keeps the discussion to a single execution path, the equivalent of max_parallel_workers_per_gather = 0.

Chapter 13: Access Methods — From Logical Rows to Physical Locations

The SeqScanExec built back in chapter 10 read from a Python list. Real storage starts here.

TIDs — The Physical Address of a Row

PostgreSQL identifies a row's physical location with a TID (tuple identifier, exposed as ctid): a pair of (block number, line-pointer number).

SELECT ctid, id, name FROM users LIMIT 3;
--  ctid  | id  | name
-- -------+-----+------
--  (0,1) |   1 | Ann
--  (0,2) |   2 | Bob
--  (0,3) |   3 | Cid

The second component is a slot number, not a byte offset within the block. That indirection means tuples can move inside a page without changing their TID, so compacting a page never forces an index rewrite. Chapter 15 covers the details.

Sequential Scan

PAGE_SIZE = 8192
 
class HeapScan:
    """Scan a heap file block by block."""
 
    def __init__(self, rel, buffer_pool, snapshot):
        self.rel, self.pool, self.snapshot = rel, buffer_pool, snapshot
 
    def open(self):
        self.blkno = 0
        self.slot = 0
        self.page = None
 
    def next(self):
        while self.blkno < self.rel.n_pages:
            if self.page is None:
                self.page = self.pool.read_buffer(self.rel, self.blkno)  # pinned
                self.slot = 0
 
            while self.slot < self.page.n_slots:
                slot, raw = self.slot, self.page.item(self.slot)
                self.slot += 1
                if raw is None:            # skip LP_UNUSED / LP_DEAD
                    continue
                tup = parse_tuple(raw)
                if not visible(tup, self.snapshot):    # MVCC visibility check
                    continue
                return tup, (self.blkno, slot + 1)
 
            self.pool.release_buffer(self.rel, self.blkno)   # unpin
            self.page = None
            self.blkno += 1
        return None

The visibility check is needed because not every row physically present on a page is visible to you: under MVCC (multiversion concurrency control), several versions of the same logical row coexist on the page.

def visible(tup, snapshot) -> bool:
    """A heavily simplified HeapTupleSatisfiesMVCC."""
    if not committed(tup.xmin, snapshot):
        return False                       # insert not committed yet
    if tup.xmin >= snapshot.xmax or tup.xmin in snapshot.in_progress:
        return False                       # inserted after our snapshot
    if tup.xmax == 0:
        return True                        # never deleted
    if not committed(tup.xmax, snapshot):
        return True                        # delete not committed yet
    if tup.xmax >= snapshot.xmax or tup.xmax in snapshot.in_progress:
        return True                        # deleted after our snapshot
    return False

Because this check requires the heap, PostgreSQL's Index Only Scan is harder than it sounds. Index entries carry no visibility information, so in principle the heap must still be consulted. The workaround is the visibility map, an auxiliary file with one bit per block meaning "every tuple on this block is visible to every transaction." When the bit is set, the heap fetch is skipped. VACUUM sets those bits, and any insert, update, or delete on a block clears its bit, so heavily updated tables often fail to get the Index Only Scans you expect.

Index Scans and Bitmap Scans

An index scan walks the index for TIDs and fetches the heap per TID. The problem is that index order (key order) and heap order (physical order) generally differ. Fetching 100 rows can mean 100 random reads, and the same heap page may be read repeatedly. Chapter 7's Mackert–Lohman formula priced that repeated-page effect; here we attack the same problem from the execution side instead.

The bitmap scan fixes this:

1. Walk the index to the end, collecting matching TIDs into a bitmap keyed by block number
2. Traverse the bitmap in block order and read the heap

Random reads become sequential, and no page is read twice. Multiple indexes can also be combined with bitwise AND / OR.

The catch is work_mem: once the bitmap no longer fits, it degrades to a coarse per-block (lossy) bitmap, and every tuple on those blocks must be rechecked against the predicate. EXPLAIN ANALYZE reports this as Heap Blocks: exact=… lossy=….

Chapter 14: The Buffer Pool — Caching Pages

The execution engine never reads table or index pages straight from disk. Everything goes through the buffer pool.

The pool is an array of fixed-size frames plus a hash table mapping (database, relation, fork, block number) to a frame index.

MAX_USAGE = 5                # PostgreSQL's BM_MAX_USAGE_COUNT
 
 
@dataclass
class Frame:
    page: object | None = None    # a Page object (defined in chapter 15)
    tag: tuple | None = None
    usage: int = 0
    pin: int = 0
    dirty: bool = False
 
 
class BufferPool:
    def __init__(self, n_frames: int, storage):
        self.frames = [Frame() for _ in range(n_frames)]
        self.table = {}          # buffer tag -> frame index
        self.hand = 0            # the clock-sweep hand
        self.storage = storage
 
    def read_buffer(self, rel, blkno) -> "Page":
        tag = (rel.relfilenode, "main", blkno)
        idx = self.table.get(tag)
        if idx is not None:                       # ── hit
            f = self.frames[idx]
            f.usage = min(f.usage + 1, MAX_USAGE)
            f.pin += 1
            return f.page
 
        idx = self.evict_one()                    # ── miss
        victim = self.frames[idx]
        if victim.tag is not None:
            if victim.dirty:
                old_node, _, old_blkno = victim.tag
                self.storage.flush_wal_up_to(victim.page.lsn)   # WAL first
                self.storage.write_page(old_node, old_blkno, victim.page)
            del self.table[victim.tag]
 
        victim.page = Page(self.storage.read_page(rel.relfilenode, blkno))
        victim.tag, victim.usage, victim.pin, victim.dirty = tag, 1, 1, False
        self.table[tag] = idx
        return victim.page
 
    def release_buffer(self, rel, blkno) -> None:
        """Return one pin. At zero the frame becomes replaceable again."""
        idx = self.table[(rel.relfilenode, "main", blkno)]
        self.frames[idx].pin -= 1
 
    def evict_one(self) -> int:
        """Pick a victim with clock-sweep (second chance)."""
        for _ in range(len(self.frames) * (MAX_USAGE + 2)):
            f = self.frames[self.hand]
            here = self.hand
            self.hand = (self.hand + 1) % len(self.frames)
            if f.pin > 0:
                continue                    # in use; cannot be evicted
            if f.usage > 0:
                f.usage -= 1                # give it a second chance
                continue
            return here
        raise RuntimeError("no unpinned buffers available")

The code encodes three rules.

pin > 0 means somebody currently holds a pointer into that page's memory. Evicting the page would leave that pointer dangling. The executor pins a page while reading tuples from it and calls release_buffer() when moving to the next block. Drop that pairing and you get a buffer leak; eventually every frame is pinned and PostgreSQL fails with ERROR: no unpinned buffers available (the bounded loop in evict_one above reproduces that).

Strict LRU has to relink a list on every hit, which becomes a lock-contention hotspot. Clock-sweep approximates it: keep a reference counter, decrement it when the hand passes, and evict at zero. A hit costs only a counter increment. PostgreSQL's usage_count ranges from 0 to 5.

PostgreSQL also has ring buffers. A sequential scan of a large table (bigger than a quarter of shared_buffers) uses only a small dedicated ring (256 KB by default), so a single sequential scan cannot evict everything useful from the pool.

This is the write-ahead logging (WAL) rule: before a data page is persisted, the WAL records describing the changes to that page must already be persisted. Reverse the order and a crash leaves data newer than the log that produced it, which cannot be recovered.

The rule is also what lets a commit avoid writing data pages at all (NO-FORCE), and lets uncommitted changes be written to data pages (STEAL). STEAL/NO-FORCE is the fastest combination, at the price of needing both REDO and UNDO during recovery.

Chapter 15: The Slotted Page — Where a Row Becomes Bytes

The bottom layer at last: how rows are packed into 8192 bytes.

The Layout

A PostgreSQL heap page is a slotted page.

+--------------------------------------------------+
| PageHeaderData (24B)                             |
+--------------------------------------------------+
| ItemIdData[0] | ItemIdData[1] | ItemIdData[2] |… |  ← grows forward
+--------------------------------------------------+
|                                                  |
|                   free space                     |
|                                                  |
+--------------------------------------------------+
| … | tuple 2 | tuple 1 | tuple 0                  |  ← grows backward
+--------------------------------------------------+

The two areas grow from opposite ends toward the middle. That is the least wasteful way to host a variable-length tuple area and a pointer array in one page, because neither area needs space reserved in advance. pd_lower marks the end of the pointer array and pd_upper the start of the tuple area, so free space is simply pd_upper - pd_lower.

PageInit(page, 256, 0)
  pd_lower = 24    // right after the header
  pd_upper = 256   // end of the page

Why the Indirection?

The line-pointer array adds an extra hop instead of letting a TID point straight at a byte offset. Chapter 13 gave the reason: tuples must be movable within a page. When gaps left by deletions are compacted (PageRepairFragmentation), byte offsets change but line-pointer numbers do not. Indexes hold TIDs, so without the indirection every compaction would require rewriting the corresponding entries in every index.

ItemIdData is a 4-byte bitfield.

/* src/include/storage/itemid.h */
typedef struct ItemIdData
{
    unsigned    lp_off:15,      /* offset from the start of the page */
                lp_flags:2,     /* state */
                lp_len:15;      /* tuple length in bytes */
} ItemIdData;

lp_flags has four states:

LP_REDIRECT supports HOT (Heap-Only Tuple) updates. When an UPDATE touches no indexed column and the new version fits on the same page, no index entry is created. The old line pointer becomes LP_REDIRECT pointing at the new slot, so indexes can still follow the old TID.

Reading a Page

import struct
 
PAGE_SIZE = 8192
SIZEOF_PAGE_HEADER = 24
SIZEOF_ITEM_ID = 4
 
LP_UNUSED, LP_NORMAL, LP_REDIRECT, LP_DEAD = 0, 1, 2, 3
 
 
def parse_page(buf: bytes):
    """Extract the bytes of every live tuple from an 8192-byte page."""
    # PageHeaderData: pd_lsn(8) pd_checksum(2) pd_flags(2)
    #                 pd_lower(2) pd_upper(2) pd_special(2)
    #                 pd_pagesize_version(2) pd_prune_xid(4)
    pd_lower, pd_upper = struct.unpack_from("<HH", buf, 12)
    n_slots = (pd_lower - SIZEOF_PAGE_HEADER) // SIZEOF_ITEM_ID
 
    for slot in range(n_slots):
        (item_id,) = struct.unpack_from(
            "<I", buf, SIZEOF_PAGE_HEADER + slot * SIZEOF_ITEM_ID)
        # Typical little-endian bitfield packing
        lp_off = item_id & 0x7FFF
        lp_flags = (item_id >> 15) & 0x0003
        lp_len = (item_id >> 17) & 0x7FFF
        if lp_flags != LP_NORMAL:
            continue
        yield slot + 1, buf[lp_off:lp_off + lp_len]   # TID offsets are 1-based

pd_lower sits at byte 12 purely because of the sizes of the header fields before it. Counting offsets to decode structs is routine in the storage layer.

Let's wrap that in the object chapters 13 and 14 expect: chapter 14's BufferPool returns a Page, and chapter 13's HeapScan calls page.item(i).

class Page:
    def __init__(self, buf: bytes):
        self.buf = buf
        (pd_lower,) = struct.unpack_from("<H", buf, 12)
        self.n_slots = (pd_lower - SIZEOF_PAGE_HEADER) // SIZEOF_ITEM_ID
        live = dict(parse_page(buf))                     # {line pointer: raw}
        # Index i must stay aligned with line pointer i+1; compacting breaks TIDs
        self.slots = [live.get(i + 1) for i in range(self.n_slots)]
        (self.lsn,) = struct.unpack_from("<Q", buf, 0)   # pd_lsn
 
    def item(self, i: int) -> bytes | None:
        """0-based slot index; None for LP_UNUSED / LP_DEAD."""
        return self.slots[i]