Learn Database Engineering

A database is a program that owns your data’s durability, concurrency and access paths so that your application does not have to — and every feature it has is there to make one of those three cheaper or safer.

A SELECT is evaluated FROM → WHERE → GROUP BY → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT; write it in that order in your head and half of SQL’s "surprises" disappear.

GROUP BY collapses many rows into one per group; aggregates summarise each group; HAVING filters groups after they exist — and the most common aggregation bug is a join that multiplied the rows before you summed them.

A join pairs rows from two tables on a condition; the join type decides what happens to rows with no partner, and where you put a condition — ON or WHERE — decides whether an outer join stays outer.

A subquery is a query used as a value, a list or a table; a CTE names one; EXISTS asks "is there at least one"; and the difference between a correlated and an uncorrelated subquery is the difference between one execution and one per row.

A window function computes a value for each row from a set of related rows — rank, running total, previous value — without collapsing the rows the way GROUP BY does.

A schema is derived from access patterns, not from nouns: list the questions the system must answer and how often, then design the tables and indexes that answer the frequent ones cheaply.

1-1, 1-N and N-M are implemented with exactly three mechanisms — a foreign key, a unique foreign key, and a junction table — and the choice between natural and surrogate keys is about what may change.

Normalization removes update, insert and delete anomalies by making sure every fact is stored once; each normal form forbids one more way a fact can hide inside a table.

Duplicating a value to make a read cheap is a legitimate design decision as long as you can name the read it serves, the write that maintains it, and the way you will detect drift.

Without an index the engine reads every row to find one; a B-tree finds it in a handful of page reads that barely grow with the table — and the price is storage, slower writes, and a planner that has to decide whether to use it.

A multi-column B-tree is sorted by its first column, then its second inside that, then its third; a query can use it from the left, through equalities, up to the first range — and not at all if it skips the first column.

B-tree answers almost everything; the other types exist for specific shapes — equality-only, a rare subset, a transformed value, text search, similarity — and each is wrong outside its shape.

Six questions decide it — frequency, how the column is used, selectivity, table size, write rate, and what already exists — and any one of them can end the conversation with "no".

The planner enumerates ways to run a query, prices each with statistics and a cost model, and hands the cheapest to an executor that pulls rows through a tree of scan, join, sort and aggregate nodes.

Read a plan from the innermost node outwards, compare estimated rows to actual rows at every node, and look for three tells — a huge Rows Removed by Filter, a high loops count, and an estimate that is off by an order of magnitude.

Slow queries have a short list of causes — missing index, wrong index, wrapped column, N+1, fan-out, deep OFFSET, SELECT *, bad statistics — and the plan tells you which one before you change anything.

A transaction makes several statements succeed or fail as one; ACID names the four separate guarantees that make that promise mean something, and the write-ahead log is how the database keeps it through a crash.

When two transactions interleave, five specific things can go wrong — lost update, dirty read, non-repeatable read, phantom read, write skew — and each has a name because each has a different cause and a different fix.

Read Uncommitted, Read Committed, Repeatable Read and Serializable are four points on a dial between throughput and anomalies; PostgreSQL implements three of them, stronger than the standard requires, and the right one depends on which anomaly your code can survive.

Instead of overwriting a row, an update writes a new version and marks the old one superseded; each transaction’s snapshot decides which versions it can see — so readers never block writers, and dead versions have to be vacuumed.

Row and table locks serialise conflicting writers; a deadlock is a cycle in who-waits-for-whom, which the database detects and breaks by killing one side — and which you prevent by acquiring locks in a consistent order.

PostgreSQL’s type system is where much of its power hides — timestamptz, numeric, arrays, ranges, enums, JSONB — and choosing the right type is the cheapest correctness and performance decision you will make.

JSONB gives you a document store inside a relational one, full-text search gives you a credible search engine, and extensions like pgvector, PostGIS and pg_stat_statements are why "just use Postgres" is so often the right answer.

Most PostgreSQL incidents are one of four things — connection exhaustion, autovacuum falling behind, a table that needed partitioning, or replication lag — and each is visible in the statistics views before it becomes an outage.

