6 — Databases: indexes, transactions and isolation

The database is usually the hardest part of a system to change and scale. Application servers can be replaced in minutes, but data has to survive everything. A good share of system design is about choosing a data store and using it well.

Data models

The old split into “SQL” and “NoSQL” hides more than it shows. The useful question is which data model a store offers, which queries it makes cheap, and which guarantees come with it. The main families are:

Many products span more than one row. DynamoDB stores key-value items whose values can be nested documents, and PostgreSQL stores documents in JSONB columns. The categories describe models, not products.

Relational, with PostgreSQL

A relational database stores rows in tables with a declared schema. Foreign keys, unique constraints and check constraints are enforced by the database, so every application that writes the data obeys the same rules. SQL can combine tables in ways nobody planned for when the schema was designed, which matters because the queries a product needs in its third year are rarely the ones it started with.

PostgreSQL also covers several cases often assumed to need another store.

• Documents. The jsonb type stores JSON in a decomposed binary format. The documentation describes it as slightly slower to input than plain json but significantly faster to process, since it needn’t be reparsed. A GIN index on a jsonb column supports containment queries such as doc @> '{"status": "paid"}'. The non-default jsonb_path_ops operator class builds a smaller, faster index for containment, but doesn’t support the key-exists operators.
• Partitioning. Declarative partitioning splits one logical table into partitions by range, list or hash. With partition pruning, the planner skips partitions that can’t contain matching rows. Dropping an old monthly partition is far cheaper than deleting its rows. This is all on one server: it helps maintenance and some queries, but doesn’t add machines.
• Read replicas. A standby server replays the primary’s write-ahead log, and hot standby lets it answer read-only queries while it does. PostgreSQL’s documentation calls standby data eventually consistent with the primary, since changes take time to arrive (chapter 12). Long queries on a standby can also be cancelled when they conflict with changes being replayed, such as rows that vacuum removed on the primary.
• Sharding. Core PostgreSQL doesn’t shard a table across machines. The Citus extension does: it’s an extension rather than a fork, and it distributes tables across worker nodes by a chosen distribution column. Queries that filter on that column go to one node. Queries that span shards run in parallel, but cost more, and joins work best when related tables are co-located, sharded by the same key. Citus’s own documentation lists workloads it doesn’t suit, starting with ones that will never outgrow a single PostgreSQL node.

A single PostgreSQL server with replicas handles a great deal of load, so it’s a sensible default. The reasons to choose something else are usually specific: a key-value workload at a scale where one primary can’t take the writes, a query shape SQL handles poorly, or an operational model the team prefers.

Key-value

A key-value store maps a key to a value and does little else. With no query planner and no joins, each operation is a lookup by key, usually hashed to one partition, so latency stays flat as data grows. That makes it a good fit for sessions, carts, feature flags, rate-limit counters and caches (chapter 7).

The cost is that any question not phrased as “get key K” has no fast path. Finding all sessions for one user needs a second structure maintained by the application, or a secondary index if the store offers one. DynamoDB, for example, adds a sort key, so items sharing a partition key are stored in order, which supports range reads within a partition.

Document

A document store keeps each record as a nested document, so an order and its line items can live together and be read in one operation. When the unit the application reads and writes is the same as the unit the store keeps, this is simple and fast.

Trouble starts with relationships between documents. Data shared by many documents, such as a customer’s address on every order, either gets copied, so updates have to touch every copy, or gets referenced, and the application joins it by hand. In MongoDB, an operation on a single document is atomic, and the documentation recommends embedding related data to reduce the need for multi-document transactions.

Wide-column

Wide-column stores such as Cassandra organize data by a primary key with two parts. The partition key is hashed to choose the nodes that hold the data. The clustering key sorts rows within a partition.

-- Cassandra CQL: one partition per sensor per day, rows sorted by time
CREATE TABLE readings (
    sensor_id text,
    day       date,
    ts        timestamp,
    value     double,
    PRIMARY KEY ((sensor_id, day), ts)
) WITH CLUSTERING ORDER BY (ts DESC);

Reading the latest readings for one sensor on one day touches one partition, already sorted. Reading all sensors above some value touches every partition, and the table isn’t designed for it. So tables are designed from the queries, and the same data is often written to several tables, one per query.

Writes are cheap because of the storage engine. Cassandra’s write path appends to a commit log, updates an in-memory memtable, and later flushes the memtable to an immutable, sorted SSTable on disk. No existing data is read or rewritten during a write. Compaction later merges SSTables in the background, which the documentation notes rewrites each piece of data several times. This is the LSM tree design from chapter 14, traded for slower reads that may have to check several files.

Graph

A graph database stores nodes and edges, and is built for queries that follow edges several hops out: friends of friends, the shortest path between two accounts, every service affected by a failing one.

PostgreSQL can do the same traversals with a recursive common table expression. PostgreSQL’s documentation explains that it’s evaluated iteratively: a working table holds the latest rows, the recursive part is joined against it, and the loop stops when no new rows appear.

