Use The Index, Luke

Ideas you will meet

Databases

Schemas, indexes, query plans and choosing a store.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• System Design Foundations · 11 minChoosing and using a databaseRelational versus NoSQL, what an index really does, and how to decide between them without following fashion.Read hereClose

  The two big families

  Relational databases (PostgreSQL, MySQL) store data in tables with rows and columns, linked by keys. You query them with SQL and can join tables. Their key promise is ACID transactions:

  • Atomicity: a group of changes happens entirely or not at all.
  • Consistency: rules such as foreign keys always hold.
  • Isolation: concurrent transactions do not see each other's half-finished work.
  • Durability: once committed, data survives a crash.

  NoSQL databases is a loose label for stores that give up some relational features for scale or flexibility:

  Type	Shape	Examples	Good for
  Key-value	key maps to a blob	Redis, DynamoDB	caches, sessions, huge lookups
  Document	JSON-like documents	MongoDB, Firestore	content with varied fields
  Wide-column	rows with flexible columns	Cassandra, HBase	massive write volumes, time series
  Graph	nodes and edges	Neo4j	relationship-heavy queries

  A quick map from the kind of question you ask to the kind of store that answers it best:

  100%

  Figure SDA-FND-04-1 · Which kind of store fits the questions you ask · © forcsguy.com

  Image: MarkBuckawicki · CC0 · Source · Wikimedia Commons: Wooden Card Catalog Furniture

  Indexes: how reads get fast

  Without an index, finding rows where email = '[email protected]' means reading every row. With an index on email the database keeps a sorted structure (usually a B-tree) and finds the row in a few steps, even among millions.

  100%

  Figure SDA-FND-04-2 · Indexed lookup versus full scan · © forcsguy.com

  The trade-off: each index takes space and every write must update it. Index the columns you filter, join and sort on, and do not index everything.

  Useful habits:

  • Look at how the database plans a query (EXPLAIN) before guessing.
  • A composite index on (user_id, created_at) serves queries on user_id alone or on both, but not on created_at alone. Column order matters.
  • Very low-variety columns (like a true/false flag) rarely benefit from an index.

  Where relational databases get strained

  A single relational database handles a lot, but you may hit limits:

  • Read load: add copies that serve reads (lesson 5).
  • Write load or data size: split the data across several databases, called sharding (lesson 5).
  • Shape of data: huge volumes of simple records, or extremely flexible documents, may fit another model better.

  Choosing: ask about the access pattern

  1. What are the most frequent queries? By key, by range, by search, by relationship?
  2. Which guarantees are non-negotiable? Strict consistency for money, or "eventually correct" for like counts?
  3. How big and how fast will it grow?
  4. What does the team already know how to operate?

  A worked example: what an index is worth

  A table holds 100 million orders, and the app asks "show this customer's orders" thousands of times a second.

  • Without an index the database reads every row to find matches: a sequential scan. At, say, 200 bytes a row that is 20 GB read from disk or cache for a single query, taking seconds. Do that 1,000 times a second and the database collapses.
  • With a B-tree index on customer_id the database walks a shallow tree. A page holds a few hundred keys, so 100 million rows need only about 4 levels: root, two internal levels, a leaf. That is roughly 4 page reads to find the row locations, then a few more to fetch the rows. Most of the upper levels live in memory, so the real cost is one or two disk reads, in milliseconds.

  The price: every index must be updated on every insert, update and delete. A table with 5 indexes turns one logical insert into about 6 physical writes, and the indexes take space (often as much as the table). So index what your queries actually filter, join and sort on, and not much else.

  100%

  Figure SDA-FND-04-3 · Finding one row among a hundred million with a B-tree · © forcsguy.com

  What a transaction does for you

  A transaction groups several changes so they succeed or fail together. A transfer of 100 from account A to account B is two updates, and it must never be applied halfway. Relational databases give transactions the ACID properties:

  • Atomic: all of it happens or none of it.
  • Consistent: rules such as "balance never negative" are enforced.
  • Isolated: concurrent transactions do not see each other's half-finished work (to a degree you choose).
  • Durable: once the database says "committed", the change survives a crash.

  Durability comes from the write-ahead log (WAL): before changing the data pages, the database appends the change to a log and forces it to disk. If the machine crashes, restart replays the log and the committed work reappears.

  100%

  Figure SDA-FND-04-4 · Why a committed write survives a crash · © forcsguy.com

  You can build a toy version in the write-ahead log lab.

  Mistakes people make

  • No index on the column you filter by, especially foreign keys. Use EXPLAIN to see whether a query scans.
  • Too many indexes. Each one slows writes and uses memory. Drop the ones nobody uses.
  • The N+1 query. Loading 100 orders and then running one query per order for its items is 101 round trips. Load them together with a join or a single IN query.
  • Money as floating point. Use integers (cents) or exact decimals.
  • Choosing NoSQL to avoid thinking about schema. If your data is relational, you will rebuild joins and constraints by hand, badly.
  • Treating the database as a queue or a log. Polling a hot table for work is a common cause of lock contention (see the SKIP LOCKED lesson for doing it properly).
  • Never testing a restore. A backup you have not restored is a hope, not a backup.

  Try it yourself

  Open the indexes in depth lesson and the query optimisation lesson next. In the System Builder, see how much load a cache and replicas take off a single database.

  Real-world reading

  Related reading

  • Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases (paper)Verbitski et al. · Amazon Web ServicesPapers
  • Minimizing Read-Write MySQL Downtime at YelpYelp engineers · YelpCase Studies
  • Sherpa: Distributed NoSQL Key-Value Store at YahooYahoo engineers · YahooCase Studies
  • Use The Index, LukeMarkus Winand · use-the-index-luke.comCourses

  Show 6 moreShow fewer

  • Fast Order Search using Data Pipeline and Elasticsearch at YelpYelp engineers · YelpCase Studies
  • MPH: Fast and Compact Immutable Key-Value Stores at IndeedIndeed engineers · IndeedCase Studies
  • Espresso: Distributed Document Store at LinkedInLinkedIn engineers · LinkedInCase Studies
  • MongoDB at Baidu: Multi-Tenant Cluster Storing 200+ Billion Documents across 160 ShardsMongodb engineers · MongodbCase Studies
  • Relational DatabasesMysql engineers · MysqlCase Studies
  • Document DatabasesMicrosoft engineers · MicrosoftCase Studies

  Open this lesson with its quiz and exercise

