Secondary indexes on sharded data

A used-car marketplace holds 40 million listings from 60,000 dealers, sharded by dealer ID across 32 shards, about 1.25 million listings each. Dealers manage their stock all day, and every one of those queries carries the dealer ID, so each touches one shard. Buyers don't know or care which dealer has the car:

Sharding & partitioning introduces the two basic answers: a local index that each shard keeps for its own rows, or a global index split by the indexed value. This page follows each through its reads, its writes, its consistency and its limits, then adds the two cases they don't cover: indexes that stay on one shard by design, and uniqueness.

With local indexes, each shard indexes (make, model, price) for its own 1.25 million listings. A new listing updates its row and the index entry on the same shard, in the same local transaction, so the index is never stale. The cost moves to reads. MongoDB's router broadcasts any query without the shard key to every shard, and Vitess does the same unless it has a cross-shard index to consult:

The router can't know which shard holds the 20 cheapest, so each shard sends its own top 20; MongoDB passes the limit to every shard and applies it again after merging. Skipping pages is worse: the router can't pass a skip down, so for page 50 every shard returns its first 1,000 rows:

Local indexes suit queries that are rare, or that need every shard anyway, like analytics. For the marketplace's busiest buyer query, every search costs 32 shards' work, and adding shards adds work to each search instead of capacity (Latency covers why waiting on many servers makes the slow tail common).

Not every secondary index needs to be global. The dealer's stock page searches within one dealer: by price, by age in stock, by model. An index whose key starts with the shard key, (dealer_id, price), keeps every entry on the same shard as its rows, so both the write and the read stay local and consistent.

Databases name this pattern differently:

• Spanner calls it an interleaved index. It's the better choice whenever queries filter by the parent's key, because the index entry lands in the same split as the row and writes stay local.
• DynamoDB calls it a local secondary index: same partition key, different sort key, and it allows strongly consistent reads.

Either way, the index answers only questions about one parent, which is exactly what the dealer's pages ask.

The catch is size per parent. DynamoDB caps everything that shares a partition key, the items plus their local index entries, at 10 GB on tables with local secondary indexes. A marketplace with one dealer far larger than the rest should check that before relying on it (Hot partitions & skew).

A global index is a second sharded table: entries keyed by (make, model, price), partitioned by make and model. All RAV4 entries live together, sorted by price, so the buyer's search reads one index partition and stops after 20 entries. The price is on the write side: a new listing goes to its dealer's shard, and its index entry goes to whichever partition owns "Toyota RAV4":

DynamoDB's global secondary indexes do it later. The table write succeeds first, and DynamoDB updates the index asynchronously, normally within a fraction of a second, so a query on the index can briefly miss a listing the table already has. A dealer who lists a car and searches for it straight away may not see it. Reads that must be current go to the table by its key.

The index is also a separate set of partitions with its own capacity. If a global index can't absorb the write rate, DynamoDB throttles writes to the table itself. And its key decides its hot spots: every RAV4 listing, price change and sale lands on the one partition holding RAV4s. A higher-cardinality key spreads that load, such as make, model and region together (Hot partitions & skew).

Distributed SQL databases update global indexes in the same transaction as the row, so a query on the index never misses a committed write. The price: the index entry usually lives in a different split from the row, so the write needs a two-phase commit across splits, which adds latency and CPU:

So the choice between asynchronous and synchronous global indexes is a choice between a moment of stale search results and slower writes everywhere (Distributed transactions: 2PC & sagas covers the protocol; Distributed SQL covers how the ranges commit). For a marketplace, search results a second old are fine; for "has this coupon code been used?", they are not.

Every VIN must appear in at most one active listing. A local unique index can't promise that: two dealers on different shards can each insert the same VIN, and neither shard sees the other. MongoDB states the rule directly: a unique index on a sharded collection works only if it begins with the full shard key, which makes (dealer_id, vin) unique, not vin.

The fix is to give each value a single owner, a record keyed by the value itself, so the claim lands on exactly one shard and that shard can refuse a second one. MongoDB's answer is a separate proxy collection sharded on the unique field. DynamoDB's documented pattern writes an extra item whose key is the value, in the same transaction as the real item, with a condition that it doesn't exist yet:

Either both items are written or neither is, so there is never a listing without its claim or a claim without its listing. Selling or deleting the car must remove the claim in the same transaction. Vitess offers the same thing built in, a unique lookup index kept consistent with the table without two-phase commit.

The marketplace ends up with four approaches, each matched to a query. The dealer's stock uses an index that starts with the dealer ID. The model search uses an asynchronous global index, since a second of lag is invisible to buyers. VIN uniqueness uses a claim item written in the same transaction. Free-text search across many filters goes to a search engine fed by a change stream (Search & inverted indexes, Change data capture).