Databases: relational algebra, query optimization, transactions, and modern engines

Why this subject matters now

Databases are the rare corner of computing where a fifty-year-old paper still describes the production systems of today. Codd's 1970 relational model and the System R optimizer design that Selinger and colleagues published in 1979 are not history. They are the architecture of PostgreSQL, MySQL, and every cloud warehouse, and the reason is that both papers got the abstraction boundary right. Describe what data is wanted, and let the system decide how. What has changed in the last decade is everything beneath that boundary, and a practitioner today is expected to know the new floor plan. Analytics moved to column stores executing vectorized or compiled plans, a line of work running from MonetDB and X100 at CWI through HyPer at TU Munich to DuckDB and every cloud warehouse. Storage and compute were pulled apart. Aurora ships only the redo log across the network, and Snowflake keeps tables in object storage and rents compute by the second. The write path of most new storage engines is an LSM tree rather than a B+tree, which trades read amplification for sequential writes in a way that can be computed exactly. Distributed transactions went from an unsolved research problem to a product category. Spanner runs two-phase commit over Paxos groups with clock-uncertainty bounds, and CockroachDB and TiDB reproduce the design over Raft. And the newest index type, the approximate-nearest-neighbor graph, turned out to be just that, an index type. pgvector inside PostgreSQL is architecturally the same move as the B+tree inside System R. The durable skill is not any one engine but the cost accounting that lets one predict, before running anything, which layout, index, join order, and isolation level a workload needs. This page is organized around exactly that accounting, with every major claim either derived or measured.

Core theory

The relational model and its algebra

Codd's model has three parts. The first is the data structure. A relation is a finite subset of a cartesian product of domains, that is, a set of tuples over a fixed list of named, typed attributes, and a database is a set of relations. The second is integrity, meaning keys (a minimal set of attributes whose values identify a tuple) and foreign keys (an attribute set in one relation whose values must appear as a key of another). The third is the manipulation language, an algebra of operators that consume relations and produce relations, so operators compose. Closure under composition is the load-bearing property. It is what makes a query plan a tree and an optimizer a tree-rewriting system. The base operators appear in the table below.

The first five are independent, in that none can be expressed by the others. Everything else, natural join, theta join, semijoin, intersection, division, is definable from them. Codd proved the algebra equivalent in expressive power to a relational calculus (first-order logic over tuples), and that equivalence, relational completeness, is the formal statement that a declarative language can be compiled to a procedural plan without loss. Two consequences matter daily. The algebra cannot express recursion (transitive closure needs a fixpoint, which is why SQL grew WITH RECURSIVE), and it cannot count (aggregation is a separate extension, the grouping operator \( \gamma \)). SQL differs from the pure algebra in one more load-bearing way. SQL relations are bags, not sets. SELECT deptno FROM emp keeps duplicates unless DISTINCT is written, and the optimizer must track bag semantics because \( \pi \) over bags is free while set-projection costs a dedup. Throughout this page the running schema is the one below.

emp(eid, name, deptno, salary)         dept(dno, dname, budget)
works(eid, pid, hours)                 proj(pid, dno, cost)
keys underlined by position: emp.eid, dept.dno, works.(eid,pid), proj.pid
foreign keys: emp.deptno -> dept.dno,  works.eid -> emp.eid,
              works.pid -> proj.pid,   proj.dno -> dept.dno

SQL to algebra, worked

Take the query that asks for names of employees earning above 90,000 who work in a department named 'widgets'.

SELECT e.name
FROM   emp e JOIN dept d ON e.deptno = d.dno
WHERE  e.salary > 90000 AND d.dname = 'widgets';

The mechanical translation is product, then selection, then projection.

The result is correct but wasteful, since it materializes \( |{\text{emp}}| \cdot |{\text{dept}}| \) tuples before discarding almost all of them. The algebraic identities that license a better plan are the ones every optimizer applies. Selection splits over conjunctions, \( \sigma_{p \wedge q}(R) = \sigma_p(\sigma_q(R)) \). A selection whose predicate mentions only \(R\)'s attributes commutes through a join, \( \sigma_p(R \bowtie S) = \sigma_p(R) \bowtie S \). And a selection whose predicate equates attributes of the two sides converts a product into a join. Applying all three gives

Each rewrite is an equality of relations, provable from the definitions. The optimizer's search space is the set of plans reachable through such equalities, and its job (taken up below) is to pick the cheapest member. Projection pushdown adds one more step. \( \pi \) can be pushed below the join as long as join attributes are retained, so the scan of emp needs to carry only (name, deptno), which is the identity that column stores exploit structurally.

Algebra to SQL: division, the hard direction

Division is the algebra's universal quantifier. The query "employees who work on every project of department 7" is, in algebra,

Division is not primitive. It unfolds by double negation, the same move as writing \( \forall x\, P(x) \) as \( \neg \exists x\, \neg P(x) \). Let \( W = \pi_{\text{eid},\text{pid}}(\text{works}) \) and \( T = \pi_{\text{pid}}( \sigma_{\text{dno}=7}(\text{proj})) \). Then

Read it inside out. \( \pi_{\text{eid}}(W) \times T \) is every (employee, required project) pair that ought to exist. Subtracting \(W\) leaves the pairs that are missing. Projecting to eid names the employees missing at least one required project, and subtracting those from all employees leaves the ones missing none. SQL has no division operator, so the same double negation is written with nested NOT EXISTS.

-- employees for whom no project of dept 7 exists that they do not work on
SELECT e.eid, e.name
FROM   emp e
WHERE  NOT EXISTS (
         SELECT 1 FROM proj p
         WHERE  p.dno = 7
         AND    NOT EXISTS (
                  SELECT 1 FROM works w
                  WHERE  w.eid = e.eid AND w.pid = p.pid));

-- equivalent counting form: often faster, and easier to read
SELECT w.eid
FROM   works w JOIN proj p ON w.pid = p.pid AND p.dno = 7
GROUP  BY w.eid
HAVING COUNT(DISTINCT w.pid) =
       (SELECT COUNT(*) FROM proj WHERE dno = 7);

The counting form works because an employee's distinct dept-7 projects can never exceed the department's total, so equality holds exactly at "all of them". One edge case separates the two. If department 7 has zero projects, the double-negation form returns every employee (vacuous truth), while the counting form returns employees whose join produced at least one group, which is none. Deciding which semantics is wanted is a specification question, not a SQL question, and interviews probe exactly this seam.

Functional dependencies and normalization

A functional dependency (FD) \( X \to Y \) on relation schema \(R\) asserts that any two tuples agreeing on the attribute set \(X\) also agree on \(Y\). Keys are the special case \( X \to R \). FDs are facts about the application, not the data at hand. They come from the domain ("an order has one customer") and the schema must be judged against them. Reasoning about FDs uses Armstrong's axioms, which are sound and complete. They are reflexivity (\( Y \subseteq X \Rightarrow X \to Y \)), augmentation (\( X \to Y \Rightarrow XZ \to YZ \)), and transitivity (\( X \to Y, Y \to Z \Rightarrow X \to Z \)). Completeness means every FD that logically follows from a set \(F\) is derivable by the axioms. The practical tool is not derivation but the attribute closure \( X^+ \), the set of all attributes determined by \(X\), computed by the obvious fixpoint loop (start with \(X\), repeatedly add the right side of any FD whose left side is contained so far). \( X \to Y \) follows from \(F\) if and only if \( Y \subseteq X^+ \), and \(X\) is a superkey iff \( X^+ = R \).

The normal forms grade how far a schema is from storing each fact once. Boyce-Codd normal form (BCNF) is the clean one. For every nontrivial FD \( X \to Y \) in \(F^+\), \(X\) must be a superkey. Violations are exactly the redundancies. If \( X \to Y \) holds and \(X\) is not a superkey, then the \(Y\)-value for a given \(X\)-value is repeated across every tuple sharing that \(X\), and with repetition come update anomalies (change it in one row and not another), insertion anomalies (cannot record an \(X,Y\) fact without a full tuple), and deletion anomalies (deleting the last tuple loses the fact). Third normal form (3NF) relaxes BCNF by additionally allowing \( X \to Y \) when every attribute of \(Y\) belongs to some key. The relaxation exists because BCNF decomposition can destroy the ability to check an FD within a single table, while 3NF synthesis never does.

BCNF decomposition, traced on a concrete schema

The schema is a flat order-lines table R(order_id, cust, city, item, qty, price), abbreviated \( R(O, C, Y, I, Q, P) \), with dependencies

