Skip to content
Français

The inverted index

  • Lesson 8
  • 35 min
  • Module 3: Lexical search: the baseline to beat

Where we are

We can now measure any search with our test set. The first search to measure is the classic one. In this lesson, we build an inverted index by hand, then with SQLite, and we see why looking up a word is so fast.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

What you will be able to do

Find the products that contain a word without reading every product. This is how every word search, Larkfield’s included, stays fast.

NotebookDo the examples of this lesson in a notebookColab · Kaggle · GitHub

The notebook builds the index of six products by hand and looks up queries with all words and with any word. Then it uses SQLite on the whole catalogue. You build the index of every product title yourself. Its setup cells download the data, so it needs no local setup. About 20 minutes.

Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.

Before you startWhat to know and to have readyAbout 35 minutes

What you need to know

What you need on your computer

  • The project larkfield-search from the earlier modules, with its virtual environment active. This lesson adds no file to it.
  • The index that search check or search index built in outputs/index/. If you ran search reset, run search index once.

Think of a thick gardening book. You want to read about hoses. You do not read all 400 pages to find the word “hose”. You turn to the index at the back. It says “hose: 112, 245”. You open page 112, and you are there in seconds.

Someone made that index once, when the book was printed. They went through every page and wrote down which words appear on it. Then they turned the list around: for each word, the pages. Every reader uses that work, again and again, for free.

A shop assistant does the same. A new assistant walks along every shelf to find a garden hose. An experienced assistant knows the answer: “Hoses are in aisle 7.” In her head, she has a list from words to places.

A search engine needs the same list. Without it, every search must read every product.

Larkfield has 40,066 products. Each one has a title and a description, about 72 words on average. To answer “garden hose” without an index, the program must read all of them and keep the ones that contain both words.

This short script does exactly that. Then it asks the SQLite index of the project the same question. Save it as scan.py in the folder larkfield-search:

import sqlite3
import time
import pandas as pd
cat = pd.read_csv("data/catalogue.csv.gz", keep_default_na=False)
texts = (cat["title"] + " " + cat["description"]).str.lower().tolist()
words = ["garden", "hose"]
start = time.perf_counter()
found = [i for i, t in enumerate(texts) if all(w in t.split() for w in words)]
scan_ms = (time.perf_counter() - start) * 1000
con = sqlite3.connect("outputs/index/fts.sqlite")
start = time.perf_counter()
rows = con.execute("SELECT product_id FROM products WHERE products MATCH ?", ('"garden" "hose"',)).fetchall()
index_ms = (time.perf_counter() - start) * 1000
print(f"Read every product: {len(found)} products in {scan_ms:.0f} ms")
print(f"Use the index: {len(rows)} products in {index_ms:.1f} ms")

Run it:

Terminal window
python scan.py
Read every product: 24 products in 100 ms
Use the index: 24 products in 0.3 ms

Both ways find the same 24 products. Reading every product takes about 100 milliseconds. The index takes about 0.3 milliseconds: about 300 times faster. The first run can be slower, because the computer reads the index file from the disk. Your times will differ, but the gap stays large.

100 milliseconds sounds small. But the search also has to rank the products, build the page and send it. Amira’s budget for the whole search is 200 milliseconds. And the time to read every product grows with the catalogue: twice the products, twice the time. With an index, the time depends mostly on the query’s words, not on the size of the catalogue.

The idea: from products to words, and back

Section titled “The idea: from products to words, and back”

An index turns the list around. A product lists its words. The index lists, for each word, the products that contain it. This is why it is called an inverted index: “inverted” means turned the other way.

Three words describe it:

  • A token is one word of the text, after a simple clean-up. Here the clean-up is: change to lower case, then split on every space and punctuation mark. “Grey Outdoor Cushion, 18” becomes four tokens: grey, outdoor, cushion, 18.
  • The postings of a token are the products that contain it. In a book, they are the page numbers after a word.
  • The vocabulary is the list of all tokens in the index.

Here are six small products, A to F. To build the index, take each product, split its title into tokens, and add the product to the postings of each token.

Left: six products. A grey outdoor cushion, B blue outdoor cushion cover, C garden hose with reel, D grey sofa, E outdoor sofa with cushions, F hose reel cart. An arrow labelled split into tokens leads to the inverted index on the right, with 12 tokens and their postings: blue B, cart F, cover B, cushion A and B, cushions E, garden C, grey A and D, hose C and F, outdoor A, B and E, reel C and F, sofa D and E, with C and E. The rows cushion and outdoor are highlighted. Below, the query outdoor cushion: outdoor gives A, B, E and cushion gives A, B. Every word gives A and B; any word gives A, B and E.
An inverted index of six products. To answer a query, the search reads only the postings of the query's tokens.
Text description of the diagram

On the left are six products: A “grey outdoor cushion”, B “blue outdoor cushion cover”, C “garden hose with reel”, D “grey sofa”, E “outdoor sofa with cushions” and F “hose reel cart”. On the right is their inverted index: 12 tokens in alphabetical order, each with its postings. For example, outdoor points to A, B and E, cushion to A and B, and hose to C and F. cushions points only to E. Below, the query “outdoor cushion” reads two rows. Every word: the products in both lists, A and B. Any word: the products in at least one list, A, B and E.

