Secondary indexes on sharded data

A partitioned table is fast to query by its partition key. Querying by anything else — orders by status when they're partitioned by user — needs a secondary index, and on partitioned data there are two ways to build one.

#Local (document-partitioned) indexes

Each partition indexes only its own rows.

• Writes stay local: inserting a row updates the index on the same partition, in the same transaction.
• Reads scatter and gather: a query by the indexed field must ask every partition and merge the results.
• Latency is set by the slowest partition (tail latency), and every query costs work on every node.

Used by MongoDB, Elasticsearch (each shard indexes its documents) and Cassandra's built-in secondary indexes.

#Global (term-partitioned) indexes

The index itself is partitioned by the indexed value: all entries for status = 'failed' live on one index partition, wherever the rows live.

• Reads are targeted: one index partition answers, then fetches only the matching rows.
• Writes are distributed: a row change must update its data partition and one or more index partitions, which may be on other nodes. Doing that atomically needs a distributed transaction, so most systems update global indexes asynchronously — the index briefly lags the data.

DynamoDB's global secondary indexes work this way and are eventually consistent; its local secondary indexes are the other kind.

#Choosing

Often the best answer is to avoid the problem: choose a partition key that serves the hot queries, and serve the others from a search engine or analytics store fed asynchronously. See range vs hash partitioning and inverted indexes.