Sources and References

Primary textbook — Ramakrishnan and Gehrke, Database Management Systems, 3rd ed., McGraw-Hill, 2003 (chapters 3–23 form the core reading). Supplementary texts — Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom, Database Systems: The Complete Book, 2nd ed., Pearson, 2009; C. Mohan, Donald Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz, “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging,” ACM TODS 17(1), 1992. Online resources — PostgreSQL 16 documentation (postgresql.org/docs); CMU 15-445/645 Database Systems lecture notes (Andy Pavlo, 2023); MIT 6.830 Database Systems open courseware; the ARIES paper (full text freely available via ACM DL).

Chapter 1: The Relational Model and DBMS Architecture

Understanding how a database management system is built — not just used — requires starting from the mathematical foundations that make relational databases correct, then working upward through the architectural layers that make them fast.

The Relational Model

A relation is a set of tuples, each conforming to a schema. Formally, a relation \( R \) over attributes \( A_1, A_2, \ldots, A_n \) with domains \( D_1, \ldots, D_n \) is a subset of \( D_1 \times D_2 \times \cdots \times D_n \). Because it is a set, there are no duplicate tuples and no inherent ordering.

A primary key is a minimal set of attributes whose values uniquely identify every tuple. A foreign key in relation \( R \) referencing relation \( S \) asserts that every value of the foreign-key attributes in \( R \) must appear as a primary-key value in \( S \); this is referential integrity.

Relational Algebra

SQL is declarative — it says what you want. The query optimizer translates SQL into relational algebra, an operational language specifying how to compute the answer. The core operators are:

Extended operators include grouping \( \gamma \), sorting \( \tau \), and explicit duplicate elimination \( \delta \). These are not expressible in pure relational algebra but are needed in practice.

Mapping SQL to Relational Algebra

A SELECT-FROM-WHERE query translates as: form the Cartesian product of the FROM tables, apply the WHERE predicate as \( \sigma \), then project via \( \pi \) onto the SELECT list. Aggregation with GROUP BY maps to \( \gamma_{G; f(A)} \), where \( G \) is the grouping-attribute list and \( f(A) \) is an aggregate function. The query optimizer manipulates this algebraic tree to find an equivalent, cheaper plan.

SELECT s.name
FROM Students s, Enrolled e
WHERE s.sid = e.sid
  AND e.cid = 'CS448'
  AND s.gpa > 3.5;

CREATE VIEW Enrolled AS
  SELECT * FROM EnrolledFall
  UNION ALL
  SELECT * FROM EnrolledSpring;

DBMS Architecture

A DBMS is a layered system. Each layer has a clean interface so that internals can change without affecting layers above:

Physical data independence means applications do not break when storage structures change (e.g., adding an index). Logical data independence means applications do not break when the schema changes (e.g., adding a column). Layering enforces both.

PostgreSQL exposes its catalog through system tables: pg_class (relations and indexes), pg_attribute (columns), pg_index (index metadata). The optimizer reads these to know which indexes exist and to obtain statistics stored in pg_statistic.

Chapter 2: Storage, Buffer Management, and File Organization

Before any query can run, data must be read from disk. The cost model for query optimization is almost entirely determined by the number of page I/Os performed, so understanding the storage layer is essential.

The Disk I/O Model

Modern storage is organized into fixed-size pages (typically 4–16 KB). Accessing a page on a hard disk requires a seek (moving the read head) plus rotational latency — combined on the order of 5–10 ms. A sequential read of the next page costs only a fraction of that because no seek is needed. SSDs reduce random I/O latency to ~0.1 ms, but the sequential-vs-random gap persists. Main memory access is \(\approx 100\) ns. The storage hierarchy:

The query optimizer therefore tries to maximize sequential I/O and minimize random I/O.

Heap Files

A heap file is an unordered collection of pages. It supports insert (always goes to a page with free space), delete (mark a slot as empty), and full scan. Each page has:

• A page header (page LSN for recovery, free-space pointer, slot count)
• A slot directory at the end of the page mapping slot numbers to record offsets
• Records packed from the beginning of the usable area

Fixed-length records allow direct offset calculation: record \( i \) starts at \( \text{header\_size} + i \times \text{record\_size} \). Variable-length records store a null bitmap followed by an array of (offset, length) pairs pointing into the record data area. The record ID (RID) is the pair (pageId, slotNo) and is stable across reorganizations within a page.

Buffer Pool

The buffer pool is a region of RAM divided into frames. A page table maps each loaded pageId to its frame index, along with a pin count (how many threads are currently using it) and a dirty bit (whether it has been modified).

When a thread needs a page it calls pin(pageId). If the page is in the pool, the pin count is incremented and the frame pointer is returned. If not, an eviction is needed: choose an unpinned frame via a replacement policy, write it to disk if dirty, then load the requested page.

Replacement policies:

Databases cannot rely on the OS page cache because the OS does not understand transaction semantics — for example, it might write a dirty page before the corresponding log record, violating write-ahead logging. Therefore, DBMS implementations bypass the OS cache (O_DIRECT on Linux) and manage their own buffer pool.

Row vs. Column Storage

NSM (N-ary Storage Model), also called row-oriented storage, stores each tuple contiguously. This is optimal for OLTP: inserting or updating a full row touches a single page.

DSM (Decomposition Storage Model), or column-oriented storage, stores each attribute in a separate file or column group. For OLAP queries that read only a few attributes over millions of rows, DSM reads far less data. Examples: MonetDB, Vertica, Apache Parquet. The trade-off is that reconstructing a full row requires joining column files on row position.

Chapter 3: Indexing — B+-Trees and Hash Indexes

An index is a data structure that maps search key values to the RIDs of matching tuples. Without an index, answering a point query requires scanning all \( N \) pages of the heap file — \( O(N) \) I/Os. With a B+-tree index, the cost drops to \( O(\log_d N) \) I/Os, and with hashing to \( O(1) \) expected. The trade-off is write overhead and space.

B+-Tree Structure

A B+-tree of order \( d \) satisfies:

• Every non-root internal node has between \( d \) and \( 2d \) keys (and one more pointer than keys).
• Every leaf node has between \( d \) and \( 2d \) key-pointer pairs.
• All data entries (key + RID list) are stored in leaf nodes; internal nodes hold only routing keys.
• Leaf nodes are linked in a doubly-linked list sorted by key, enabling efficient range scans.

The height of a B+-tree storing \( N \) entries is \( h \approx \lceil \log_d N \rceil \). For \( d = 100 \) and \( N = 10^6 \), \( h \approx 3 \) — meaning a point lookup costs 3–4 I/Os regardless of table size.

