Viva prep: the four papers

Client communications manager (connection state and protocol handling), process manager (assigns workers and does admission control), relational query processor (authorization, compilation, execution), transactional storage manager (access methods, buffer pool, lock and log managers for ACID), and shared components and utilities (catalog, memory manager, replication, backup). Introduced in Section 1.1 via the gate-agent query and shown in Figure 1.1.

It is 1:1: one worker handles all SQL from one client (Section 2, p. 151). It matters because the three process models differ only in how that worker is realized (an OS process, an OS thread, or a borrowed process from a pool), which changes memory footprint, isolation, and scalability.

Thread per worker scales better to many connections because a thread carries less state than a process and thread switches avoid switching security context, memory-manager state, and file/network handle tables. Process per worker is simpler and gets OS memory protection and tooling, but consumes more memory and switches more slowly. Both still share the buffer pool and lock table, so process isolation is partial.

Efficient, scalable OS threads were not widely available until the 1990s and varied across platforms, so for legacy, portability, and scalability reasons DBMSs implemented their own (Section 2.2.1). The main hazard is that one blocking operation blocks every thread in the process, so the package must use only asynchronous non-blocking I/O and avoid blocking OS calls, replicating OS scheduling logic inside the DBMS.

It refuses new work unless resources are available, preventing thrashing so the system degrades gracefully (latency rises with arrival rate but throughput stays at peak) (Section 2.4). It sits in two tiers: a dispatcher-level cap on connections and an execution admission controller inside the query processor that runs after parse and optimize and keys mainly on the optimizer's estimated memory footprint, since buffer-pool memory pressure is the usual cause of thrashing.

Shared memory: all processors reach the same RAM and disk at equal cost (typical 2 to 8-way servers and multi-core). Shared nothing: a cluster where no node touches another's RAM or disk, with tables horizontally partitioned. Shared disk: all processors reach the disks equally but cannot read each other's RAM (Sections 3.1 to 3.3). The terminology comes from reference [87].

Even though value-based horizontal partitioning lets nodes work independently, they must still exchange control messages for transaction completion, load balancing, distributed deadlock detection, and two-phase commit (Section 3.2). Partial failure is handled by bringing all nodes down, Informix Data Skip (run on live nodes with no well-defined semantics), or redundancy from full failover to chained declustering, under which the n-1 survivors each take n/(n-1) of the load.

Because each machine has its own buffer pool and locks with no shared memory to coordinate them, shared disk needs a distributed lock manager and a cache-coherency protocol, which are complex and can bottleneck under contention (Section 3.3). It cannot mask corruption that occurs before a page reaches storage, since all nodes then see the corrupt page and RAID replicates it.

View expansion (replace a view with its tables and predicates recursively), constant arithmetic evaluation (10+2+R.y becomes 12+R.y), logical predicate rewriting (NOT salary > 1000000 becomes salary <= 1000000, and unsatisfiable conjunctions become FALSE), semantic optimization using constraints (redundant join elimination via a non-null foreign key), and subquery flattening/normalization (Section 4.2). The rewriter uses only the query and catalog, never table data.

It optimized each SELECT-FROM-WHERE block with bottom-up dynamic programming, restricted to left-deep plans, postponed Cartesian products, and used simple cardinality-based selectivity (Section 4.3). Modern systems add bushy plans, histogram and sampling-based selectivity that handles column dependencies, top-down Cascades search as an alternative to dynamic programming, two-phase parallel optimization, and plan caching with recompilation. Both dynamic programming and top-down search remain exponential in the number of tables.

Ioannidis and Christodoulakis showed that selectivity errors early in optimization propagate multiplicatively up the plan tree, so a mistake near the leaves corrupts every estimate above it and can produce a badly wrong plan (Section 4.3, reference [45]).

Every operator subclasses an iterator with init(), get_next(), and close(), and any iterator can feed any other, so operator logic is independent of neighbors (Section 4.4). Because get_next() is an ordinary call returning a tuple via the call stack, a tuple reaches the parent exactly when control returns, so one thread runs the entire graph with no inter-operator queues or rate matching.

