When a database is partitioned by primary key, queries against non-primary attributes become expensive. A naive approach requires broadcasting every secondary index query to all partitions, which scales poorly. Secondary index partitioning strategies address this problem by organizing index data so that queries can be answered efficiently without always contacting every node.
There are two fundamental approaches: document-based partitioning (local indexes) and term-based partitioning (global indexes). Each makes a different tradeoff between write complexity and read efficiency. Understanding these tradeoffs is essential for designing systems that balance query latency with write throughput.
Document-Based Partitioning (Local Indexes)
In document-based partitioning, each partition maintains its own secondary index covering only the documents stored on that partition. When a document is written, the secondary index on the same partition is updated. No cross-partition coordination is needed during writes.
The cost shows up at read time. A query on a secondary index attribute must be sent to every partition, because any partition might hold matching documents. This pattern is commonly called "scatter/gather." If a table is split across 100 partitions, a secondary index lookup fans out to all 100, and the coordinator must merge results.
Scatter/gather is tolerable when the number of partitions is small or when queries are infrequent relative to writes. It becomes a bottleneck when partition counts grow large or when tail latency matters, because the overall response time is bounded by the slowest partition.
Most document databases use this approach. MongoDB, for instance, uses local secondary indexes within each shard. Elasticsearch also maintains per-shard inverted indexes, relying on scatter/gather for search queries by default, though custom routing keys can direct writes and reads to a subset of shards, reducing fan-out when the data distribution allows it. Cassandra's secondary indexes are local to each node, which is why the Cassandra documentation warns against high-cardinality secondary index queries on large clusters.
Characteristics
- Writes are simple. Only the local partition's index needs updating.
- No distributed transaction required for index maintenance.
- Reads require scatter/gather across all partitions.
- Tail latency grows with partition count.
Term-Based Partitioning (Global Indexes)
In term-based partitioning, the secondary index itself is partitioned, but by the indexed term rather than by document locality. For example, if the secondary index is on a "color" field, all index entries for colors starting with A through M might live on partition 0, and N through Z on partition 1. Alternatively, the term can be hash-partitioned for uniform load distribution.
A query on a specific term value now only needs to contact the partition(s) responsible for that term range. This eliminates scatter/gather for point lookups on the indexed attribute. Range queries on the index may still require contacting multiple partitions, depending on whether the index is range-partitioned or hash-partitioned.
The cost shifts to writes. When a document is written, its secondary index entries may need to be updated on a different partition than the one storing the document. This introduces cross-partition writes, which are slower and harder to make consistent. In practice, global secondary indexes are often updated asynchronously, meaning there is a window where a read of the index might not reflect recent writes.
Amazon DynamoDB's global secondary indexes follow this model. They are updated asynchronously, and DynamoDB documentation explicitly notes that global secondary indexes are eventually consistent. Google's Spanner also supports global indexes and can provide stronger consistency guarantees through its use of Paxos-based distributed transactions and the commit-wait mechanism, though this comes at the cost of higher write latency.
Characteristics
- Reads are efficient. Only the relevant index partition is contacted.
- Writes are more complex. Cross-partition updates are required.
- Consistency is harder to maintain. Asynchronous updates introduce staleness.
- Better suited for read-heavy workloads with selective queries.
Choosing Between Strategies
The decision depends on workload characteristics. Write-heavy workloads with occasional secondary index queries favor local indexes, because writes remain cheap and localized. Read-heavy workloads where secondary index queries are frequent and must be fast favor global indexes, because reads avoid scatter/gather.
There is also a hybrid consideration. Some systems allow both strategies, letting operators choose per-index. If a secondary index is queried rarely, a local index avoids the write overhead of a global one. If a secondary index is the primary query path, a global index avoids the read amplification of scatter/gather.
Partition count matters too. Scatter/gather over 5 partitions is qualitatively different from scatter/gather over 500. Systems that expect to scale to many partitions will feel the pain of local indexes more acutely.
Key Points
- Document-based (local) secondary indexes partition the index alongside the data, requiring scatter/gather for reads but keeping writes simple.
- Term-based (global) secondary indexes partition the index by the indexed term, enabling efficient reads but complicating writes.
- Local indexes require no cross-partition coordination on writes, making them attractive for write-heavy workloads.
- Global indexes typically rely on asynchronous updates, introducing eventual consistency between the base data and the index.
- The choice between local and global indexes is fundamentally a tradeoff between read amplification (local indexes) and write amplification and consistency complexity (global indexes).
- Tail latency in scatter/gather grows with the number of partitions, making local indexes increasingly costly at scale.
- Some systems support both strategies, allowing per-index configuration based on access patterns.
References
Martin Kleppmann. Designing Data-Intensive Applications. O'Reilly Media, 2017. Chapter 6: Partitioning.
Amazon Web Services. "Amazon DynamoDB Developer Guide: Global Secondary Indexes." https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/GSI.html
James C. Corbett et al. "Spanner: Google's Globally-Distributed Database." Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2012.