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
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).