An inverted index maps terms to the list of documents containing them. A web-scale inverted index has billions of documents and trillions of term-document pairs. It doesn’t fit on one machine. You have to partition it.

Two Partitioning Strategies#

Document partitioning: split documents across machines. Machine 1 has documents 1-1M, machine 2 has documents 1M-2M, and so on. Each machine builds a complete local inverted index over its documents. A query for “distributed systems” goes to every machine in parallel, each returns its local top-K results, a merger combines and re-ranks.

Term partitioning: split terms across machines. Machine 1 handles terms starting with A-F, machine 2 handles G-M, etc. A query for “distributed systems” sends “distributed” to Machine 3 and “systems” to Machine 5, then merges the posting lists to find documents containing both.

Why Document Partitioning Wins#

Document partitioning (also called sharding by document ID) is the dominant approach in practice. The reasons:

Query fan-out is bounded: every query touches every shard, but the fan-out factor is the shard count, which you control. With term partitioning, a query with many terms touches many different machines, and the fan-out grows with query complexity.

Shard independence: each shard can be updated, reindexed, and restarted independently. With term partitioning, adding a new document requires updating posting lists on many machines.

Better utilization: document shards are roughly equal size. Term shards can be badly skewed (the shard handling common words like “the” or “is” is far larger than the shard handling rare terms).

graph TD A[Query: distributed systems] --> B[Scatter to all shards] B --> C[Shard 1: local top-10 results] B --> D[Shard 2: local top-10 results] B --> E[Shard 3: local top-10 results] C --> F[Merge: global top-10 by relevance score] D --> F E --> F F --> G[Return results to user] style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style D fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style E fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style F fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style G fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

The Merge Problem#

Each shard returns its local top-K results ranked by local scores. The global merger re-ranks across all shards. The complication: TF-IDF and similar scoring functions use global statistics (how rare is this term across all documents?). With document sharding, each shard only knows term frequency within its documents, not across the whole index.

Solutions: maintain global term statistics in a shared lookup that all shards consult when scoring, or accept slightly inaccurate local scores and rely on final re-ranking to correct them. Most systems use the latter with periodic global statistics updates.

Adding New Documents#

New documents go to a “delta index”: a small, fast index of recently added documents. Periodically, the delta index is merged into the main index shards. Searches query both the main index and the delta index, merging results. This avoids the cost of reorganizing the main index on every write, similar to how LSM trees handle writes through in-memory writes and periodic compaction.

At Salesforce#

Our Salesforce search indexed records per org. Effectively, each org was its own document shard. Cross-org search didn’t exist, which simplified everything: a user’s search touched only their org’s shard. Relevance scoring was computed locally per org. The lesson: if you can scope your search to a subset of data by design, you avoid the hardest parts of distributed search (global statistics, cross-shard merging).

What I’m Learning#

Index partitioning converts a single-machine search problem into a scatter-gather problem. The scatter is cheap if queries are simple. The gather requires careful score normalization to produce globally correct results. Scoping search to sub-collections is the cheapest optimization of all.

Have you worked with search systems that needed to partition their index, and how did you handle score normalization across shards?