Redis is an in-memory server of data structures — strings, hashes, lists, sets, sorted sets, streams — with atomic operations and per-key expiry; caching is the most common use, not the defining one.

Relational, document, key-value, wide-column, graph, search, time-series and vector are not a ladder from old to scalable; each is a different bet on which access pattern you will need most, and the price is the patterns you give up.

A document store trades joins for locality — the whole object arrives in one read — and the design decision that replaces normalization is whether each relationship is embedded in the parent or referenced by id.

Four specialised models, each built around one query shape: partition-local time-ordered reads at huge write rates, multi-hop traversal, relevance-ranked text, and range aggregates over time.

An embedding turns text into a point in a high-dimensional space where nearby means similar; vector search finds the k nearest points to a query, and the whole engineering problem is doing that sublinearly without losing too much recall.

Scale in the cheapest order — indexes, connection pool, read replicas, cache, partitioning, sharding — because each step buys capacity by adding a problem, and skipping to sharding is adding the biggest problem first.

A primary streams its changes to replicas that serve reads; asynchronous replication is fast and lagging, synchronous is consistent and slow, and the "I saved it and see the old value" bug is replication lag meeting a naive read route.

Partitioning splits one table across pieces of one database; sharding splits data across separate database nodes — and everything that crosses a shard boundary (joins, transactions, uniqueness, aggregates) becomes the application’s problem.

CAP is not "pick two" — it is a choice you make only during a network partition, between refusing writes to stay consistent and accepting them to stay available; the rest of the time you are trading latency for consistency.

Cache-aside, read-through, write-through and write-behind differ in who talks to whom and therefore in who is responsible for keeping the cache honest — and every one of them has a window where the cache is wrong.

The hard part of caching is knowing when the cached value became wrong; the operational hazards are stampedes when many keys expire together and hot keys when one key gets a disproportionate share of traffic.

A table is a description; what exists on disk is a file of fixed-size pages, each holding records made of a header, a NULL bitmap, fixed-size values, offsets and variable-size bytes. Seven layers from `SELECT` to the SSD, and why the page in the middle is the unit everything else is measured in.

One row as the engine writes it: a header, a NULL bitmap, the fixed-size columns at computed positions, offsets to the variable-size columns, then their bytes. Then the two real layouts — PostgreSQL's heap tuple with `t_xmin`/`t_xmax`/`t_ctid`, and InnoDB's row with its hidden `DB_TRX_ID` and `DB_ROLL_PTR`.

Why the engine never reads a row: the file is `Page 0, Page 1, …`, page N is at byte N × 8192, and a record is addressed as (page, slot). Page reads, page writes, torn writes and checksums — and the cost model that follows: the page is the unit of I/O and of the buffer pool.

Variable-size records inside a fixed-size page: a slot directory growing down from the header, records growing up from the end, free space in the middle. Records move, slots stay — which is what keeps every index entry pointing at (page, slot) valid. Then fragmentation, compaction, and what happens when an update no longer fits.

With no index, `WHERE email = ?` is a loop over every page of the table file: fetch page, test each row, fetch the next page. It is linear, it cannot stop early without a uniqueness guarantee, and it is the cheapest I/O per page the storage layer can do — which is exactly why the planner keeps choosing it.

Start from "how can we avoid reading every page?" and you are forced, step by step, into a sorted array of (key → location), then binary search, then — because the array outgrows memory and storage is read in pages — into pages of entries with a page of separators, and finally a tree of pages. Nobody designed the B+ tree; it is what falls out.

A B+ tree is a set of numbered pages: one root, internal pages of separator keys and child page ids, and leaf pages of (key → row locator) entries chained left to right. Lookups read one page per level; inserts split a full page and push a separator up; deletes borrow from or merge with a sibling. Every rule exists to keep pages between half-full and full and all leaves at the same depth.

A balanced binary tree and a B+ tree are both O(log n). One of them is 24 random page reads for 10 million keys and the other is 3. The base of the logarithm is the fanout, the fanout is how many decisions fit in one page, and a page is the unit of I/O — that is the whole argument, and it flips completely in memory.

A hash index skips the tree entirely: hash the key, take a bucket number, read that bucket, find the record reference. One page for equality, no matter the size. The price is that the hash destroys order — no ranges, no prefixes, no ORDER BY — and that buckets fill up: collisions chain into overflow pages and growth means rehashing.

