The single divergence between SQL and the relational algebra that has consequences everywhere else. It breaks idempotence of union, makes projection unsafe to push through a duplicate-sensitive operator, and is why UNION and UNION ALL are different operators rather than an optimisation of each other.

Every surprising NULL behaviour in SQL is this one rule applied in a place with a different default for UNKNOWN. WHERE rejects UNKNOWN; CHECK accepts it, so a constraint is weaker than the identical predicate in a query; GROUP BY treats NULLs as equal although = does not.

Closure — a relation in, a relation out — is what makes an expression rewritable without changing its meaning. The algebra is therefore not a teaching device but literally the rule set module 06 searches over.

Transitive closure is not expressible in relational algebra because every algebra expression has a fixed number of joins. WITH RECURSIVE evaluates a fixpoint instead. For a linear rule the productive rounds number the longest shortest-path length among reachable pairs — the diameter only with qualifications for disconnected graphs and cycles — plus one empty round to confirm termination; semi-naive evaluation feeds each round only what the previous one newly produced.

Over every legal instance, not over one sample — inferring dependencies from data you happen to have is the commonest error in normalisation, because a small instance satisfies many dependencies the domain does not guarantee.

Computed by fixpoint iteration in O(|F|·|R|). It is why the full closure F⁺ never has to be computed: membership reduces to Y ⊆ X⁺. Candidate keys are found by searching attribute closures.

Produced by two reduction passes — remove extraneous attributes from left-hand sides, then remove dependencies implied by the rest. It is the input to 3NF synthesis, which is why synthesis produces a schema with no redundant relations.

The binary test is that the common attributes of the two fragments must be a key of at least one of them. A decomposition failing it produces spurious tuples — rows that were never in the original — which is silent data corruption rather than a performance problem.

The second correctness criterion, independent of losslessness. A dependency that survives only across a join is in practice not checked at all, because checking it would require joining on every write.

Always achievable losslessly and sometimes not while preserving dependencies — which is exactly why real schemas stop at 3NF. BCNF decomposition is also not confluent: splitting on a different violating dependency yields a different, equally valid BCNF schema.

Always yields a decomposition that is both lossless and dependency-preserving, which is the theorem that decides between the two normalisation algorithms. It must add a relation containing a candidate key if none of the produced relations already contains one.

Redundancy a relation in BCNF can still contain, because independence is not a functional determination. Every functional dependency is a multivalued one, so 4NF implies BCNF.

One of three primary organisations, alongside sorted and hashed files. The cost table over these three is the unit every later operator cost in the course is quoted against.

The indirection through a slot is what lets a record move within its page during compaction while its identifier stays valid — and whether that identifier is stable decides whether secondary indexes can store it directly or must store the primary key and pay a second lookup.

LRU’s characteristic failure in a database, and the reason engines do not use plain LRU. LRU-K is the principled fix — it distinguishes a page referenced twice recently from one referenced once — and ring buffers are the cheap one.

With K = 2 a page touched once by a scan ranks below a page touched twice by the workload, so a scan evicts other once-touched pages before any established one — protection that holds while such victims exist, not an absolute guarantee. It is the policy sequential flooding motivates, and 2Q is its practical approximation.

Buys cache behaviour rather than I/O, since the page is still the I/O unit. It returned as the standard layout for engines that must serve both transactional and analytical workloads, and is the shape of every modern columnar file format.

Entry size is dominated by the key rather than the pointer, which makes key encoding the real lever on tree height — a 64-byte key and an 8-byte key can differ by a whole level at realistic row counts.

The single invariant every B+tree algorithm exists to restore. Split restores it on insert, merge or redistribution on delete, and the fact that the tree grows only at the root is what keeps all leaves level.

A leaf split copies the separator up and keeps the key in the leaf; an interior split moves it up and the key leaves the node. Half of all explanations get that distinction wrong.

"Safe" means the node cannot split or merge under this operation, and the condition differs for search, insert and delete. It is how a concurrent descent avoids holding the root for its whole duration.

Lehman and Yao’s design removes the need to hold the parent latch at all during descent. It costs one pointer and one key per page and is the strongest of the practical concurrency answers for mixed read/write workloads.