Parallelism and network communication are encapsulated in special exchange iterators (Graefe, reference [23]) that push data internally between partitions while still exposing the pull-style get_next() API to ordinary iterators, so the rest of the operators are unchanged (Section 4.4.1).

When a statement reads and updates the same table, pipelining an index scan into an update (for example a 10% raise for everyone under $20K) can rediscover a tuple that moved rightward in the B+-tree after being updated and update it repeatedly, violating SQL's rule that a statement cannot see its own updates (Section 4.4.3). Fixes: have the optimizer avoid indexes on the updated column, or materialize all target Record-IDs first and then fetch and update them; pipelined updates need multiversion storage. It is unrelated to the phantom problem.

A SARG is a search argument of the form column-operator-constant passed to an access method's init() (NULL means scan all); it is a System R term (Section 4.5). Pushing it down lets B+-trees work efficiently and, even for heap scans, lets the access method test predicates a page at a time, avoiding the per-tuple cost of returning a pinned tuple or copy, having the caller reject it, then unpinning or deleting and re-calling. This amortizes work across a collection for CPU savings while keeping a clean storage/relational boundary.

It reflects customer base. IBM served high-budget shops with skilled DBAs who value predictable performance, so it re-optimizes only when a plan can no longer run (for example a dropped index). Microsoft entered at the low end where customers want self-tuning, so SQL Server re-optimizes on significant cardinality changes (Section 4.3.1). The trade-off is predictability versus efficiency in a changing environment.

open, next, and close. open initializes operator state (for example allocates a hash table) and recursively opens all inputs. next produces and returns one result record at a time, calling next on inputs only when more input is needed, and signals end-of-stream when exhausted. close releases resources and recursively shuts down the inputs (Section III.B).

The consumer pulls: the root operator's next is called repeatedly, and each operator calls next on its input only when it needs another record. This is lazy evaluation, so an operator never produces more than the consumer demands, which the paper says minimizes both time overhead (operator synchronization) and space (records resident in memory at once) for single-process execution (Section III.B).

Because an operator only ever calls open-next-close on its input, it never needs to know what produces that input (anonymous streams). This lets any operators nest in any combination, lets new operators be added without touching existing ones, and lets exchange be inserted anywhere to add parallelism. Uniformity is the basis of both extensibility and the orthogonality of data manipulation and parallelism (Sections III.B, IV, VI).

A support function is an imported function entry point plus a typeless argument that performs all item-level work (predicates, hashing, comparison, projection, side effects). Volcano's iterators are empty shells without them. Because all interpretation of data items is imported, Volcano needs no instance type system and works for any data type or model, which is why a new abstract data type does not change the Volcano code at all (Introduction, Section III.A, Section IV).

A state record holds an iterator instance's arguments and runtime state, and operators are linked by input pointers stored in state records. Because all state lives in the state record and there are no static variables, an algorithm such as sort can be instantiated several times in one query by giving each occurrence its own state record (Section III.B).

SeqScan is the file-scan iterator. Filter is the filter operator's predicate function and Project is its transform function, so Volcano fuses selection, projection, and side-effect/apply into one filter operator. Join is the one-to-one match operator, with hybrid hash and sort-merge implementations whose build/probe/flush phases map onto open (build) and next (probe then flush) (Sections III.B.1, III.B.2).

All of join, semi-join, outer joins, anti-join, intersection, union, difference, anti-difference, aggregation, and duplicate elimination reduce to the same step: separate the matching and non-matching subsets of two inputs and emit selected subsets, possibly transformed (Fig. 3). Unary operations compare items within one input; binary operations compare items across two. One general module is more compact and lets the same overflow and algorithm machinery serve all of them (Section III.B.2).

Exchange encapsulates all parallelism: it forks processes, creates a shared-memory port, partitions or routes data, and drives the subtree below it as a producer while acting as an ordinary iterator to the consumer above. It is a meta-operator because it performs no data manipulation; it only provides control. Crucially it uses and provides the standard iterator interface, so the operators around it never know it is there (Section VI).

