19. Search and Inverted Indexes
1
The picture to keep in your head2
19.1 Why doesn't `LIKE '%word%'` scale?3
19.2 How do you tokenise and normalise text?4
19.3 What is an inverted index?5
19.4 How does ranking work (TF-IDF, BM25 in brief)?6
19.5 How do prefix search and tries work?7
19.6 How do you keep the search index in sync with the database?8
19.7 Where does Elasticsearch fit in the big picture?9
19.8 How do you shard a search index?10
Memory card and where the analogy breaks11
Practice: five levels12
Interview questions13
Solutions14
Sources15
Code lab19. Search and Inverted Indexes
19.1 Why doesn't `LIKE '%word%'` scale?
3 min read+10 XP
In the library: Without the cards, finding "every book about databases" means walking every shelf and opening every book. It works for a room of 50 books. Not for 2 million.
In the system: The first search anyone writes:
sql
Figure: prefix matches can use a sorted index; "anywhere" matches can't.
The problems:
- No index can help. A B-tree (Chapter 9) is sorted, so it can find titles that start with "data" (
LIKE 'data%'), like finding a word in a dictionary. But "database anywhere in the text" has no starting point, so the database reads every row. With 2 million rows of about 1 KB each and a disk reading 500 MB/s, that's about 4 seconds per search, before anyone else is searching. - No understanding of words. "database" won't match "Databases" in some collations, or "DB", and "data" matches "database" and "updatable" alike.
- No ranking. Every match is equal: a book titled "Databases" and one that mentions the word once in a 2,000-word description come back in whatever order.
Some databases add full-text search (PostgreSQL's tsvector with a GIN index, MySQL's FULLTEXT), which is the same idea as this chapter, built in. For a serious search feature, teams usually use a search engine: Elasticsearch, OpenSearch, Solr or similar.
Memory code: "A word in the middle has nowhere to jump to."