Inverted index: find documents without reading them all

How an inverted index powers search: from a coffee menu to text analysis, index updates, sharding, ranking, and access control in system design.

14 phút đọcTrung cấpEyeBlogs

Đọc bản tiếng Việt →

A hand leafing through catalog cards in a wooden library drawer to look up document information. Photo: TheEngineerHistorian, CC0 (Wikimedia Commons).
Mục lục

You remember that your company has a document explaining refunds, but not who wrote it or where it lives. You type “refund” into the search box. If the system must open and read every document each time, the work grows with the collection.

An inverted index prepares a lookup book in advance: each term points to a list of documents containing it. Instead of asking “Which terms are in this document?”, the system asks “Which documents contain this term?” Think of the index at the back of a book: look up a subject first, then turn to the pages it lists.

But that book only helps find candidates. Designing the whole search system means answering more questions: who updates it, when changes become searchable, how to split it across machines, and how to avoid showing private documents to the wrong person.

What does an inverted index invert?

Shrink the collection to four lines from a drinks menu. The data below is illustrative, not a measurement of a real service. We keep the Vietnamese wording because it will also help explain text analysis later: “cà phê” means coffee, “sữa” means milk, “đá” means ice, and “trà” means tea.

Document ID Content Meaning
1 cà phê sữa đá iced coffee with milk
2 cà phê đen black coffee
3 trà sữa milk tea
4 sữa pha cà phê milk mixed with coffee

Ordinary storage goes from a document ID to its content. An inverted index adds the reverse direction:

Term IDs of documents containing the term
cà 1, 2, 4
phê 1, 2, 4
sữa 1, 3, 4
đá 1

Each list is called a posting list, like a slip of paper listing the page numbers to open. The collection of lookup terms is the index’s dictionary, like the labels in a library card catalog. PostgreSQL describes GIN indexes for text search using this principle: each term has an entry pointing to matching records[1].

If the user requires all three terms “cà”, “phê”, and “sữa”, keep the IDs present in all three lists. Documents 1 and 4 remain. This is an intersection, like selecting people who appear on both a registration list and a list of completed payments.

If any one of the terms is enough, take the union: collect IDs appearing in any of the lists. These rules produce different results. The search box needs a defined interpretation; the data structure does not make that product decision for us.

Four Vietnamese drinks-menu documents become posting lists. The query cà phê sữa matches all its terms in documents 1 and 4, but matches the exact phrase only in document 1.
Figure 1. Looking up terms narrows down which documents need attention. Generated by the program near the end of this article, using illustrative data.

Why is “milk mixed with coffee” not the same phrase?

Knowing that terms occur together does not tell us their order. Document 4 contains every query term, but not the exact phrase “cà phê sữa”. Matching all terms and matching a phrase are different operations.

We can also record term positions, like noting both a page number and a line in our lookup book. Starting at zero, document 1 has “cà” at position 0, “phê” at 1, and “sữa” at 2. Those positions are consecutive and in the right order. In document 4, “sữa” comes before “cà”.

Positions require more space and indexing work. In return, the system can check phrases, proximity, and other query types. The information we retain must support the questions we want to answer. A set of IDs alone cannot reveal every relationship in the text.

What should the search box promise before we choose servers?

Return to the company’s document collection. Before choosing a tool, agree on a small contract with users. In this illustrative design, search finds documents by keyword, supports department filters, and shows only content the user may access.

Suppose we set these targets: an edited document becomes searchable within 5 seconds under normal operating conditions, and 95% of queries finish within 300 milliseconds at an agreed load. These are hypothetical design and testing targets, not measured results or Elasticsearch guarantees.

Access control needs a separate promise. A delay before seeing a new paragraph might be acceptable. Continuing to expose a snippet after access has been revoked is not simply another version of the same delay.

We also need to distinguish finding every document containing “refund” from putting the right refund instructions first. The former concerns matching; the latter concerns ranking quality. Fast responses full of irrelevant results do not satisfy the requirements.

Where does the lookup book fit in the architecture?

Start with the fewest components that meet the requirements. Separate the update path from the search path.

Path Steps in the illustrative design
Write User edits → save the document and a change event → indexer reads the event → update the index
Read User searches → authenticate and establish access scope → analyze the query → look up, filter, and rank → check current permissions before returning content

The indexer is like a librarian updating catalog cards when a book arrives. It reads text, breaks it into searchable units, and records the corresponding documents. Search uses that prepared book instead of rebuilding it for every question.

