Skip to main content

Partitioning and Secondary Indexes

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 6 — rewritten and condensed for teaching.

Partitioning of Key-Value Data covered the clean case: look a record up by its primary key, and that key alone tells you exactly which partition to query. Real applications need more than that — secondary indexes answer questions like "find every listing where color = red" or "find all of user 123's posts," where the thing you're searching by doesn't uniquely identify one record at all. Secondary indexes are everywhere in relational and document databases, and they're the entire reason search servers like Solr and Elasticsearch exist.

The problem: secondary indexes don't map cleanly onto a partitioning scheme built purely around primary keys. There are exactly two real strategies for handling this, and they trade off against each other in opposite directions.

Document-Partitioned (Local) Indexes​

Picture a used-car marketplace, partitioned by listing ID — IDs 0–499 on partition 0, 500–999 on partition 1, and so on. Users need to filter by color and make, so each of those needs a secondary index. The straightforward approach: each partition maintains its own secondary index, covering only the documents that already live in that partition. Add a red car to partition 1, and partition 1 alone updates its own color:red entry — it has no idea, and no need to know, what's happening in any other partition. This is exactly why it's called a local index — every partition's index is self-contained.

Writes are simple this way: adding, updating, or deleting a document only ever touches the one partition that document already lives on — no coordination with any other partition required. Reads are where the cost shows up: since there's no reason red cars would cluster on any particular partition, a search for color:red might match documents scattered across every partition. Answering it means querying every partition and merging the results — a pattern called scatter/gather. Even run in parallel, scatter/gather is genuinely expensive: it's directly exposed to tail latency amplification (the more partitions a query touches, the higher the chance at least one of them is having a slow moment, and the whole query waits on the slowest response). Despite that cost, it's extremely common in practice — MongoDB, Riak, Cassandra, Elasticsearch, SolrCloud, and VoltDB all use document-partitioned secondary indexes. Most vendors recommend structuring your partitioning so common secondary-index queries can be answered from one partition when possible — but that gets genuinely hard once a query filters on more than one secondary index at a time (color and make, simultaneously).

Practice: build a local index and scatter/gather​

Implement both halves of a document-partitioned index directly: building each partition's own local index, then a scatter/gather query that checks every partition and merges the results.

Check: document-partitioned indexes​

Quiz

Document-partitioned (local) secondary indexes

1 / 3

Why is a document-partitioned secondary index called a "local" index?

Pick an answer to see if you are right.

Term-Partitioned (Global) Indexes​

The alternative: build one global index spanning every partition's data — a color:red entry that can reference matching documents from anywhere in the dataset, not just one partition. That global index can't just live on a single node (that would simply relocate the bottleneck, not remove it) — so it gets partitioned too, just independently of how the primary data happens to be partitioned. This is called a term-partitioned index, since it's the search term itself (color:red, say) that determines which index partition holds it — terminology borrowed straight from full-text search, where a "term" is just a word appearing somewhere in a document.

A term-partitioned index can itself be split either by the term's own value (handy for range queries — e.g., an index on numeric price) or by a hash of the term (trading that range-query capability for a more even load spread) — the exact same range-vs-hash choice from the previous lesson, just one level up, applied to the index rather than the primary data.

The payoff: reads get cheap again. A client only has to contact the one index partition that owns the term it's searching for — no scatter/gather, no querying every node. The cost shows up squarely on the write side instead: a single document write can touch several terms simultaneously (this car is both red and a Toyota), and those terms can easily live on entirely different index partitions, on different nodes. Keeping a global index perfectly, instantaneously up to date on every write would mean a full distributed transaction spanning every affected partition — support for which isn't universal, and which later lessons in this series cover in depth.

In practice, most real systems sidestep that cost by making global secondary index updates asynchronous — a document write commits immediately, and the corresponding index entries catch up shortly afterward. Amazon DynamoDB, for instance, documents its global secondary indexes as typically updating within a fraction of a second under normal conditions, with longer delays possible during infrastructure trouble. That's a genuine, visible trade-off: a client reading the global index immediately after a write may not yet see it reflected there. Riak's search feature and Oracle's data warehouse (which lets you choose local or global indexing per index) are two other real examples of this design.

Check: term-partitioned indexes​

Quiz

Term-partitioned (global) secondary indexes

1 / 3

Why must a term-partitioned (global) secondary index itself be partitioned, rather than stored entirely on one node?

Pick an answer to see if you are right.

Key takeaways
  • Secondary indexes don't map cleanly onto primary-key partitioning, because the value being searched for (a color, a make) doesn't identify a single record or partition the way a primary key does.
  • Document-partitioned (local) indexes keep each partition's index self-contained — writes stay cheap and single-partition, but reads require scatter/gather across every partition, with real tail-latency exposure.
  • Term-partitioned (global) indexes partition the index independently of the primary data, by term (or a hash of it) — reads become cheap single-partition lookups, but a single document write can now touch several index partitions at once, which is exactly why global indexes are so often updated asynchronously in practice.
  • Neither approach is strictly better — it's the same fundamental read/write trade-off partitioning always makes, just applied one level up, to the index rather than the primary data.

Further Reading​