Insertion traverses to the leaf. If the leaf overflows (more than \( 2d \) entries), it is split: the middle key is pushed up to the parent, which may itself split, propagating toward the root. If the root splits, a new root is created, increasing tree height by one.

         [3]
        /    \
  [1|2]      [3|4|5]

Deletion traverses to the leaf and removes the entry. If the node underflows (fewer than \( d \) entries), it either borrows from a sibling (redistribution) or merges with a sibling, pulling a key down from the parent. Merges can propagate upward.

PostgreSQL implements B+-trees via its GiST (Generalized Search Tree) framework, which supports multi-column, partial (indexed only on a subset of rows), and expression indexes (e.g., LOWER(email)).

Clustered vs. Unclustered Indexes

A clustered index keeps the heap file sorted in the same order as the index. A range scan using a clustered index reads pages sequentially. An unclustered index does not control heap order; each matching tuple may be on a different page, so a range scan of \( k \) matches can cost up to \( k \) random I/Os — potentially worse than a full scan for large \( k \).

A covering index stores all columns needed by a query, avoiding heap lookups entirely (an index-only scan).

Static Hashing

Static hashing partitions records into \( B \) buckets using hash function \( h(k) \bmod B \). Each bucket is a chain of pages. A point lookup costs \( O(1 + \text{overflow pages}) \). Static hashing cannot answer range queries and is expensive to resize (must rehash all records).

The fundamental limitation of static hashing becomes apparent over time. As records are inserted, buckets grow beyond a single page and require overflow chains. Once the overflow chains exceed one or two pages, the average lookup cost exceeds two I/Os — at which point a B+-tree is often competitive for point queries while also supporting range queries. This is why static hashing is rarely used as a primary index structure in production databases, though it survives as an in-memory hash table for hash join probe phases and for in-memory databases where overflow chains are irrelevant.

Extendible Hashing

Extendible hashing eliminates the cost of full rehashing. A directory of \( 2^g \) pointers (where \( g \) is the global depth) maps the \( g \)-bit hash prefix to a bucket. Each bucket has a local depth \( \ell \leq g \).

When a bucket overflows: split it into two, increment local depth. If local depth would exceed global depth, double the directory (copy each entry; only the overflowed bucket needs a new page). Doubling the directory is cheap because only pointers are copied. On average, only one bucket page is needed per split.

Directory (g=2):
  00 → Bucket A  (local depth ℓ=2, holds keys hashing to 00)
  01 → Bucket B  (ℓ=2)
  10 → Bucket C  (ℓ=2)
  11 → Bucket D  (ℓ=2)

Directory (g=3):
  000 → Bucket A   (ℓ=3, keys hashing to 000)
  001 → Bucket B   (ℓ=2, pointer copied from old 01)
  010 → Bucket C   (ℓ=2, pointer copied from old 10)
  011 → Bucket D   (ℓ=2, pointer copied from old 11)
  100 → Bucket A'  (ℓ=3, new bucket for keys hashing to 100)
  101 → Bucket B   (ℓ=2, same pointer as 001)
  110 → Bucket C   (ℓ=2, same pointer as 010)
  111 → Bucket D   (ℓ=2, same pointer as 011)

Linear Hashing

Linear hashing avoids the directory entirely. Splits occur in a fixed round-robin order controlled by a split pointer \( p \). When overall load factor exceeds a threshold, bucket \( p \) is split using a secondary hash function, and \( p \) advances. A query uses \( h(k) \bmod 2^r \); if the result is less than \( p \), use \( h(k) \bmod 2^{r+1} \). This gives amortized \( O(1) \) operations.

The elegance of linear hashing lies in the fact that directory doubling — the expensive operation in extendible hashing — never occurs. Instead, the number of buckets grows smoothly, one bucket at a time. However, a query may require checking a small number of overflow pages if the split pointer has not yet reached the bucket that should have been split to accommodate a particular key. Linear hashing is therefore preferred in environments with very large numbers of buckets (where directory doubling in extendible hashing would be expensive) or in environments where uniform growth is more important than instantaneous point-query optimality.

Chapter 4: Query Evaluation — Iterators and Join Algorithms

A query plan is a tree of relational operators. The key design question is: how do operators communicate, and how much memory does each require? The iterator model answers the first question; the choice of join algorithm answers the second.

The Iterator (Volcano) Model

Every physical operator implements three methods:

open()   -- initialize state, recursively open children
next()   -- produce the next output tuple (returns EOF when done)
close()  -- release resources, recursively close children

The root of the plan tree is called next() repeatedly by the client. Each call pulls one tuple up through the tree. This pull-based pipelining means that most operators never materialize their entire output to disk — data flows tuple-by-tuple through the pipeline. The main exception is operators that need to see all input before producing any output (blocking operators): sort, hash join build phase, aggregation.

Selection and Projection

Selection applies a predicate to each tuple from its child and calls next() again if the predicate fails. Cost equals the child’s output cost — no additional I/O.

Projection emits only the requested attributes. Duplicate elimination requires either sorting (to bring duplicates adjacent) or hashing (to detect duplicates). Both approaches add \( O(N) \) I/O for large inputs.

Nested Loop Join

Let \( R \) have \( P_R \) pages and \( S \) have \( P_S \) pages.

Simple NLJ: for each tuple of \( R \) (outer), scan all of \( S \) (inner). Cost: \( P_R + |R| \cdot P_S \) — one full scan of \( S \) per outer tuple. Prohibitively expensive.

Block NLJ: load a chunk of \( B-2 \) pages from \( R \) into memory (using \( B-2 \) buffer frames, one for the inner scan, one for output). Scan \( S \) once per chunk. Cost:

With \( B = 102 \) and \( P_R = 1000 \), this is \( 1000 + 10 \cdot P_S \) instead of \( 1000 + |R| \cdot P_S \).

Index NLJ: if \( S \) has an index on the join attribute, for each outer tuple probe the index to find matching inner tuples. Cost: \( P_R + |R| \cdot (\text{index traversal cost}) \). Extremely efficient when \( R \) is small and the index is clustered.

Sort-Merge Join (SMJ)

SMJ first sorts both inputs on the join attribute, then merges them in a single scan. Because matching tuples are adjacent after sorting, each page of each input is read at most once during the merge (assuming no large groups of equal keys).

Cost (simple case): \( 2(P_R + P_S) \) to sort both inputs (two-pass, see Chapter 5) plus \( (P_R + P_S) \) for the merge pass. Total: \( 3(P_R + P_S) \).