("an order belongs to one customer, a customer has one city, an item has one list price, an order line has one quantity.") First find the key. Compute \( (OI)^+ \). Start with \( \{O, I\} \), apply \( O \to C \) to get \(C\), apply \( C \to Y \) to get \(Y\), apply \( I \to P \) to get \(P\), and apply \( OI \to Q \) to get \(Q\). So \( (OI)^+ = \{O, C, Y, I, Q, P\} = R \), and \(OI\) is a superkey. Neither \(O^+ = \{O, C, Y\}\) nor \(I^+ = \{I, P\}\) is all of \(R\), so \(OI\) is the unique candidate key. The decomposition algorithm runs as follows. While some relation \(S\) in the current set has a violating FD \( X \to Y \) (nontrivial, \(X\) not a superkey of \(S\)), replace \(S\) by \( S_1 = X^+ \cap S \) and \( S_2 = (S - X^+) \cup X \). Each split is lossless because the shared attributes \( S_1 \cap S_2 = X \) form a key of \(S_1\) (this is the binary lossless-join test, under which a two-way split on \(X\) is lossless iff \( X \to S_1 \) or \( X \to S_2 \)).

Step 1. \( O \to C \) violates BCNF in \(R\) (\(O\) is not a superkey). \( O^+ = \{O, C, Y\} \). Split \(R\) into \( R_1(O, C, Y) \) and \( R_2(O, I, Q, P) \) (all of \(R\) minus \( \{C, Y\} \)).

Step 2. In \( R_1(O, C, Y) \) the projected FDs are \( O \to C \), \( C \to Y \) (and transitively \( O \to Y \)), and the key is \(O\). The FD \( C \to Y \) violates BCNF (\(C\) is not a superkey of \(R_1\)). \( C^+ \cap R_1 = \{C, Y\} \). Split into \( R_{11}(C, Y) \) with key \(C\), and \( R_{12}(O, C) \) with key \(O\). Both are now in BCNF, since the only nontrivial FDs are their key dependencies.

Step 3. In \( R_2(O, I, Q, P) \) the projected FDs are \( I \to P \) and \( OI \to Q \), and the key is \(OI\). The FD \( I \to P \) violates BCNF. \( I^+ \cap R_2 = \{I, P\} \). Split into \( R_{21}(I, P) \) with key \(I\), and \( R_{22}(O, I, Q) \) with key \(OI\). Both in BCNF.

The final schema is customer_of_order(O, C), city_of_customer(C, Y), price_of_item(I, P), order_line(O, I, Q). Every FD in \(F\) lands intact inside one table, so this decomposition is also dependency-preserving, which is not guaranteed in general. The standard counterexample is \( R(A, B, C) \) with \( AB \to C \) and \( C \to B \) (say, street-and-city determine postal code, postal code determines city). \(C \to B\) forces a split that separates \(A\) from \(B\), after which \( AB \to C \) can only be checked by joining, and no BCNF decomposition of that schema preserves it. 3NF synthesis (minimal cover, one table per FD, add a key table if needed) accepts the small redundancy of \( C \to B \) inside \( R(A,B,C) \) to keep every check local. The engineering translation is BCNF when the FDs decompose cleanly, 3NF when they fight, and deliberate denormalization only downstream of a measured join cost, never as a default.

Storage: pages, heaps, rows, and columns

Below the algebra sits a file of fixed-size pages, because the unit of transfer between disk and memory is a block and every cost model counts blocks. PostgreSQL uses 8 KB pages, SQLite defaults to 4 KB, InnoDB to 16 KB. A heap-file page holds a header, an array of line pointers growing forward, and tuple bodies growing backward from the end, so a tuple is addressed by (page number, slot number), the tuple identifier or TID, and can be moved within its page (compaction) without changing its address. This is the N-ary storage model, NSM, with all attributes of a tuple stored contiguously.

NSM (row store) page:                     DSM (column store), one file per column:
+-----------------------------------+     amount: [124.02][88.10][512.33][...]
| header | ptr1 ptr2 ptr3 ...  ->   |     region: [3][0][7][2][...] dict-encoded
|                                   |     qty:    [16][2][9][...] bit-packed
|   <- ... tup3 | tup2 | tup1 |     |     values of ONE column are adjacent:
+-----------------------------------+     scan touches only what the query reads
row of one tuple adjacent: good for       and compresses 5-10x (RLE, dictionary,
"fetch order 3141592 with all fields"     delta, FOR), so the scan reads less

The decomposition storage model, DSM, stores each column contiguously instead. The arithmetic that decides between them is bytes touched per query. The benchmark table built for this page has 7 columns averaging about 77 bytes per row in SQLite's row format (385.4 MB for 5,000,000 rows, measured below). An analytic query touching region, amount, qty needs roughly 8 + 8 + 8 = 24 bytes of those rows (before compression), yet a row store must read all 385 MB because the wanted bytes are interleaved with the rest at byte granularity. A column store reads three columns, and compression multiplies the advantage. The same 5M rows occupy 44.8 MB in DuckDB's format, 8.6 times smaller, because a column of 8 region strings dictionary-encodes to 3 bits per value and sorted-ish integer columns delta-encode. The full measured comparison, run for this page on this machine, is in the implementation section. The headline is a 48x single-threaded gap on a GROUP BY aggregate in the column store's favor and a 100x gap on a point lookup in the row store's favor, both from the same data, which is the whole design space in two numbers. PAX (partition attributes across) is the hybrid used by Parquet, ORC, and Snowflake micro-partitions. Rows are grouped into large blocks, columnar within each block, so single-row reconstruction never crosses a block while scans still enjoy columnar locality and per-block min/max statistics allow skipping blocks entirely (zone maps).

B+trees: fanout arithmetic

The B+tree is the default ordered index of every row store since the 1970s. All data entries live in the leaves, which are linked left to right for range scans. Internal nodes hold only separator keys and child pointers, every path from root to leaf has the same length, and nodes stay at least half full under the standard split/merge rules, so the tree's height is logarithmic in the number of entries with the fanout as the base. The fanout is where the engineering lives, so compute it. Take an 8 KB page with a 24-byte header. An internal entry is an 8-byte key plus an 8-byte child pointer, 16 bytes, so an internal node holds

and a leaf holds about 510 entries of (key, TID) at the same 16 bytes each. For \( N = 10^9 \) indexed rows,

Four levels, so a point lookup touches 4 pages. And the top three levels total \( 1 + 8 + 3{,}845 = 3{,}854 \) pages, 31.6 MB, which fits in memory on anything, so a billion-row index costs one disk I/O per cold lookup and zero warm. This is the calculation to internalize. Height grows as \( \log_f N \), and with \( f \approx 500 \) each additional level multiplies capacity by 500, so real B+trees are 3 or 4 levels essentially forever. A range scan of \(k\) matching entries costs the descent plus \( \lceil k / 510 \rceil \) linked leaf pages, which is why clustered ranges are nearly sequential I/O. Insertion splits a full leaf in two and pushes a separator up, splitting upward recursively. The root splitting is the only way height grows, which keeps the tree balanced without rebalancing passes. The price of the B+tree is random writes. Updating one 100-byte row dirties an entire 8 KB page, a write amplification of 80 on a write-heavy workload, and that number is the LSM tree's opening argument.

LSM trees: write amplification, derived

The log-structured merge tree (O'Neil, Cheng, Gawlick, O'Neil, 1996) refuses random writes entirely. Writes go to an in-memory sorted structure (the memtable) and, for durability, a sequential write-ahead log. When the memtable fills (say 64 MB) it is written to disk in one sequential burst as an immutable sorted run (an SSTable). Runs accumulate and are merged in the background into a hierarchy of levels of geometrically increasing capacity, ratio \( T \) (commonly 10). Level \(L_1\) holds, say, 256 MB, \( L_2 \) 2.56 GB, \( L_3 \) 25.6 GB, \( L_4 \) 256 GB. Reads must consult the memtable and potentially every run (Bloom filters spare most point reads the disk touches). The design space is how eagerly to merge, and the two poles have exactly computable costs. Write amplification (WA) is total bytes written to disk per byte of user data ingested.

Leveled compaction (the RocksDB default for lower levels) keeps each level as a single sorted run. When \( L_{i-1} \) overflows, a file from it is merged into \( L_i \). Because \( L_i \) is \( T \) times larger and covers the same key space, a file's key range in \( L_{i-1} \) overlaps about \( T \) files' worth of data in \( L_i \), so merging 1 byte down rewrites roughly \( T \) resident bytes alongside it. Amortized over a byte's life, it is written once by the WAL, once by the flush to \( L_0 \), and then approximately \( T \) times at each of the \( L \) levels it descends through,

With \( T = 10 \) and \( L = 4 \) levels (the 256 GB configuration above), this is \( \approx 42 \). The payoff is on the read side. One run per level means a point read consults at most \( L + \) (number of \(L_0\) files) runs, and a range scan merges \( \approx L \) iterators. Space amplification is small. Levels below the last hold \( 1/T + 1/T^2 + \dots \approx 11\% \) extra, plus obsolete versions awaiting compaction, so \( \approx 1.11 \times \) data size in steady state.

