Part 4 of 8 · 3 min read
Global indexes: partitioned by term
One index covering all partitions, itself split by the value searched.
Think of a single card catalogue for the whole library, split into drawers by subject: A to M in one cabinet, N to Z in another. A reader looking for "bridges" opens one drawer and finds the room numbers of every book on the subject. Adding a book, though, means updating a card in every subject drawer that the book touches, which may be in different cabinets.
Global (term-partitioned) index
A global index covers the records of all partitions. It is itself partitioned, but by the term searched (the value in the index, such as colour:red), not by the record ID.
Example: the index on colour is split in two: colours starting with a to r in index partition 0, and s to z in index partition 1. All red cars from all data partitions are listed under colour:red.
The book explains that the whole index cannot sit on one node, since that node would become the bottleneck and defeat the purpose of partitioning. So the index is partitioned, but differently from the data. It can be split by the term itself, which helps range scans (for example on the asking price of a car), or by a hash of the term, which spreads the load more evenly.
Advantage: a read needs only the partition that holds the term. No scatter/gather. Disadvantage: a write to one record can touch several partitions of the index, since each term in the record may live on a different node. A car that is red, a Ford and priced at 8,000 has three terms, possibly on three index partitions.
Ideally the index is always up to date. For a global index, that would need a distributed transaction across all the partitions touched by a write, which not every database supports. In practice, updates to a global index are often asynchronous: a read shortly after a write may not yet show the change. The book gives the example of Amazon DynamoDB, which says its global secondary indexes are normally updated within a fraction of a second, but may be delayed longer if there are infrastructure faults. Riak's search feature and the Oracle data warehouse (where the choice between local and global is offered) are other examples.
A worked example. A car is added with colour red, make Ford, price band 8,000 to 9,000.
| Step | Local index | Global index |
|---|---|---|
| Data write | Partition for the car's ID | Partition for the car's ID |
| Index writes | In the same partition: 3 entries | 3 entries on up to 3 different index partitions (3 extra network messages) |
| Search "red cars" | Ask 4 partitions (4 messages) | Ask 1 index partition (1 message), then fetch the 800 cars from their data partitions |
| Freshness | Immediate | Often a fraction of a second behind |
Note that fetching the records themselves still involves the data partitions. The index returns IDs, and the IDs lead back to the partitions that hold the records. For 800 red cars across 4 partitions, that is 4 partitions anyway if the full records are needed. The saving appears when the answer is small (a few matches) or when the index holds the needed fields itself.
| Local index | Global index | |
|---|---|---|
| Index partitioned by | The record's partition | The term |
| Read | Scatter/gather over all partitions | One index partition per term |
| Write | One partition | Several index partitions |
| Freshness | Immediate | Usually asynchronous |
| Good when | Writes are many, queries are rare or filter on the partition key | Reads by term are many and writes are fewer |
Check yourself:
- A record has 5 indexed fields. How many index partitions might one write touch in a global index? In a local index?
- Why are global indexes usually updated asynchronously?