SMJ handles range join conditions (e.g., \( R.a \leq S.b \)) and produces output sorted on the join key, which can be exploited by a parent ORDER BY or merge join.

Hash Join

Hash join exploits the fact that only tuples with the same hash value can join.

Build phase: apply hash function \( h_1 \) to both \( R \) and \( S \) to partition each into \( B-1 \) buckets written to disk. Corresponding buckets of \( R \) and \( S \) can only contain matching tuples.

Probe phase: for each of the \( B-1 \) bucket pairs, load the \( R \)-bucket into a hash table using a second hash function \( h_2 \), then probe with each tuple from the \( S \)-bucket. Tuples that hash to the same \( h_2 \) value are join candidates; compare on the actual attribute.

Cost (assuming each partition fits in memory for the probe phase):

The requirement is that each partition fits in \( B \) pages, i.e., \(\frac{P_R}{B-1} \leq B\), or \( P_R \leq B^2 \).

Hybrid hash join keeps one partition entirely in memory during the build phase, saving one write and read for that partition.

Join Algorithm Comparison

Chapter 5: External Sorting and Other Operators

Sorting is foundational to query processing: it enables sort-merge join, sort-based aggregation, duplicate elimination, ORDER BY, and certain index builds. When the input does not fit in memory, external sort-merge is required.

Two-Pass External Sort-Merge

Assume \( B \) buffer pages are available. The input has \( N \) pages.

Pass 0 (run generation): repeatedly read \( B \) pages into memory, sort them, and write the sorted run to disk. This produces \( \lceil N/B \rceil \) runs, each of length \( B \) pages.

Pass 1 (merge): merge up to \( B-1 \) runs simultaneously using a priority queue (one frame per run, one output frame). A two-pass sort (one pass-0 plus one pass-1) handles inputs up to \( B \cdot (B-1) \approx B^2 \) pages.

In general, the number of merge passes needed is \( \lceil \log_{B-1}(\lceil N/B \rceil) \rceil \), and the total I/O cost is:

(factor of 2 for each pass because every page is read and written once).

Replacement Sort

Instead of sorting each \( B \)-page chunk in isolation, replacement sort maintains a priority queue of all \( B \) pages. Output the minimum key; when a new record is read, if its key is \( \geq \) the last output, add it to the current run; otherwise hold it for the next run. This produces runs of expected length \( 2B \) (for random input), halving the number of initial runs and reducing merge passes.

The factor of 2 for random input is a classic result from the theory of sorting: with a priority queue of \( B \) records fed from a random stream, the expected run length is \( 2B \) because at any point in time, roughly half the records in the heap are eligible for the current run (their key exceeds the last output) and half are deferred to the next run. For real-world data that is partially sorted (e.g., time-series data with nearly-increasing timestamps), runs can be far longer — sometimes covering the entire input if the data arrives in sorted order. This makes replacement sort particularly effective for sorting nearly-sorted data, where it degenerates to a single pass with no merge needed.

Aggregation and Duplicate Elimination

Sort-based aggregation: sort on the GROUP BY attributes; then scan once, maintaining running aggregates and emitting a result whenever the group key changes. Cost dominated by the sort.

Hash-based aggregation: partition on the GROUP BY attributes using \( h_1 \) (same as hash join build phase). For each partition, build an in-memory hash table and aggregate. Requires that each partition fits in memory. Cost: \( 3N \) I/Os (similar to hash join).

DISTINCT is duplicate elimination — identical to aggregation with no aggregate function. The same sort-based or hash-based approaches apply.

Set Operations

Union: sort both inputs, merge (output all tuples, skip duplicates). Or hash-partition both, then process bucket pairs.

Intersection and Difference: sort-merge or hash-based, same cost structure as sort-merge join with an equality predicate. \( \text{Cost} \approx 3(P_R + P_S) \).

Outer Joins via Sort-Merge

Left outer join: perform sort-merge join; for each outer tuple with no match, emit it padded with NULLs. Full outer join: both unmatched sides get NULL-padded output. Sort-merge naturally handles this since unmatched tuples are detected during the merge scan.

Hash join can also handle outer joins with a minor modification: during the probe phase, track which build-side tuples were matched. After the probe is complete, any unmatched build-side tuples (for right outer joins) are emitted with NULL-padded probe-side attributes. This requires one additional bit per build-side tuple in the hash table, adding negligible memory overhead. Left outer hash join does not need this tracking — any probe-side tuple that finds no match in the hash table is immediately emitted with NULLs, during the probe pass itself.

Chapter 6: Query Optimization

Query optimization is the process of choosing, from the large space of equivalent execution plans, the one with lowest estimated cost. It is one of the most complex components of a DBMS and the primary reason why declarative SQL outperforms hand-written procedural code in practice.

Relational Algebra Equivalences

The optimizer rewrites the algebraic tree using equivalences before enumerating plans:

• Cascade of selections: \( \sigma_{\theta_1 \land \theta_2}(R) \equiv \sigma_{\theta_1}(\sigma_{\theta_2}(R)) \)
• Commutativity of join: \( R \bowtie S \equiv S \bowtie R \)
• Associativity of join: \( (R \bowtie S) \bowtie T \equiv R \bowtie (S \bowtie T) \)
• Pushing selections down: apply \( \sigma \) as early as possible to reduce intermediate result sizes
• Pushing projections down: project away unneeded attributes early to reduce tuple width

Join commutativity and associativity mean that for \( n \) relations there are \( \frac{(2(n-1))!}{(n-1)!} \) distinct join orderings — for \( n = 10 \) this exceeds 17 million. Enumeration must be pruned.

The System R (Selinger) Optimizer

The System R optimizer (Selinger et al., 1979) uses dynamic programming over left-deep join trees (trees where every right child is a base relation, never an intermediate result). Left-deep trees enable pipelining: the inner relation is always a base-table scan or index scan, not a materialized intermediate.

DP subproblem: for each subset \( S \) of relations, find the cheapest plan for joining them. Build up from single relations to all \( n \) relations. The key insight: the best plan for \( S \) depends only on cost and interesting orders — sort orders on \( S \)’s output that might benefit a parent operator (e.g., for ORDER BY or a downstream merge join). Plans producing the same result with the same interesting order but higher cost are pruned.

Cost Estimation

Cost estimation requires predicting:

1. Cardinality of each intermediate result
2. Selectivity of each predicate

For a predicate \( A = v \), selectivity is estimated as \( 1/V(R, A) \) where \( V(R, A) \) is the number of distinct values of \( A \) in \( R \) (stored in the catalog). For a range predicate \( A \leq v \), selectivity is \( (v - \min_A)/(\max_A - \min_A) \).