Within a process all operators use demand-driven (pull, lazy) dataflow. Between processes exchange uses data-driven (push, eager) dataflow, so it can collect output into packets and push them through the port. The two stated reasons are that data-driven flow composes more easily with horizontal partitioning and that it removes the need for request messages, which would add control overhead. Exchange translates between the two paradigms at the process boundary (Section VI.A).

No. Flow control is an optional back-pressure semaphore on the data-driven path that bounds how far producers may run ahead of consumers, allowing slack and genuinely overlapped producer/consumer execution. Demand-driven dataflow is a rigid request-and-deliver discipline in which the consumer blocks while the producer computes the next record, so there is no overlap. Flow control limits eager production; pull simply never produces ahead at all (Section VI.A).

Vertical parallelism (pipelining) between a producer process and a consumer process. Bushy parallelism, where different CPUs run different subtrees. Intra-operator parallelism, where several CPUs run the same operator on disjoint partitions. Vertical and bushy are inter-operator parallelism. Intra-operator parallelism is requested by setting the degree-of-parallelism argument in the exchange state record and supplying a partitioning support function; bushy parallelism is requested by inserting exchange operators between subtrees (Section VI.A, VI.B).

A port can hold multiple queues, one per consumer process. The producer calls a partitioning support function to decide which queue (packet) each output record goes to. By supplying different support functions you get round-robin, key-range, or hash partitioning. As elsewhere, exchange provides the mechanism and the support function provides the policy (Section VI.B).

An operator is written, debugged, and tuned in a single process and then parallelized just by inserting exchange into the plan, with no change to the operator; even operators not yet designed can be parallelized if they use the iterator interface. To port to a new parallel machine only exchange changes. The evidence cited is near-linear speedup, specifically 14.9 on 16 CPUs for parallel sorting on shared memory (Abstract, Section VII, reference [18]).

choose-plan is a meta-operator with the standard open-next-close interface that selects among several equivalent subplans at runtime. Its open calls a support function (given the bindings parameter) to pick a plan, then opens it; next and close forward to the chosen input. It is used for dynamic query evaluation plans, for example an embedded query whose predicate constant is a program variable, so the plan can switch between an index scan and a full file scan depending on the actual value (Section V).

Passing data through temporary files, as many textbooks suggest, has a substantial performance penalty and is used in neither real systems nor Volcano. Intermediate results (streams) live on virtual devices whose pages exist only in the buffer pool and disappear when unpinned, so the same file and buffer mechanisms serve both permanent and intermediate data while keeping data in memory (Introduction, Section III.A, Section III.B).

Each pinned record is owned by exactly one operator at a time. On receiving a record an operator may keep it, unfix it (for example on predicate failure), or pass it on; operators that build new records must fix their outputs and unfix their inputs. To keep buffer-call counts low, the buffer interface needs two calls per cluster on the producer side and one per cluster on the consumer side, independent of records per cluster (Section III.B).

It is a sparse, distributed, persistent, multidimensional sorted map (Section 2). The key is the triple (row:string, column:string, time:int64) and the value is an uninterpreted array of bytes. Sparse means absent cells cost nothing; sorted means rows are stored in lexicographic row-key order.

Every read or write under a single row key is atomic across any number of columns (Section 2). It does not provide general cross-row or distributed transactions in the base API; clients can only batch cross-row writes (Section 3). They deferred general transactions deliberately because most applications needed only single-row atomicity (Section 9).

The tablet server checks the mutation is well-formed and the writer is authorized (reading permitted-writers from a Chubby file, usually a cache hit), writes the mutation to the per-server commit log using group commit, and only after the commit inserts it into the in-memory sorted memtable (Section 5.3). The data is durable once the log write commits; the memtable insert just makes it readable.

A read runs over a merged view of the memtable plus the tablet's sequence of SSTables (Section 5.3). Both structures are lexicographically sorted, so the merge is an efficient merge of sorted streams. Bloom filters and the block/scan caches reduce how many SSTables actually get touched (Section 6).