Gives lock-free-like read performance without a lock-free data structure: a successful read writes no shared state. Writers still exclude each other, and a stalled writer can make readers retry indefinitely. A buffer pool does not rule it out, but the engine must keep a frame from being reused during an optimistic read — LeanStore integrates the two.

Test-and-set degrades under contention because every failed attempt pulls the same cache line to another core, so coherence traffic per acquisition grows with the number of waiters, and draining a queue of waiters grows quadratically. An MCS queue keeps remote references per acquisition constant — though not the time spent waiting.

An interior entry is a routing decision, not a value, so the rest of the key is dead weight against fanout. Close to free, and should be assumed present in any serious B+tree.

The ε parameter unifies the write-optimised family: ε = 1 recovers the ordinary B-tree and ε → 0 approaches an LSM, with insert cost falling and search cost rising monotonically between them.

Every node pointer indirects through the mapping table, so a node is modified by one atomic compare-and-swap and never in place. Shipped in SQL Server Hekaton.

Local depth is the field doing the work: a bucket with local depth below the global depth splits without touching the directory. Doubling is O(2^d) pointers but touches no data pages, which is why an operation that sounds catastrophic is cheap.

Removes the directory entirely, at the cost of splitting buckets that did not need it and tolerating overflow chains on the ones that did.

A trie’s height depends on key length rather than key count, which wins structurally in memory. ART’s adaptive nodes and path compression fix the two problems — space explosion and depth — that make a naive radix tree unusable.

Genuinely smaller than a tree on read-only data, and unshipped in any mainstream write path: updates need a rebuild or a delta buffer and the error bound is empirical rather than worst-case.

Won over run-length schemes such as WAH because it keeps random access and boolean operations fast rather than only compressing well. It is the posting-list format of most modern search and column engines.

The escape from the unclustered-index crossover: it converts up to m random page fetches into one leaf-range scan, which is why included columns exist. Coverage is per query, and not every engine can act on it unconditionally — PostgreSQL still visits a heap page that is not marked all-visible, to check row visibility.

Composes arbitrarily and needs no scheduler, at the cost of a virtual call per operator per tuple — ruinous when the per-tuple work is a single comparison, which is why analytical engines left it.

Sort, hash build and aggregation. They, rather than the operators generally, determine a plan’s memory footprint and its time-to-first-row, so a plan’s cost profile is read off its breakers.

Wins decisively on scans over many rows and buys nothing for a single-row lookup, which is why tuple-at-a-time and vectorised engines coexist rather than one replacing the other.

The pass count is 1 + ⌈log_{B−1}⌈N/B⌉⌉, which is why 100 buffer pages sort 100 GB in two passes. It underlies ORDER BY, GROUP BY, merge join and index bulk-loading.

Costs 3(N+M) and needs B > √|R| for a single partitioning pass. Its failure case is skew, where one partition still does not fit and recursive partitioning is required.

Saves that partition’s I/O entirely, so it degrades gracefully from an in-memory hash join to a fully partitioned one as memory shrinks.

The property that lets parallel and partitioned aggregation reduce each piece to a small state early. Holistic aggregates such as MEDIAN and COUNT DISTINCT have no bounded exact partial state — they can still be partitioned exactly, but not reduced early — which is why mergeable sketches such as HyperLogLog exist.

Absorbs uneven costs of independent work at runtime instead of fixing each worker’s share in advance. Worker count and work assignment are separate decisions: a fixed team, even PostgreSQL’s worker processes, can claim scan ranges dynamically. It cannot split indivisible work such as one hot join key, which needs the operator itself to decompose the work.

Neumann’s produce/consume model makes the pipeline rather than the operator the unit of code generation. Whether it beats vectorisation is genuinely open: it must repay its compile latency over the rows that remain, and engines mix the two — ClickHouse vectorises and JIT-compiles expressions, PostgreSQL JIT-compiles only expressions and tuple deforming.

Changes the complexity class rather than the constant. The general algorithm pushes a dependent join down until nothing depends on the outer row; the COUNT bug is the trap, since naive unnesting turns "zero matching rows" into "no row at all".

