Topic domain
Databases
Storage engines, query processing, and transactional guarantees.
- Articles
- 80
- Clusters
- 8
- Foundational
- 24
- Intermediate
- 32
- Advanced
- 24
Relations, normalization, and integrity.
- Relations as Sets: Why the Relational Model Excludes Duplicate Rows
- Attribute Closure and the Mechanical Derivation of Candidate Keys
- Referential Integrity and the Semantics of Foreign Key Actions
- Boyce-Codd Normal Form and the Cost of Losing a Dependency
- Multivalued Dependencies and the Redundancy BCNF Cannot See
- Nulls, Three-Valued Logic, and the Constraints They Break
Parsing, planning, and execution operators.
- Parsing SQL: Clause Structure and Expression Precedence
- Name Resolution and Binding a Query to the Catalog
- Logical Plans and Rewrite Rules That Preserve Results
- Physical Operator Selection and Access Path Mechanics
- External Merge Sort: Runs, Fan-in, and the Sort-Merge Join
- Hash Joins and Hash Aggregation: Build, Probe, and Spill
Indexes
10B-trees, LSM indexes, and access paths.
- Fanout, Height, and Why B-Trees Stay Shallow
- Separator Keys and Search Routing in Internal Nodes
- Clustered and Secondary Access Paths and the Cost of a Row Fetch
- Node Splits, Merges, and What the Fill Factor Buys
- The LSM Write Path from Memtable to Sorted Run
- Leveled Compaction and the Shape of the LSM Tree
Isolation levels and version visibility.
- Conflict Serializability and the Precedence Graph Test
- The Read Phenomena Ladder and What Each Isolation Level Still Permits
- First-Committer-Wins Validation in Snapshot Isolation
- Heap Tuple Headers, Transaction Identifiers, and Visibility Rules
- Undo Records and Reconstructing Older Row Versions
- When a Snapshot Is Taken and How Commit Order Is Assigned
Buffer pools, pages, and write amplification.
- Slotted Pages: Fitting Variable-Length Records into Fixed-Size Blocks
- Buffer Pool Frames, Pin Counts, and Replacement Under Pin Pressure
- Write-Ahead Log Record Ordering and the Force-at-Commit Boundary
- Page Splits and the Write Cost of a Single B-Tree Insert
- LSM Compaction: Size-Tiered and Leveled Strategies Compared
- Doublewrite Buffers and the Torn Page Problem
Topology, failover, and consistency.
- The Replication Log as the Ordering Unit in Single-Leader Replication
- Statement Versus Row-Based Logs: Determinism and the Cost of Replay
- Where the Commit Returns: Synchronous and Asynchronous Replication Boundaries
- Leader Failover: Detection Windows, Fencing, and Split-Brain Avoidance
- Quorum Intersection: Why R + W > N Is Necessary but Not Sufficient
- Hash and Range Partitioning: Choosing What the Shard Key Preserves
Cost models, cardinality, and plan choice.
- How a Query Cost Model Reduces I/O and CPU to One Number
- Selectivity Estimation from Histograms and Most-Common-Value Lists
- The Crossover Between an Index Scan and a Sequential Scan
- Join Order Search and the Explosion of the Plan Space
- Join Cardinality and Where the Containment Assumption Fails
- Plan Caching, Generic Plans, and the Parameter Sensitivity Problem
Migrations, vacuuming, and capacity.
- How a Migration Runner Records and Orders Applied Versions
- Which ALTER TABLE Statements Rewrite the Table and Which Only Touch the Catalogue
- Dead Tuples, Bloat, and What VACUUM Actually Reclaims
- How Metadata Locks Block a DDL Statement Behind Ordinary Queries
- Expand and Contract: Changing a Column While Both Versions Run
- Batching a Backfill Without Holding Locks or Losing Restarts
All Databases articles
- Oct 23, 2026 Quorum Intersection: Why R + W > N Is Necessary but Not Sufficient What the quorum inequalities actually prove about read-write overlap, why they say nothing about the newest value, and where per-key quorums break down across a cluster.
- Oct 18, 2026 Page Splits and the Write Cost of a Single B-Tree Insert What an insert actually writes when a leaf page has no room, why the split propagates to the root, and how fill factor and right-links change the count.
- Oct 8, 2026 Secondary Indexes Under MVCC: Version Chasing and Index Write Amplification Why every row version needs its own index entries, how a lookup follows pointers through superseded versions, and what a non-covering index costs in a versioned store.
- Aug 13, 2026 Buffer Pool Frames, Pin Counts, and Replacement Under Pin Pressure How a page identifier is mapped to a frame of memory, why a pin is not a lock, what happens when every candidate for eviction is pinned, and how clock sweeps approximate LRU.
- Jul 7, 2026 Shard Routing and Ownership Metadata: The Directory That Must Not Disagree How clients find the shard for a key, what happens when the routing table is stale, and why ownership epochs turn a racy handoff into a detectable error.
- Jul 1, 2026 Join Dependencies and the Ternary Structure Fifth Normal Form Protects Why a relation can be pairwise lossless and still not be a join of two projections, how a three-way join dependency arises from a cyclic constraint, and what 5NF removes.
- Jun 25, 2026 Fanout, Height, and Why B-Trees Stay Shallow How page size, key width, and pointer width determine the branching factor of a B-tree, and why three or four levels cover billions of keys.
- Jun 17, 2026 Hash and Range Partitioning: Choosing What the Shard Key Preserves Why range partitioning keeps ordered scans and concentrates writes, why hashing spreads load and destroys locality, and how consistent hashing changes only the movement cost.
- Jun 15, 2026 Write-Ahead Log Record Ordering and the Force-at-Commit Boundary Why a log record must reach stable storage before the page it describes, what LSN comparison guarantees during recovery, and where group commit fits in the sequence.
- Jun 10, 2026 Boyce-Codd Normal Form and the Cost of Losing a Dependency Why BCNF decomposition can make a functional dependency unverifiable without a join, how 3NF avoids that, and when the extra anomaly is the better trade.
- Jun 10, 2026 Costing a Parallel Plan: Workers, Gather, and the Serial Fraction Why dividing a plan cost by the number of workers overestimates the gain, how the planner prices worker startup and row transfer, and when a parallel plan loses to a serial one.
- May 26, 2026 Two-Phase Commit Across Shards: The Coordinator, the Veto, and the In-Doubt Window How prepare and commit phases make a cross-shard transaction atomic, why a coordinator failure leaves participants unable to decide, and what presumed abort changes.
- May 17, 2026 Bitmap Index Scans and the Order of Heap Fetches Why a plan collects row identifiers into a bitmap before fetching rows, how the bitmap is compressed and ordered, and when losing row order is acceptable.
- May 10, 2026 Page Compression: Prefix, Dictionary, and the Cost of Decoding How prefix truncation, shared dictionaries, and byte-level encoding shrink a page, why decompression sits on the critical path, and where compression defeats the buffer pool.
- May 8, 2026 Leveled Compaction and the Shape of the LSM Tree Why leveled compaction keeps each level ten times the size of the one above, what that costs in write amplification, and how tiering trades it back.
- Apr 30, 2026 Logical Plans and Rewrite Rules That Preserve Results Why the planner rewrites a bound query into relational algebra before choosing algorithms, and which transformations are safe under NULLs, outer joins, and volatile functions.
- Apr 29, 2026 Name Resolution and Binding a Query to the Catalog How an unresolved syntax tree becomes a typed expression tree: namespace scoping, column ambiguity, view expansion, and where implicit casts are inserted.
- Apr 16, 2026 Referential Integrity and the Semantics of Foreign Key Actions What a foreign key actually asserts, how each ON DELETE and ON UPDATE action resolves the violated constraint, and why MATCH SIMPLE accepts a partially null key.
- Mar 10, 2026 The Transaction ID Horizon and What Happens at Wraparound How 32-bit transaction identifiers are consumed, why freezing exists, and the sequence of failures that turns a neglected counter into a refused-write outage.
- Feb 27, 2026 Inclusion Dependencies and the Undecidability That Follows Them How inclusion dependencies generalize foreign keys across arbitrary attribute sets, why their implication problem needs infinite chase sequences, and what breaks when they are combined with functional dependencies.
- Feb 22, 2026 Statement Versus Row-Based Logs: Determinism and the Cost of Replay How statement replication breaks on nondeterministic SQL, what row images cost in bytes, and which failures each format survives.
- Feb 10, 2026 Join Order Search and the Explosion of the Plan Space Left-deep and bushy trees, why the search is NP-hard, and the pruning rules that keep a twenty-table join tractable.
- Jan 3, 2026 Concurrent Descent and Page Latching in a Shared B-Tree How readers descend without blocking writers, why a split needs the parent as well as the child, and how the Lehman-Yao protocol avoids deadlock.
- Nov 28, 2025 External Merge Sort: Runs, Fan-in, and the Sort-Merge Join How a sort spills to disk, why replacement selection builds longer runs than naive chunking, and how the merge phase feeds a sort-merge join without a second pass.
- Nov 18, 2025 Selectivity Estimation from Histograms and Most-Common-Value Lists How a single-column statistic turns a predicate into a row count, why equidepth buckets are chosen over equiwidth, and where the estimate fails for correlated columns.
- Oct 21, 2025 Leader Failover: Detection Windows, Fencing, and Split-Brain Avoidance How a failed leader is detected, why a timeout cannot distinguish a dead leader from a slow one, and how fencing tokens stop two leaders from accepting writes.
- Oct 16, 2025 LSM Compaction: Size-Tiered and Leveled Strategies Compared How an LSM tree turns random writes into sequential ones, what each compaction strategy costs in read amplification and space amplification, and when the write stalls arrive.
- Oct 9, 2025 Where the Commit Returns: Synchronous and Asynchronous Replication Boundaries What a commit acknowledgement actually guarantees at each replication mode, how quorum commits move the durability boundary, and why a synchronous replica becomes a latency dependency.
- Oct 8, 2025 Which ALTER TABLE Statements Rewrite the Table and Which Only Touch the Catalogue How engines decide between a catalogue edit and a full table copy, what the fast-default and instant-column mechanisms store instead, and where the boundary sits.
- Sep 8, 2025 When a Snapshot Is Taken and How Commit Order Is Assigned The choice between transaction-start and first-statement snapshots, the in-progress list that defines the read view, and why a single commit counter is a shared resource.
- Aug 27, 2025 Batching a Backfill Without Holding Locks or Losing Restarts Key-range batching, batch sizing, commit frequency, and the idempotence rules that let a long data update be interrupted and resumed safely.
- Aug 14, 2025 Multivalued Dependencies and the Redundancy BCNF Cannot See How an MVD asserts independence between two attribute groups, why the four-way combination of independent lists forces redundancy, and how 4NF decomposes on it.
- Jul 19, 2025 Heap Tuple Headers, Transaction Identifiers, and Visibility Rules How a row version records the transaction that created it and the one that deleted it, and how a reader decides whether that version belongs in its snapshot.
- Jul 18, 2025 Forecasting Table and Index Growth from Row Width and Page Fill Turning tuple width, page overhead, fill factor, and index amplification into a byte forecast, and the four effects that make a linear extrapolation wrong.
- Jul 1, 2025 Online Resharding: Moving a Range Without Stopping Writes How a range is migrated while it is being written to, why the cutover is a metadata transaction, and what the dual-write window costs in correctness.
- Jun 2, 2025 Anti-Entropy Repair: Merkle Trees, Read Repair, and the Cost of Finding Divergence How replicas that missed writes discover what they missed, why a Merkle tree narrows comparison to a logarithmic path, and what repair cannot fix.
- Jun 2, 2025 Latch Coupling and Deadlock Avoidance in the Buffer Pool Why latches are not locks, how lock coupling keeps a B-tree descent deadlock-free, what a partitioned buffer pool hash table buys, and where contention concentrates.
- May 10, 2025 First-Committer-Wins Validation in Snapshot Isolation How snapshot isolation validates writes against concurrent committers, why a write-write check is sufficient for its own guarantees, and the serializability it leaves on the table.
- Apr 28, 2025 Dangerous Structures: Detecting Serialization Cycles Under Snapshot Isolation Why snapshot isolation needs only two edge types to find every nonserializable cycle, how pivot detection works, and what the false positive rate costs.
- Apr 25, 2025 Sixth Normal Form and the Cost of One Attribute per Relation How a decomposition into key-plus-one-attribute relations removes every update anomaly by construction, what the extra joins cost, and which workloads make that cost worth paying.
- Apr 5, 2025 Prefix Compression and Suffix Truncation in Index Pages How shared key prefixes are stored once per page, why the first key of a page is stored whole, and what restart points cost a search inside a compressed page.
- Feb 22, 2025 Why a Replication Slot Pins Write-Ahead Log and How to Bound It The retention rule that makes a slot hold log segments until a consumer confirms them, the disk consequence of an idle slot, and the settings that cap it.
- Feb 13, 2025 Concurrent Index Builds and the Invalid Index They Can Leave Behind Why a non-blocking index build performs two scans, what state it commits between them, and how a failure leaves an index that exists but cannot be used.
- Jan 15, 2025 Vectorized Execution: Batches, Selection Vectors, and Push vs Pull Why processing tuples in column batches amortizes interpretation overhead, how selection vectors represent filtered rows, and what a push-based pipeline changes.
- Dec 4, 2024 How a Query Cost Model Reduces I/O and CPU to One Number Why planner costs are weighted units rather than milliseconds, how sequential and random page reads enter the sum, and which effects the arithmetic deliberately ignores.
- Dec 3, 2024 Vacuum Horizons, Dead Version Collection, and Table Bloat How an engine decides that a row version can never be seen again, why one old snapshot stalls collection for an entire database, and what freezing does to the identifier space.
- Nov 26, 2024 The LSM Write Path from Memtable to Sorted Run How an insert becomes a log record, a memtable entry, a flushed sorted file, and finally a merged run, and what each step costs in write amplification.
- Nov 13, 2024 The Crossover Between an Index Scan and a Sequential Scan Why fetching a few percent of a table by index can cost more than reading all of it, how physical correlation moves the crossover point, and what bitmap scans change.
- Oct 23, 2024 Nulls, Three-Valued Logic, and the Constraints They Break How UNKNOWN propagates through SQL predicates, why NOT IN behaves unexpectedly with nulls, and which integrity constraints a null silently satisfies.
- Sep 15, 2024 Learning Optimizers: Learned Cardinality Models and Plan Regression What a learned selectivity model replaces in the catalog, why a plan that is cheaper on average can be a regression for one query, and how plan management contains the damage.
- Sep 6, 2024 Node Splits, Merges, and What the Fill Factor Buys How a B-tree page divides when it overflows, why merges are rarely performed, and what setting a fill factor at build time actually changes.
- Aug 1, 2024 The Read Phenomena Ladder and What Each Isolation Level Still Permits Why the four SQL isolation levels are defined by the anomalies they forbid rather than the guarantees they give, and which anomalies fall through the definitions.
- Jul 12, 2024 Join Cardinality and Where the Containment Assumption Fails How equality joins are estimated from distinct-value counts, why the uniform-frequency assumption collapses on skewed keys, and how the error compounds across a chain of joins.
- Jul 3, 2024 Physical Operator Selection and Access Path Mechanics What distinguishes a sequential scan from an index scan, a bitmap heap scan from an index-only scan, and how each access path decides when to stop reading.
- May 11, 2024 Plan Caching, Generic Plans, and the Parameter Sensitivity Problem Why a reused plan is compiled for a parameter it will never see again, how the choice between custom and generic plans is made, and why parameter sniffing produces plans that fit one value.
- Apr 24, 2024 Adaptive Plans: Choosing the Join Algorithm After Execution Starts How a statistics collector at a plan node defers the choice between nested loop and hash join, what the switch costs mid-flight, and why re-planning after a blocking operator is a different mechanism.
- Mar 14, 2024 Write Amplification Across the Storage Stack How one logical row change becomes many device writes, how to attribute the multiplier to each layer, and which layer dominates for B-trees and LSM trees.
- Mar 12, 2024 Expand and Contract: Changing a Column While Both Versions Run The four-step sequence that lets old and new application code share one schema, which intermediate states must be safe, and where the sequence breaks down.
- Feb 16, 2024 Doublewrite Buffers and the Torn Page Problem Why a page write is not atomic on real hardware, how a shadow copy restores the page after a partial write, and what the extra sequential write costs.
- Jan 23, 2024 Attribute Closure and the Mechanical Derivation of Candidate Keys How Armstrong axioms generate the closure of a dependency set, why closure of an attribute set is computed by repeated scanning, and how to enumerate minimal keys without exponential search.
- Jan 1, 2024 Clustered and Secondary Access Paths and the Cost of a Row Fetch What separates a clustered index from a secondary index, how a secondary lookup pays for a second descent, and why covering indexes change the plan.
- Dec 10, 2023 Dead Tuples, Bloat, and What VACUUM Actually Reclaims How update-in-place storage produces dead row versions, what a vacuum pass removes from pages, and why the table file does not shrink when it finishes.
- Nov 24, 2023 Gap Locks and Next-Key Locking in an Index-Ordered Store How a locking engine prevents phantoms by locking the space between index entries, why the locks are taken on index records rather than rows, and what the resulting deadlocks look like.
- Nov 24, 2023 Separator Keys and Search Routing in Internal Nodes How internal B-tree pages choose the keys that route a search, what happens when a separator is too short to be unique, and how duplicate keys are ordered.
- Nov 10, 2023 Conflict Serializability and the Precedence Graph Test How read-write conflicts between concurrent transactions form a directed graph, why a cycle means no equivalent serial order exists, and where the test stops being useful.
- Oct 21, 2023 Parsing SQL: Clause Structure and Expression Precedence How a statement becomes a parse tree, where the SQL grammar is genuinely ambiguous, and which decisions the parser deliberately leaves to later stages.
- Oct 6, 2023 Point Lookups, Tombstones, and Read Amplification in LSM Trees How a single-key lookup consults memtables, filters, and runs, why deletion must write a tombstone, and when the tombstone can finally be dropped.
- Oct 4, 2023 Relations as Sets: Why the Relational Model Excludes Duplicate Rows How Codd defined a relation as a subset of a Cartesian product, what follows from value-based identity, and why SQL tables are multisets instead.
- Jun 23, 2023 The Replication Log as the Ordering Unit in Single-Leader Replication Why single-leader replication ships a serialised change log rather than rows, how log positions act as a logical clock, and where the ordering guarantee stops.
- Jun 9, 2023 fsync, fdatasync, and Where the Durability Boundary Actually Sits What the kernel guarantees when a write returns, which metadata fdatasync skips, why direct I/O does not remove the need for a flush, and how double buffering wastes memory.
- May 19, 2023 Exchange Operators: Partitioning, Broadcasting, and Parallel Pipelines How a plan is divided into fragments, what a repartition exchange does to tuple order and memory, and why the exchange is the only operator that moves rows between workers.
- May 8, 2023 The Chase as a General Test for Dependency Implication How the chase algorithm decides whether a decomposition is lossless and whether one dependency set implies another, and why its termination is guaranteed but its runtime is not.
- Apr 11, 2023 How Metadata Locks Block a DDL Statement Behind Ordinary Queries The lock queue that a schema change must pass through, why a short query in front of it can stall every new reader of the table, and the timeout that bounds the damage.
- Apr 5, 2023 Sort, Hash, and Materialize: Memory Limits and Spill to Disk How a hash join decides it must partition, what a sort does when the work memory runs out, and why an underestimated row count becomes a disk-bound plan.
- Jan 19, 2023 Undo Records and Reconstructing Older Row Versions How engines that keep only the current row in the heap rebuild earlier versions from before-images in undo segments, and what that indirection costs on the read path.
- Dec 25, 2022 Slotted Pages: Fitting Variable-Length Records into Fixed-Size Blocks Why a page keeps its records at the end and its directory at the front, how item identifiers decouple record addresses from byte offsets, and where the free space goes.
- Dec 6, 2022 Adaptive Execution: Runtime Filters and Mid-Query Replanning How a running plan uses observed cardinalities to change join strategy, and how bloom filters and partition pruning eliminate work before it happens.
- Sep 26, 2022 How a Migration Runner Records and Orders Applied Versions The ledger table, version ordering, checksums, and locking that make a migration run reproducible, and what happens when two runners start at the same time.
- Jul 27, 2022 Grouping, Duplicate Elimination, and Grouping Sets What a GROUP BY actually computes, how the sort-based and hash-based forms differ in output order, and how ROLLUP and CUBE collapse into one scan.
- Jul 19, 2022 Hash Joins and Hash Aggregation: Build, Probe, and Spill How a hash table is built from one join input, why the probe side must be streamed, and what happens when the build side exceeds the memory grant.