A B+ tree finds the right page in four reads — but four SSD reads are 400 µs, and the same four pages are wanted ten thousand times a second. The buffer pool keeps recently used pages in RAM frames, maps page ids to frames with a hash table, tracks which frames are dirty or pinned, and evicts under its own rules instead of the operating system's.

When every frame is full, one page has to go. Least-recently-used is the obvious answer and it fails twice: its exact list costs a lock on every hit, and one sequential scan through a large table evicts the entire working set. Clock approximates LRU with a bit per frame; ring buffers, midpoint insertion and LRU-K keep a scan from flooding the pool.

`SELECT * FROM users WHERE id = 42` is nine stages from text to row: parse, plan, three index pages, the buffer pool decision on each, one heap page, one slot, one tuple. Where each page comes from — pool or storage — decides whether the query takes 4 µs or 400.

`UPDATE accounts SET balance = balance - 100 WHERE id = 42` finds the row like a read, then logs the change, modifies the page in memory, touches an index only if an indexed column changed, marks the page dirty, fsyncs the log at COMMIT — and writes the data page minutes later. The gap between COMMIT and that flush is where durability is decided.

COMMIT returns, the machine dies, the dirty page was never written. The naive fix — flush every dirty page at commit — costs random 8 KB writes per changed byte and still leaves torn pages. The write-ahead log appends a description of each change to a sequential file, fsyncs it at COMMIT, and lets data pages be written whenever convenient. LSNs order everything; checkpoints let the log be truncated.

On restart the engine has a log and a set of page images that lag behind it by an unknown amount. Recovery finds the last checkpoint, scans the log forward to learn which transactions committed, replays every change whose page does not yet have it (redo, made idempotent by page LSNs), rolls back the transactions that never committed (undo — or, in PostgreSQL, nothing), and opens for business.

BEGIN hands out a transaction id and a snapshot; reads consult it, writes stamp it onto row versions and into the WAL; COMMIT is one log record, one fsync and one bit flip in the transaction status table — and ROLLBACK, in PostgreSQL, writes almost nothing at all.

Interleave four operations from two transactions and €20 disappears; the engine's job is to allow only interleavings whose result equals some serial order, and the two ways to do that — refuse conflicting steps (locking) or keep every version and check afterwards (multi-version / optimistic) — are the roots of every isolation mechanism.

A lock is a row in a hash table keyed by the resource, with a list of who holds it in which mode and a queue of who is waiting; the compatibility matrix decides grant or wait, intention locks let row and table granularity coexist, and PostgreSQL avoids the table entirely for row locks by writing the holder's id into the row itself.

Two transactions each holding what the other needs will wait forever; the lock manager's wait queues already encode "who waits for whom" as a directed graph, a depth-first search finds the cycle, and the engine breaks it by aborting one participant — PostgreSQL after a one-second grace period, InnoDB immediately.

If a row is never overwritten but versioned, a reader can be handed the version that was current when it started and never wait for a writer; the version chain is a linked list with a creating and a superseding transaction id on each node, the snapshot is three numbers and a list, and the visibility rule is a dozen lines that every read in the engine runs.

Under MVCC an UPDATE is an insert plus a stamp and a DELETE is only a stamp; neither frees a byte, so every write leaves a dead version behind that some later process — VACUUM, autovacuum, InnoDB purge — has to find, remove from the page and every index, and hand back to the free space map before the table stops growing.

The same snapshot machinery produces three isolation levels by changing one thing — when the snapshot is taken — plus one rule for writers; Serializable then adds either dependency tracking that aborts (PostgreSQL) or locking reads that block (InnoDB), which is why the same level name costs retries on one engine and waits on the other.

When a database must absorb far more writes than it serves reads, updating a B+ tree page per row is the wrong shape. The log-structured merge tree appends every write, sorts in memory, flushes immutable sorted files and reconciles them later — trading cheap writes for a read path that has to look in several places.

A memtable flush has to become a file that a reader can search without loading it, that compresses well, and that many readers can share without locks. The SSTable answers with sorted data blocks, a sparse index with one entry per block, a bloom filter and a footer that says where everything is — and it never changes after it is written.