Look at product E, “outdoor sofa with cushions”. It has the token cushions, not cushion. For the index, these are two different tokens, as different as “sofa” and “cushion”. Keep this in mind: it comes back below.

To answer the query “outdoor cushion”, the search does not read the six products. It reads two rows of the index:

  • outdoor → A, B, E
  • cushion → A, B

Then it combines the two lists. There are two common ways:

Query Every word must match (AND) Any word may match (OR)
outdoor cushion A, B A, B, E
grey cushion A A, B, D
outdoor cushions E A, B, E

Every word keeps the products that are in all the lists. In mathematics, this is the intersection of the lists. Any word keeps the products that are in at least one list: the union.

The last row shows the trap. “outdoor cushions”, with an s, finds only E with every word. The two cushions A and B do not have the token cushions, so they drop out. A person sees the same product. The index sees a different word.

Larkfield: SQLite FTS5 is an inverted index

Section titled “Larkfield: SQLite FTS5 is an inverted index”

Larkfield’s search today uses SQLite FTS5. SQLite is the small database that comes with Python. FTS5 is its full-text search part, and it builds an inverted index of text. In the project, larkfield_search/index.py creates it with one statement:

con.execute("CREATE VIRTUAL TABLE products USING fts5(product_id UNINDEXED, title, description, "
"tokenize = 'unicode61 remove_diacritics 2')")

The tokenize setting says how FTS5 makes tokens: it splits on spaces and punctuation, uses lower case, and removes accents, so “é” becomes “e”. The product_id column is UNINDEXED: it is stored, but its words do not go into the index. The next two lessons come back to that.

FTS5 can show its own vocabulary, with the number of products for each token. This script prints the postings size of each word of a query, then counts the products with every word and with any word. Save it as postings.py in larkfield-search:

import sqlite3
import sys
query = sys.argv[1]
con = sqlite3.connect("outputs/index/fts.sqlite")
con.execute("CREATE VIRTUAL TABLE temp.vocab USING fts5vocab(main, 'products', 'row')")
words = query.lower().split()
for w in words:
row = con.execute("SELECT doc FROM temp.vocab WHERE term = ?", (w,)).fetchone()
print(f"{w:<12} in {row[0] if row else 0:>6,} products")
for name, joiner in [("every word", " AND "), ("any word", " OR ")]:
match = joiner.join(f'"{w}"' for w in words)
n = con.execute("SELECT count(*) FROM products WHERE products MATCH ?", (match,)).fetchone()[0]
print(f"{name:<12} {n:>9,} products")

fts5vocab is a view of the index that FTS5 makes for you. The temp. part means that the view lives only while the script runs, so the index file does not change. Run it for two queries:

Terminal window
python postings.py "garden hose"
python postings.py "grey outdor cushion"
garden in 1,352 products
hose in 111 products
every word 24 products
any word 1,439 products
grey in 240 products
outdor in 0 products
cushion in 1,284 products
every word 0 products
any word 1,511 products

Read the first query. 1,352 products have “garden” and 111 have “hose”. Only 24 have both. These are the 24 products of scan.py. With any word, 1,439 products match: every garden product and every hose.

Now read the second query. “outdor” is a spelling mistake, and no product has it. Its postings list is empty. So “every word must match” returns nothing, although 1,284 products have “cushion”. This is the empty page from Module 1. The index did its work correctly: the rule “every word” is the problem.

The FTS5 index of Larkfield has 44,757 different tokens in the titles and descriptions. How many products does each one appear in? The chart groups the tokens by the size of their postings.

The 44,757 tokens of Larkfield's FTS5 index (title and description), grouped by the number of products that contain them (1, 2 to 9, 10 to 99, 100 to 999, 1,000 or more). Half of the tokens are in one product only.
Text description of the chart

The chart has five bars. Each bar is a group of tokens, by the number of products that contain the token. 22,895 tokens are in one product only. 13,525 tokens are in 2 to 9 products. 5,859 tokens are in 10 to 99 products. 2,108 tokens are in 100 to 999 products. Only 370 tokens are in 1,000 products or more. The most common tokens are “and” (30,588 products), “a” (29,081), “the” (28,152), “with” (26,779) and “to” (26,610).

The chart shows two kinds of token. A few tokens are everywhere: “and” is in 30,588 of the 40,066 products. Such a word tells you almost nothing about a product. Most tokens are rare: half of them are in one product only. They are names, models, typing mistakes in the descriptions, and unusual words.

A rare word says a lot. If a person types “emma”, only 6 products have it. If a person types “chair”, 4,293 products have it. The next lesson turns this observation into part of a score.

The vocabulary also shows how the catalogue writes words. “gray” is in 1,496 products, and “grey” in only 240. A person who types “grey” misses most grey products, because the index sees two words. Module 4 fixes this.

Larkfield’s search today uses every word. The notebook measures what this costs on the 60 English validation queries: 24 of them find nothing with every word, and none with any word.

