Databases and Storage Engines

The query that worked until the customer grew

A support page lists the newest failed orders for one tenant. It was quick when every tenant had a few thousand orders. One large customer now has millions, and the page takes seconds to load.

select id, status, created_at, total
from orders
where tenant_id = ?
  and status = 'failed'
order by created_at desc
limit 50;

“The database is slow” is no more useful than “the network timed out.” The query may be scanning far more rows than it returns. The chosen index may find failed orders but not isolate the tenant. The plan may estimate ten matches where the large tenant has a million. A replica may be behind. The buffer cache may be cold after a failover. Vacuum, checkpointing, compaction, a backup, or a backfill may be competing for the same I/O.

The investigation begins with the path one operation must take:

query -> plan -> index -> data pages -> result
write -> log -> memory/pages -> indexes -> replication -> maintenance

Those arrows are the useful center of database choice. A database promises to preserve some facts, find them through particular access paths, and recover them after failure. Every promise has a foreground cost and, usually, a background one.

Start with operations, not product names

Before proposing a store, write down the few operations whose failure would change the design. For this order system they might be:

• create an order and preserve its payment identity;
• fetch an order with its items by ID;
• list recent failed orders for one tenant;
• append a high volume of order and device events;
• search support notes by text;
• retain audit history for seven years;
• restore one tenant after an accidental deletion.

Then add the promises around those operations: expected volume and growth, latency, constraints, acceptable staleness, durability, retention, and recovery time. “Use PostgreSQL” or “use NoSQL” does not answer any of them.

The facts suggest more than one storage shape. Orders, items, customers, and payments have relationships and durable invariants; a relational model can express them with keys, constraints, joins, and transactions. Raw events are append-heavy and may fit a partitioned log or an LSM-backed store. Text search wants an inverted index and relevance semantics. Broad historical analysis wants a columnar path that can scan selected columns without competing with checkout traffic.

A document store is useful when the product usually reads and changes one aggregate as a unit. A key-value store is useful when identity and access are both an exact key. A graph store earns its place when relationship traversal is the dominant work. None of these labels removes the need to state the important query, invariant, and recovery promise.

Using several stores can be honest architecture. It also creates several copies of a fact. For every search index, cache, warehouse table, or denormalized read model, name the source of truth, update mechanism, allowed lag, rebuild path, and behavior while the copy is wrong.

Let the query choose the index

Return to the support page. An index on created_at can produce recent rows, but it may walk past orders from every tenant. An index on status may still cover a large fraction of the table. The useful access path begins with the query’s equality conditions and continues into the ordered range:

create index orders_tenant_status_created_id
on orders (tenant_id, status, created_at desc, id desc);

For a B-tree index, the leading tenant_id and status values narrow the part of the tree to scan. The remaining keys already have the requested order. id supplies a stable tie-breaker when two orders share a timestamp. The next page can continue from the final pair rather than counting past an ever-growing offset:

select id, status, created_at, total
from orders
where tenant_id = ?
  and status = 'failed'
  and (created_at, id) < (?, ?)
order by created_at desc, id desc
limit 50;

This is a design to test, not an incantation. Engines differ in their index rules, tuple comparisons, included columns, and treatment of sort direction. Data distribution matters too. Run the engine’s actual-plan facility on representative tenant sizes. Compare estimated and actual rows, look for a large scan or sort before the limit, and measure the write cost after adding the index.

An index is a durable read promise paid for by writes. Each insert, key update, and delete must maintain every affected index. The extra structure takes storage, consumes cache, appears in backups and replication traffic, and needs its own maintenance. A covering index may avoid visits to the base table for a hot query, but a wide covering index can cost more than those visits save. Keep an index because a consequential access path uses it, not because a column occasionally appears in a filter.

Constraints may use the same machinery for a different purpose. A unique index can make duplicate values conflict even when two application processes race. That is stronger than checking first and inserting later. Exactly which invariant belongs inside a transaction is the subject of the next chapter; the storage lesson here is that durable invariants should not depend solely on every writer remembering the same application check.

What the B-tree does with that promise

A B-tree or B+tree keeps ordered keys in balanced pages. Internal pages direct the search through separator keys; a leaf page contains the target key or the start of a range. Neighboring leaf pages make an ordered scan possible. The engine keeps hot pages in a buffer pool or cache, so the height of the tree does not translate directly into a disk read at every level.

Our composite index places one tenant’s failed orders beside one another in index order. A point lookup descends to one position. The dashboard descends once, then walks the next fifty entries. That is why index order is part of the query design rather than a property to add afterward.

Writes expose the other side. Changing an order can dirty a table page and several index pages. A full page may split, producing more page writes and changing the shape of the tree. Randomly distributed keys can touch pages across the index; a monotonically increasing key can concentrate insertion at one edge. More indexes improve selected reads while increasing write and space work for all writes.

B-trees are a strong default for mixed transactional workloads because point lookups, ordered scans, and incremental updates share one structure. They are not free, and they are not the only way to postpone organization work.

A committed write has a history

The database should not need every changed data page to reach its final disk location before acknowledging a transaction. Instead, a write-ahead-log engine records enough redo information before the corresponding data pages are flushed. After a crash, recovery can replay durable log records and bring the data files forward.

change rows and indexes in memory
        -> append log record
        -> make the required log durable
        -> acknowledge commit
        -> flush dirty data pages later

The exact durability promise depends on engine settings, storage behavior, and whether acknowledgment also waits for another node. Group commit can amortize one durable log flush across several transactions. Checkpoints limit how far recovery must work from an earlier consistent point; they can also create I/O pressure if their writes arrive in bursts.