Bounds estimation error on skewed data, which equi-width does not: a bucket covering a heavily populated range is narrow, so the uniformity assumption inside it costs less.

Wrong whenever predicates correlate, and the canonical case is a city and its state, where the product underestimates by orders of magnitude. No engine has solved it; every engine’s answer is to let you declare the correlation.

The subtlety that makes Selinger’s dynamic programming correct: the search must keep one best plan per sort order, not one overall. An optimiser that forgets it systematically underuses merge joins.

Reusing that strategy for other values can cause severe slowdowns on skewed data, because the value that triggered compilation need not represent later executions — the same prepared statement is fast for one value and catastrophic for another, with nothing in the query to indicate which.

An axis orthogonal to serializability: a perfectly serializable schedule can be impossible to roll back. Strict ⊂ cascadeless ⊂ recoverable, and this chain is why strict two-phase locking exists.

Stronger than recoverable. Without it, aborting one transaction can cascade into aborting every transaction that read from it, which is unbounded work at exactly the wrong moment.

The two-phase rule alone gives serializability; holding to commit is bought separately, for recoverability and to make undo a simple before-image restore. Naming the variant matters — "2PL" without one says almost nothing.

The extra property distributed commit protocols depend on, since it lets a coordinator use commit order as a global serialization order without further reasoning.

IS and IX on the way down let a table-level request detect a conflict with a row-level holder without inspecting a million rows. SIX covers the scan-and-modify case that S plus IX would otherwise require.

Bounds lock-table memory and converts fine-grained contention into table-level blocking at an unpredictable moment. The alternative — refusing to escalate — fails the transaction outright when the table fills, which is at least a clear error.

Unimplementable in general, because deciding whether two predicates intersect is not computable. Every engine approximates it with the index instead.

The practical approximation of a predicate lock. It produces false conflicts because the gap is coarser than the predicate, and it is why the same application deadlocks on REPEATABLE READ and not on READ COMMITTED under InnoDB.

A write older than the item’s write timestamp would be overwritten immediately anyway, so ignoring it preserves the timestamp order while aborting fewer transactions.

Its throughput curve falls rather than flattens beyond the contention crossover, because work is done before it is discovered to be wasted. "Optimistic is modern, locking is legacy" is marketing: the two curves cross.

Deadlock-free because waits always run one way along the timestamp order, at the cost of aborting transactions that were never actually deadlocked.

One of four independent axes in the MVCC design space. Append-only retains full versions in the main table; delta storage retains inverse changes separately. Full images avoid historical reconstruction, not the walk to find them; deltas save space for narrow updates but require reconstruction. Both need garbage collection.

The anomaly that defines snapshot isolation’s boundary: SI prevents dirty reads and changes to repeated snapshot reads, and rejects overlapping writers of the same row, yet permits this nonserializable history because the two write sets are disjoint.

Tracks concurrent read–write antidependencies with SIREAD markers, which block no one, and aborts a transaction when two consecutive rw edges form a dangerous structure. The pattern is necessary for an SI cycle, not proof of one, so it accepts false positives; PostgreSQL narrows them with commit-order and read-only refinements.

Necessary the moment a transaction can exceed the buffer pool, and it is precisely what creates the obligation to keep undo information.

Turns commit from a random-write storm into one sequential log write, and creates the obligation to keep redo information. Steal plus no-force is what every durable engine ships, and the log is the debt those two incur.

What makes the write-ahead invariant checkable rather than hoped for, and what lets redo decide per page whether a logged change is already present.

Dirty pages are flushed lazily afterwards, so no transaction is blocked. The recLSN of each dirty page, not the checkpoint record itself, is where redo actually starts.

Looks wasteful and is the opposite: it reconstructs the exact crash state, so undo starts from a known point. Selective redo would need to know which changes to skip, which is exactly the information the crash destroyed.

Its UndoNxtLSN is what makes recovery restartable: a crash during recovery never re-undoes completed work, so total work stays bounded no matter how many times the machine dies.

The index is shared, so undoing a split because one transaction rolled back would corrupt it for everyone. The log records the action as complete in itself.