In this architecture, the document store holds the official content and versions. The index is derived data that can be rebuilt from that source. If the catalog is damaged, the books still exist, but rebuilding the catalog is not free.

We do not necessarily need a separate search cluster at the beginning. PostgreSQL supports full-text search and GIN indexes[1]. For modest requirements, keeping search in the database can reduce synchronization and operational work. Choose a separate tool when search features, load, or scaling requirements actually call for one.

Nor should we assume that every SQL search scans all the data. Index use depends on the query and index type. The goal is to avoid rereading all the text for every search, not to avoid relational databases.

Is “cà phê” one word or two?

A Vietnamese reader recognizes “cà phê” as a meaningful expression. A machine initially sees characters. Splitting on spaces produces “cà” and “phê” separately. That can still support an index, but it is not equivalent to recognizing Vietnamese compound words.

Text analysis is like agreeing on how names are written in a customer register: should “LAN” and “Lan” count as the same name? The process usually breaks text into searchable units, called tokens, and normalizes them. Elastic describes these steps at both indexing time and search time[2].

If the collection is indexed one way and queries are processed incompatibly, seemingly identical words may not match. The two sides need not use identical rules: query-time synonym expansion is one reason to use different processing. What matters is understanding how the rules work together.

For Vietnamese, converting uppercase letters to lowercase is usually straightforward to explain. Removing diacritics is a product choice. “Ma”, “má”, and “mã” can collapse into one form, which helps people typing without accents but can reduce precision.

One approach keeps an accented field for precise matches and adds an unaccented field with a lower ranking weight. Document identifiers need different treatment: “HD-001” is more like a document’s identity number than a sentence. One tokenizer does not fit every field.

It was saved. Why can’t search find it yet?

The source document and its index live in different places. A successful save in the first does not prove that the second has caught up.

Suppose the application performs two independent operations: save the document, then notify the indexer. If it stops between those steps, the new document might never be indexed. Sending the notification first does not fix this, because the subsequent save can fail.

A transactional outbox is one design option: save the document and a “needs indexing” record in the same database transaction. Think of a reception desk confirming an application only after recording both the paperwork and the work-order slip. Another process forwards the saved slips to the indexer.

This closes the gap between saving data and recording the work that must follow. It does not mean every notification arrives exactly once. The forwarding process may send a notification and stop before recording that it was sent, then send it again after restarting.

Use a stable document ID and increasing version numbers. Replaying version 8 must not create a second document; a delayed version 7 must not overwrite version 8. This follows the same principle as idempotency in payments: repeating an operation should not duplicate its effects.

Deletion also needs a version marker retained long enough, like leaving a “file withdrawn” slip rather than erasing every trace. Otherwise, an old notification arriving late can bring the document back. Retention must account for how far back events can be replayed and how long they can be delayed.

Reaching the index does not mean being searchable immediately

In Elasticsearch, a refresh makes recent changes available to search. This involves opening new parts of the index for reading. A write being accepted does not mean every query can immediately see it[3].

Imagine the librarian finishing a new batch of cards but not yet placing it in the lookup drawer. Write acknowledgement, search visibility, and durability are separate milestones. A single “success” message should not stand in for all three.

Forcing frequent refreshes can trade visibility delay for indexing cost. With the hypothetical 5-second target, measure event forwarding, indexer lag, and visibility through real queries. A log entry saying “sent” does not measure the whole path.

Internally, Lucene keeps index data in immutable segments, like bound batches of cards whose individual lines are not edited in place. Small batches are gradually merged into larger ones; merging also removes data marked as deleted[6]. A document disappearing from search therefore does not mean all its disk space has already been reclaimed.

Merging reads and writes data, competing with search and indexing for resources. Very frequent refreshes can create more small segments to merge. A decision that sounds like “show updates sooner” also affects write load and free disk space.

As the collection grows, split by term or by document?

When the lookup book becomes too large, split it. Sharding is like dividing a library among several rooms: each room holds part of the collection and can work in parallel.

Two approaches come to mind. With term-based partitioning, room A holds terms from the start of the alphabet and room B holds later terms. With document-based partitioning, each room holds a group of documents and an index for its own portion.

Partitioning approach Advantage Cost
By term A term identifies where to look up its posting list Multi-term queries may require exchanging lists across machines; common terms can create hotspots
By document Each shard searches and ranks its own documents A query may need to visit many shards and combine their results

