Skip to content

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.

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.

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.

  1. Identify entities (nouns): customer, order, product.
  2. 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).
  3. 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.
  4. 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 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: X→YX \to Y means each value of XX determines exactly one value of YY.

  • 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.

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.

A table without an index is a heap: finding a row means scanning all nn rows, O(n)O(n). An index is an auxiliary data structure mapping key values to row locations.

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-right

With 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: O(log⁡Bn)O(\log_B n) for lookup/insert, where BB 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.

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.

  • Composite indexes follow the leftmost prefix rule: an index on (a, b, c) supports filters on a, on a,b and on a,b,c, but not on b alone. Order columns: equality predicates first, then the range/sort column.
  • Covering indexes (INCLUDE columns 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 on lower(email)).
CREATE INDEX order_customer_placed ON "order" (customer_id, placed_at DESC);
-- supports: WHERE customer_id = ? ORDER BY placed_at DESC LIMIT 20
CREATE INDEX order_pending ON "order" (placed_at) WHERE status = 'pending';

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).

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.
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.

“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.

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,000

Things 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 rows indicate 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.

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):

  1. Expand: add the new column/table (nullable or with a default that does not rewrite the table), add indexes concurrently (CREATE INDEX CONCURRENTLY in PostgreSQL).
  2. Deploy code that writes both old and new (and reads old).
  3. Backfill existing rows in small batches (avoid one giant transaction).
  4. Deploy code that reads the new; verify.
  5. Stop writing old; deploy.
  6. 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 lock
  • 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.
  • 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.
  1. Conceptual. A table employee(id, dept_id, dept_name, dept_head) — identify the functional dependencies, the normal form it violates, and the decomposition.
  2. 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?
  3. Conceptual. Walk through write skew with the on-call doctors example; list two ways to prevent it.
  4. 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.
  5. Conceptual. Plan a zero-downtime rename of users.name to users.full_name on a 500M-row table.
Solutions (sketch)
  1. dept_id -> dept_name, dept_head: a transitive dependency (violates 3NF). Split into employee(id, dept_id) and department(id, name, head).
  2. (customer_id, status, placed_at DESC): equality columns first, then the sort column, so the index delivers rows in order. A partial index WHERE status = 'paid' on (customer_id, placed_at DESC) is smaller if this is the dominant query.
  3. 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 UPDATE on the on-call rows, or a constraint/summary row).
  4. Add full_name; dual-write in app; batch backfill; switch reads; stop writing name; drop name later. Use a view or generated column as an alternative bridge.
  • 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).