Search for red. Your store shows Bored Games.

transcript

A shopper searches your store for red. It gets Red Shoes. And Bored Games. And Hundred Items.

Red Shoes. Correct. Bored Games? Bored contains r, e, d. So does hundred. LIKE matches characters, not words.

It's slow too. With a leading wildcard, no index can help. So a full table scan. 50 million rows. 50 million string comparisons. Over 30 seconds a query. Database CPU at 100 percent. Every other query blocked.

Here's the key insight. The database asks: which documents contain this word? And reads every one. Flip it. Once, ahead of time, store each word with its documents. Finding a word is no longer a scan. It's one lookup.

Search running shoes. Look up running: products 1, 2, 4 and 5. Look up shoes: 1, 2 and 3. Microseconds each. Intersect them, starting with the smaller list. Products 1 and 2. Under a millisecond. And red only matches the word red.

30 seconds became under a millisecond. The work moved to index time, done once. That's the inverted index. Behind Lucene, Elasticsearch, and every modern search engine.

Full breakdown in the lecture.