A point read in an LSM tree may have to consult ten files, and most of them do not hold the key. A bloom filter answers "definitely not here" from a few bits per key, with no false negatives and a tunable false-positive rate — turning ten block reads into one.

Every flush adds a file; every update adds a version; every delete adds a tombstone. Compaction is the background k-way merge that folds files together, keeps the newest version of each key, drops the rest — and, depending on how files are chosen, decides whether the engine is cheap to write, cheap to read, or cheap on disk.

Every storage engine pays for a logical operation with more physical work than the operation itself: extra bytes written, extra pages read, extra bytes stored. Naming the three amplifications precisely — and seeing that no design minimises all of them — is the vocabulary for comparing B+ trees, leveled LSMs and tiered LSMs honestly.

Two ways to organise bytes on disk: keep one sorted structure and update it in place, or append sorted runs and merge them later. Neither is better. Each is the right answer to a different workload, and the comparison is a table of dimensions, not a verdict.

A SELECT is a request, not a program. Seven stages turn it into one: parser, binder, planner, optimizer, executor and storage — each with its own data structure and its own way of failing.

Before a query can be planned it must become a tree. The lexer cuts text into tokens, a recursive-descent parser builds the tree by the grammar, and semantic analysis resolves every name against the catalog — the same front end every compiler has.

For one bound query there are many correct procedures, differing by orders of magnitude. The planner lists them — access paths per table, join orders, join methods — and needs statistics to tell them apart. The tree it hands over is what EXPLAIN prints.

Statistics in, a number out: n_distinct, most-common values and histograms become a selectivity, a row estimate, and finally an I/O + CPU cost in units where a sequential page is 1.0 and a random page is 4.0. The arithmetic is simple; the inputs decide everything.

Three ways to pair rows from two inputs: loop over both (quadratic, needs nothing), hash one and probe with the other (linear, needs memory), or sort both and walk two cursors (linear after the sort, needs order). The planner picks by input sizes, available indexes and memory.

One real statement — best-selling products in a category — followed from text to result through every layer: parser, AST, candidate plans, cost, chosen plan, buffer pool, scans, joins, aggregate, sort, limit. At each step: what happens, why, the algorithm, the memory, the storage, the DSA concept underneath.

PostgreSQL keeps every row version inside the table's own 8 KB heap pages, stamps each one with the transaction ids that created and deleted it, and pays for that simplicity with dead tuples, VACUUM and transaction-id wraparound — this is the general storage, MVCC and durability machinery as one engine actually built it.

In InnoDB the table is a B+ tree ordered by primary key, secondary indexes store primary keys instead of addresses, old row versions live in undo logs rather than in the table, and durability rests on a circular redo log plus a doublewrite buffer — the same general mechanisms as PostgreSQL, with nearly every decision made the other way.

Two ways to put a table on disk — rows in a heap addressed by indexes, or rows inside the primary-key tree addressed by key — and every difference in query cost, write amplification, index size and bulk-load speed between PostgreSQL and InnoDB follows from that one choice.

A replica is a machine that consumes the primary's change log and re-applies it; every property of replication — what a replica can serve, how far behind it is, what a failover loses, whether two primaries can exist — is a statement about positions in that log.

Splitting data across nodes is a pure function from key to node plus the metadata to find it, and every operational property — balance, hot spots, how much moves when a node joins, which queries fan out — is a property of that function.

A distributed database is several machines that each fail independently and cannot tell a slow peer from a dead one; quorums, leader election and consensus exist so that a majority can keep a single history alive through those failures — and every failure has a specific recovery it demands.

EXPLAIN names the slow node; the internals layer explains its price. Every slow query is some number of page reads times the fraction that missed the buffer pool, and every slow write is index pages dirtied, an fsync, a lock wait or a compaction debt — each with a metric that exposes it and a lesson one layer down.

Five knobs — storage engine, rows, RAM, index, workload — and one thousand operations. The simulator turns the mechanisms of the internals layer into a page budget you can watch move: hits and misses, storage reads and writes, index depth, WAL, compaction, amplification and latency, with two configurations side by side.