Engineering Fast Search with Inverted Indexes

Search has become a part of our daily lives, whether on the web or within an app. But have you ever wondered how it actually works? What happens when you search for something, and how does the system filter through massive amounts of information in just a few milliseconds?

In this article, let’s talk about inverted indexes, the data structure behind search.

Firsty, Let's understand how you'd search for a word in a given corpus of documents. Let's start with the naive way:

Given the below documents, say the word to search is “cricket” :

The naive approach would be to iterate over all the documents, and all the words inside each documents, and then add the matched result to the final answer.

As we can see the problem here is that to answer just one query we are touching every document , regardless of whether the word appears in one document or across all documents. And every query has to do this from scratch, and when there are million of records or documents, then this linear search becomes slow.

In inverted index, the basic idea is to make text search fast so instead of storing the “documents → words it contains” , we try to reverse/invert it to “words → documents that contains it. ”

For example , The inverted index for the 3 documents we considered for the naive approach would be :

Now that we learned about the data structure, lets optimize a bit more on top of that, for faster, efficient, and informative lookups :

Words like “a”, “the”, “an”, “in” , “on” appear in almost every document. So if we store these words in the dictionary then the posting list would grow to contain all the documents, which just takes up memory but are contributing very less for the searches. So most search engines just drop these low information, high frequency words before putting them into the data structure.

Lemmatization does roughly the same job as stemming, reducing words to a base form, but it's smarter about it. Instead of blindly chopping suffixes, it uses an actual vocabulary and grammar knowledge to find the true dictionary form of a word.

So far our postings lists had just a list of document IDs. But we can pack in a lot more metadata information to add additional capabilities in search :

1. Term Frequency (tf) :

   How many times the term occurs in the doc

   This information is useful for ranking search results. A document in which the search term appears multiple times may be considered more relevant than one in which it appears only once.

2. Positions :

   Where in the doc does the term appear

   Positions are useful for phrase searches and proximity searches.

   For example, while searching for:

   the search engine checks whether the position of Agents immediately follows the position of AI. This helps in u know much accurate searches.

3. Offsets :

   Gives the character positioning

   Offsets are mainly useful for highlighting matched words in search results and displaying relevant text snippets. For better viewer experience like you can see below as to how substack search does.

A champion list stores only the top-ranked documents for each term instead of checking the entire posting list during every search.

For example:

AI → [DOC3, DOC8, DOC1, DOC5, DOC9, ...]

The complete posting list may contain thousands of documents. A champion list keeps only the best few:

AI → [DOC3, DOC8, DOC1]

These documents are usually selected based on factors such as:

• High term frequency

• Importance of the term within the document

• Overall document quality or popularity

Posting lists are usually stored in ascending order of doc_id.

AI     → [2, 7, 11, 20, 35]
Agents → [1, 7, 11, 18, 35]

Suppose a user searches for:

AI Agents

When the lists are unsorted, the search engine may compare every document in the first list with every document in the second list.

If list1 contains m documents and list2 contains n documents, the time complexity is:

O(m × n)

This becomes expensive when the posting lists contain thousands or millions of document IDs.

With sorted posting lists

When both lists are sorted, the search engine can use two pointers and move through both lists from left to right.

For example:

AI     → [2, 7, 11, 20, 35]
Agents → [1, 7, 11, 18, 35]

The result is:

[7, 11, 35]

The time complexity is:

O(m + n)

Therefore, keeping posting lists sorted makes queries containing more than 1 word much faster

Posting lists may contain millions of document IDs, so storing every ID as a fixed-size integer can consume significant disk space and memory.

For example:

AI → [10001, 10008, 10015, 10019, 10030]
1 int = 4 bytes
5 total integers = 5 x 4 = 20 bytes

A common compression method is delta encoding, where we store the first document ID and then the gaps between consecutive IDs:

AI → [10001, 7, 7, 4, 11]
1 int = 4 bytes
5 totoal integers in the list = 5 x 4 = 20 bytes

This works because posting lists are sorted. The original IDs can be reconstructed through cumulative addition.

Well, Delta encoding alone does not reduce space if every value is still stored as a fixed-size integer. Hence, it is combined with VarInts.

A VarInt (variable length integer encoding) stores small numbers using fewer bytes and larger numbers using more bytes (). For example:

7     → 1 byte
10001 → 2 bytes

So the original list may require about 10 bytes with VarInts, while the delta-encoded list may require only 6 bytes.

This comes to the end of the article on how Information retrieval works with inverted indexes. Hope you liked this one.

In the next article, we’ll explore different approaches to search, including phonetic, lexical, and semantic search, along with ranking techniques such as BM25