The resolution of the torn-page problem: after a partial write a page is in no known state, so a purely logical redo cannot be applied, while purely physical logging costs a full page image per change.

InnoDB’s answer to torn pages, against PostgreSQL’s full-page images in the log. Both cost roughly double the write volume and place it differently.

Needs no log at all, which is why LMDB has none. It pays in fragmentation, write amplification and — because the root swap serialises — a single writer.

Moves recovery work off the critical path without reducing it, trading steady-state overhead for availability immediately after a crash.

The buffer pool inverted: memory is the primary store and disk is the overflow, so the unit of eviction follows what the workload actually references rather than what the page happens to contain.

Removes distributed commit rather than accelerating it, at the price of needing the full read/write set in advance, forbidding non-deterministic functions, and requiring aborts themselves to be deterministic.

Why a random write still costs more than a sequential one on a device with no seek: the FTL relocates and erases, so the device has its own write amplification and its own garbage collector competing with the database’s.

Turns comparisons into integer compares and, when the dictionary is sorted, lets range predicates run on codes directly — absent constants short-circuit to empty before any data is read. The encoding stops paying once cardinality passes the point where the code is no narrower than the value.

Aggregates answer from the run vector without touching the values — SUM over RLE is Σ value×count, so sorted data makes aggregates nearly free and compression nearly total at the same time.

A column of 0–7 fits in 3 bits each; patched variants choose a frame width and spill the exceptions, which is why the width is chosen per frame rather than per column. Combined with dictionary codes it is the default integer encoding in every columnar format.

Compresses strings where dictionary encoding cannot — high-cardinality text — and still lets some predicates evaluate on compressed data, since an encoded byte string compares correctly for equality.

The cheapest index that exists: proportional to block count, maintained on write for free, and conservative forever — a block whose range cannot match is skipped, one that can is read and re-checked. Worth everything on a sorted column and almost nothing on a random one, which is why it is usually the only index a column store keeps.

Trades the perfect pruning of a compound key’s leading column for a geometric share of pruning across every column at once — useful when several predicate columns matter equally and none deserves the lead position.

A filter then reads only the columns it needs, at the cost of a gather whose price depends on where the survivors sit — clustered survivors touch few pages, scattered ones touch nearly every page of each column even when their positions are sorted, and unsorted positions can fetch the same page again and again.

The currency of late-materialised execution: passed between operators instead of tuples, so each operator adds work to the positions that remain rather than the columns the query needs. Its ordering relative to storage decides the gather cost.

The unit of skipping and of memory-bounded reads: statistics, indexes and dictionaries live per column chunk inside a row group, so a reader that can skip a group skips every column’s share of it.

Merge-on-read’s surgical form: a delete applies at read time without rewriting the data file, at the cost of carrying delete state to every reader. Equality deletes do the same by key where positions are unknown; sequence numbers decide which delete applies to which write.

The table-format answer to in-place delete: the file stays immutable, the bitmap marks what is gone, and compaction later reclaims the space — the same trick a column store’s delete mask plays, raised to the level of a shared table format.

Pays nothing at write time and charges every read — the mirror of copy-on-write, which pays the rewrite immediately so readers stay dumb. Which side of the line an engine picks is fixed by whether its writes or its reads are the scarce resource.

The baseline every other access path is compared against, and the one cost in the table with no failure mode: it is the same whatever the predicate, the selectivity or the data distribution. Sequential, so each page costs c_seq rather than c_rand — which is why a scan reading ten times the pages can still beat an index doing random fetches.

Half the file on average for a unique match, because the scan can stop; the whole file when the match is not unique or does not exist, since nothing proves absence until every page is read. The gap between expected and worst case is the reason this row exists — a heap file has no bad case for scanning and a bad case for searching.

The best search cost of the three primary organisations, and irrelevant in practice because of the next row: keeping the file sorted costs O(N) per insert. Sorted files survive as the output of a bulk load, not as a maintained organisation — which is exactly the problem the B+tree solves.

The cost that kills the sorted file as a primary organisation. Every insert shifts on average half the file, and each shifted page is read and written. This single cell is why module 04 exists.