Histograms (equi-width or equi-depth) store the value distribution of an attribute and yield more accurate estimates than assuming uniform distribution. PostgreSQL stores histograms in pg_statistic and updates them via ANALYZE.

A fundamental limitation is the independence assumption: the selectivity of a conjunction \( \theta_1 \land \theta_2 \) is estimated as \( \text{sel}(\theta_1) \times \text{sel}(\theta_2) \). When attributes are correlated (e.g., city and zip code), this dramatically underestimates the true selectivity.

Modern systems address correlated attributes via multi-dimensional histograms or machine learning-based cardinality estimators. PostgreSQL 10 introduced extended statistics (CREATE STATISTICS), which allows the DBA to declare that two or more columns are correlated; PostgreSQL then computes a joint MCV list and a joint histogram for conjunctive selectivity estimation. Even with these improvements, cardinality estimation remains the hardest unsolved problem in query optimization: a 2019 study by Leis et al. (“How Good Are Query Optimizers, Really?”) showed that PostgreSQL’s cardinality estimates for multi-join queries are off by a factor of \(10^3\) or more in 20% of benchmark cases, leading to suboptimal join orders.

Access Path Selection

For each base relation, the optimizer chooses between:

• Full heap scan: reads all \( N \) pages sequentially; cost \( = N \).
• Clustered index scan: if a predicate matches the leading index column; cost \( \approx \text{sel} \times N \) pages.
• Unclustered index scan: cost can be up to \( \text{sel} \times |R| \) random I/Os; beneficial only for very selective predicates.
• Index-only scan: if all referenced attributes are in the index; no heap I/O needed.

The access path decision interacts subtly with multi-column predicates. If a table has a B+-tree index on \((A, B)\), the index is useful for predicates on \(A\) alone, or on \((A, B)\) together, but not for predicates on \(B\) alone — because B is not the leading key. PostgreSQL’s planner handles this with a bitmap index scan: it evaluates multiple indexes on different attributes, constructs a bitmap of matching page IDs from each, ANDs (or ORs) the bitmaps, and then fetches only the pages identified by the result. This allows a conjunction of two selective predicates on different indexed attributes to be answered without a full scan, even though neither index alone fully evaluates the conjunction.

Plan Enumeration Frameworks

The Cascades/Volcano framework (used in SQL Server, DB2) uses a memo structure and top-down search with memoization. Transformation rules rewrite logical operators; implementation rules map logical to physical operators. Rules fire lazily and prune via cost bounds.

PostgreSQL uses the Selinger-style bottom-up DP for \( \leq 12 \) relations, then switches to a genetic algorithm (GEQO) for more, because the search space is too large for exhaustive DP.

Query Reformulation

View expansion: inline the view definition into the query before optimization.

Subquery flattening: convert correlated subqueries (EXISTS, IN) to semi-joins or joins. For example:

becomes a semi-join \( R \ltimes_{R.a = S.a} S \), which can be executed as a hash join that emits at most one copy of each \( R \)-tuple.

Magic sets: for recursive queries (e.g., transitive closure), magic-sets rewriting pushes bindings from the query into the recursive computation to avoid computing the full closure.

Chapter 7: Transactions and Concurrency Control

Concurrency is essential for throughput, but concurrent execution of transactions can corrupt data. The theory of concurrency control answers the question: which interleaving of operations is safe?

ACID Properties

The four ACID properties are enforced by different DBMS subsystems. Atomicity is enforced by the recovery manager via undo logging: if a transaction aborts (voluntarily or due to deadlock detection), the recovery manager rolls back all its writes using the before images in the log. Consistency is enforced partly by the DBMS (integrity constraints, foreign key checks at commit time) and partly by the application (business logic invariants). Isolation is enforced by the concurrency control manager (2PL, MVCC, or OCC). Durability is enforced by the recovery manager via redo logging: after a crash, committed writes are replayed from the log.

Serializability

A schedule is an interleaving of operations from multiple transactions. A schedule is serial if no two transactions interleave. A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Two operations conflict if they access the same data item and at least one is a write.

The conflict graph (precedence graph) has a node per transaction and an edge \( T_i \to T_j \) if an operation of \( T_i \) conflicts with a later operation of \( T_j \). A schedule is conflict-serializable if and only if its conflict graph is acyclic.

Isolation Anomalies and Levels

A dirty read occurs when a transaction reads a value written by an uncommitted transaction. A non-repeatable read occurs when a transaction re-reads a value and finds it changed (by a committed transaction). A phantom read occurs when a transaction re-executes a range query and finds new tuples inserted by another committed transaction.

Two-Phase Locking (2PL)

2PL is the dominant protocol for conflict serializability. A transaction has two phases:

1. Growing phase: may acquire locks, may not release any.
2. Shrinking phase: may release locks, may not acquire any.

Theorem: any schedule generated by 2PL is conflict-serializable.

Lock modes and compatibility:

Multi-granularity locking (MGL) allows locking at the level of database, table, page, or tuple. Before acquiring an S or X lock on a node, the transaction must hold an intention lock (IS or IX) on all ancestors. The SIX lock (S + intention exclusive) is useful for transactions that scan a table but update some tuples.

Strict 2PL releases all locks only at commit or abort. This prevents cascading aborts (where a transaction must be rolled back because it read a value written by an aborted transaction) and is the standard used in practice.

The distinction between plain 2PL and strict 2PL matters in failure scenarios. Under plain 2PL, T1 may release its X-lock on A immediately after finishing its writes, while still holding other locks. T2 can then read A (now with T1’s value) before T1 commits. If T1 subsequently aborts, T2 has read a value that never committed — a dirty read — and T2 must also be aborted to maintain consistency. This cascading abort can ripple through many transactions. Strict 2PL prevents this by ensuring no transaction reads another’s uncommitted writes: all locks are held until commit or abort, so the only values readable are those of committed transactions. The price is reduced concurrency — transactions block on locked data longer — but the operational simplicity of never experiencing cascading aborts makes strict 2PL universally preferred in production systems.

Deadlock

Deadlock occurs when two or more transactions each hold a lock the other needs. Detection: maintain a wait-for graph; a cycle indicates deadlock. The DBMS selects a victim (usually the youngest or cheapest to restart) and aborts it.

Prevention: assign timestamps at transaction start. Under Wait-Die, an older transaction waits; a younger one aborts (dies). Under Wound-Wait, an older transaction forces the younger to abort (wounds it); a younger transaction waits.