This path explains three forms of amplification. Write amplification occurs when one logical change produces log writes, table writes, index writes, replication, or later rewriting. Read amplification occurs when one logical lookup examines many pages or files. Space amplification comes from indexes, old row versions, tombstones, snapshots, and replicas beyond the live logical data. A design seldom eliminates amplification. It decides which kind the workload and operators can afford.

An LSM tree moves the organization work

Suppose the order system also receives millions of immutable device events per hour. Updating several B-tree indexes for every event may put too much random work on the foreground path. A typical log-structured merge-tree path accepts a different bargain:

append to WAL -> update sorted memtable -> acknowledge
memtable fills -> flush immutable sorted file
background compaction -> merge sorted files and discard obsolete entries

The initial writes are sequential or in memory. Files on disk are immutable. This makes high ingest attractive, but the work has moved rather than vanished. A point read may have to consider the memtable and several sorted files; indexes and Bloom filters can avoid files that cannot contain the key. A range scan may merge results from several runs. An update or delete leaves an older value or a tombstone that compaction can remove only when it is safe to do so.

Compaction policy decides how aggressively files are merged. More aggressive organization can reduce read and space amplification while rewriting more bytes. A policy that favors cheap writes can leave more runs for reads and need more temporary space. If flush and compaction cannot keep up, the engine must let amplification grow, consume disk, or slow incoming writes. A background task has become foreground latency.

This makes “LSM is faster” the wrong conclusion. An LSM-backed design fits when sustained ingest, key and range access, retention, and available compaction bandwidth make that trade worthwhile. The recent-status query may still deserve a small table keyed by (tenant_id, device_id), while raw events flow to the append-optimized path and historical scans run elsewhere. One physical shape need not serve three incompatible access patterns.

Growth changes ownership and visibility

A replica holds another copy for availability, durability, read capacity, or geographic proximity. With synchronous replication, commit waits for the configured remote acknowledgment and therefore couples latency and availability to that participant. With asynchronous replication, the primary can acknowledge first, leaving a window of lag and, under some failover histories, possible loss of the newest acknowledged changes.

If the support page reads from an asynchronous replica, lag is product behavior: an agent can refresh after updating an order and see the old status. Possible responses include reading the primary for a period after a write, routing with a session position, choosing a sufficiently caught-up replica, or showing an explicit pending state. “Eventually consistent” is incomplete until the design says what someone sees before “eventually.”

Replication does not divide write ownership. Sharding does. A shard key decides which node or range owns a record, so it must serve both distribution and locality. tenant_id keeps the support query local and gives a natural administrative boundary, but one enormous tenant can become a hot shard. A random key spreads writes while turning tenant reports into scatter-gather work. Adding a time bucket may help retention and spread ingest while making long histories cross partitions.

There is no key that optimizes every operation. Choose from the critical operations, then describe hot-key handling, rebalancing, tenant moves, cross-shard queries, and what happens when a migration is interrupted. Shards are long-lived data ownership, not a last-minute capacity switch.

Background work belongs in the design

The support query and event ingest share storage with work users never asked for directly: vacuum or version cleanup, compaction, checkpoints, statistics, index creation, backfills, rebalancing, snapshots, and backups. Each competes for CPU, memory, I/O, network, or locks.

When the query slows after growth, inspect the operation and its surroundings:

• Is the actual plan using the intended access path, and are its row estimates credible?
• How many rows, pages, or sorted files are examined to return fifty orders?
• Did a cast, function, collation, or changed predicate prevent index use?
• Are cache misses, replica lag, compaction backlog, old row versions, or I/O saturation correlated with the tail?
• Did a statistics refresh, new data skew, index build, backfill, backup, or failover change the environment?

The answer should lead to a falsifiable change. Add or reorder an index and compare the actual plan. Remove an overlapping index and measure write latency. Move analytics off the primary and observe I/O. Throttle a backfill and watch replication lag. A product name is not a diagnosis.

Recovery is the final storage operation

A replica is not a backup: it can faithfully reproduce an accidental delete or corrupt application write. A credible recovery design starts with two product statements. The recovery-point objective says how much recent data may be lost. The recovery-time objective says how long restoration may take.

From there, choose the mechanics: physical or logical backups, snapshots, incremental copies, archived logs for point-in-time recovery, and separate failure domains. Include encryption keys, schema state, external object storage, and the means to rebuild derived indexes. Decide whether recovery must restore the whole cluster or one tenant without overwriting everyone else’s valid data.

Only a restore answers whether the backup is usable. Test it at realistic size, with realistic credentials, then verify application invariants and a known set of records. Measure the time. A successful backup job proves that bytes were written; it does not prove that the product can return.

Follow one harder change

The large tenant now asks for seven years of orders, sub-second support pages, near-real-time text search, and deletion of one customer’s personal data. At the same time, device-event ingest is expected to triple.

Before adding another database, trace the consequences:

1. Which system owns the order and the deletion decision?
2. Which index serves the support page, and what does it add to every write?
3. Which derived stores receive the data, how far may they lag, and how are they rebuilt or purged?
4. Which engine absorbs the event rate, and how much flush and compaction work does that rate create?
5. Which partition key keeps ordinary reads local without trapping the large tenant forever?
6. What exact restore can meet the promised loss and recovery windows?

That sequence is more durable than a catalog of databases. Begin with the operation, follow its access path into pages or sorted files, account for the work deferred to logs and maintenance, and finish at restore. The next chapter takes one promise left deliberately unresolved here: when two writers race, which transaction boundary keeps the durable facts true?