So “any word” removes the empty pages. But it brings a new problem. “garden hose” with any word matches 1,439 products. A person reads ten. Which ten come first?

FTS5 itself can order its results. Larkfield’s search sorts them with FTS5’s own score, but only after “every word” has removed most products. The project’s bm25 run uses any word and its own scoring. You saw both rows of the comparison table in Module 1:

Run Matching NDCG@10 on the test queries (95% interval) Zero results
current every word must match 0.195 (0.155 to 0.237) 66.7%
bm25 any word may match 0.429 (0.381 to 0.476) 12.8%

The inverted index finds the candidates. The ranking decides their order. Both runs use an inverted index; they differ in which products they keep and in how they order them.

When to use it, when not, and what it costs

Section titled “When to use it, when not, and what it costs”

Use an inverted index whenever people search with words that appear in your text. Every word search does: product search, a help centre, an email box. It is the base of the next lesson, and of every lexical search in this course. Lexical means “based on the words themselves”.

What it costs. You build it once and store it. Larkfield’s FTS5 index takes 35.8 MB on the disk for 40,066 products. The project builds it, with BM25, in about 2 seconds. When a product changes, the index must change too. Module 8 shows how to keep it up to date.

What it cannot do. It finds exact tokens, nothing more:

  • “cushions” and “cushion”, or “grey” and “gray”, are different tokens. Normalising the text helps (Module 4).
  • “couch” and “sofa” have no token in common. The index cannot know that they mean the same. Synonyms (Module 4) and search by meaning (Module 5) help.
  • A word that is not in the text cannot be found. Product codes such as LK-91857 are in the product_id column, not in the title or the description. The last lesson of this module adds a rule for them.

Run postings.py for “teal chair”, “ligth bulb” and “light bulb”. For each one, predict first: will “every word” find anything? Then compare the sizes of the postings.

What we got: “teal chair” finds 8 products with every word (teal 211, chair 4,293). “ligth bulb” finds nothing, because “ligth” is in no product, but any word finds the 523 products with “bulb”. “light bulb” finds 473 with every word. One wrong letter turns 473 products into none.

Common mistake

The plural finds other products

Symptom: you search “outdoor cushions” and “outdoor cushion”. You expect the same products, but postings.py gives different counts:

outdoor in 3,252 products
cushions in 1,577 products
every word 702 products
any word 4,127 products
outdoor in 3,252 products
cushion in 1,284 products
every word 425 products
any word 4,111 products

Cause: the index stores tokens exactly as the clean-up made them. cushion and cushions are two rows of the index, with two different postings lists. A product that says “cushion” once is not in the postings of cushions.

Diagnosis: look up each word of the query in the vocabulary, as postings.py does. When a word you expected has a small or empty list, check the other forms: the plural, the other spelling, the word with an accent.

Fix: treat the query and the products the same way. If you change “cushions” to “cushion” in the query, you must also change it in every product before you build the index. Module 4 does this with a stemmer, and measures what it fixes and what it breaks.

Consequence in AI work: every search system has a clean-up step before the index. When search “misses” an obvious product, the reason is often the tokens, not the ranking.

Check your understanding

Use the index of the six products. Which products does “grey outdoor” find with every word, and which with any word? How many rows of the index does the search read?

Show the answer

The search reads two rows: grey → A, D and outdoor → A, B, E. With every word, it keeps the products in both lists: A. With any word, it keeps the products in at least one list: A, B, D, E. It never reads the products themselves, only two rows.

Check your understanding

Larkfield's index says: “garden” in 1,352 products, “hose” in 111 products. How many products can “every word” return, at most? Why is the answer 24 and not 111?

Show the answer

At most 111: every product with both words is in the shorter list, the postings of “hose”. The real answer is 24 because most hoses do not say “garden”, and most garden products are not hoses. Every word keeps only the products in both lists. Any word keeps the products in at least one list: 1,439.

Check your understanding

Tomás says: “Our search returns nothing for ‘grey outdor cushion’. The index must be broken. Let us rebuild it.” What do you answer, and what would you check first?

Show the answer

The index is not broken. It has no postings for “outdor”, because no product contains that word. With every word, one empty list makes the whole answer empty. Rebuilding the index changes nothing. Check the postings of each query word first, as postings.py does: “grey” 240, “outdor” 0, “cushion” 1,284. The fix is in the query, not in the index: allow any word, or correct the spelling (Module 4).

Recap

  • An inverted index lists, for each token, the products that contain it: its postings. It is built once and used by every search.
  • A query reads only the postings of its own tokens. “Every word” keeps the products in all the lists, and “any word” keeps the products in at least one.
  • Larkfield’s search uses SQLite FTS5, an inverted index. A lookup takes well under a millisecond; reading every product takes about 100 milliseconds.
  • The index matches exact tokens only: “cushion” is not “cushions”, “grey” is not “gray”, and a product code is not in the text.
  • Most of the 44,757 tokens are rare, and a few are in most products. A rare word says more about a product than a common one.

You can now find every product that contains a query’s words, fast. But “garden hose” with any word matches 1,439 products, and a person reads ten. Next, you score each product with BM25, and see every part of the score.

Next: BM25