For this collection, choose document-based sharding. A coordinator acts like the head librarian: send the question to the relevant rooms, gather candidates, and select the overall result. Elasticsearch likewise distributes reads across shards and uses a node to coordinate results[4].

Not every query must visit every shard if a narrower scope is known. Routing by customer company, for example, can target only the shards holding that company’s data. But one large customer may dominate the load. Equal customer counts do not guarantee equal work.

The article on consistent hashing explores mapping data to machines. Here, the more important choice is a partitioning unit suited to the queries. A hash function alone does not determine how many places a search needs to ask.

A replica is not another slice of the collection

A replica is like a backup catalog covering the same books, unlike a shard holding a different set of books. Replicas can share read traffic and provide a replacement when a machine fails. They also need updates, consuming storage and write work[4].

Adding replicas can increase read-serving capacity. Adding shards divides data and work. These are not interchangeable operations, and too many shards increase coordination overhead.

If a shard does not answer, the system must choose: report an incomplete search, or return the available results with a warning. It should not silently say “nothing found” when part of the collection was never searched. Elastic notes that a search response can have a successful HTTP status while containing only partial results[4].

The terms match. Which document comes first?

A short refund guide and a long report can both contain “refund”. Matching terms alone does not determine which one is more useful.

Ranking is like choosing which book to hand over first among books on the same subject. One common scoring method is BM25, which Elasticsearch documents as its default[5]. Its intuition accounts for term rarity, frequency, and document length. Repeating a term does not keep adding score in a simple straight-line proportion.

We can also give title matches more weight than body matches, like favoring a book with the right subject on its cover. But that is a hypothesis to test with real questions, not a universally correct rule.

Across shards, scores also depend on the statistics used. A term rare in one shard may be common across the collection. Better score comparability may require an extra statistics-gathering step, at the cost of more communication.

Suppose we need 10 results and scores are comparable. Each shard returns its top 10, and the coordinator merges them to select the overall top 10. That approach is no longer automatically sufficient if later stages discard documents by permission or change their scores. Post-filtering requires fetching more candidates or continuing the search.

Apply known filters within the query where possible. Taking 10 documents and discarding 9 from the wrong department is not equivalent to finding that department’s 10 best documents.

Can access control lag behind like content?

A document’s access has been revoked, but the index has not caught up. If the system returns a title and snippet from the stale index, information is exposed before the user even opens the document.

In this design, company scope and permissions filter candidates. Before returning titles, snippets, and links, the service also checks current permissions against the authoritative source. If the check fails, that content is not returned. Checking only when the document is opened is too late.

The limitation matters: a stale permission filter may omit documents whose access was just granted. Counts, suggestions, and other metadata must follow the same policy to avoid leaking information. Protecting only the result list is not enough.

If search results are cached, the cache key must distinguish the appropriate account and permission scopes. This connects to caching and copies that have not caught up. A delayed profile picture update and a delayed access revocation do not carry the same risk.

What does an inverted index save, and what does it not save?

Near the end, we can look at the algorithm. With two posting lists sorted by increasing ID, use two pointers: advance the side with the smaller ID; when they match, retain the ID. Think of comparing two guest lists already sorted by invitation number.

For list lengths aa and bb, a simple intersection takes at most a number of steps proportional to a+ba+b. For several terms, considering shorter lists first can narrow candidates earlier. Real implementations also compress lists and skip sections that need not be read.

An inverted index does not turn every query into a fixed-cost lookup. A term appearing throughout the collection still has a long list. Phrase matching requires positions; ranking, permission checks, and fetching content have their own costs.

The main benefit is shifting work from query time to preparation. We spend storage, indexing effort, and synchronization work to avoid repeatedly reading text. Adding a document means updating many term entries, not merely adding a row with its name.

Changing text-analysis rules may require rebuilding the index. A safer rollout builds a new index alongside the old one, catches up with updates received during the build, validates it, and switches serving over. It is like preparing a new catalog while the library stays open: do not miss the books arriving during the work.

Operational monitoring should follow the original promises: edit-to-search visibility, slow-end query latency, partial-shard responses, and the quality of top results. Test during reindexing and when a replica is unavailable. Timing one in-memory term lookup does not establish that the whole system meets its requirements.

Build the lookup book yourself

This Python program indexes the same four documents from the opening example. Each entry keeps document IDs and occurrence positions. It checks both all-term and exact-phrase matches, then exports Figure 1 into the image directory. Only matplotlib is needed beyond Python’s standard library; the data is fixed, so there is no random seed to set.

