Secondary Indexes

The KV store so far only indexes by the primary key. To find all keys where the VALUE matches some predicate, you'd scan everything. Secondary indexes solve this — at the cost of extra bookkeeping on every write.

Primary records:
  user:1 -> {name: alice, city: nyc}
  user:2 -> {name: bob,   city: la}
  user:3 -> {name: carol, city: nyc}

Secondary index on city:
  city=nyc -> [user:1, user:3]
  city=la  -> [user:2]

Query "all users in NYC" becomes one O(1) lookup in the secondary index, returning the list of primary keys, then per-key fetches. Without the index, you'd scan every user.

Two implementation styles

Local (per-shard) secondary index — used by Postgres, MySQL, Cassandra:

• The index lives on the same node as the data.
• Write a record -> also update its index entries on the same node.
• Cheap writes; query may need to fan out to many shards.

Global (separate) secondary index — used by DynamoDB GSI, ElasticSearch:

• The index is its own data structure with its own partitioning.
• A write must do a distributed transaction to keep index and data consistent (or accept eventual consistency).
• Expensive writes; query goes to one place.

Update path

When the indexed field changes:

1. Look up the OLD value (read the primary record).
2. Remove the key from the OLD bucket in the index.
3. Add the key to the NEW bucket.
4. Write the new primary record.

If you forget step 2, the index becomes stale: queries return phantom hits. Most databases run a periodic consistency check.

Cost on writes

Each secondary index adds 1–2 extra I/Os per write (read old + write index update). Many production systems track this:

• Postgres: every INSERT/UPDATE writes a row to each index it participates in.
• MongoDB: index-on-write cost grows linearly with the number of indexes.

Rule of thumb: don't index a column you'll never filter by. Each unused index taxes every write.

Composite indexes and selectivity

A composite index (city, age) answers WHERE city='nyc' AND age=30 in O(1). But it doesn't answer WHERE age=30 alone efficiently — you still need an age index.

The selectivity of an index matters: an index on country where 90% of values are 'us' barely narrows results. The query planner often skips a low-selectivity index in favor of a full scan.