Database indexing

A table is a pile of rows. To find one row by a field with no help, the database reads the whole pile. An index is a second structure, kept in sorted order, that points from a field's value to the rows that have it. It is the first tool for a slow query and the first one to overuse.

Crux: an index turns a scan of every row into a few steps by keeping a sorted copy of one or more columns. It speeds reads and slows writes, so index the queries you run most and nothing else.

Why indexes exist

Arithmetic with assumptions: a table of 100 million rows at 200 B each is 20 GB (100 M × 200 B). With no index, a query by an unindexed column reads all of it. At an assumed 1 GB/s of sequential reading, that is about 20 seconds for one lookup.

With an index on that column, the database does a handful of page reads, a few milliseconds. The ratio, thousands of times, is why this is the first thing to check.

How rows sit on disk

Rows are stored in files of fixed-size pages, and the database reads whole pages, never single rows. A full scan reads every page in order. A lookup by an unindexed value cannot skip any page. Reading pages one after another (sequential) is much faster than jumping to scattered ones (random), even on SSDs, and an index is a way to turn "read everything" into "read a few specific pages".

The B-tree: the default

Most relational databases build a B-tree (strictly a B+ tree) for an index. It is a shallow, wide tree.

• Each node is one page on disk (commonly 8 KB in Postgres and 16 KB in MySQL's InnoDB), holding many sorted keys and pointers.
• A lookup goes from the root down one node per level. Each step discards most of what remains.
• The tree stays balanced by splitting and merging pages as rows come and go, so every lookup has the same depth and random inserts do not degrade it.
• Keys at the bottom are in order and linked, so a range (BETWEEN) and an ORDER BY are cheap: find the start, then read along.

How deep is it? A page holds hundreds of entries. Assume 500 entries per page:

1 level:   500 keys
2 levels:  500 × 500            =         250,000
3 levels:  500 × 500 × 500      =     125,000,000

So a 100-million-row index is about three levels deep, three or four page reads, and the top levels are almost always cached in memory. A lookup is therefore close to one disk read, whether the table has a thousand rows or a hundred million.

Alternatives

• Hash index. Maps a value to a row with one hash. Equality only, no ranges and no ordering. Rarely the right pick, since a B-tree does equality almost as fast and also does ranges. Many in-memory stores are hash tables underneath.
• LSM tree (log-structured merge tree). Writes go to memory and an append-only log, then are merged into sorted files on disk in the background. Writes are very fast (sequential). Reads may check several files, so engines add Bloom filters. Used by Cassandra, RocksDB and others. In more detail: new writes sit in a sorted in-memory table and a log (for crash safety); when it fills, it is saved as an immutable sorted file; background compaction merges files and drops overwritten values. A read may look in memory and then several files, which is the cost (read amplification), and compaction uses disk and CPU while it runs. Trade: cheap writes against slower, more variable reads, plus background compaction work. Choose it for write-heavy data such as metrics, events and message logs; choose a B-tree when reads and range scans matter more. (DynamoDB's internals are not fully public, so do not state its storage engine as fact.)
• Inverted index. Maps each word to the documents that contain it. This is how full-text search works (see the search lesson in key technologies).
• Geospatial indexes. Map locations so that "nearby" is a cheap lookup. A geohash turns a coordinate into a string where a shared prefix means a shared area, so a B-tree can serve it. A quadtree splits a map into four cells, and splits a crowded cell again, so dense cities get finer cells. An R-tree groups nearby shapes into overlapping boxes, and is what spatial extensions to relational databases use. Searching a point means checking its cell and the neighbouring ones, because a nearby item can sit just across a cell border.

Composite indexes

An index can cover several columns, for example (country, city). It is sorted by the first column, then by the second within each first value.

The leftmost prefix rule: the index helps queries that use its first column, or its first two, and so on. It does not help a query on only the second column.

• Put the column you filter by equality first, and the column you range or sort by last. For "orders for user 7 in the last week, newest first", use (user_id, created_at).
• One composite index replaces several single ones that share a prefix: (a, b) also serves queries on a alone.

A covering index contains every column the query needs, so the database never visits the table (an index-only scan). It is fast, and the index is bigger.

What an index costs

• Writes. Every insert, update to an indexed column, or delete must also change each index. A table with 5 indexes does 1 table write plus 5 index writes per insert, six in all.
• Space. An index is a copy of its columns plus pointers. Large indexes fall out of memory and get slow.
• Planning effort. More options for the query planner, and more to keep in mind.

When an index does not help:

• Low selectivity. An index on a column with two values (a boolean) returns half the table. A scan is cheaper.
• Function on the column. WHERE lower(email) = 'x' cannot use a plain index on email. Index the expression, or store it normalised.
• Leading wildcard. LIKE '%term' cannot use a B-tree. That is the reason for a search index.
• Small tables. A scan of a few thousand rows is as fast.
• Write-heavy logs. An append-only table taking thousands of inserts a second pays for every index on every row. Index only what a real query needs.

Useful variations: a unique index enforces a rule as well as speeding a lookup. A partial index covers only some rows (WHERE active), staying small.

How to work with indexes

• Start from the queries, not the columns. List the hot queries from the data model, with their rates, and give each a path.
• Read the plan. EXPLAIN shows whether the database scans or uses an index, and how many rows it expects. Check the plan, do not guess.
• Primary key first. In many engines the primary key is already an index, and in some (InnoDB) the table is stored in that order. Choose it well.
• Remove unused indexes. They cost writes and give nothing.

Indexes and sharding

On a sharded table, an index on the shard key sends a query to one shard. An index on another column is either local (each shard has its own, so the query asks every shard) or global (one index spread by its own key, so a write updates two places). The sharding lesson explains the consequences.

A worked example: the link shortener

• links by code. code is the primary key, one lookup, the hot path at about 12,000 per second at peak.
• "My links, newest first." (owner_id, created_at). Equality first, then the sort column, so the query reads one contiguous run in order.
• clicks by (code, clicked_at). "Clicks for this link in a time range" is a range read on the second column after an equality on the first.
• No index on url unless "does this URL already exist?" is a requirement, and then it is a unique index and an extra write on every create (about 40 per second, which is cheap).

The clicks table takes about 4,000 writes per second. Every extra index adds work to each, so keep it to the one that serves a real query.

Common mistakes

• Indexing every column "just in case".
• Composite indexes in the wrong order, so the query cannot use them.
• Indexing low-selectivity columns.
• Wrapping an indexed column in a function.
• Adding an index to fix a slow query without reading the plan.
• Forgetting that an index slows writes on a write-heavy table such as clicks.
• Indexing a tiny table, or an append-only log nobody queries by that column.
• Not knowing what a covering index would save: an extra column in the index can avoid every table visit for a hot query.

Check yourself

• Why does a 100-million-row lookup cost about 3 page reads with a B-tree?
• Which queries can a B-tree serve that a hash index cannot?
• For (user_id, created_at), which queries are fast and which are not?
• What is a covering index, and what is its cost?
• Name three reasons an index might not be used.
• What does an LSM tree trade to make writes fast, and what does compaction do?
• Why is reading pages in order faster than reading scattered pages, and how does an index help?
• How would you index "restaurants within 2 km"?