Skip to content

LearnIndex & store

Inverted index

Posting list

A map from each word to the list of documents (and often positions) that contain it, so keyword search reads short lists instead of every document.

In DocSlurpIllustrated explainer

On this page
An inverted index maps each word to the chunks that contain itFour chunks: 1 "The margin plan lifts profit within two quarters", 2 "Each plan funds a new office", 3 "Raise the margin with pricing", 4 "Margin plans add profit during expansion". After lowercasing, dropping stop words and stemming "plans" to "plan", the index lists: expansion in chunk 4; margin in 1, 3, 4; office in 2; plan in 1, 2, 4; pricing in 3; profit in 1 and 4; raise in 3. The query "margin plan" reads only two posting lists, margin 1 3 4 and plan 1 2 4, and intersects them to get chunks 1 and 4 without scanning any chunk text.ChunksTerm → posting listQuery1The margin plan lifts profitwithin two quarters.2Each plan funds a new office.3Raise the margin with pricing.4Margin plans add profitduring expansion.lowercase · drop stop words · plans → planexpansion4margin134office2plan124pricing3profit14raise3margin planIntersectmargin 1 · 3 · 4plan 1 · 2 · 414chunks 1 and 46 ids read, 0 chunks scanned
Search reads the index, not the documents. Building the index flips "chunk → words" into "word → chunks". A two-word query then touches two short lists of ids and intersects them, so the cost grows with how many chunks contain those words, not with the size of the collection.

The problem: reading everything to find one word

The finance team has 200,000 chunks of plans, memos and board updates. Someone searches “margin plan”. The obvious approach reads every chunk and checks whether it contains both words. That is what grep does, and it is fine for a few megabytes. At hundreds of thousands of chunks, every query reads the whole corpus, and the cost grows with each document you add, no matter how rare the words are.

The trick: index the words, not the documents

A book solves this with an index at the back: “EBITDA, 12, 47, 103”. You look up the word, not the pages. An inverted index does the same for every word in every document.

Stored documents map each chunk to its words. The index inverts that, mapping each word to the chunks that contain it. Each word’s list of chunk ids is a posting list, kept sorted.

Build one by hand from the four chunks in the figure:

Chunk Text
1 The margin plan lifts profit within two quarters.
2 Each plan funds a new office.
3 Raise the margin with pricing.
4 Margin plans add profit during expansion.

Before indexing, each chunk is normalized: lowercased, split into words, stripped of stop words like “the” and “a”, and stemmed so “plans” becomes “plan”. Then every remaining word adds the chunk’s id to its posting list:

expansion → 4
margin    → 1, 3, 4
office    → 2
plan      → 1, 2, 4
pricing   → 3
profit    → 1, 4
raise     → 3

Answering a query

The query “margin plan” is normalized the same way, giving two terms. Search fetches the two posting lists and intersects them:

margin → 1, 3, 4
plan   → 1, 2, 4
both   → 1, 4

Because both lists are sorted, the intersection is one pass with two pointers: compare the heads, advance the smaller, keep matches. Six ids read, and not one chunk opened. Chunk 4 matches even though it says “plans”, because the query and the chunk went through the same normalization.

The cost of that query depends on how long the posting lists are, which depends on how common the words are. A rare word like “pricing” has a short list and is cheap to search for, whatever the size of the collection. That is the whole point: the index turns “scan everything” into “read a few short lists”.

An OR query takes the union of the lists instead. A ranking function such as BM25 then scores each matching chunk. Most of what it needs is already in the index: how many chunks contain each term (the length of its posting list) and, when stored alongside each id, how many times the term appears in that chunk.

What else goes in a posting

A bare list of ids answers “which chunks contain this word”. Real indexes often store more per entry:

  • Term frequency: how many times the word appears in that chunk, for ranking.
  • Positions: where in the chunk each occurrence sits. Positions make phrase queries possible: “margin plan” as a phrase needs “margin” at position p and “plan” at p + 1. Without positions, an index can only say both words appear somewhere.
  • Compression: sorted ids are stored as gaps (1, 3, 4 becomes 1, 2, 1), which are small numbers that compress well.

Where it breaks

  • It only knows the words it was given. A chunk that says “profit target” never appears for “margin plan”. This is vocabulary mismatch, and it is why hybrid search pairs keyword search with vector search.
  • Normalization must match on both sides. If chunks were stemmed and the query was not, “plans” in the query finds nothing. Change the analyzer and you must rebuild the index.
  • Stemming and stop words cut both ways. A stemmer can merge unrelated words, and dropping stop words makes queries like “The Who” match nothing.
  • Very common words have huge lists. A term present in most chunks makes its list nearly as long as the corpus. Engines cap or sample the work for such queries, which can make broad queries rank an incomplete set.

When to use it

Any time users search for exact words: names, error codes, product numbers, clause titles, rare technical terms. Keyword search over an inverted index is fast, cheap and predictable, and it is exact where embeddings are fuzzy. Pair it with vector search when users describe things in their own words.

In DocSlurp

DocSlurp keeps two inverted indexes over chunk text. LanceDB maintains a native full-text index on each project’s chunk table, with English stemming, stop-word removal, lowercasing and ASCII folding, and without positions. Because it has no positions, quoted phrases and -negation go to the second index: a PostgreSQL GIN index over each chunk’s tsvector, which supports both. See PostgreSQL full-text search.

In DocSlurp

In DocSlurp

Both keyword engines are inverted indexes: a PostgreSQL GIN index over each chunk’s tsvector (core/server/db/migrations/0000_current_schema.sql) and LanceDB’s FTS index on chunk text, built without positions (core/worker/src/stages/lancedb-maintenance.ts).

Sources

Jump to