Databases & Data Modeling
What you’ll learn. How to model data relationally and when to denormalize; the mechanics of B-tree and LSM-tree storage and why indexes speed reads and slow writes; ACID and the isolation-level anomalies (with concrete examples); how to think about SQL vs NoSQL; how to read a query plan; and how to change a live schema safely. SQL examples target PostgreSQL; application code is Python or TypeScript, labelled.
Why the database is usually the system
Section titled “Why the database is usually the system”Most applications are a thin layer over a database; most performance and correctness problems end up there. Data outlives code: schemas are far harder to change than services. Time spent on a sound data model repays itself many times.
Relational modeling
Section titled “Relational modeling”The relational model (Codd, 1970) represents data as relations (tables) of tuples (rows) with typed attributes (columns). A primary key uniquely identifies a row; a foreign key references another table’s key, which enforces referential integrity. SQL is the declarative language: you say what you want, the planner decides how.
From requirements to tables
Section titled “From requirements to tables”- Identify entities (nouns):
customer,order,product. - Identify relationships and cardinality: one-to-many (customer has many orders), many-to-many (orders and products via a junction table
order_item), one-to-one (rare; often merge). - Choose keys. Natural keys (email) change and leak meaning; surrogate keys (bigint identity, UUID/ULID/UUIDv7) are stable. Time-ordered IDs (UUIDv7, ULID) avoid the index fragmentation of random UUIDv4 in B-trees.
- Encode rules as constraints:
NOT NULL,UNIQUE,CHECK, foreign keys. Constraints are the most reliable validation, because every code path (including that script someone runs at 2am) passes through them.
CREATE TABLE customer ( id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY, email text NOT NULL UNIQUE, created_at timestamptz NOT NULL DEFAULT now());
CREATE TABLE product ( id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY, sku text NOT NULL UNIQUE, price_cents integer NOT NULL CHECK (price_cents >= 0));
CREATE TABLE "order" ( id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY, customer_id bigint NOT NULL REFERENCES customer(id), status text NOT NULL CHECK (status IN ('pending','paid','shipped','cancelled')), placed_at timestamptz NOT NULL DEFAULT now());
CREATE TABLE order_item ( order_id bigint NOT NULL REFERENCES "order"(id) ON DELETE CASCADE, product_id bigint NOT NULL REFERENCES product(id), qty integer NOT NULL CHECK (qty > 0), unit_price_cents integer NOT NULL, -- snapshot: price at time of purchase PRIMARY KEY (order_id, product_id));Note the unit_price_cents snapshot: historical facts should not change when the current price changes. Store money as integers or numeric, never floating point. Store timestamps in UTC as timestamptz.
Normalization
Section titled “Normalization”Normalization removes redundancy to prevent update anomalies (the same fact stored twice and updated inconsistently), insertion anomalies, and deletion anomalies. It is defined through functional dependencies: means each value of determines exactly one value of .
- 1NF: atomic values; no repeating groups or arrays-in-a-cell (as a modeling rule).
- 2NF: no non-key attribute depends on part of a composite key.
- 3NF: no non-key attribute depends on another non-key attribute (no transitive dependencies). Mnemonic: every non-key attribute depends on “the key, the whole key, and nothing but the key”.
- BCNF: every determinant is a candidate key (a stricter 3NF).
Example violation: order(order_id, customer_id, customer_email): customer_id -> customer_email, a transitive dependency. Changing a customer’s email requires updating every order. Fix: move customer_email to customer.
Denormalization
Section titled “Denormalization”Normalization optimizes for write correctness; reads that need many joins can be slow. Controlled denormalization duplicates data for read performance: counters (comment_count), precomputed totals, materialized views, wide read models in CQRS. Rules: normalize first; denormalize only on measured need; keep a single source of truth and a clear mechanism (trigger, application code, materialized view refresh) for keeping copies consistent.
Storage engines and indexes
Section titled “Storage engines and indexes”A table without an index is a heap: finding a row means scanning all rows, . An index is an auxiliary data structure mapping key values to row locations.
B-trees
Section titled “B-trees”The default index in nearly all relational databases (PostgreSQL, MySQL/InnoDB, SQLite). A B-tree (more exactly B+-tree) is a balanced, wide, shallow tree whose nodes are disk pages (commonly 4-16 KB). Internal nodes hold keys and child pointers; leaves hold keys plus row pointers (or the rows themselves in a clustered index), and leaves are linked for range scans.
[ 30 | 60 ] / | \ [10|20] [40|50] [70|80] <- internal / leaf pages ... ... ... leaves: sorted keys -> row pointers, linked left-to-rightWith a fan-out around several hundred, a tree of height 3-4 indexes hundreds of millions to billions of rows, so a lookup costs ~3-4 page reads (the upper levels are almost always cached). Complexity: for lookup/insert, where is the fan-out. Strengths: point lookups, range scans, ordering. Weakness: write amplification and random I/O; inserts modify pages in place, may split pages, and are written to a write-ahead log first.
LSM-trees
Section titled “LSM-trees”Log-structured merge trees (RocksDB, LevelDB, Cassandra, ScyllaDB, HBase; used inside many modern engines) optimize for write throughput. Writes go to an in-memory sorted memtable (plus a WAL for durability); when full it is flushed as an immutable sorted file (SSTable). Reads may need to check the memtable and several SSTables (aided by Bloom filters to skip files that cannot contain the key). Background compaction merges SSTables, discarding overwritten and deleted entries (deletes are written as tombstones).
write -> WAL + memtable (RAM) --flush--> L0 SSTables --compaction--> L1 ... Ln (larger, sorted, non-overlapping)read -> memtable -> L0 -> L1 -> ... (bloom filters prune)| B-tree | LSM-tree | |
|---|---|---|
| Writes | In-place, random I/O | Sequential appends, batched |
| Write amplification | Moderate (page rewrites + WAL) | Compaction rewrites data several times |
| Read | Predictable ~log n | May touch several levels; slower tail |
| Space | Fragmentation | Temporary space amplification during compaction |
| Fit | Read-heavy, transactional | Write-heavy, ingestion, time-series |
The “RUM conjecture” frames the trade-off: you cannot minimize Read, Update and Memory overhead all at once.
Designing useful indexes
Section titled “Designing useful indexes”- Composite indexes follow the leftmost prefix rule: an index on
(a, b, c)supports filters ona, ona,band ona,b,c, but not onbalone. Order columns: equality predicates first, then the range/sort column. - Covering indexes (
INCLUDEcolumns in PostgreSQL) hold all needed columns so the query is answered from the index alone (an index-only scan). - Partial indexes (
WHERE status = 'pending') index only a hot subset. - Selectivity: an index on a low-cardinality column (boolean) is rarely useful alone.
- Other types: hash, GIN (arrays, JSONB, full-text), GiST/SP-GiST (geometric), BRIN (huge naturally ordered tables).
- Every index slows writes and consumes space; do not index everything. Drop unused indexes.
- Functions on indexed columns defeat the index (
WHERE lower(email) = ...needs an expression index onlower(email)).
CREATE INDEX order_customer_placed ON "order" (customer_id, placed_at DESC);-- supports: WHERE customer_id = ? ORDER BY placed_at DESC LIMIT 20CREATE INDEX order_pending ON "order" (placed_at) WHERE status = 'pending';Transactions and isolation
Section titled “Transactions and isolation”A transaction groups operations into a unit with the ACID properties:
- Atomicity: all or nothing (implemented via the WAL/undo).
- Consistency: constraints hold before and after (the application’s invariants; the weakest letter, partly the app’s responsibility).
- Isolation: concurrent transactions do not interfere (to a configurable degree).
- Durability: committed data survives crashes (WAL flushed to disk with
fsync).
Anomalies
Section titled “Anomalies”Without isolation, concurrency produces:
- Dirty read: reading another transaction’s uncommitted data.
- Non-repeatable read: reading the same row twice and seeing different values.
- Phantom read: a repeated range query returns new rows.
- Lost update: two transactions read a value, both modify it, and one overwrites the other.
- Write skew: two transactions read overlapping data, each updates different rows based on what it read, and together they violate an invariant. Example: two on-call doctors each check “at least one other doctor is on call” and both go off call.
Isolation levels
Section titled “Isolation levels”| Level | Dirty read | Non-repeatable | Phantom | Write skew |
|---|---|---|---|---|
| Read Uncommitted | possible | possible | possible | possible |
| Read Committed | no | possible | possible | possible |
| Repeatable Read / Snapshot | no | no | mostly no* | possible |
| Serializable | no | no | no | no |
*Definitions in the SQL standard differ from real implementations. PostgreSQL’s Repeatable Read is snapshot isolation (no phantoms but write skew possible); its Serializable uses Serializable Snapshot Isolation (SSI), which detects dangerous dependency patterns and aborts one transaction. MySQL/InnoDB’s Repeatable Read behaves differently again. Treat the table as a guide; read your database’s docs.
Implementation approaches: MVCC (multi-version concurrency control: readers see a consistent snapshot, writers create new row versions; readers do not block writers; PostgreSQL, InnoDB, Oracle) vs two-phase locking (readers and writers block each other; classical serializable). Serializable guarantees results equal to some serial order; applications must be ready to retry on serialization failures.
# Python (psycopg 3): safe read-modify-write patterns# 1) Atomic update in the database (no read at all):cur.execute("UPDATE account SET balance = balance - %s WHERE id = %s AND balance >= %s", (amount, acct, amount))assert cur.rowcount == 1, "insufficient funds"
# 2) Pessimistic lock:cur.execute("SELECT balance FROM account WHERE id = %s FOR UPDATE", (acct,))
# 3) Optimistic concurrency with a version column:cur.execute("UPDATE doc SET body=%s, version=version+1 WHERE id=%s AND version=%s", (new_body, doc_id, seen_version))if cur.rowcount == 0: raise ConflictError("someone else changed it; reload and retry")Keep transactions short; long ones hold locks/snapshots, bloat MVCC garbage, and raise conflict rates. Never hold a transaction open across a network call to another service.
Distributed transactions (two-phase commit, sagas) are covered in Distributed Systems.
SQL vs NoSQL
Section titled “SQL vs NoSQL”“NoSQL” lumps together very different systems, usually by their data model:
| Family | Examples | Data model | Strengths | Trade-offs |
|---|---|---|---|---|
| Key-value | Redis, DynamoDB (also doc-ish) | key -> blob | Speed, simple horizontal scale | Query only by key |
| Document | MongoDB, Firestore | JSON-like docs | Flexible schema, locality of an aggregate | Joins awkward, duplication |
| Wide-column | Cassandra, HBase, Bigtable | rows with sparse columns | Massive write throughput, multi-DC | Query patterns must be designed up front |
| Graph | Neo4j | nodes + edges | Multi-hop relationship queries | Niche, scale-out harder |
| Search | Elasticsearch/OpenSearch | inverted index | Full-text, aggregations | Not a system of record |
| Time-series | TimescaleDB, InfluxDB | time-indexed | Ingest and downsample | Specialized |
| Vector | pgvector, dedicated vector DBs | embeddings | Similarity search | Often an add-on to other stores |
Historical reasons for NoSQL (horizontal scale, flexible schemas) have narrowed: modern relational systems (PostgreSQL with JSONB, partitioning, replicas; “NewSQL” like CockroachDB, YugabyteDB, Spanner, TiDB) offer scale-out SQL. A sound default: start with PostgreSQL; it handles transactional data, JSON documents, full-text search, queues (SKIP LOCKED), and moderate vector search. Pick a specialized store when a specific requirement (extreme write rate, multi-region active-active, graph traversals, ranked text search) justifies the operational cost of another system and the consistency problems of keeping them in sync (see polyglot persistence and outbox in Architecture Styles).
Modeling differs. Relational: model the data, then query any way you like (flexible queries, normalized). Document/wide-column/DynamoDB: model access patterns first; denormalize and embed so a request hits one item/partition. The price of flexible reads vs fast, predetermined reads.
Scaling out (replication, sharding, partitioning) and CAP trade-offs are covered in System Design Fundamentals and Distributed Systems.
Query planning
Section titled “Query planning”The query optimizer converts SQL into an execution plan, choosing scan types, join orders and join algorithms using table statistics (row counts, value distributions) to estimate costs. Inspect with EXPLAIN (estimates) and EXPLAIN (ANALYZE, BUFFERS) (runs the query; actual times and rows).
EXPLAIN (ANALYZE, BUFFERS)SELECT * FROM "order" WHERE customer_id = 42 ORDER BY placed_at DESC LIMIT 20;-- Good: Index Scan using order_customer_placed ... (actual rows=20)-- Bad: Seq Scan on "order" ... Rows Removed by Filter: 9,800,000Things to read in a plan:
- Scan types: Seq Scan (reads the whole table; fine for small tables or large fractions), Index Scan, Index Only Scan, Bitmap Heap Scan (combine multiple indexes).
- Join algorithms: Nested Loop (good when one side is tiny or indexed), Hash Join (equality joins on larger sets; builds a hash table), Merge Join (pre-sorted inputs).
- Estimates vs actuals: large mismatches in
rowsindicate stale statistics (ANALYZE), correlated columns or skew; they cause bad plans. - Sorts spilling to disk, high
Buffers: read.
Common problems and fixes: missing or non-covering index; non-sargable predicates (functions on columns, implicit casts, leading wildcard LIKE '%x'); N+1 queries from ORMs (one query for a list, then one per row: fix with joins or eager loading/batching); SELECT * pulling wide columns; deep OFFSET; unbounded result sets; lock contention. Always measure with realistic data volumes: a plan on 1,000 rows says little about 100 million.
Schema migrations
Section titled “Schema migrations”The schema evolves with the application. Treat migrations as code: versioned, reviewed, applied by tooling (Alembic, Django migrations, Flyway, Liquibase, Prisma Migrate, Atlas, Knex).
The hard part is zero-downtime change when old and new application versions run simultaneously during a rolling deploy, and large tables make some operations lock or rewrite for minutes. The standard discipline is expand and contract (parallel change):
- Expand: add the new column/table (nullable or with a default that does not rewrite the table), add indexes concurrently (
CREATE INDEX CONCURRENTLYin PostgreSQL). - Deploy code that writes both old and new (and reads old).
- Backfill existing rows in small batches (avoid one giant transaction).
- Deploy code that reads the new; verify.
- Stop writing old; deploy.
- Contract: drop the old column/table in a later migration.
Renaming a column is therefore multiple deploys, not one ALTER. Dangerous operations on big tables: adding a NOT NULL column with a volatile default (older engines rewrite), adding a foreign key or CHECK without NOT VALID then VALIDATE, changing a column type, and long ALTERs waiting behind a long transaction and then blocking everything queued behind them (always set lock_timeout). Migrations should be forward-only in production (rolling forward with a fix is usually safer than a down-migration), tested on production-sized data, and decoupled from code deploys.
-- Safe-ish add-and-backfill sequence (PostgreSQL)ALTER TABLE customer ADD COLUMN display_name text; -- fast, nullable-- app v2 writes display_name; backfill in batches:UPDATE customer SET display_name = name WHERE id BETWEEN 1 AND 10000 AND display_name IS NULL;-- ... repeat per batch ...ALTER TABLE customer ADD CONSTRAINT dn_nn CHECK (display_name IS NOT NULL) NOT VALID;ALTER TABLE customer VALIDATE CONSTRAINT dn_nn; -- lighter lockPitfalls
Section titled “Pitfalls”- Storing derived or duplicated data with no reconciliation mechanism.
- Using floats for money; storing local time without zone.
- EAV (“entity-attribute-value”) tables to dodge schema design; JSONB is usually better for truly variable attributes.
- Over-indexing and never reviewing slow query logs.
- Assuming the default isolation level protects your invariant.
- Using the database as a message queue without understanding locking, or as a cache without eviction.
- Letting the ORM hide query counts; log SQL in development.
Key takeaways
Section titled “Key takeaways”- Model entities, relationships and constraints first; normalize to 3NF/BCNF, denormalize deliberately and measurably.
- B-trees give balanced read/write performance; LSM-trees favor write-heavy workloads via sequential writes and compaction.
- Indexes trade write cost and space for read speed; composite order and covering matter.
- ACID’s isolation is a spectrum; know the anomalies (especially lost update and write skew) and use atomic updates, locks, versioning or SERIALIZABLE with retries.
- Default to PostgreSQL; add specialized stores for specific needs.
- Read plans with
EXPLAIN ANALYZE; fix estimates, indexes and N+1 patterns. - Migrate with expand-and-contract; never break running application versions.
Exercises
Section titled “Exercises”- Conceptual. A table
employee(id, dept_id, dept_name, dept_head)— identify the functional dependencies, the normal form it violates, and the decomposition. - Hands-on (SQL). For
WHERE customer_id = ? AND status = 'paid' ORDER BY placed_at DESC LIMIT 10, design the best index and justify column order. Would you use a partial index? - Conceptual. Walk through write skew with the on-call doctors example; list two ways to prevent it.
- Hands-on (Python). With SQLite or Postgres, reproduce a lost update with two connections and fix it using an atomic
UPDATE ... SET x = x + 1. - Conceptual. Plan a zero-downtime rename of
users.nametousers.full_nameon a 500M-row table.
Solutions (sketch)
dept_id -> dept_name, dept_head: a transitive dependency (violates 3NF). Split intoemployee(id, dept_id)anddepartment(id, name, head).(customer_id, status, placed_at DESC): equality columns first, then the sort column, so the index delivers rows in order. A partial indexWHERE status = 'paid'on(customer_id, placed_at DESC)is smaller if this is the dominant query.- Both read “count of on-call doctors = 2” in their snapshots, each removes themselves; invariant broken. Prevent via SERIALIZABLE isolation (retry on failure) or locking the shared row/set (
SELECT ... FOR UPDATEon the on-call rows, or a constraint/summary row). - Add
full_name; dual-write in app; batch backfill; switch reads; stop writingname; dropnamelater. Use a view or generated column as an alternative bridge.
Further reading
Section titled “Further reading”- Martin Kleppmann, Designing Data-Intensive Applications (2017), chapters on storage, transactions and replication.
- Abraham Silberschatz, Henry Korth, S. Sudarshan, Database System Concepts (7th ed., 2019).
- Alex Petrov, Database Internals (2019).
- Markus Winand, SQL Performance Explained and the website use-the-index-luke.com.
- PostgreSQL documentation: MVCC, transaction isolation,
EXPLAIN. - E. F. Codd, “A Relational Model of Data for Large Shared Data Banks” (1970).
- Patrick O’Neil et al., “The Log-Structured Merge-Tree (LSM-Tree)” (1996).
- Hal Berenson et al., “A Critique of ANSI SQL Isolation Levels” (1995).