Multi-Version Concurrency Control (MVCC)

MVCC maintains multiple versions of each data item, tagged with transaction IDs. Readers access a consistent snapshot without acquiring read locks, so they never block writers and writers never block readers.

In PostgreSQL, each tuple has xmin (the ID of the transaction that created it) and xmax (the ID of the transaction that deleted or updated it, or 0 if current). A transaction with snapshot \( T \) sees a tuple if \( \text{xmin} \leq T \) and \( (\text{xmax} = 0 \) or \( \text{xmax} > T) \). Old versions accumulate; the VACUUM process reclaims space occupied by versions no longer visible to any active transaction.

Optimistic Concurrency Control (OCC)

OCC assumes conflicts are rare. Each transaction proceeds in three phases:

1. Read phase: execute, keeping a read set and write set in private workspace.
2. Validation phase: check that the read set has not been modified by a concurrent committed transaction (certification).
3. Write phase: if validation succeeds, apply writes; otherwise restart.

OCC avoids locking overhead and is effective for read-heavy, low-contention workloads.

Chapter 8: Crash Recovery and ARIES

Crash recovery ensures that committed transactions survive failures and aborted transactions leave no trace — i.e., it enforces Atomicity and Durability. The ARIES algorithm (Mohan et al., 1992) is the most influential recovery algorithm and underlies recovery in IBM DB2, Microsoft SQL Server, and PostgreSQL.

Failure Model

• Transaction abort: voluntary or due to deadlock; must undo writes.
• System crash: power failure or OS crash; RAM is lost, disk is intact. Must redo committed writes and undo uncommitted writes.
• Media failure: disk is destroyed; requires archived backup plus log replay.

Write-Ahead Logging (WAL)

The fundamental rule of crash recovery: before a dirty page is written to disk, the log record(s) describing that change must be written to disk first (the redo rule). Additionally: before a transaction commits, all its log records must be written to disk (the commit rule). This is write-ahead logging.

Each log record contains:

• LSN (Log Sequence Number): a monotonically increasing identifier assigned to each record.
• TransId: the transaction that made the change.
• PageId: the affected page.
• PrevLSN: the LSN of the previous log record of this transaction (forms a per-transaction chain).
• Type: UPDATE, COMMIT, ABORT, CLR, BEGIN_CHECKPOINT, END_CHECKPOINT.
• Before image and after image (for UPDATE records).

Each data page stores the pageLSN: the LSN of the most recent log record that modified this page. During redo, if a page’s pageLSN \( \geq \) the LSN of a log record, the update has already been applied and is skipped.

ARIES: Three Phases

ARIES recovery proceeds in three phases after a crash:

Analysis Phase

Starting from the most recent checkpoint record, scan the log forward to the end. Maintain:

• Active Transaction Table (ATT): transactions that were in progress at the crash, with their last LSN and status.
• Dirty Page Table (DPT): pages that were dirty at crash, with their recLSN (the LSN of the first log record that dirtied the page — the earliest point from which redo is needed).

The redo start point is \( \min(\text{recLSN}) \) over all entries in the DPT.

Redo Phase

Starting from the redo start point, replay every update log record encountered, whether the transaction committed or not. The principle is repeating history: reconstruct the exact pre-crash database state. For each UPDATE record with LSN \( l \):

• If the page is not in the DPT, skip (it was flushed to disk before the crash and is up to date).
• If the page is in the DPT with \( \text{recLSN} > l \), skip.
• Otherwise, fetch the page. If \( \text{pageLSN} \geq l \), skip. Otherwise apply the update and set \( \text{pageLSN} = l \).

Undo Phase

All transactions in the ATT with status “in-progress” at crash end are losers and must be rolled back. Process their log records in reverse order of LSN (using the prevLSN chains). For each update to undo, write a Compensation Log Record (CLR) — a redo-only record that records the undo action and sets a undoNextLSN field pointing to the next record to undo for that transaction. CLRs are never undone themselves, making recovery idempotent: if the system crashes again during recovery, redo will replay the CLRs and undo will resume from the correct point.

Checkpointing

A fuzzy checkpoint allows normal processing to continue while checkpointing. The DBMS writes a BEGIN_CHECKPOINT record, then writes an END_CHECKPOINT record containing the current ATT and DPT. No pages need to be flushed. After the END_CHECKPOINT is stable on disk, the log can be truncated up to \( \min(\text{recLSN in DPT}) \). The analysis phase at recovery starts from the most recent BEGIN_CHECKPOINT.

The purpose of checkpointing is to bound the length of log replay on restart. Without checkpointing, recovery must replay the entire log from the beginning of time — potentially hours or days of log records. With periodic checkpointing (e.g., every 5 minutes), recovery at most replays 5 minutes of log. The trade-off is the I/O cost of writing the ATT and DPT to disk at checkpoint time, and the CPU overhead of tracking dirty pages and active transactions. In practice, most production systems checkpoint every 1–5 minutes, balancing recovery time against ongoing overhead.

Recovery Correctness

ARIES guarantees correctness by the combination of two principles:

1. Repeating history in the redo phase ensures that even uncommitted writes are re-applied, reconstructing the exact pre-crash state before beginning undo. This avoids the errors of “undo-only” and “redo-only” approaches.
2. CLR idempotency ensures that if a crash occurs during recovery itself, a second recovery run produces the same result without re-undoing already-undone work.

The “repeating history” principle may seem counterintuitive: why redo the writes of uncommitted (loser) transactions before undoing them? The reason is that undo operations are not reversible in general — you cannot simply “skip” a loser transaction’s writes during redo without knowing the exact sequence of writes by other transactions that may have depended on them. By first replaying the entire log (including loser writes), ARIES reconstructs the exact database state that existed at the time of the crash. Only then does it undo the losers, which is now safe because the database is in a known, deterministic state.

Chapter 9: Parallel and Distributed Databases

As data volumes exceed what a single machine can store or process, parallelism becomes essential. Parallel databases achieve high throughput by distributing work across multiple processors or nodes.

Parallel DBMS Architectures

Shared-nothing (MPP) scales best because there is no single bottleneck resource. All inter-node communication is via explicit message passing. The challenge is distributing data and workload evenly.

Data Partitioning

Data is partitioned across nodes so that each node holds a fraction:

• Round-robin: distribute tuples cyclically across nodes. Perfectly balanced, but no partition pruning — all nodes must participate in every query.
• Hash partitioning: assign tuple to node \( h(\text{key}) \bmod N \). Enables partition pruning for equality predicates; all tuples with the same key land on the same node (needed for parallel hash join without repartitioning).
• Range partitioning: assign ranges of key values to nodes. Enables range predicate pruning and range scans on one or a few nodes. Vulnerable to data skew if key distribution is non-uniform.