• Storage, Queues and Real-time · 11 minChanging a live database: online indexes and schema changesHow to add an index or alter a large table without blocking traffic: concurrent index builds, shadow-table copies with change capture, cut-over, and how to roll back.Read hereClose

  The problem

  Tables grow, queries change, and sooner or later you must add an index or change a column on a table that is serving live traffic. A naive change can lock the table for minutes or hours. For a 2 billion row table that is an outage.

  The goal of an online change: keep reads and writes working, limit extra load, and be able to back out.

  Pattern 1: build the index concurrently

  Some databases can build an index while writes continue. PostgreSQL's CREATE INDEX CONCURRENTLY scans the table twice and waits for existing transactions, so it does not block writes.

  Trade-offs: it takes longer and uses more I/O; it cannot run inside a transaction block; if it fails it can leave an invalid index that you must drop before retrying. Watch for long-running transactions that make it wait.

  Pattern 2: shadow table plus change capture

  For schema changes that rewrite the table, many teams use a copy approach, used by tools such as gh-ost and pt-online-schema-change:

  1. Create a shadow table with the new structure.
  2. Backfill by copying rows in small chunks.
  3. Meanwhile capture every change to the original (from the replication log or with triggers) and apply it to the shadow table.
  4. When the copy has caught up, cut over: a brief swap that renames the shadow table into place.
  5. Keep the old table for a while for rollback.

  100%

  Figure SDA-SQR-02-1 · Online schema change with a shadow table · © forcsguy.com

  Safety checklist

  • Throttle by replica lag, CPU and connection counts; the migration must back off when production suffers.
  • Test on a copy of production-sized data first; time and I/O surprise people.
  • Verify with row counts and sampled checksums before cut-over.
  • Plan the cut-over window for low traffic; make it short and reversible.
  • Keep the old table for rollback until you are confident.
  • Watch replicas: large changes can cause replication lag, which in turn breaks read-after-write assumptions.

  Backward-compatible steps (expand and contract)

  Schema and code must change in an order that never breaks either:

  1. Expand: add the new column or index; old code still works.
  2. Deploy code that writes both shapes and reads the new one when available.
  3. Backfill old rows in batches.
  4. Switch reads fully to the new shape.
  5. Contract: remove the old column in a later release, once nothing reads it.

  100%

  Figure SDA-SQR-02-2 · Expand and contract · © forcsguy.com

  Real-world reading

  Related reading

  • PostgreSQL: CREATE INDEX (CONCURRENTLY)PostgreSQL Global Development Group · PostgreSQLDocumentation
  • gh-ost: GitHub's online schema migration tool for MySQLGitHubGitHub
  • gh-ost: GitHub's online migration tool for MySQLGitHub Engineering · GitHubCase Studies
  • Online migrations at scaleJacqueline Xu · StripeCase Studies

  Show 1 moreShow fewer

  • Use The Index, LukeMarkus Winand · use-the-index-luke.comCourses

  Open this lesson with its quiz and exercise