The only constant-time search in the table, and it answers exactly one question — no ranges, no prefixes, no ordering. The overflow term grows with load factor and is what extendible and linear hashing exist to bound.

The structural cost is the height h = ⌈log_F N_records⌉, three or four for a large table. The practical cost is about one I/O, because the top two levels are a few megabytes and therefore permanently resident. Quoting h as the I/O count is the commonest overestimate in access-path costing.

The leaf chaining is the reason every database chose B+trees over B-trees: after the descent the scan is sequential, so a range costs the same per row as a heap scan does. Only true when the index is the relation’s order or the query is answered from the index alone.

The m term is page fetches, not records, under the worst case that scattered matches share no pages — and each is random rather than sequential. A scan gets p records per page read and this path gets one, so the crossover sits near 1/p of the relation — under 1% at 100 records per page — rather than at half of it. The single most useful number in the module; locality and caching move it.

Collapses the previous row’s m random fetches into a leaf-chain scan, a difference of orders of magnitude at moderate selectivity, and the reason included-column indexes exist. The descent already reads the first leaf, so the exact count is one less; engines that check visibility in the relation add those fetches back.

Splits are rare in amortisation but not in the tail: a split writes the old page, the new page and the parent, and can propagate to the root. Under ascending keys the splits concentrate on one page, which is both a contention point and the reason ordered keys pack better.

The term index selection trades against: a cold descent plus one leaf write, per entry a write changes. It is paid whether or not any query uses the index, which is why "index every predicate" loses — the read saving is bounded by the query rate and the write cost is not. An update touching no key or included column of an index may leave it untouched; splits, merges and log bytes are extra.

The log base is B−1 rather than B because one frame buffers output. The practical consequence is that the pass count is almost always two: with 100 buffer pages, 100 GB sorts in two passes, so sorting is nearly linear in practice despite the logarithm.

Produces grouping-key order for free, which is worth real money when an ORDER BY on the key follows or a merge join consumes it. If the sort’s final merge feeds grouping directly, the sorted-file write and re-read disappear and the cost is external sort − N — the same as a one-round hash spill, so spilling alone does not favour sorting; the ordered output does.

Cheaper than sorting whenever the distinct group count fits in memory, and unordered. Memory follows the number of groups, not rows. The spill case is a partitioning round, which is why its cost matches Grace hash join’s shape; partial or recursive spilling costs N plus two I/Os per spilled page per level.

Listed so the reader can see what every other join algorithm is avoiding. The multiplier is a record count, not a page count, which is what makes it catastrophic rather than merely bad.

The same algorithm as the row above and orders of magnitude cheaper, purely from using memory. It wins outright when the outer relation fits in B−2 frames, where the cost collapses to N + M — one scan of each.

The best join in the table when the outer is small and the inner index is selective, and the worst when the optimiser underestimates the outer’s cardinality — which is the single commonest catastrophic plan in production. The fetch term is 1 for a covering index and m for an unclustered one.

Free when both inputs are already sorted — which is what makes interesting orders worth tracking in the optimiser. Its degenerate case is many duplicates on both sides, where the merge reintroduces a nested loop inside itself.

Read, write, read again — hence the factor of three. The condition B > √|R| is the most useful inequality in the module: below it, partitions still do not fit and the algorithm recurses, and skew can break the condition for one partition even when the average holds.

Degrades continuously from an in-memory hash join to a fully partitioned one as memory shrinks, rather than switching discontinuously. It is what a competent engine actually runs when it reports a hash join.

Under force it would be a random write of every page the transaction touched. The whole point of the write-ahead log is to convert that into this, and group commit then amortises even the fsync across every transaction committing in the same window.

PostgreSQL pays it as a full-page image in the log; InnoDB pays it as a second write to the doublewrite buffer. Both roughly double write volume for the affected pages, which is why checkpoint interval is a write-amplification parameter and not only a recovery-time one.

Bounded by the checkpoint interval, and slower per byte than the writes that produced it, because the log was written by many concurrent transactions and is replayed by one process. Measure the replay rate on a copy rather than inferring it from the production write rate.