WITH RECURSIVE reach(person) AS (
    SELECT 42
  UNION                                -- UNION removes rows already seen
    SELECT f.followee
    FROM follows f JOIN reach r ON f.follower = r.person
)
SELECT count(*) FROM reach;

This query has no depth limit, and relies on UNION to stop at people already seen. A version with UNION ALL, or one that carries a depth or path column so that every row differs, keeps every path instead. A simulation of that evaluation, on 100,000 people who each follow 20 random others, counted the rows each round produces, and the index lookups into follows that produce them:

import random

random.seed(1)
N, DEGREE = 100_000, 20                      # people, follows per person
edges = {u: random.sample(range(N), DEGREE) for u in range(N)}

def recursive_cte(start, depth, union_all):
    seen, working = {start}, [start]
    rows, lookups = 1, 0
    for _ in range(depth):
        lookups += len(working)              # one index lookup per working row
        nxt = []
        for u in working:
            for v in edges[u]:
                if union_all or v not in seen:
                    seen.add(v)
                    nxt.append(v)
        if not union_all:
            nxt = list(dict.fromkeys(nxt))
        rows += len(nxt)
        working = nxt
    return rows, lookups, len(seen)

for depth in range(1, 6):
    print(depth, recursive_cte(0, depth, True)[:2], recursive_cte(0, depth, False))

Two things stand out. Keeping every path grows twentyfold each hop, so deduplication matters more than the query language. And by the fourth hop the traversal reaches most of the graph, whatever engine runs it. A graph database’s advantage is a cheaper hop: each node points straight at its edges, where a recursive CTE does an index lookup per row. That matters for deep, selective traversals run constantly. For two or three hops over data that’s otherwise relational, a recursive CTE on an indexed edge table is often enough.

Search engines

A search engine such as Elasticsearch builds an inverted index, mapping each term to the documents that contain it (chapter 14). It handles text analysis, relevance ranking and faceted counts, which relational indexes don’t do well.

It’s rarely the primary store. Writes become searchable only after a refresh: Elasticsearch’s documentation says indexes refresh every second by default, and only those searched in the last 30 seconds. It isn’t designed around multi-record transactions or constraints. Changing how a field is analyzed generally means reindexing. So the usual design keeps the source of truth in a database and feeds the search index from it through change data capture (chapter 15), accepting that search results lag slightly. If the index is lost, it can be rebuilt from the database.

Time-series

Time-series data is a stream of timestamped points per series: CPU usage per host, price per ticker, reading per sensor. Writes are almost all appends near the present, reads are ranges over recent time, and old data is either downsampled into coarser summaries or deleted.

Time-series stores are built for that shape. They compress runs of similar values, keep data ordered by series and time, and expire it in whole blocks. In PostgreSQL, the same pattern is a table range-partitioned by time, where expiry means dropping the oldest partition. Monitoring systems such as Prometheus are a specialized case, holding recent metrics for alerting rather than long-term business data.

“Schemaless” moves the schema

Document and key-value stores are often called schemaless. The data still has a schema, because the code reading it expects certain fields with certain types. What changes is where it’s enforced.

Schema-on-read is useful when records genuinely vary, or when the data comes from outside and its shape can’t be controlled. It costs discipline elsewhere: version fields in documents, readers that tolerate missing fields, and backfills when old shapes pile up. Many document stores now offer optional schema validation, which moves some of the rules back.

PostgreSQL can mix the two. Columns hold the fields every row has and that queries filter on, and a jsonb column holds the parts that vary.

Transactions aren’t the dividing line

Older comparisons say non-relational stores lack transactions. Several now have them, within limits.

• MongoDB. Multi-document transactions require feature compatibility version 4.0 on a replica set, and 4.2 on a sharded cluster. The documentation says that a distributed transaction usually costs more than single-document writes and shouldn’t replace good schema design, and that for many cases the embedded model is still the better one.
• DynamoDB. TransactWriteItems groups up to 100 put, update, delete and condition-check actions, which all succeed or all fail. They can span tables in the same account and Region, the items together can’t exceed 4 MB, and no two actions can target the same item. A ClientRequestToken makes a retried call idempotent for 10 minutes. A transaction is cancelled if it conflicts with another one in progress, so callers have to retry.

The real difference is in scope and cost. In PostgreSQL, any set of statements can be a transaction, with isolation levels to choose from. In these stores, transactions are an extra operation with size limits and higher latency, and the data model is still designed so that most writes don’t need them.

Choosing by access pattern

The way to pick a store is to write down how the data will be used before naming a product. For each kind of data:

1. List the queries, with their rough rates. Lookups by key, ranges by time, searches by text, traversals, ad hoc reports.
2. List the writes. Rate, size, whether they’re appends or updates, and which ones must change several records atomically.
3. State the consistency needs. Can a read be a few seconds stale? Must a constraint, such as “a seat is sold once”, hold?
4. Estimate size and growth (chapter 4).
5. Ask what changes. New query shapes are likely in a product, and less so in a metrics pipeline.

Then match patterns to models:

Most systems end up with more than one store, each holding data shaped for one job: PostgreSQL as the system of record, Redis for sessions and caches, a search index for text. Every extra store is another thing to run, back up and keep in sync, so each one should earn its place with an access pattern the default can’t serve.

How indexes work

Without an index, finding a row means reading the whole table. An index is a separate sorted structure that maps values to rows, like the index at the back of a book.

Most indexes are B-trees, which keep keys sorted in a shallow tree of pages. A lookup touches only a handful of pages, even across billions of rows, and sorted order makes range queries efficient too.

Indexes aren’t free.

• Every write has to update each index on the table.
• They take disk space and memory.

A composite index covers several columns, and column order matters. An index on (country, city) helps a query on country, or on both, but not one on city alone, for the same reason a phone book sorted by surname doesn’t help with first names.

A covering index holds every column a query needs, so the query never has to read the table.

To see how a database will run a query, EXPLAIN shows the plan, and a full table scan on a large table is the first thing to look for.

ACID transactions

A transaction groups several operations into one unit. Moving money between accounts has to subtract from one and add to the other, and both must happen or neither.

Isolation and its anomalies

Isolation is the subtle one. Full isolation is slow, so databases offer weaker levels, and each permits certain anomalies.

The SQL standard defines four levels. PostgreSQL’s implementation differs from the names in useful ways.

Serializable is safest, but aborted transactions need to be retried, so application code has to be ready for that.

A lost update

This is the anomaly that catches people most often. Two sessions in PostgreSQL each read the stock level and then write a new value, at the default Read Committed level:

CREATE TABLE stock (item text PRIMARY KEY, qty int);
INSERT INTO stock VALUES ('widget', 10);

-- Session A                                 -- Session B
SELECT qty FROM stock;      -- 10
                                             SELECT qty FROM stock;      -- 10
UPDATE stock SET qty = 9;   -- 10 - 1
                                             UPDATE stock SET qty = 9;   -- 10 - 1
SELECT qty FROM stock;      -- 9, two sold, should be 8

The fix is a single statement:

UPDATE stock SET qty = 10;

-- Session A                                 -- Session B
UPDATE stock SET qty = qty - 1;
                                             UPDATE stock SET qty = qty - 1;
SELECT qty FROM stock;      -- 8

Both sessions read 10, and both wrote 9, so one sale vanished. The fix is to let the database do the arithmetic in a single statement. Other fixes are SELECT ... FOR UPDATE, which locks the row, or optimistic locking, where each row has a version number and an update only succeeds if the version hasn’t changed.

Write skew

A hospital requires at least one doctor on call. Two doctors are on call, and each asks to go off call at the same moment. Each transaction checks that another doctor is on call, sees one, and removes itself. Both commit, and nobody is on call. Neither transaction changed the row the other one changed, so a simple row check doesn’t catch it. Serializable isolation does.

Multi-version concurrency control

Many databases, including PostgreSQL, use MVCC. A write creates a new version of a row, and each transaction sees the versions that existed at its snapshot. So readers don’t block writers, and writers don’t block readers. The cost is old versions that need cleaning up, which PostgreSQL does in a process called vacuum.

Connection pools

Opening a database connection is slow, and each one uses server memory. So applications keep a connection pool of open connections and share them.

The pool size sets a hard limit. With 20 connections and 10 ms queries, the maximum is 2,000 queries a second. Larger pools aren’t always better, because the database has to split its CPU and locks among more active queries, and past a point, throughput falls.

Slow queries are especially dangerous here. If queries slow from 10 ms to 1 second, the same pool now handles 20 a second, and every request queues for a connection. This is one of the most common ways a small database slowdown turns into a full outage.

The N+1 problem

An object-relational mapper can hide a costly pattern. Listing 100 posts and their authors can produce one query for the posts and 100 more for the authors, one at a time. On a page, that’s 101 round trips where two would do. The fix is to fetch all the authors in one query, with a join or WHERE id IN (...).

Normalization and denormalization

Normalization stores each fact in one place, which keeps data consistent. Denormalization stores copies to make reads faster, at the cost of keeping them in sync. A social feed that stores a precomputed like count is a typical example.

The usual approach is to normalize first, and denormalize specific things when measurement shows a need.

Schema changes

Changing the schema of a large live table is risky, because some operations lock it. The safe pattern is expand and contract:

1. Add the new column, nullable.
2. Deploy code that writes to both old and new.
3. Backfill old rows in small batches.
4. Deploy code that reads from the new column.
5. Remove the old column.

Each step can be rolled back, and the system keeps running throughout.

Scaling reads and writes

Reads usually scale with read replicas (chapter 12). Writes are harder, and the usual options are a bigger machine, then partitioning (chapter 11).

The takeaway

Pick a data model from the access patterns, and start from PostgreSQL unless a pattern clearly needs something else. “Schemaless” moves the schema into the application, and transactions now exist outside relational databases, with limits. Indexes make reads fast at a cost to writes. Transactions are a powerful tool, but their default isolation level allows anomalies, and the lost update is the one to watch for. Most database incidents involve a slow query and a full connection pool.