Data Partitioning

Data is partitioned across nodes so that each node holds a fraction:

• Round-robin: distribute tuples cyclically across nodes. Perfectly balanced, but no partition pruning — all nodes must participate in every query.
• Hash partitioning: assign tuple to node \( h(\text{key}) \bmod N \). Enables partition pruning for equality predicates; all tuples with the same key land on the same node (needed for parallel hash join without repartitioning).
• Range partitioning: assign ranges of key values to nodes. Enables range predicate pruning and range scans on one or a few nodes. Vulnerable to data skew if key distribution is non-uniform.

Parallel Query Execution

A parallel query plan introduces exchange operators between tree nodes:

• Gather: collect tuples from multiple workers into one stream.
• Repartition: redistribute tuples across nodes/threads using hash or range partitioning on a specified attribute (needed to co-locate matching tuples for a parallel hash join).
• Broadcast: send all tuples from one partition to all other partitions (for small dimension tables in a star join).

Intra-query parallelism runs a single query faster by splitting work among multiple workers. A parallel hash join partitions both inputs across \( k \) workers; each worker performs a local hash join on its shard. Speedup is ideally \( k \); in practice, skew and synchronization overhead reduce it.

MapReduce

MapReduce (Hadoop) is a batch-processing paradigm for large-scale data:

1. Map: each input record emits zero or more (key, value) pairs.
2. Shuffle: the runtime groups all emitted pairs by key, distributing them to reducers.
3. Reduce: for each key, process the list of values and emit aggregate results.

MapReduce provides automatic fault tolerance (restart failed tasks) and is easy to program. However, it lacks a query optimizer, requires materializing intermediate results between stages, and does not support fine-grained concurrency control. Modern systems (Spark, Flink) replace HDFS materialization with in-memory pipelining.

Distributed Commit: 2PC

When a transaction spans multiple nodes, all must agree to commit or abort. Two-Phase Commit (2PC):

1. The coordinator sends PREPARE to all participants.
2. Each participant writes a prepare log record, acquires all needed locks, and votes YES or NO.
3. If all votes are YES, the coordinator writes a COMMIT log record and sends COMMIT to all. If any vote is NO, the coordinator sends ABORT.
4. Participants apply the decision and release locks.

The weakness of 2PC is blocking: if the coordinator crashes after sending PREPARE but before sending the decision, participants are stuck holding locks until the coordinator recovers. Three-Phase Commit (3PC) adds a pre-commit phase to eliminate this blocking in the absence of network partitions, but is rarely used in practice due to added latency.

Distributed Query Processing

A distributed query must decide whether to ship data (move data from remote node to local for processing) or ship query (send the query fragment to the data). Shipping data is expensive over wide-area networks. Semi-join reduction reduces the data shipped: before joining \( R \) on node 1 with \( S \) on node 2, ship the join-key projection of \( S \) to node 1, compute the semi-join to filter \( R \), then ship only the filtered \( R \) tuples to node 2. If \( S \) is highly selective, this saves significant bandwidth.

Chapter 10: Decision Support and Advanced Topics

OLTP workloads consist of many short read-write transactions; OLAP (decision support) workloads consist of complex analytical queries scanning large fractions of the database. Optimizing for both simultaneously is difficult, and modern systems often specialize.

Star Schemas and Decision Support

A star schema consists of a central fact table (e.g., sales transactions) surrounded by dimension tables (e.g., product, customer, date, store). The fact table is typically very large (billions of rows); dimension tables are smaller. A snowflake schema normalizes dimension tables further (e.g., date → month → quarter → year), at the cost of more joins.

Queries on star schemas typically filter on dimension attributes and aggregate fact measures. Bitmap indexes are effective on dimension foreign keys because the bit-AND of multiple bitmap indexes efficiently evaluates multi-dimensional filter conditions without reading the fact table.

SELECT SUM(s.revenue)
FROM Sales s
JOIN Product p ON s.prod_id = p.prod_id
JOIN Customer c ON s.cust_id = c.cust_id
JOIN Date d ON s.date_id = d.date_id
WHERE p.category = 'Electronics'
  AND c.country = 'Canada'
  AND d.quarter = 'Q4' AND d.year = 2024;

Materialized Views

A materialized view is a precomputed query result stored as a physical table. For example, a daily sales aggregation query can be answered in milliseconds from a materialized view rather than minutes from the raw fact table.

View maintenance keeps the materialized view current as the base data changes. Recomputation is simple but expensive. Incremental maintenance applies the delta of changes (insertions and deletions) to the view using the delta rule. For a view \( V = R \bowtie S \):

The lattice of views generalizes this: multiple materialized views can be organized by the coarseness of their aggregation, and finer-grained views can be answered from coarser ones by further aggregation.

Column Stores and Compression

Column stores (e.g., Vertica, ClickHouse, DuckDB) store each column in a separate file, sorted by a chosen sort key. This enables:

• Projection pruning: read only the columns referenced by the query.
• Vectorized execution: process a batch of values from a single column using SIMD CPU instructions.
• Aggressive compression: values in a column are of the same type and often highly regular.

The interaction between compression and vectorized execution is particularly powerful. Consider a region column in a sales table with 10 million rows and only 5 distinct values (North, South, East, West, Central). Dictionary encoding maps each distinct value to a 3-bit integer (since \(\lceil \log_2 5 \rceil = 3\)), compressing the column by 10× compared to storing each string directly. A predicate WHERE region = ‘North’ evaluates against the dictionary (cost: 1 comparison) and produces a 3-bit integer code; then the compressed column is scanned with bitwise comparisons against the code — processing 64 values per 192-bit SIMD register in a single CPU instruction cycle. The query runs without ever decompressing the column, achieving both space savings and faster execution than the uncompressed case.

Common compression schemes:

Queries can often operate directly on compressed data without decompressing first.

In-Memory Databases

When the entire working set fits in RAM, the buffer manager becomes unnecessary overhead. Systems like VoltDB, H-Store, and HyPer eliminate it entirely. The DBMS manages memory directly and logs only to disk for durability. Because data is never lost on a controlled shutdown, redo logging for data pages is not needed — only undo logging (or MVCC snapshots) is needed for transaction isolation.

HyPer uses MVCC with hardware transactional memory and morsel-driven parallelism: the relation is divided into fixed-size morsels (chunks of \(\approx\) 10,000 tuples); worker threads dynamically steal morsels from a global work queue, achieving adaptive load balancing.