Minor compaction freezes a full memtable and writes it to GFS as a new SSTable, shrinking memory and recovery cost. Merging compaction folds a few SSTables plus the memtable into one new SSTable to bound the number of files a read must merge. Major compaction rewrites all SSTables into exactly one and drops all deletion entries and deleted data, reclaiming space and ensuring timely physical deletion (Section 5.4).

Immutability means reads need no file-system locking, so row concurrency control is cheap; the only mutable shared structure is the memtable, made copy-on-write (Section 6, "Exploiting immutability"). It turns deletion into garbage collection of obsolete SSTables (mark-and-sweep with METADATA as roots), and it makes tablet splits fast because children share the parent's SSTables instead of rewriting them.

Level one is a Chubby file pointing to the root tablet; the root tablet (first METADATA tablet, never split) points to all other METADATA tablets; each METADATA tablet points to user tablets (Section 5.1, Figure 4). With ~1KB per METADATA row and 128 MB METADATA tablets, it addresses 2^34 tablets, i.e. 2^61 bytes. The root is never split precisely to cap the hierarchy at three levels.

Up to six round-trips, versus three for a cold cache (Section 5.1). Stale entries are only discovered on a miss, so the client may chase a wrong location, miss, and have to walk back up the hierarchy, doubling the worst-case path. Prefetching multiple tablets' metadata per METADATA read mitigates this.

Each tablet server holds an exclusive Chubby lock on a uniquely named file (Section 5.2). The master periodically checks lock status; if a server is unreachable or reports losing its lock, the master tries to acquire that lock and, on success, deletes the server's file so the server can never serve again, then reassigns its tablets. The master also kills itself if its own Chubby session expires, and master death does not reassign tablets, so there is no split brain.

A log per tablet would create huge numbers of concurrent GFS files, cause many disk seeks, and shrink group-commit batches (Section 6). The cost is that one log co-mingles many tablets' mutations, so recovery sorts entries by (table, row name, log sequence number) to make each tablet's mutations contiguous, parallelized over 64 MB segments coordinated by the master, avoiding re-reading the whole log once per recovering server.

Chubby ensures a single active master, stores the bootstrap location, discovers and fences tablet servers, and stores schema and ACLs (Section 4). It is five Paxos replicas, live with a majority. The risk is a hard dependency: if Chubby is unavailable long enough, Bigtable is unavailable; measured unavailability from Chubby was 0.0047% on average across 14 clusters.

A column family is the unit of access control and accounting, grouping related column keys (Section 2). A locality group groups several families that are accessed together so each group gets its own SSTable per tablet, letting a read skip groups it does not need (Section 6). A locality group can also be marked in-memory and given its own compression settings.

Each random read must fetch a full 64KB SSTable block from GFS over the network even though only a 1000-byte value is wanted; at ~1212 reads/s that is ~75 MB/s and it saturates the tablet server CPU and the network (Section 7). When scaling out, these block transfers saturate shared 1 Gbps links, so random reads scale only ~100x across 500 servers while random reads from memory scale ~300x. Apps mitigate by lowering block size to ~8KB.

Bigtable's memtable-plus-immutable-SSTable design with compaction is an LSM-tree storage engine: writes buffer in a sorted in-memory structure, flush to immutable sorted files, and reads merge memory and disk. Section 10 states explicitly that this is "analogous to the way that the Log-Structured Merge Tree [26] stores updates," citing O'Neil et al. 1996.

Durability comes from below Bigtable: GFS replicates the commit log and SSTable files, and Chubby replicates coordination state via Paxos (Section 4). Cross-cluster availability is handled above the single-cluster data plane; for example Personalized Search first used client-side eventual-consistency replication and then a server-side replication subsystem (Section 8.3), and the paper notes planned cross-data-center multi-master replication (Section 11).

A delete writes a deletion entry (tombstone) into a new SSTable that suppresses older live values during the merged read (Section 5.4). The data is only physically removed when a major compaction rewrites all SSTables into one without any deletion entries or deleted data; Bigtable cycles major compactions over all tablets so deleted data disappears in bounded time, which matters for sensitive data.