Tiered compaction (Cassandra's size-tiered, RocksDB universal) lets each level accumulate up to \( T \) independent runs. When full, all \( T \) are merged into a single run deposited at the next level. Now a byte is written once per level, because merges only combine runs and never rewrite a resident lower level,

which is 6 for the same configuration, seven times less than leveled. The bill arrives on reads and space. Up to \( T \) runs per level means \( T \cdot L = 40 \) runs to consult in the worst case (Bloom filters mitigate point reads, range scans pay in full), and space amplification can approach \( 2\times \) or worse transiently, because a full merge at the last level needs its inputs and output resident together and obsolete versions survive until their level's merge. The table below gives the summary, with the B+tree for scale, using the same \( T = 10, L = 4 \).

Two subtleties keep this honest. First, the B+tree's 80 is random writes while the LSM's 42 is sequential, and sequential bandwidth exceeds random-write throughput by an order of magnitude on SSDs once the FTL's own write amplification is counted, so leveled LSMs win the write path even at similar WA. Second, WA competes with the user for the same disk. At WA 42, sustaining 100 MB/s of ingest consumes 4.2 GB/s of write bandwidth, which is why write-heavy deployments (and RocksDB's own tuning guide) shift lower levels toward tiered, and why the Monkey and Dostoevsky line of work at Harvard (Dayan and Idreos, 2017-2018) treats the merge policy and per-level Bloom bits as a continuous knob to optimize against the workload rather than a binary choice.

Join algorithms and their costs

Every cost below counts page I/Os, the System R convention. \( M \) and \( N \) are the page counts of the outer relation \(R\) and inner relation \(S\), \( m \) the tuple count of \(R\), and \( B \) the buffer pages available. There are three families.

Nested loops. Naive tuple-at-a-time scanning of \(S\) for each tuple of \(R\) costs \( M + m N \), far too much (\(m\) is tuples, not pages). Block nested loops fixes the units. Read \( B - 2 \) pages of \(R\), then scan \(S\) once per chunk,

If \(R\) fits in memory this is \( M + N \), optimal. Index nested loops replaces the inner scan with an index probe, costing \( M + m \cdot (\text{probe cost}) \), where a probe is 1-4 I/Os as computed in the B+tree section plus one heap fetch per match if unclustered. It wins easily when \(m\) is small and loses badly when \(m\) is millions, exactly the two regimes the optimizer must distinguish, which is why cardinality estimation errors flip plans between these extremes.

Sort-merge. Sort both inputs on the join key, then merge. External sort of \(M\) pages with \(B\) buffers makes runs of length \( \approx 2B \) (replacement selection) or \(B\), then merges \( B - 1 \) at a time, so the pass count is \( 1 + \lceil \log_{B-1} \lceil M/B \rceil \rceil \) and each pass reads and writes everything, for a cost of \( 2M \cdot \text{passes} \). With realistic memory (\( B \ge \sqrt{M} \)) sorting is two passes, so

