Secondary Indexes on Partitioned Data

How to look records up by something other than the partition key: local indexes with scatter/gather reads, global indexes with costlier writes, and how real databases keep each in step.

Overview

A partitioned database finds a record quickly when you give it the partition key: hash or look up the key, go to one partition, done. But applications also search by other fields: orders by status, products by color, users by email. An index on a field other than the primary key is a secondary index, and on partitioned data it raises a question with no free answer: which partition holds the index entries?

There are two answers. A local index keeps each partition's index next to that partition's data, so writes are cheap and reads must ask every partition. A global index partitions the index by the indexed value, so reads go to one place and writes may touch several machines. Most real systems offer one or both, and the choice decides your read latency, write cost and how fresh the index is.

Local indexes: each partition indexes its own data

With a local index (also called a document-partitioned index), each partition keeps an index covering only the records it stores. A write touches one partition: the record and its index entries change together, on one machine, often in one local transaction.

The cost moves to reads. A query on the indexed field must be sent to every partition and the results merged, which is called scatter/gather. Many systems work this way:

MongoDB — Each shard keeps its own indexes; a query without the shard key (or its prefix) is broadcast to all shards and mongos merges the results
Cassandra — Secondary indexes (the older 2i and the newer SAI) are built locally on each node; the docs recommend SAI for new indexes
Elasticsearch — Each shard is its own Lucene index; a search goes to one copy of every shard of the index unless a routing value narrows it
DynamoDB local secondary index — Same partition key as the table, different sort key; it can be read with strong consistency, and each partition key value is limited to 10 GB including its index entries

Elasticsearch shows a common refinement, query then fetch: in the first round each shard returns only the IDs and scores of its best matches; the coordinator picks the overall top results and fetches just those documents in a second round.

Why scatter/gather gets slow

A scatter/gather read is as slow as its slowest partition. If each partition is slow 1% of the time (its p99), the chance that at least one of N partitions is slow on a given query grows quickly with N.

1 — 1%
10 — About 9.6%
50 — About 39.5%
100 — About 63.4%

The work also multiplies: every query costs every partition a lookup, so adding partitions adds read load instead of spreading it. Local indexes are fine when the cluster is small, queries are rare, or most queries can include the partition key.

Global indexes: partition the index by the indexed value

A global index (also called a term-partitioned index) is itself partitioned, by the indexed value. All entries for status = shipped live in one index partition, whichever data partitions the orders are on. A read goes to the one index partition that owns the value.

The cost moves to writes. One record write can touch the data partition plus one index partition per indexed field, often on other machines, and an update that changes an indexed value both removes an old entry and adds a new one. Keeping all of that atomic needs a distributed transaction, so most systems choose between two options.

Asynchronous — The index is updated after the write returns — DynamoDB global secondary indexes — Index reads are eventually consistent: usually a fraction of a second behind, longer in rare failures
Synchronous — The index is updated in the same transaction — Spanner secondary indexes — Always consistent, but a write to a global index usually needs a two-phase commit across splits

DynamoDB states the consequences plainly: reads from a global secondary index cannot be strongly consistent, each index update consumes the index's own write capacity, and if an index lacks capacity, writes to the base table are throttled.

A middle path: index inside the partition key

If most queries already know the partition key, put the index inside it. The index entries then live with the data, and a query that supplies the partition key reads one partition.

DynamoDB local secondary indexes and Spanner interleaved indexes (where the parent table's key is a prefix of the index key) work this way; Spanner notes that such index writes stay local instead of needing a distributed transaction.

Choosing

Where the index lives — With each data partition — Partitioned by the indexed value
Read on the indexed field — Every partition (scatter/gather) — One index partition (or a few for a range)
Write cost — One partition — Data partition plus index partitions
Freshness — Updated with the data — Asynchronous (stale for a moment) or synchronous (slower writes)
Good for — Write-heavy data, rare or small-cluster queries — Read-heavy lookups by a selective field

What you will be able to do

Explain why a secondary index is hard to place when data is partitioned.
Compare local and global indexes by read cost, write cost and freshness.
Estimate how fan-out hurts tail latency, with the arithmetic.
Name how MongoDB, Cassandra, Elasticsearch, DynamoDB and Spanner handle secondary indexes.
Design an access pattern that avoids scatter/gather by scoping the index to the partition key.

Key concepts

Secondary index: An index on a field other than the primary or partition key, used to find records by that field.
Local (document-partitioned) index: Each partition indexes only its own records. Writes stay on one partition; queries on the field must ask every partition.
Global (term-partitioned) index: The index is partitioned by the indexed value, so a lookup goes to one index partition, but a write may update index partitions on other machines.
Scatter/gather: Sending a query to every partition and merging the answers. It is as slow as the slowest partition and adds load to all of them.
Query then fetch: A two-round search: shards first return IDs and scores of their best matches, then the coordinator fetches only the overall top documents.
Asynchronous index maintenance: The index is updated after the write returns, so index reads may briefly miss recent writes. DynamoDB global secondary indexes work this way.
Index scoped to the partition key: An index whose key starts with the partition key, so its entries live with the data and single-partition queries stay local.

When to use it

Adding a search-by-field feature (email, status, tag) to a sharded table in a design interview
Explaining why a DynamoDB global secondary index query can miss a write that just succeeded
Deciding whether a query should carry the partition key to avoid scatter/gather
Estimating the latency of a query that fans out to every shard

Interview questions

Users are sharded by user ID. How do you support login by email?
How does Elasticsearch run a search across a distributed index?
Why can a DynamoDB global secondary index return stale results, and what do you do about it?
Local or global secondary index: how do you decide in an interview?