Free Databases & data systems lessons
Storage layout and indexes from first principles
Storage engines group records into pages because devices and caches transfer blocks efficiently. A buffer manager keeps useful pages in memory. A heap file offers simple placement; a B-tree keeps keys ordered with balanced, page-sized nodes; a log-structured design turns updates into sequential writes and later compaction.
An index entry commonly stores the indexed key plus a row locator or primary key. A lookup reads index pages, finds candidate entries, and may fetch table pages to retrieve unindexed columns. A covering index includes everything the query needs, avoiding those extra lookups at the cost of a larger index and heavier writes.
Plans, cardinality, joins, and execution
The planner rewrites expressions, estimates row counts and selectivity from statistics, and compares access paths and join orders with a cost model. Execution operators form a tree or pipeline: scans produce rows, filters discard them, joins combine them, and aggregates reduce them. A wrong cardinality estimate can make a disastrous plan look cheap.
An indexed nested loop can be excellent when the outer side is small and each inner lookup is selective. A hash join can scan both inputs and match through an in-memory hash table, often better for large equality joins. If the build side spills, memory and I/O change the tradeoff.
Isolation, locking, MVCC, and invariants
Atomicity makes its writes take effect together or not at all. Isolation constrains what concurrent transactions can observe. Locks prevent conflicting access by waiting; multiversion concurrency control lets readers use snapshots while writers create versions. Neither automatically protects a business invariant unless operations and isolation are designed for it.
A reader can see the committed database as of a logical point while a writer creates a newer version. This avoids many read–write conflicts, but old versions must remain while any relevant snapshot can need them. Long transactions can therefore retain storage and delay cleanup.
Logging, recovery, replication, and failure boundaries
With write-ahead logging, relevant log records reach the durability boundary before changed data pages do. After a crash, recovery replays committed work and removes or ignores incomplete work according to the engine’s protocol. Replication creates additional copies, but acknowledgement policy decides which failures those copies can survive without losing accepted writes.
Three asynchronous replicas may all lag an acknowledged primary. A primary failure can therefore lose accepted writes despite four total copies. Quorum or synchronous acknowledgement strengthens that boundary but adds latency and may reduce availability during partitions. The product must choose consciously.