Modern Trends

NewSQL systems (CockroachDB, TiDB, Google Spanner) provide full ACID guarantees with horizontal scalability. Spanner uses TrueTime (GPS + atomic clock timestamps) to implement external consistency across globally distributed nodes.

Cloud-native databases (Amazon Aurora, Snowflake, Azure Synapse) separate storage from compute: the storage layer is replicated object storage (S3 or equivalent); compute nodes are stateless and can be elastically scaled. Aurora uses a redo-log-only protocol — only log records are shipped from the compute layer to the storage layer, reducing write amplification.

Vectorized execution (pioneered in MonetDB/X100 and adopted in DuckDB) processes data in batches of 1,024–8,192 values per operator call rather than one tuple at a time. This dramatically reduces interpretation overhead and enables SIMD parallelism within each batch.

Chapter 11: Query Optimization — Deeper Dive

The cost estimation discussion in Chapter 6 left open several questions: how exactly are join cardinalities estimated when values are non-uniformly distributed, how do the three principal join algorithms compare across a concrete I/O model, and what happens when the optimizer’s estimates are wrong at execution time?

Selectivity Estimation for Joins

The key quantity that drives every join-order decision is the join selectivity: the fraction of the Cartesian product \(R \times S\) that survives the join predicate. For an equi-join on attribute \(A\),

where \(V(R,A)\) is the number of distinct values of \(A\) in \(R\). This formula assumes uniformity and independence — neither of which holds in practice.

For a point predicate \(A = v\), the optimizer locates the bucket containing \(v\) and estimates the selectivity as \(1 / V_{\text{bucket}}\), where \(V_{\text{bucket}}\) is the number of distinct values in that bucket. For a join predicate \(R.A = S.A\), matching histogram buckets are compared: bucket \(i\) of \(R\) overlaps bucket \(j\) of \(S\) only on the overlapping value range, and the contribution to join cardinality is estimated as \((\text{count}_i \times \text{count}_j) / \max(V_i, V_j)\) for each overlapping pair, then summed.

I/O Cost Formulas for Join Algorithms

Let \(B(R)\) denote the number of pages of relation \(R\), \(B(S)\) the pages of \(S\), and \(B\) the number of available buffer pages. The three principal join algorithms compare as follows.

Adaptive Query Processing

Even the best cardinality estimates can be wrong by orders of magnitude for multi-join queries with correlated predicates. Adaptive query processing reacts to estimation errors at runtime.

The eddies framework (Avnur and Hellerstein, 2000) routes tuples through operator pipelines dynamically, steering tuples toward operators that are currently most selective and least congested. The routing policy is updated by observing the output rate of each operator.

A simpler production technique is re-optimization: execute the plan up to the first operator with high uncertainty (e.g., a join), materialize the intermediate result, measure its actual cardinality, and if the measured cardinality differs from the estimate by more than a threshold (e.g., 10×), re-invoke the optimizer with the corrected statistic to plan the remainder of the query. PostgreSQL 14 added incremental sort as a mild form of this; CockroachDB and SQL Server perform full mid-query re-optimization.

Chapter 12: Concurrency Control — Full Protocols

The brief MVCC and OCC introductions in Chapter 7 merit deeper treatment. This chapter gives the complete protocol for each, then compares their throughput profiles.

MVCC: Complete Protocol

In a full MVCC system, every write operation creates a new version of the modified tuple rather than overwriting the old one. The version chain is stored either in a separate delta store (as in SQL Server) or inline in the heap using the slot mechanism (as in PostgreSQL).

The most important property of MVCC is that readers never block writers and writers never block readers. This is the key advantage over 2PL for read-heavy OLTP workloads: a long-running read transaction (e.g., a reporting query) does not hold any locks, so concurrent write transactions proceed without blocking. The cost is version storage: every write creates a new version, and VACUUM must periodically reclaim old versions. On write-heavy tables with many updates, the version chain can grow long, requiring sequential chain traversals for reads — the tuple bloat problem.

Serializable Snapshot Isolation (SSI)

Snapshot isolation prevents dirty reads and non-repeatable reads but allows write skew: two transactions each read a set of tuples and then write to different tuples in a way that jointly violates a constraint, even though neither write conflicts directly with the other’s read.

Serializable Snapshot Isolation (SSI), introduced by Cahill et al. (2008) and implemented in PostgreSQL since version 9.1, detects write skew by tracking rw-anti-dependencies. A rw-anti-dependency from \(T_1\) to \(T_2\) exists when \(T_1\) reads a version that \(T_2\) subsequently writes (without \(T_1\) seeing \(T_2\)’s write, because \(T_2\) started after \(T_1\)’s snapshot). SSI tracks these edges in a conflict graph; if a cycle of the form \(T_1 \xrightarrow{rw} T_2 \xrightarrow{rw} T_3\) (with \(T_3 = T_1\) in the simplest case) is detected at commit time, one transaction is aborted.

Chapter 13: Recovery — ARIES in Full Detail

Chapter 8 gave a worked example of ARIES recovery. This chapter provides a complete LSN-level trace to make each phase concrete.

Worked ARIES Log Sequence Example

Chapter 14: Columnar Storage and Modern OLAP

The DSM discussion in Chapter 2 introduced the idea of column-oriented storage. This chapter develops the compression techniques and execution model that make modern OLAP systems an order of magnitude faster than row-store alternatives.

Compression Schemes in Detail

Column data exhibits patterns that general-purpose compressors (gzip, LZ4) cannot exploit at query time because they require decompression before processing. Column-specific schemes maintain the data in a form that the query engine can operate on directly.

Late vs. Early Materialization

In a column store executing a query like SELECT name, salary FROM Employees WHERE dept = 'Eng', there are two strategies for combining the results of the column scans.

Early materialization: immediately after evaluating the predicate on the dept column (producing a set of row positions), fetch the name and salary values for those positions and assemble full tuples. All subsequent operators work on complete tuples — the familiar row-store model. Simple but wastes effort if additional predicates further filter the result.

Late materialization: propagate only the position vector (a list of matching row indices) through the operator pipeline. Fetch actual column values only at the last possible moment, just before the final projection. Each operator in the pipeline works on position vectors and compressed column data. For a query with three predicates, late materialization avoids fetching name and salary for rows that are filtered out by the second or third predicate.

Vectorized Execution on Compressed Columns

