Indexes

At Amazon Ads, the API I worked on answered over a million calls a second, each inside 20 ms, and not one of them searched for anything. Each went straight to its answer, by key. The opposite, reading ten billion rows one by one for a single question, would take nearly three hours at a million rows a second.

The short version

• An index is the back of the book. A sorted list of values, each pointing to where its row lives. Sorted data halves the search at every step: ten billion gets to one in about 34 steps.
• The B-tree makes it four. Bayer and McCreight's 1970 tree is short and wide: with ~500 keys per page, four levels reach 62.5 billion entries, so one row is about four page reads, and the leaves are linked, so ranges come free.
• The zoo. Hash (exact matches only), inverted (word → documents, for search), vector (HNSW: nearest meaning, for RAG) and LSM trees (built for non-stop writes).
• The catch. Every index is paid for on every write (one insert, five indexes, six writes). Index what you query, need selectivity, mind column order (leftmost first), don't wrap the column in a function, and cover your hottest query.
• One read, by key. My API stored one item per (product, creative), so every call was a point lookup. DynamoDB hashes the partition key to pick the partition, so a viral key gets hot (hence a cache of hot keys on every host); a Bloom filter made "no" free; and a global secondary index is a second copy keyed differently, updated asynchronously.

As in my post about this API, every number about that system is illustrative, and the design there is simplified. The ten-billion-row table, the scan times and the 500-keys-per-page tree are illustrative arithmetic too.

And my job today. I now work on Azure Resource Graph, which handles 12B+ Azure resources a day. The episode uses it only as an illustration, built from Microsoft's public docs, not as a description of its internal design: when a resource changes, Azure Resource Manager notifies Resource Graph, which "then updates its database", and "a regular full scan" catches anything missed. You query that copy in KQL (Resources | summarize count()), never the resources themselves. The docs name the price too: the data "isn't strongly consistent" and is "indexed with a short latency".

DynamoDB's docs say it plainly: the partition key's value goes into an internal hash function, and the output decides the partition the item lives in. That's a hash index spread across a fleet, which is why the same viral key always lands on the same partition, and why AWS asks you to design for uniform activity across all your partition keys.

Further reading

• A Million Questions a Second — my long post on the ad-relevance API: point lookups, hash partitioning, hot keys and the Bloom filter.
• DynamoDB partitions — how a hashed partition key picks where an item lives.
• Overview of Azure Resource Graph — Microsoft's public description of how it stays current, and its consistency trade.
• DynamoDB global secondary indexes — a second key, updated asynchronously on every write.
• Use The Index, Luke — Markus Winand's free book on SQL indexing; column order, functions and covering indexes.
• PostgreSQL: Indexes — the costs, index types, multicolumn and expression indexes, index-only scans.
• Azure Cosmos DB indexing policies — index-everything by default, and trimming paths for cheaper writes.
• B-tree — Bayer and McCreight's 1970 structure behind almost every database index.
• Log-structured merge-tree — O'Neil et al. (1996): indexing for write-heavy workloads.
• HNSW — Malkov and Yashunin: the layered graph behind most vector search.
• Designing Data-Intensive Applications — Kleppmann; chapter 3 compares B-trees and LSM trees.

Next episode: Prompt like a spec, and why rules beat clever wording. Previously: Context Is RAM. All episodes →