Sort-merge additionally emits output sorted on the join key, an "interesting order" (Selinger's term) that a later ORDER BY, GROUP BY, or merge join upstream can consume for free. A plan that loses on this join can win on the query.

Hash join. Build an in-memory hash table on the smaller input and probe with the larger, \( M + N \) I/Os when \( \min(M, N) \lesssim B \). Otherwise Grace hash join partitions both inputs by a hash of the key into \( \approx B - 1 \) partitions (write everything once), then joins matching partitions pairwise (read everything once), giving

provided \( B \gtrsim \sqrt{\min(M,N)} \) so each build partition fits. Skewed keys break the provision, and recursive repartitioning or hybrid variants handle the residue. Hash join is the workhorse of every analytic engine, but it only computes equijoins, and inequality joins fall back to sort-merge or nested loops. The one-line summary the optimizer lives by is index nested loops for tiny outers, hash for large equijoins, and merge when order is useful or memory is tight.

Cost-based optimization: the Selinger dynamic program, traced

Selinger, Astrahan, Chamberlin, Lorie, and Price (1979) contributed three ideas that define query optimization to this day. They estimate result sizes from catalog statistics, price plans in I/O and CPU, and search join orders with dynamic programming over subsets, keeping only the cheapest plan per subset (plus per interesting order). The estimation rules store per relation the tuple count \( |R| \) and per column the distinct-value count \( V(R, a) \). Then

the first from assuming uniform values, the second from assuming the smaller value set is contained in the larger (so each tuple of the side with more distinct values matches \( |S| / V \) tuples of the other). Modern engines refine with histograms and samples but the skeleton is unchanged. PostgreSQL's versions live in src/backend/utils/adt/selfuncs.c.

The concrete catalog for the trace follows. The query asks for employees in the 'widgets' department together with their project assignments, emp ⋈ dept ⋈ works with dname = 'widgets'.

The cost model for the trace is deliberately minimal. Every base access is a full scan costing its page count, every join is an in-memory hash join costing the pages read of both inputs, and every intermediate result is materialized with its pages (at 20 tuples per page) paid again when read by the next join. Cardinalities come first.

\( |\sigma_{\text{dname}}(D)| = 500 / 500 = 1 \) tuple. \( |E \bowtie \sigma(D)| = (10{,}000 \times 1) / \max(500, 500) = 20 \) tuples (the one department's employees). \( |E \bowtie W| = (10{,}000 \times 30{,}000)/\max(10^4, 10^4) = 30{,}000 \) tuples (every assignment keeps its one employee). \( |\sigma(D) \times W| = 30{,}000 \) tuples, since there is no predicate linking \(D\) and \(W\), so this pair is a cartesian product. The final result is \( 30{,}000 \times 1 / 500 = 60 \) tuples either way. Now the DP runs bottom up.

The DP keeps one row per subset. At \( \{D, E\} \) it already discarded the plan \( E \bowtie \sigma(D) \) versus \( \sigma(D) \bowtie E \) distinction that matters only for build-side choice, and at the top level it composes only surviving subplans. The winner runs the most selective work first. Filtering \(D\) to one tuple makes the first join's output 20 rows, and everything downstream is nearly free, while the plan that joins \( E \bowtie W \) first drags 30,000 intermediate rows through materialization. The 3x cost gap here becomes orders of magnitude with more tables. The complexity of the DP is \( O(3^n) \) plan combinations for \(n\) relations considered as subset-plus-complement splits (each of the \(3^n\) (subset, disjoint-subset) pairs considered once), against \( (2(n-1))! / (n-1)! \) unrestricted plan shapes. System R further restricted to left-deep trees, \( n \cdot 2^{n-1} \) DP states, and deferred cartesian products to last resort. PostgreSQL runs this exact DP up to geqo_threshold (12 tables by default) in src/backend/optimizer/path/joinrels.c and switches to a genetic search beyond it. The two Selinger assumptions that fail hardest in practice are uniformity (skew breaks \( |R|/V \)) and independence (correlated predicates multiply selectivities that should not multiply), and both failure modes compound exponentially in the number of joins, which is the finding of Leis and colleagues' "How Good Are Query Optimizers, Really?" (VLDB 2015, TU Munich).

Transactions: ACID made precise

A transaction is a sequence of reads and writes that the application wants treated as one unit. ACID names four separable guarantees. Atomicity means all of the transaction's writes become visible or none do, and the mechanism is undo (rollback via the log). Consistency means that if each transaction individually preserves the application's invariants, the system never exposes a state violating them. This is a contract about composition, discharged by isolation, not a mechanism of its own. Isolation means concurrent execution is equivalent to some serial execution, in a sense made exact below, or is explicitly weakened to a named level. Durability means that once commit is acknowledged, the writes survive crashes, and the mechanism is redo (write-ahead logging, the ARIES section). Isolation and durability carry the intellectual weight, so each gets its own treatment.

Conflict serializability and the precedence graph

Model a schedule as the interleaved sequence of operations \( r_i(x) \), \( w_i(x) \) of transactions \( T_1, \dots, T_n \). Two operations conflict when they belong to different transactions, touch the same object, and at least one is a write, giving read-write, write-read, and write-write pairs. A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping adjacent non-conflicting operations, or equivalently if some serial schedule orders every conflicting pair the same way. The test is the precedence graph, with one node per committed transaction and an edge \( T_i \to T_j \) whenever some operation of \( T_i \) conflicts with and precedes some operation of \( T_j \).

Theorem. A schedule is conflict-serializable iff its precedence graph is acyclic. Proof sketch, both directions. If the graph is acyclic, take a topological order of it and claim the serial schedule in that order is conflict-equivalent. Every conflicting pair's order is an edge, and topological order respects every edge, while the swaps needed to reach that serial schedule only ever exchange non-conflicting neighbors, since any blocked exchange would be a conflicting pair ordered against its edge. Conversely, a cycle \( T_a \to T_b \to \dots \to T_a \) means any candidate serial order must place \( T_a \) both before and after itself, contradiction. \( \square \)

A worked example. Take the schedule \( S_1: \ r_1(A)\ w_2(A)\ r_3(B)\ w_1(B)\ w_3(C)\ r_2(C) \) and enumerate conflicting pairs in temporal order. \( r_1(A) \) before \( w_2(A) \) gives the edge \( T_1 \to T_2 \), \( r_3(B) \) before \( w_1(B) \) gives \( T_3 \to T_1 \), and \( w_3(C) \) before \( r_2(C) \) gives \( T_3 \to T_2 \). No other pairs share an object with a write. The graph, \( T_3 \to T_1 \to T_2 \) and \( T_3 \to T_2 \), is acyclic. A topological order is \( T_3, T_1, T_2 \), so \( S_1 \) is conflict-equivalent to running \( T_3 \) then \( T_1 \) then \( T_2 \) serially. Now swap two operations to get \( S_2: \ r_1(A)\ w_2(A)\ r_2(B)\ w_1(B) \). The edges \( T_1 \to T_2 \) (on \(A\)) and \( T_2 \to T_1 \) (on \(B\)) form a 2-cycle, so no serial order agrees with both conflicts, and \( S_2 \) is not conflict-serializable. It is the classic inconsistent-analysis interleaving. Conflict serializability is sufficient but not necessary for correctness (view serializability is the weaker exact notion, but its test is NP-complete, per Papadimitriou 1979), so every practical scheduler enforces the conflict version.

Two-phase locking, with the proof

Two-phase locking (2PL) is the classical scheduler. A transaction acquires a shared lock before reading and an exclusive lock before writing, and once it releases any lock it may acquire no more. Each transaction thus has a lock point, the moment it holds its maximal lock set.

Claim. Every 2PL schedule is conflict-serializable. Proof. Suppose \( T_i \to T_j \) in the precedence graph, so some operation \( o_i \) precedes and conflicts with \( o_j \). Conflicting operations need incompatible locks on the same object, so \( T_i \) must release that lock before \( T_j \) acquires it. By the two-phase rule, \( T_i \)'s release happens at or after \( T_i \)'s lock point, and \( T_j \)'s acquisition happens at or before \( T_j \)'s lock point. Therefore \( \text{lockpoint}(T_i) \lt \text{lockpoint}(T_j) \). If the graph had a cycle, lock points would decrease around it and return to the start, impossible for real numbers, hence the graph is acyclic and the theorem above finishes the argument. \( \square \)

Plain 2PL still allows cascading aborts (\( T_j \) reads \( T_i \)'s write, then \( T_i \) aborts) and does not prevent a transaction from exposing uncommitted data. Strict 2PL, holding all exclusive locks until commit, buys recoverability and cascadelessness, and is what real lock managers implement. 2PL trades this correctness for two costs. The first is deadlocks, handled by waits-for-graph detection or timeouts (a deadlock is precisely a cycle of lock waits, the dynamic shadow of the precedence cycle 2PL prevents). The second is blocking, quantified by Gray, Lorie, Putzolu, and Traiger's 1976 granularity paper, which also introduced the intention-lock hierarchy (IS, IX, SIX) that lets a table scan take one table lock while row updates take row locks, with compatibility checked at every level of the hierarchy. Phantoms require one more idea. A predicate read ("all employees with salary above 90,000") cannot lock rows that do not exist yet, so serializable locking must lock the gap. Index-range locks (next-key locks in InnoDB) lock the leaf interval the predicate scanned, blocking inserts into it.

Isolation levels and their anomalies, exactly

The SQL standard defines isolation levels by which of three phenomena they exclude. Berenson, Bernstein, Gray, Melton, O'Neil, and O'Neil (1995) showed the standard's definitions are ambiguous and incomplete, and their anomaly catalog is the one worth memorizing. The table lists the anomalies, each as a minimal history.

Snapshot isolation (SI) is the interesting row, because it is what "REPEATABLE READ" means in PostgreSQL and what "SERIALIZABLE" meant in Oracle for years. SI gives every transaction a consistent snapshot as of its start, plus the first-committer-wins rule, under which two concurrent transactions writing the same object cannot both commit. This kills dirty reads, fuzzy reads, phantoms (the snapshot is a frozen row set), and lost updates (first-committer-wins). It permits exactly the anomaly whose two writes touch different objects, write skew. The canonical instance is a clinic that requires at least one doctor on call. Alice and Bob are both on call, and two concurrent transactions each check the invariant (each reads both rows in its snapshot, sees 2 on call) and each takes its own doctor off call. The writes are disjoint (Alice's row, Bob's row), so first-committer-wins never fires, both commit, and zero doctors are on call. Each transaction was individually correct, the pair violated the invariant, the exact failure the C in ACID delegates to isolation. Fekete, Liarokapis, O'Neil, O'Neil, and Shasha (2005) characterized when SI is safe. Anomalies require a dangerous cycle with two consecutive read-write antidependency edges between concurrent transactions, and Cahill, Röhm, and Fekete's serializable snapshot isolation (SSI, 2008) turned that theorem into a runtime that tracks rw-antidependencies and aborts a transaction when two consecutive edges appear. Ports and Grittner shipped SSI as PostgreSQL's SERIALIZABLE level (VLDB 2012). It is optimistic, so its failure mode is serialization-failure retries under contention rather than blocking. The isolation experiment in the implementation section reproduces the on-call scenario against a real engine and shows all three outcomes, the nonrepeatable read without a transaction, the stable snapshot within one, and the write on a stale snapshot rejected.

MVCC as PostgreSQL implements it

Multiversion concurrency control implements snapshots by never updating in place. Every PostgreSQL heap tuple carries system columns xmin (the transaction ID that created it) and xmax (the transaction that deleted or superseded it, or 0). An UPDATE is a delete-plus-insert. The old version gets its xmax set, a new version is inserted (in the same page when possible, chained as a heap-only tuple so indexes need no new entry), and both versions coexist. A snapshot is the triple (xmin horizon, xmax horizon, in-progress list) captured at statement or transaction start, and a tuple is visible to a snapshot iff its creator committed before the snapshot and its deleter (if any) had not. Readers therefore never block writers nor writers readers, while write-write conflicts still lock. The costs are structural, not incidental. Dead versions accumulate until VACUUM removes those older than the oldest live snapshot (a long-running transaction pins the horizon and bloats every hot table), each page stores its versions inline so hot-update workloads inflate heap and WAL, and the 32-bit transaction counter wraps, so anti-wraparound freezing must relabel old tuples as "frozen" before 2 billion transactions pass. Falling behind on freezing is a well-known cause of production outages. The contrasting design, used by MySQL/InnoDB, Oracle, and SQL Server's version store, keeps only the newest version in place and reconstructs old versions from undo segments on demand. Reads of hot rows pay reconstruction, but there is no VACUUM debt and space reclaims itself. Neither dominates, and the choice surfaces as PostgreSQL's bloat versus InnoDB's long-transaction undo growth.

ARIES recovery: write-ahead logging and the three passes

Durability and atomicity reduce to one discipline and one algorithm. The discipline is write-ahead logging. Every change writes a log record before the changed page can reach disk (the undo rule), and all of a transaction's log records reach disk before commit is acknowledged (the redo rule). The log is a sequential file of records, each with a log sequence number (LSN). Every data page stores the pageLSN of the last record applied to it, which is the hinge of the whole algorithm, because comparing a page's LSN with a record's LSN says exactly whether that update is already on the page. Each record carries the transaction's previous record (prevLSN), chaining a transaction's history for undo. ARIES (Mohan, Haderle, Lindsay, Pirahesh, Schwarz, 1992) commits to two policies that maximize normal-case performance, steal (dirty pages may be flushed before their transaction commits, so undo must be possible) and no-force (commit does not flush data pages, only the log, so redo must be possible). Recovery then runs three passes.

A worked example. Two transactions, a crash, and this log (values shown as before-image to after-image).

Analysis scans forward from the last checkpoint (here, the start), rebuilding two tables. In the transaction table, \(T_2\) committed at 40 (a winner), while \(T_1\) has no commit record, so it is a loser with lastLSN 50. The dirty page table (pages possibly dirty in memory at the crash, with recLSN, the first record that dirtied each) holds P5 recLSN 10, P3 recLSN 20, P9 recLSN 50.

Redo repeats history. Start at the smallest recLSN (10) and reapply every update, winners and losers alike, unless provably present. At LSN 10 (P5), P5's pageLSN is 30 \( \ge \) 10, already applied, so skip. At LSN 20 (P3), pageLSN 0 \( \lt \) 20, so redo, B becomes 260, P3.pageLSN := 20. At LSN 30 (P5), pageLSN 30 \( \ge \) 30, skip. At LSN 50 (P9), pageLSN 0 \( \lt \) 50, so redo, D becomes 3, P9.pageLSN := 50. At this point the database state equals the state at the crash instant, including the loser's uncommitted writes. Repeating history first is ARIES's signature, because it makes undo start from a known state even with fine-grained (record-level) locking.

Undo rolls back losers, newest record first, following prevLSN chains, and the to-undo set starts at \( \{50\} \). Undoing LSN 50 restores D to 1 and writes a compensation log record (CLR) LSN 60 recording "undid 50", whose undoNextLSN points at 10, the next record still to undo. Undoing LSN 10 restores A to 100, writes CLR LSN 70 with undoNextLSN null, then an end record for \(T_1\). CLRs are redo-only, never themselves undone. If the system crashes again mid-undo, the next recovery redoes the CLRs already written (their effects have LSNs like any update) and resumes undo exactly at the surviving undoNextLSN, so progress is monotone. Each crash strictly shrinks the remaining undo work, and recovery is idempotent without ever undoing an undo. Checkpoints in ARIES are fuzzy. They write the two tables, not the data pages, so a checkpoint costs milliseconds and bounds analysis time by how often it runs. Redo time is bounded by the age of the oldest recLSN, which is why background page flushing, not checkpointing, is what really bounds recovery. PostgreSQL implements physical redo very much in this mold in src/backend/access/transam/xlog.c, with full-page images after each checkpoint to defeat torn pages. SQLite's rollback-journal mode is the opposite corner of the design space (undo-only, force-at-commit), and its WAL mode moves it halfway toward ARIES.

Distributed databases: commit, replication, and placement

Two-phase commit

When one transaction spans machines, atomicity needs agreement. Either every participant commits or none does. Two-phase commit (2PC) is the minimal protocol. In phase one the coordinator sends prepare, and each participant forces a prepared record (redo and undo information durable) and votes yes, or votes no. In phase two, if all voted yes, the coordinator forces a commit record, the decision, and tells everyone. Any no, and the decision is abort. The cost accounting comes to two network round trips and two forced log writes on the critical path per participant, so a transaction that commits locally in microseconds pays milliseconds distributed. The deeper cost is blocking. A participant that voted yes has surrendered its right to decide, and if the coordinator dies after prepare but before broadcasting, the participant must hold its locks until the coordinator recovers. It cannot commit (maybe someone voted no) and cannot abort (maybe the decision was commit). This window is not an implementation flaw. No non-blocking atomic commit exists under crash faults with unbounded message delay, a corollary of the Fischer-Lynch-Paterson impossibility result. Production systems shrink the window rather than close it, by making the coordinator's decision itself highly available. Spanner (Corbett and colleagues, 2012) runs each participant group and the coordinator's state over Paxos replication, so "coordinator recovers" means "the replica group elects a new leader in seconds", and 2PC over consensus groups became the standard recipe (CockroachDB and TiDB do the same over Raft).

Replication and consensus, briefly

Replication choices form a small matrix. Synchronous replication (commit waits for replicas, giving zero data loss at the latency of the slowest acked replica) contrasts with asynchronous (commit is local and fast, and a failover loses the unshipped tail). Leader-based replication (all writes through one node, simple, total order for free) contrasts with multi-leader or leaderless designs (Dynamo-style quorums with \( R + W \gt N \), DeCandia and colleagues 2007, available under partition, though concurrent writes need version vectors and application-level merge). Consensus protocols make leader-based replication safe through failover by making the replica set agree on one log. Raft (Ongaro and Ousterhout, 2014) decomposes the problem into leader election (randomized timeouts, majority votes, terms), log replication (leader appends, followers acknowledge, an entry commits when a majority holds it), and the safety argument (a candidate cannot win without a log at least as up to date as any majority, so committed entries survive elections). A committed write therefore costs one round trip to a majority, and reads either go through the leader with a lease or pay a quorum check. The pointer for the full argument is the Raft paper's Figure 2 and its safety proof section. The practical content for a database engineer is the cost model, majority round trips on the write path and the throughput ceiling of a single leader, which is what pushes systems to shard first and replicate per shard.

Sharding and consistent hashing, with the arithmetic

Hash partitioning by \( h(k) \bmod N \) distributes perfectly until \(N\) changes. Add one node to eight. A key stays put only when \( h \bmod 8 = h \bmod 9 \), and by the Chinese remainder theorem \(h \bmod 72\) is uniform over 72 residues, of which exactly the 8 residues \( r \in \{0, \dots, 7\} \) with \( r \bmod 8 = r \bmod 9 = r \) qualify, so \( 8/72 = 1/9 \) of keys stay and \( 8/9 \) of the entire dataset migrates for a 12.5% capacity increase. Consistent hashing (Karger and colleagues, 1997) hashes nodes and keys onto the same ring, and each key belongs to the first node clockwise. Adding a node claims one arc, moving only the keys in it, an expected fraction \( 1/(N+1) \). With 1.2 billion keys, mod-hashing moves \( 1.2 \times 10^9 \times 8/9 = 1.067 \times 10^9 \) keys, while consistent hashing moves \( 1.2 \times 10^9 / 9 = 1.33 \times 10^8 \), eight times fewer, and only to the new node. One refinement is mandatory. A single point per node makes arc lengths exponentially distributed (coefficient of variation 1), so loads vary widely. Giving each node \(v\) virtual points makes its share a sum of \(v\) independent arcs with relative standard deviation \( \approx 1/\sqrt{v} \), so \( v = 100 \) brings imbalance to about 10% and \( v = 1000 \) to about 3%. Dynamo popularized exactly this construction, and Cassandra, Riak, and many caches inherit it. The alternative that most SQL-on-Raft systems chose instead is range partitioning with explicit split/move (Bigtable tablets, CockroachDB ranges, TiKV regions), which preserves order for scans and lets a placement service move hot ranges deliberately, at the price of running that placement service.

Worked problems

Problems 1 through 6 above sit next to the theory they exercise, FD closures and normal forms (Problem 1), B+tree geometry (Problem 2), cost-based plan choice (Problem 3), serializability and isolation (Problem 4), LSM compaction budgets (Problem 5), and consistent hashing (Problem 6). Two more integrate across sections.

Implementation

Row store versus column store: a measured experiment

The layout argument from the storage section, run for real. The experiment builds one table of 5,000,000 synthetic order rows (7 columns, an integer key, two low-cardinality strings, a float, two integers, and a 40-character filler note), loads identical data into SQLite 3.37.2 (row store) and DuckDB 1.5.5 (column store), and runs three queries in both. All numbers below were measured for this page on this machine (Intel Xeon Platinum 8480+, data fully cached, best of 7 to 9 warm runs, Python 3.10 drivers).

Every row of this table is a section of this page made concrete. The 8.6x size gap is columnar compression (dictionary encoding of the 8-value region column, bit-packing, no per-row header). The 48x single-threaded aggregate gap is bytes touched (three columns instead of seven interleaved) times per-value interpretation cost (SQLite's bytecode VM dispatches per row, while DuckDB's vectorized operators amortize dispatch over 2,048-value vectors, the X100 argument below). The extra 14x from threads is embarrassing parallelism over column segments, unavailable to SQLite's single-threaded VM. And the point-lookup row is the other side of the ledger. The B+tree descent (SQLite) reads one path and one row, while the column store must reconstruct a tuple from seven separately compressed segments. OLTP engines and OLAP engines are not competing implementations of one problem. They are correct answers to different terms of the same cost model.

-- identical schema and queries in both engines
CREATE TABLE sales(
  id      INTEGER PRIMARY KEY,   -- rowid B+tree in SQLite; zonemapped column in DuckDB
  region  TEXT,                  -- 8 distinct values: dictionary-encodes to 3 bits
  product TEXT,                  -- 200 distinct values
  amount  REAL,
  qty     INTEGER,
  ts      INTEGER,
  note    TEXT);                 -- 40-char filler: realistic row width

-- Q1: full-table aggregate, 3 of 7 columns touched. measured:
--   SQLite 2378.5 ms | DuckDB 49.4 ms (1 thread), 3.6 ms (52 threads)
SELECT region, COUNT(*), AVG(amount), SUM(amount * qty)
FROM sales GROUP BY region;

-- Q2: selective aggregate. measured: 385.0 ms | 49.9 ms | 2.4 ms
SELECT COUNT(*), AVG(amount) FROM sales WHERE amount > 500.0;

-- Q3: point lookup. measured: SQLite 6.0 us | DuckDB 604.8 us
SELECT * FROM sales WHERE id = 3141592;

import sqlite3, duckdb, time, statistics
import numpy as np

N = 5_000_000
rng = np.random.default_rng(42)
REGIONS = ["north","south","east","west","central","apac","emea","latam"]
cols = dict(
    id=np.arange(1, N + 1),                                  # [N] int64
    region=[REGIONS[i] for i in rng.integers(0, 8, N)],      # [N] str, 8 distinct
    product=["p%03d" % i for i in rng.integers(0, 200, N)],  # [N] str, 200 distinct
    amount=np.round(rng.exponential(120.0, N) + 5.0, 2),     # [N] float64
    qty=rng.integers(1, 20, N),                              # [N] int64
    ts=rng.integers(1_600_000_000, 1_750_000_000, N),        # [N] int64
    note=["order-note-" + "x" * 29] * N)                     # [N] 40-char filler

s = sqlite3.connect("bench.sqlite")
s.execute("PRAGMA journal_mode=WAL")
s.execute("""CREATE TABLE sales(id INTEGER PRIMARY KEY, region TEXT,
             product TEXT, amount REAL, qty INTEGER, ts INTEGER, note TEXT)""")
s.executemany("INSERT INTO sales VALUES(?,?,?,?,?,?,?)",
              zip(*[cols[c] if isinstance(cols[c], list) else cols[c].tolist()
                    for c in cols]))
s.commit()                                # 385.4 MB file (measured)

d = duckdb.connect("bench.duckdb")
import pandas as pd
df = pd.DataFrame(cols)
d.execute("CREATE TABLE sales AS SELECT * FROM df")
d.execute("CHECKPOINT")                   # 44.8 MB file (measured)

Q = """SELECT region, COUNT(*), AVG(amount), SUM(amount*qty)
       FROM sales GROUP BY region"""
def best(con, q, reps=9):
    ts = []
    for _ in range(reps):
        t0 = time.perf_counter(); con.execute(q).fetchall()
        ts.append(time.perf_counter() - t0)
    return min(ts) * 1000

print(best(s, Q))                         # 2378.5 ms   (measured)
d.execute("SET threads=1");  print(best(d, Q))   # 49.4 ms  (measured)
d.execute("SET threads=52"); print(best(d, Q))   #  3.6 ms  (measured)

Isolation levels, demonstrated against a real engine

The second experiment runs the on-call scenario from the isolation section against SQLite in WAL mode, where two connections give a real reader-snapshot semantics. A read transaction in WAL mode sees the database as of its first read, exactly the SI reader half. There are three phases, with the outputs as measured.

import sqlite3
# two doctors on call; invariant: at least one on call
setup = sqlite3.connect("oncall.db")
setup.execute("PRAGMA journal_mode=WAL")
setup.execute("CREATE TABLE doctors(name TEXT PRIMARY KEY, on_call INTEGER)")
setup.executemany("INSERT INTO doctors VALUES(?,?)", [("alice",1),("bob",1)])
setup.commit(); setup.close()

a = sqlite3.connect("oncall.db", isolation_level=None, timeout=0.5)
b = sqlite3.connect("oncall.db", isolation_level=None, timeout=0.5)
COUNT = "SELECT COUNT(*) FROM doctors WHERE on_call=1"

# 1. autocommit reads: no snapshot held between statements
r1 = a.execute(COUNT).fetchone()[0]              # 2
b.execute("UPDATE doctors SET on_call=0 WHERE name='bob'")
r2 = a.execute(COUNT).fetchone()[0]              # 1  <- nonrepeatable read
# measured output: first read=2, read after other commit=1
b.execute("UPDATE doctors SET on_call=1 WHERE name='bob'")   # reset

# 2. open transaction: WAL gives the reader a stable snapshot
a.execute("BEGIN")
r1 = a.execute(COUNT).fetchone()[0]              # 2
b.execute("UPDATE doctors SET on_call=0 WHERE name='bob'")   # commits fine
r2 = a.execute(COUNT).fetchone()[0]              # 2  <- repeatable: snapshot holds
# measured output: read before other commit=2, read after=2

# 3. write skew attempt: A, still on its stale snapshot (count=2),
#    takes alice off call. Disjoint rows, so SI would let both commit.
try:
    a.execute("UPDATE doctors SET on_call=0 WHERE name='alice'")
    a.execute("COMMIT")
except sqlite3.OperationalError as e:
    print("rejected:", e)
# measured output: rejected: database is locked
#   (SQLITE_BUSY_SNAPSHOT: writing on a stale snapshot is refused, so the
#    invariant survives; final state alice=1, bob=0, one doctor on call)

-- Same scenario in PostgreSQL, two psql sessions. Under REPEATABLE READ
-- (which is snapshot isolation in PostgreSQL) BOTH commits succeed and the
-- invariant breaks; under SERIALIZABLE (SSI) the second commit aborts.

-- session A                              -- session B
BEGIN ISOLATION LEVEL REPEATABLE READ;    BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT COUNT(*) FROM doctors              SELECT COUNT(*) FROM doctors
  WHERE on_call;   -- 2                     WHERE on_call;   -- 2
UPDATE doctors SET on_call = false        UPDATE doctors SET on_call = false
  WHERE name = 'alice';                     WHERE name = 'bob';
COMMIT;  -- ok                            COMMIT;  -- ok: WRITE SKEW, 0 on call

-- rerun with BEGIN ISOLATION LEVEL SERIALIZABLE; the later committer gets:
-- ERROR: could not serialize access due to read/write dependencies
--        among transactions
-- HINT:  The transaction might succeed if retried.

The measured SQLite outcome is the interesting one. SQLite is not vulnerable to write skew, but not because it detects the rw-cycle. WAL mode permits exactly one writer at a time and refuses a write from a connection whose snapshot is stale (SQLITE_BUSY_SNAPSHOT, surfacing in Python as "database is locked"). That is a stronger and blunter rule than first-committer-wins. It aborts on any concurrent committed write, overlapping or not, which makes SQLite serializable by construction and unscalable for concurrent writers by the same construction. The three engines line up as a spectrum of the same design variable. SQLite serializes writers entirely, PostgreSQL SI orders only overlapping writes and admits write skew, and PostgreSQL SSI adds the dependency tracking that recovers serializability optimistically.

A Selinger optimizer in fifty lines, and a hash join in C++

The dynamic program from the optimization section, made executable. It reproduces the cost table exactly (1,051 / 3,000 / 2,050 for the pairs, 1,552 for the winning three-way plan), and extending the catalog dictionary is the fastest way to build intuition for how estimates steer plans. The C++ tab implements the two phases of an in-memory hash join over the same schema shapes, with the build/probe asymmetry and the reason the smaller input builds spelled out in code.

from itertools import combinations

# catalog: pages, tuples; join predicates carry max(V,V) per Selinger
CAT = {
    "E": dict(pages=1000, tuples=10_000),
    "D": dict(pages=50,   tuples=500),
    "W": dict(pages=500,  tuples=30_000),
}
PREDS = {frozenset("ED"): 500, frozenset("EW"): 10_000}
FILTER = {"D": 1 / 500}          # dname = 'widgets'
TPP = 20                          # tuples per materialized page

best = {}                         # frozenset -> (cost, rows, plan string)
for r, c in CAT.items():
    best[frozenset(r)] = (c["pages"], c["tuples"] * FILTER.get(r, 1.0), r)

names = sorted(CAT)
for size in (2, 3):
    for combo in combinations(names, size):
        subset = frozenset(combo)
        for right in sorted(subset):          # left-deep: extend by one relation
            left = subset - {right}
            lcost, lrows, lplan = best[left]
            sel = 1.0                          # selectivity of applicable predicates
            for pair, maxv in PREDS.items():
                if right in pair and (pair - {right}) <= left:
                    sel *= 1.0 / maxv          # else: cartesian product, sel stays 1
            out_rows = lrows * CAT[right]["tuples"] * FILTER.get(right, 1.0) * sel
            if size < len(names):              # intermediate: pay to materialize it
                cost = lcost + CAT[right]["pages"] + max(1, round(out_rows / TPP))
            else:                              # top: reread left intermediate instead
                cost = lcost + max(1, round(lrows / TPP)) + CAT[right]["pages"]
            plan = f"({lplan} JOIN {right})"
            if subset not in best or cost < best[subset][0]:
                best[subset] = (cost, out_rows, plan)

for s in sorted(best, key=len):
    c, r, p = best[s]
    print(f"{''.join(sorted(s)):3s}  cost={c:6.0f}  rows={r:8.0f}  {p}")

# verified output of this exact script:
# E    cost=  1000  rows=   10000  E
# D    cost=    50  rows=       1  D
# W    cost=   500  rows=   30000  W
# DE   cost=  1051  rows=      20  (E JOIN D)
# DW   cost=  2050  rows=   30000  (W JOIN D)
# EW   cost=  3000  rows=   30000  (W JOIN E)
# DEW  cost=  1552  rows=      60  ((E JOIN D) JOIN W)

// In-memory equijoin: build on the smaller input, probe with the larger.
// Grace hash join is this same code run once per disk partition pair.
#include <cstdint>
#include <string>
#include <unordered_map>
#include <vector>

struct Emp  { int64_t eid; int64_t deptno; std::string name; };
struct Work { int64_t eid; int64_t pid; double hours; };
struct Out  { int64_t eid; int64_t pid; std::string name; };

std::vector<Out> hash_join(const std::vector<Emp>& emp,     // M pages
                           const std::vector<Work>& works)  // N pages, larger
{
    // Phase 1: BUILD. One pass over the smaller input. The table maps
    // key -> row indexes; multimap semantics because keys repeat.
    std::unordered_map<int64_t, std::vector<uint32_t>> ht;
    ht.reserve(emp.size());
    for (uint32_t i = 0; i < emp.size(); ++i)
        ht[emp[i].eid].push_back(i);           // O(M) build, O(M) memory

    // Phase 2: PROBE. One pass over the larger input; each probe is O(1)
    // expected. Total: O(M + N) work and M + N page reads, the formula
    // from the cost section. Build side chosen small so 'ht' fits: if it
    // does not, partition both inputs by hash(eid) % k first (Grace).
    std::vector<Out> out;
    for (const Work& w : works) {
        auto hit = ht.find(w.eid);
        if (hit == ht.end()) continue;         // no match: most probes, ideally
        for (uint32_t i : hit->second)         // usually 1 employee per eid
            out.push_back({w.eid, w.pid, emp[i].name});
    }
    return out;
    // What a real engine adds: a Bloom filter on the build keys pushed into
    // the probe scan (skips misses before hashing), vectorized probes that
    // process 2048 keys per call, and NUMA-partitioned tables. The
    // asymmetry survives every refinement: small side owns memory, large
    // side streams.
}

How it is done in practice

Vectorized execution and query compilation

The classical executor is the Volcano iterator model (Graefe, 1994). Every operator exposes next() returning one tuple, and plans compose as iterator trees. Its elegance hides a cost invisible in the I/O model, per-tuple virtual calls, branch mispredictions, and attribute interpretation, hundreds of instructions of overhead per row for operators whose useful work is one comparison or one addition. Two research lines fixed it, and both now run the industry. The CWI line, Boncz, Zukowski, and Nes's MonetDB/X100 (CIDR 2005), keeps the iterator tree but passes vectors of roughly a thousand values per call. Interpretation overhead amortizes across the vector, primitives become tight loops the compiler auto-vectorizes with SIMD, and the vector size is tuned to keep the working set inside the CPU cache (the same group's earlier MonetDB had gone all the way to full-column materialization and found it thrashes memory, and X100 is the deliberate midpoint). This architecture became VectorWise, then the design template for Snowflake's executor, Meta's Velox, and DuckDB, whose authors Raasveldt and Mühleisen (CWI, SIGMOD 2019) describe it as "vectorized processing in an embedded package". The 49.4 ms single-thread aggregate measured above is this architecture doing its job. The competing line is query compilation. Neumann's HyPer (TU Munich, VLDB 2011) generates LLVM IR per query, fusing each pipeline (scan to hash-build, scan-probe to aggregate) into one loop that keeps the current tuple in registers, erasing operator boundaries entirely. Amazon Redshift compiles to C++, SingleStore and Umbra (HyPer's successor) compile, and SQLite's bytecode VM is compilation's humble ancestor. Kersten and colleagues' head-to-head study (VLDB 2018, TU Munich and CWI together) reached a balanced verdict. Compilation wins calculation-heavy queries and tight OLTP loops, vectorization wins memory-bound scans and offers better profiling, adaptivity, and compile-time, both beat tuple-at-a-time by one to two orders of magnitude, and the industry keeps both.

HTAP and the storage-compute split

Two architectural moves define the current production landscape. The first is hybrid transactional/analytical processing, serving the analytic query from the operational data without an overnight ETL. Kemper and Neumann's HyPer (ICDE 2011) proposed one machine doing both via MVCC snapshots, but the shipping designs are mostly dual-format instead. TiDB replicates each Raft group into TiFlash, a columnar learner replica, and routes analytics there with freshness guaranteed by the Raft index (VLDB 2020). SingleStore mixes an in-memory rowstore with columnar segments, Oracle Database In-Memory and SQL Server columnstore indexes bolt the column format onto the row engine, and AlloyDB attaches a columnar cache to a PostgreSQL primary. The second move is disaggregation. Aurora (Verbitski and colleagues, SIGMOD 2017) observed that a replicated MySQL ships full pages five ways and made one change with system-wide consequences. The storage tier understands the redo log, so the database ships only log records to six storage replicas across three availability zones (write quorum 4/6, read quorum 3/6), and storage nodes materialize pages themselves. Crash recovery becomes the storage tier's steady-state behavior, and the paper reports 35x throughput over MySQL on the same hardware class. Snowflake (Dageville and colleagues, SIGMOD 2016) split along a different axis. Tables live in object storage as immutable compressed micro-partitions with min-max metadata (PAX at datacenter scale), and stateless "virtual warehouses" of compute spin up per workload, scale independently, and share nothing but the data. Time travel and zero-copy cloning fall out of immutability for free. Every subsequent cloud warehouse and the lakehouse formats (Parquet plus Iceberg/Delta tables) are variations on this separation, and the classical cost model survives translated. Page I/O became object-store GET requests, and the buffer pool became the local NVMe cache.

Vector search as an index type

Retrieval-augmented systems made "nearest neighbor under cosine distance over \( 10^8 \) embeddings" a database workload, and the right frame is the one this page has used throughout. It is an index type with a cost model, not a new kind of database. Exact search is a scan, and \( 10^8 \) vectors at 768 fp32 dimensions is 307 GB and \( 7.7 \times 10^{10} \) multiply-adds per query. The two approximate index families trade recall for that cost. IVF (inverted file) clusters vectors into \( n_{\text{list}} \) cells by k-means and searches only the \( n_{\text{probe}} \) cells nearest the query. With \( n_{\text{list}} = 10^4 \) and \( n_{\text{probe}} = 32 \), the scan shrinks to \( 32 \times 10^8 / 10^4 = 3.2 \times 10^5 \) candidates, a 312x reduction, and product quantization (Jégou, Douze, Schmid, 2011) compresses each candidate to 8-64 bytes so the scan stays in cache. Recall is recovered by re-ranking survivors at full precision. HNSW (Malkov and Yashunin, 2018) builds a multi-layer navigable small-world graph. Greedy descent through sparse upper layers lands near the target in \( O(\log N) \) hops, then a beam search of width efSearch over the bottom layer (max degree \(M\), typically 16-64) refines. Queries touch roughly \( \text{efSearch} \times M \) vectors, thousands rather than hundreds of thousands, with 95-99% recall, at the price of memory-resident graph plus vectors and slow, hard-to-parallelize builds. IVF rebuilds cheaply and pairs with disk, while HNSW answers fastest from RAM. The architectural point is that pgvector implements both as PostgreSQL index access methods, so the planner weighs an HNSW probe against a B+tree scan with the same machinery Selinger built, and the dedicated vector databases (Faiss-backed services, Milvus, and peers) compete on exactly the terms this page prices, index build amplification, memory residency, and filtered-search selectivity, the vector world's rediscovery of predicate pushdown.

The current research frontier

Four active fronts, each with several groups contending. Learned components. Kraska and colleagues at MIT proposed replacing B+tree internals with learned models of the key distribution (2018) and followed with SageDB. The measured wins are real for static sorted data (a model is a smaller, faster router than three internal levels) and contested for updates, where the Wisconsin and TU Munich groups showed tuned classical structures close most of the gap. Learned cardinality estimation, attacking the optimizer's weakest input, is further along, with Neumann's group at TU Munich and the DSAIL group at MIT publishing competing estimators, and industry deployment still cautious because a bad estimate is a regressed plan in production. Cloud-native transactions. After Aurora, the question is multi-writer disaggregation. PolarDB-MT (Alibaba), Aurora Limitless, and Neon's copy-on-write branching of the WAL each pick a different point between shared-disk and sharded-nothing. Academically the FoundationDB paper (SIGMOD 2021) rehabilitated deterministic and optimistic designs, and Calvin-style deterministic execution (Yale, Abadi's group) returned in production as Fauna. HTAP freshness. The open trade is how stale the analytic replica may be. TiFlash pins freshness to Raft, Google's F1 Lightning and Napa choose lag with SLAs, and the academic line (Berkeley, ETH Zurich) measures the throughput cost of true freshness. Embedded and composable engines. DuckDB made the single-node column engine a library, Velox (Meta) and DataFusion (Apache Arrow, Rust) make executors embeddable components, and Arrow is becoming the lingua franca that lets optimizers, executors, and storage from different projects compose, a quiet unbundling of the monolithic DBMS that Hellerstein and Stonebraker's Red Book essays anticipated. Vector indexes are converging into general engines from both directions, with pgvector and DiskANN-in-SQL-Server (Microsoft Research's graph index engineered for SSDs) as the leading edge.

Open source to read

Ordered roughly by reading difficulty. Each entry names the door to walk in through.

• sqlite/sqlite is the most-deployed database ever, small enough to actually read. Start with src/btree.c (a complete, documented B+tree) and src/vdbe.c, the bytecode VM whose per-row dispatch cost the measurement above made visible.
• duckdb/duckdb is a modern vectorized column engine in readable C++. Open src/execution/operator/aggregate/ for the hash aggregate that produced the 3.6 ms measurement, and src/optimizer/ for a working join reorderer.
• postgres/postgres is the reference implementation of half of this page. The Selinger DP lives in src/backend/optimizer/path/ (costsize.c prices what this page derives), the B+tree in src/backend/access/nbtree/ with its README, MVCC visibility in src/backend/access/heap/heapam_visibility.c, WAL in src/backend/access/transam/, and SSI in src/backend/storage/lmgr/predicate.c.
• facebook/rocksdb is the production LSM tree. Read db/compaction/compaction_picker_level.cc against the write-amplification derivation, and the wiki's "Compaction" pages for the leveled/tiered knobs of Problem 5.
• pgvector/pgvector implements vector search as an index access method, the whole thesis of that section in about 15k lines of C. src/hnsw.c and src/ivfflat.c map one-to-one onto the two families.
• facebookresearch/faiss is the reference ANN library, and faiss/IndexIVFPQ.h is IVF plus product quantization as shipped.
• cockroachdb/cockroach is Spanner's architecture in Go over Raft. See pkg/kv/kvserver/ for ranges and leases, and pkg/kv/kvclient/kvcoordinator-adjacent code for the transaction protocol's parallel commits, a genuinely novel 2PC variant.
• tikv/tikv offers Raft-replicated Percolator-style transactions over RocksDB in Rust, and src/storage/txn/ shows 2PC built from primary and secondary locks.
• vitessio/vitess is the sharding-middleware alternative to NewSQL, proven at YouTube scale. go/vt/vtgate/ is scatter-gather query routing over consistent-hash-adjacent keyspace partitioning.
• etcd-io/raft is the most-read Raft implementation, and raft.go follows the paper's Figure 2 closely enough to study them side by side.

Common misconceptions

"SQL is the relational model." SQL diverges from Codd's model in ways that bite. Relations are bags, not sets (duplicates change aggregate results and equivalence rules), and NULL introduces three-valued logic in which x = NULL is never true, so NOT IN against a list containing NULL silently returns nothing, and two NULLs are equal for GROUP BY but unequal for =. Knowing where the model ends and the standard begins is what debugging those queries requires.

"Normalization is obsolete because analytics denormalizes anyway." The star schema's wide fact table is a deliberate, priced denormalization at the read replica, downstream of a normalized system of record. Running the business's writes on denormalized tables reintroduces exactly the update anomalies BCNF names, and the modern twist runs opposite to the folklore. Columnar compression makes the normalized form cheaper to scan than the folklore expects, because repeated dimension values dictionary-encode to almost nothing.

"B-trees are deep, and that is why lookups are slow." The fanout arithmetic gives 510 children per 8 KB node, a billion rows in four levels, three of which (31.6 MB) sit permanently in cache. A cold lookup is one I/O. When an indexed lookup is slow the cause is almost never depth. It is an unclustered index fetching scattered heap pages, the regime Problem 3 priced at one I/O per matching row.

"REPEATABLE READ means my transactions are serializable." In PostgreSQL, REPEATABLE READ is snapshot isolation, and Oracle's SERIALIZABLE is SI too. Both permit write skew, demonstrated concretely above with two committed transactions breaking an invariant each one checked. Serializability requires either range-locking 2PL or SSI, and both cost something, blocking or retries. Choosing a level is choosing which anomalies the application tolerates, from the Berenson catalog, not picking a speed dial.

"NoSQL replaced relational databases." The systems that defined the movement converged back. Bigtable grew Megastore and then Spanner, which speaks SQL and runs 2PC, DynamoDB added transactions, and MongoDB added multi-document ACID and a WiredTiger B+tree/LSM storage engine. What survived of the movement is valuable and narrower. Explicit partition keys, quorum tuning, and the discipline of designing for the access path are all relational-era ideas (the granularity paper, range partitioning) wearing new clothes.

"Column stores are simply faster." Take the same data, same machine, same queries measured above. The column store wins the scan aggregate 48x single-threaded and loses the point lookup 100x. Neither number is an implementation accident. Both follow from bytes touched per operation. An engine is fast for a workload, and the workload term is not optional.

"The optimizer finds the best plan." It finds the cheapest plan under a cost model fed by cardinality estimates, and those estimates rest on uniformity and independence assumptions that correlated real data violates. Errors compound multiplicatively across joins, so six tables can put the estimate off by 10^4 (the VLDB 2015 measurement study's central result). This is why hints, plan pinning, and "it was fast yesterday" incidents exist, and why cardinality estimation, not search, is the optimizer research frontier.

"WAL is an implementation detail of one database." Write-ahead logging is the load-bearing idea of durable systems generally. Every filesystem journal, every message queue with acknowledged delivery, Raft's replicated log, and Aurora's log-is-the-database design are the same two rules (log before data, log before ack) re-instantiated. Recognizing ARIES's three passes inside a filesystem checker or a stream processor's checkpoint recovery is the transfer test for this material.

Self-check

References

1. Ramakrishnan, R., Gehrke, J. Database Management Systems, 3rd ed., McGraw-Hill, 2003.
2. Silberschatz, A., Korth, H., Sudarshan, S. Database System Concepts, 7th ed., McGraw-Hill, 2019. db-book.com
3. Bailis, P., Hellerstein, J., Stonebraker, M. (eds.). Readings in Database Systems ("the Red Book"), 5th ed., 2015. redbook.io
4. Codd, E. F. "A Relational Model of Data for Large Shared Data Banks." CACM 13(6), 1970. doi:10.1145/362384.362685
5. Selinger, P., Astrahan, M., Chamberlin, D., Lorie, R., Price, T. "Access Path Selection in a Relational Database Management System." SIGMOD 1979. doi:10.1145/582095.582099
6. Gray, J., Lorie, R., Putzolu, G., Traiger, I. "Granularity of Locks and Degrees of Consistency in a Shared Data Base." Modelling in Data Base Management Systems, North-Holland, 1976.
7. Bernstein, P., Goodman, N. "Concurrency Control in Distributed Database Systems." ACM Computing Surveys 13(2), 1981. doi:10.1145/356842.356846
8. Berenson, H., Bernstein, P., Gray, J., Melton, J., O'Neil, E., O'Neil, P. "A Critique of ANSI SQL Isolation Levels." SIGMOD 1995. doi:10.1145/223784.223785
9. Fekete, A., Liarokapis, D., O'Neil, E., O'Neil, P., Shasha, D. "Making Snapshot Isolation Serializable." ACM TODS 30(2), 2005. doi:10.1145/1071610.1071615
10. Ports, D., Grittner, K. "Serializable Snapshot Isolation in PostgreSQL." PVLDB 5(12), 2012. arXiv:1208.4179
11. Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., Schwarz, P. "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging." ACM TODS 17(1), 1992. doi:10.1145/128765.128770
12. O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. "The Log-Structured Merge-Tree (LSM-Tree)." Acta Informatica 33(4), 1996. doi:10.1007/s002360050048
13. Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., Lewin, D. "Consistent Hashing and Random Trees." STOC 1997. doi:10.1145/258533.258660
14. Chang, F., Dean, J., Ghemawat, S., Hsieh, W., Wallach, D., Burrows, M., Chandra, T., Fikes, A., Gruber, R. "Bigtable: A Distributed Storage System for Structured Data." OSDI 2006. research.google/pubs/pub27898
15. DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W. "Dynamo: Amazon's Highly Available Key-value Store." SOSP 2007. doi:10.1145/1294261.1294281
16. Corbett, J., Dean, J., Epstein, M., et al. "Spanner: Google's Globally-Distributed Database." OSDI 2012. research.google/pubs/pub39966
17. Ongaro, D., Ousterhout, J. "In Search of an Understandable Consensus Algorithm (Raft)." USENIX ATC 2014. raft.github.io/raft.pdf
18. Boncz, P., Zukowski, M., Nes, N. "MonetDB/X100: Hyper-Pipelining Query Execution." CIDR 2005. cidrdb.org/cidr2005
19. Neumann, T. "Efficiently Compiling Efficient Query Plans for Modern Hardware." PVLDB 4(9), 2011. vldb.org/pvldb/vol4/p539-neumann.pdf
20. Kersten, T., Leis, V., Kemper, A., Neumann, T., Pavlo, A., Boncz, P. "Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask." PVLDB 11(13), 2018. vldb.org/pvldb/vol11/p2209-kersten.pdf
21. Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T. "How Good Are Query Optimizers, Really?" PVLDB 9(3), 2015. vldb.org/pvldb/vol9/p204-leis.pdf
22. Raasveldt, M., Mühleisen, H. "DuckDB: an Embeddable Analytical Database." SIGMOD 2019 (demo). doi:10.1145/3299869.3320212
23. Verbitski, A., Gupta, A., Saha, D., et al. "Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases." SIGMOD 2017. doi:10.1145/3035918.3056101
24. Dageville, B., Cruanes, T., Zukowski, M., et al. "The Snowflake Elastic Data Warehouse." SIGMOD 2016. doi:10.1145/2882903.2903741
25. Jégou, H., Douze, M., Schmid, C. "Product Quantization for Nearest Neighbor Search." IEEE TPAMI 33(1), 2011. doi:10.1109/TPAMI.2010.57
26. Malkov, Y., Yashunin, D. "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs." IEEE TPAMI 42(4), 2018. arXiv:1603.09320

Key takeaway