This is a model of the mechanism, without an update pipeline, sharding, or BM25 scoring. It splits text into runs of word characters rather than performing Vietnamese word segmentation. Run it from the blog’s root directory to save the image in the right place.

inverted-index.py
from collections import defaultdict
from pathlib import Path
import re
import unicodedata
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
def tokens(text):
# Preserve Vietnamese accents; split into runs of word characters.
return re.findall(r"\w+", unicodedata.normalize("NFC", text).lower())
docs = {
1: "cà phê sữa đá",
2: "cà phê đen",
3: "trà sữa",
4: "sữa pha cà phê",
}
index = defaultdict(dict)
for doc_id, text in docs.items():
for position, term in enumerate(tokens(text)):
index[term].setdefault(doc_id, []).append(position)
query = tokens("cà phê sữa")
candidates = set.intersection(*(set(index.get(t, {})) for t in query))
phrase_hits = []
for doc_id in sorted(candidates):
starts = index[query[0]][doc_id]
if any(all(p + i in index[t][doc_id] for i, t in enumerate(query))
for p in starts):
phrase_hits.append(doc_id)
print("All terms:", sorted(candidates))
print("Exact phrase:", phrase_hits)
# Draw the computed lists, without random or separately entered results.
surface, ink, muted = "#fcfcfb", "#0b0b0b", "#52514e"
plt.rcParams.update({"font.family": "DejaVu Sans", "font.size": 13})
fig, axes = plt.subplots(1, 2, figsize=(11, 5.8), facecolor=surface)
rows = [([[str(i), text] for i, text in docs.items()], ["ID", "Content"]),
([[t, ", ".join(map(str, sorted(index[t])))]
for t in ["cà", "phê", "sữa", "đá"]], ["Term", "Document IDs"])]
for ax, (data, headers), title in zip(
axes, rows, ["Stored by document", "Look up term → documents"]
):
ax.axis("off")
ax.set_title(title, loc="left", color=ink, fontsize=16, pad=18)
table = ax.table(cellText=data, colLabels=headers, cellLoc="left",
colLoc="left", bbox=[0, 0.14, 1, 0.76], colWidths=[0.22, 0.78])
table.auto_set_font_size(False)
table.set_fontsize(13)
for (r, c), cell in table.get_celld().items():
cell.set_facecolor(surface)
cell.set_edgecolor("#e1e0d9")
cell.set_text_props(color=ink if r == 0 else muted)
cell.set_linewidth(0.7)
fig.suptitle("Find “cà phê sữa” without rereading every document", color=ink,
fontsize=18, y=0.98)
fig.text(0.06, 0.16, f"All terms: {sorted(candidates)}", color=ink, fontsize=15)
fig.text(0.54, 0.16, f"Exact phrase: {phrase_hits}", color=ink, fontsize=15)
fig.text(0.06, 0.075, "Posting lists find candidates. Term positions check their order.",
color=muted, fontsize=13)
fig.subplots_adjust(top=0.80, bottom=0.26, left=0.06, right=0.96, wspace=0.18)
out = Path("images/inverted-index")
out.mkdir(parents=True, exist_ok=True)
fig.savefig(out / "tu-va-tai-lieu-en.png", dpi=160, facecolor=surface)
plt.close(fig)

Verified output: matching all terms returns [1, 4]; matching the exact phrase returns [1]. Change the term order in document 4 and run it again. The document IDs in the posting lists can stay the same while phrase-search results change.

Back to the missing refund document

The search box does not need to reread the whole collection every time you type. Some work has already happened: reading documents, recording terms, and keeping the IDs and positions that queries need. When a question arrives, the system turns to the pages likely to contain an answer.

Speed is only part of the task. The lookup book must also keep up with changes, work across several places, and avoid pointing readers to pages they may not access. That is the step from understanding a data structure to designing a system: ask not just how to look something up, but under which conditions its result is correct.

Free geometry illustrations for students and teachers: EyeViz.

Tài liệu tham khảo

  1. [1]Preferred Index Types for Text Search. PostgreSQL Documentation.
  2. [2]Text analysis. Elastic Documentation.
  3. [3]Near real-time search. Elastic Documentation.
  4. [4]Reading and writing documents. Elastic Documentation.
  5. [5]Similarity settings. Elastic Documentation.
  6. [6]Merge settings. Elastic Documentation.