• Storage, Queues and Real-time · 9 minThe repository pattern: hiding storage behind a domain interfaceWhat a repository is, how it keeps business logic independent of the database, how to write one well, and the traps: leaky abstractions and generic repositories.Read hereClose

  The problem

  Business logic such as "an order can only be cancelled before shipping" should not care whether orders live in PostgreSQL, DynamoDB or a test double. If the rule code is full of SQL, ORM calls and table names, it is hard to read, hard to test and hard to change.

  A repository is an object that looks like an in-memory collection of domain objects, and hides how they are loaded and saved.

  100%

  Figure SDA-SQR-05-1 · Layers around a repository · © forcsguy.com

  A small example

  interface OrderRepository {
    nextId(): string;
    findById(id: string): Promise<Order | null>;
    findOpenForCustomer(customerId: string): Promise<Order[]>;
    save(order: Order): Promise<void>;
  }
  
  class InMemoryOrderRepository implements OrderRepository { /* a Map, for fast tests */ }
  class PgOrderRepository implements OrderRepository { /* SQL here, and only here */ }
  

  The application service receives an OrderRepository, so tests can pass the in-memory version and production passes the PostgreSQL one.

  Guidelines

  • One repository per aggregate root. An order and its line items are saved together; do not give every table its own repository.
  • Name methods after business questions (findOpenForCustomer), not storage mechanics (selectWhere).
  • Return domain objects, not ORM entities or rows. Keep mapping inside the implementation.
  • Keep transactions in the application layer (or a unit of work), so one use case can change several aggregates atomically.
  • Mind the queries. Load what the use case needs in one go to avoid the N+1 problem, and give read-heavy screens a separate read model instead of bending the repository.

  100%

  Figure SDA-SQR-05-2 · Writes through repositories, reads through a read model · © forcsguy.com

  When it is not worth it

  • Tiny CRUD apps where the domain is just the table: the ORM already is the abstraction, and a repository adds ceremony.
  • Generic repositories (Repository<T> with find(filter)) just re-export the database through another name and defeat the purpose.
  • Pretending storage is interchangeable. Switching from SQL to a document store changes consistency and query models, not just the class behind the interface. Design the interface for what your domain needs and accept that some choices are real commitments.

  Real-world reading

  Related reading

  • Repository (Patterns of Enterprise Application Architecture)Martin Fowler · martinfowler.comBlogs
  • Use The Index, LukeMarkus Winand · use-the-index-luke.comCourses
  • Online migrations at scaleJacqueline Xu · StripeCase Studies

  Open this lesson with its quiz and exercise