The page_LSN is the LSN of the log record describing the most recent update applied to that page (Section 4.2). It lets ARIES test, during redo, whether a logged update is already reflected on the page, so the system never redoes an effect already present and never undoes an effect not present. Without it operation logging would be unsound.

Before a dirty page is written to the durable database, the log records describing its changes (at least the undo portions) must already be on stable storage; and a transaction is not committed until its commit record and all earlier log up to that LSN are forced to stable storage (Section 1.1). The buffer manager enforces this, sometimes by forcing the log up to a page's page_LSN before stealing it.

Steal lets an uncommitted transaction's dirty page reach disk before commit, so on a crash those uncommitted changes must be undone. No-force lets a committed transaction's dirty pages stay in the buffer, so on a crash those committed changes may be missing from disk and must be redone (buffer management discussion in Section 4).

Repeating history means the redo pass reapplies every logged update whose effect did not reach disk, for all transactions including losers (Section 3). This reestablishes the exact database state as of the failure. Only then are losers undone. This guarantees ARIES never has to undo an update that is absent and never undoes-then-redoes a committed update already on disk, the failures it criticizes in other methods (Section 2).

A CLR is the log record written when ARIES undoes an update (Section 3). It is redo-only because it is never itself undone; its UndoNxtLSN points to the predecessor of the record it compensated, so once undo work is logged it is permanent and rollback proceeds forward through the remaining records to undo (Section 4.1).

UndoNxtLSN in the last-written CLR records exactly how far rollback has progressed. If a failure interrupts rollback, recovery resumes at UndoNxtLSN and skips records already undone, so no record is undone twice and no extra CLRs are generated for already-compensated work (Section 3). Contrast IMS, which can undo the same non-CLR multiple times.

Analysis scans forward from the last checkpoint, rebuilds the Transaction Table and Dirty Pages Table, identifies losers, and computes RedoLSN (Section 6.1). Redo scans forward from RedoLSN repeating history (Section 6.2). Undo scans backward rolling back losers and writing CLRs (Section 6.3).

RedoLSN is the minimum RecLSN over all entries in the Dirty Pages Table (Section 4.4 and Section 6.1). RecLSN for a page is the end-of-log LSN at the moment the page was first dirtied, marking the earliest log point whose updates might not yet be on disk. The minimum across all dirty pages is therefore the earliest point redo could matter.

Redo checks the page: it reapplies a record only if the page's page_LSN is less than the record's LSN, otherwise the update already reached disk and is skipped (Figure 11). Undo does not consult the page_LSN to decide whether to undo, because after repeating history every loser update is known to be present and must be reversed (Section 3, Section 6.3).

Logical undo means the undo of an action need not be the exact physical inverse on the same page(s) as the original. It is possible because the CLR describes what the undo actually did, so the system has a precise record independent of the original page layout (Section 3). This supports high-concurrency operations such as record-level changes that may move data across pages.

Losers are transactions that at the time of the failure had neither committed nor reached the in-doubt (prepared) state of two-phase commit (Section 3). The set is determined by the analysis pass from the Transaction Table state (Section 6.1).

It tracks the state of active transactions (Section 4.3). Key fields: TransID, State (for example prepared/in-doubt 'P' or unprepared 'U'), LastLSN (latest log record of the transaction), and UndoNxtLSN (next record to undo; taken from the last CLR's UndoNxtLSN if the latest record is a CLR, else equal to LastLSN).

System R writes the updated page to a new location and keeps the old version as a shadow for recovery; ARIES updates in place and relies on the log (Section 1.1, Figure 1). The paper argues (Section 10) that System R's logging and recovery paradigms are inappropriate in the WAL context, and that shadowing causes large space overhead and major perturbations during checkpoint and image copy.

It skips to the record identified by that CLR's UndoNxtLSN rather than processing the compensated record again (Section 3, Section 6.3). This is how the backward sweep avoids redoing undo work and how the single-sweep, max-LSN driving of multiple losers stays efficient.

The affected page's page_LSN is set to the redone log record's LSN, and nothing is logged during redo (Figure 11, Section 6.2). Logging is unnecessary because redo only repeats already-logged history.