Vectorized execution processes batches of 1,024–8,192 values. Combined with dictionary encoding, the inner loop of a selection operator compares 64-bit words (each holding multiple packed codes) against a bitmask derived from the dictionary lookup. On a modern CPU with 256-bit AVX2 registers, 32 one-byte codes can be compared in a single instruction — achieving effective throughput of \(32 \times \text{clock frequency}\) comparisons per second.

Dremel Nested Data Model

Google’s Dremel (Melnik et al., 2010) extends columnar storage to nested and repeated fields — the data model underlying Protocol Buffers, Parquet, and ORC. A nested record like {name: "Alice", address: {city: "Waterloo", zip: "N2L"}} cannot be stored in a flat column without duplication or loss of structure.

Dremel encodes each leaf field in its own column, accompanied by two metadata arrays: a repetition level (how many repeated ancestor fields restarted since the previous value) and a definition level (how many nullable ancestor fields are defined rather than null). Together, these allow full reconstruction of the original nested record from the column representation, without any additional per-record length or offset information.

Chapter 15: Distributed Databases — CAP, Consistency, and Consensus

Chapter 9 treated parallel databases within a data center. This chapter addresses the harder problem of databases spanning multiple data centers or operating over unreliable networks.

CAP Theorem

Real-world systems do not face binary choices. PACELC (Abadi, 2012) extends CAP: even when there is no partition (\(P\)), a system must trade off latency (\(L\)) against consistency (\(C\)). Strong consistency requires synchronous replication — waiting for all replicas to acknowledge a write — which adds latency. Eventual consistency allows asynchronous replication — responding immediately, propagating updates later — which reduces latency but allows stale reads.

Two-Phase Commit: Coordinator Failure Scenarios

The brief 2PC description in Chapter 9 omitted the critical failure cases. Consider what happens when the coordinator fails at each point in the protocol.

Spanner’s External Consistency via TrueTime Commit Wait

The Spanner TrueTime mechanism (introduced briefly in Chapter 10) is a solution to the following problem: in a geographically distributed database, how do you assign commit timestamps that respect real-world time ordering, even across data centers with skewed clocks?

Paxos vs. Raft: A Comparison

Both Paxos and Raft are consensus protocols that allow a set of nodes to agree on a value (or a log of values) even if some nodes crash, as long as a majority remain available.

Paxos (Lamport 1989) is the theoretical foundation: a two-phase protocol (Prepare/Promise then Accept/Accepted) that is provably correct but famously difficult to implement fully — multi-Paxos, leader election, log compaction, and membership changes all require extensions not present in the original paper.

Raft (Ongaro and Ousterhout 2014) is explicitly designed for understandability. It decomposes consensus into three subproblems with clear separation: leader election, log replication, and safety. A Raft cluster elects a single leader that receives all writes, replicates them to followers, and commits once a majority acknowledge. Leader election uses randomized timeouts to avoid split votes. Raft is used in etcd, CockroachDB, TiKV, and InfluxDB.

The practical difference: Raft’s clear leader-based model makes it easier to implement correctly, at the cost of a single-leader bottleneck for write throughput. Multi-Paxos can support multi-leader configurations (though this complicates conflict resolution), potentially achieving higher write throughput at the cost of implementation complexity.

Chapter 16: Query Languages Beyond SQL

SQL is the dominant query language for relational data, but it is not expressive for all problems. Recursive queries, graph traversal, and certain deductive reasoning tasks are more naturally expressed in Datalog, a logic-based query language.

Datalog: Rules, Recursion, and Stratified Negation

Stratified negation allows Datalog rules to use negation as long as no recursive rule negates itself (a cycle through negation). Rules are stratified into layers: stratum 0 contains base facts and rules with no negation; stratum 1 contains rules that may use negated stratum-0 predicates; and so on. Queries with stratified negation are evaluated bottom-up, one stratum at a time, and are well-defined (no semantic ambiguity). Queries with unstratified negation (negation within a cycle) are not supported in standard Datalog.

Relational Division and Its SQL Encoding

Relational division \(R \div S\) answers queries of the form “find all \(X\) values in \(R\) that appear paired with every \(Y\) value in \(S\).” This is the “for all” quantifier, which SQL does not have directly — SQL uses double negation instead.

SELECT DISTINCT sid FROM Enrolled e1
WHERE NOT EXISTS (
    SELECT cid FROM RequiredCourses r
    WHERE NOT EXISTS (
        SELECT * FROM Enrolled e2
        WHERE e2.sid = e1.sid AND e2.cid = r.cid
    )
);

Chapter 17: Advanced Indexing

GiST: Generalized Search Tree Framework

The B+-tree is optimal for one-dimensional ordered data. Many applications require indexes over multi-dimensional points, geometric shapes, full-text tokens, or other structured types. GiST (Generalized Search Tree, Hellerstein et al. 1995) provides a single tree framework parameterized by a key type and a set of predicate methods (consistent, union, penalty, picksplit).

R-trees (Guttman 1984) instantiate GiST for spatial data. Each internal node stores a minimum bounding rectangle (MBR) that encloses all objects in its subtree. A spatial query (e.g., “find all restaurants within 5 km of point \(q\)”) traverses the tree top-down, pruning subtrees whose MBR does not intersect the query region. PostgreSQL implements R-trees via GiST with the PostGIS extension.

Full-Text Inverted Indexes and BM25

A full-text inverted index maps each term \(t\) to its posting list: the sorted list of document IDs (and optionally positions within each document) that contain \(t\). Queries that specify multiple terms intersect posting lists using a merge algorithm identical to sort-merge join.

TF-IDF scores a document \(d\) for query term \(t\) as:

where \(\text{tf}(t,d)\) is the term frequency (occurrences of \(t\) in \(d\)), \(N\) is the total number of documents, and \(\text{df}(t)\) is the document frequency (number of documents containing \(t\)). Rare terms (low \(\text{df}\)) receive high IDF weight.

BM25 (Robertson and Zaragoza 2009) improves on TF-IDF by accounting for document length normalization and term frequency saturation:

where \(k_1 \approx 1.2\) controls term frequency saturation, \(b \approx 0.75\) controls length normalization, \(|d|\) is the document length, and \(\text{avgdl}\) is the average document length across the corpus. BM25 is the default ranking function in Elasticsearch and PostgreSQL’s full-text search (ts_rank).

LSM-Trees: LevelDB and RocksDB

Conventional B+-trees perform random writes — a single key insertion may require a random disk seek to the leaf page. For write-intensive workloads (e.g., time-series databases, log ingestion), this random I/O is the bottleneck. The Log-Structured Merge-Tree (LSM-tree) (O’Neil et al. 1996) trades random writes for sequential writes at the cost of additional read I/O and periodic compaction.