Search: inverted index, ranking, Elasticsearch in practice

Users type a few words and expect the best matches fast. A food app has millions of dishes. The interviewer asks: "Design search for this app", or "Why not use a database query?"

A weak answer says "use Elasticsearch" and stops. Another weak answer says "use LIKE in the database". A strong answer explains why a database index does not help here. It shows how a list of words points to documents, and how results are put in order. It says how the data is split over servers. It also says that search is a copy of the database, and how the copy is kept up to date.

At SDE-2 level you should explain the word index and the ordering of results. At SDE-3 level you should also choose the number of shards, and explain what the user sees when the copy is late.

Look at the index at the back of a book. For each word it lists the pages where the word appears. To find "paneer", you do not read every page. You look at one line.

A search server does the same for all its documents. A document is one item that you can find, such as one dish listing. A term is one word after cleaning.

Why a database index is not enough

A B-tree (lesson 20) can help with =, ranges and LIKE 'paneer%'. It does not help with LIKE '%paneer%', because the start of the text is not known. The database must read every row. This is a full scan. A database query also has no idea of "best match". It cannot rank, and it does not know that "dishes" and "dish" are the same word.

The inverted index

An inverted index lists, for each term, the ids of the documents that contain it. Each list is a postings list. It is sorted by id. First the text is analysed:

1. Split the text into words.
2. Make them lower case.
3. Reduce each word to its root: "dishes" becomes "dish". This is stemming.

The same steps run on the query, so the words match. Here are four documents:

1. Paneer butter masala
2. Butter chicken
3. Paneer tikka
4. Masala dosa

The index is:

The query "paneer butter" needs two lists: [1, 3] and [1, 2]. For "both words" (AND), walk down the two sorted lists together. Keep an id that is in both. The result is [1]. For "either word" (OR), the result is [1, 2, 3]. The walk takes at most as many steps as the two lists have ids. It never looks at the other documents.

The cost is the work at write time. A new or changed document changes the lists of every word in it.

Ranking

An OR query can match thousands of documents. The user reads the top ten, so the order matters. Three ideas decide a score:

1. Term frequency. A document that has the word more often is a better match. But the gain slows down: the tenth mention adds less than the second.
2. Inverse document frequency (IDF). A word that is in few documents tells more than a word that is in most documents. "Special" is in many dish names, so it tells little. A simple version: IDF = log10(N / n), where N is the number of documents and n is the number that contain the word. (Elasticsearch uses a slightly different formula with the same idea.)
3. Length. A match in a short name counts more than a match in a long text.

Elasticsearch uses a method called BM25 that combines these three. Its settings k1 (how fast the gain slows down, default 1.2) and b (how much length matters, default 0.75) can be changed. Real search also adds business signals such as rating or a paid boost. A filter such as "vegetarian only" or "under Rs 300" keeps or removes documents and does not change the score.

Typos. A user may type "panner". A fuzzy search also accepts terms that are a few letters away: one letter added, removed or changed counts as one step. It costs more work, so use it only when a search finds few results.

Elasticsearch in practice

Elasticsearch is a search server. It stores documents as JSON and builds the inverted index for you. Its words are a little different:

• An index here is a named collection of documents, like a table. It is not a database index.
• A mapping gives each field a type. A text field is analysed, so you can search words in it. A keyword field is kept whole, for exact filters and sorting.
• An index is split into primary shards. A shard is a small, complete search index. The shard of a document is hash(routing value) mod the number of primary shards. The routing value is the document id by default. This is the hash mod of lesson 43, so the number of primary shards is fixed when you create the index. A split tool exists, but it only multiplies the number by a set factor, and the index must be read-only while it runs.
• Each primary shard has replicas (lesson 39). They answer searches and survive a server failure.

A search goes to one server, the coordinating node. It sends the query to one copy of every shard. Each shard returns its best results. The coordinating node merges them and returns the top results. This is scatter-gather (lesson 43). Many tiny shards slow each search, because it must ask all of them. Elasticsearch advises 10 to 50 GB per shard, and fewer than 200 million documents.

Paging. Page 1,000 of 10 results needs the top 10,000 from every shard. The default limit for from plus size is 10,000. For deeper paging, use a cursor (lesson 10).

Near real time. A new document is searchable after the next refresh, which runs about every second. Files are small and never changed. A changed document is written again as a new version.

Keeping search in step with the database

The database is the truth. The search index is a copy. There are three ways to fill it.

1. Write to both. The app saves in the database and then in the search server. One of the two can fail, and the two copies stay different. This is the dual-write problem of lesson 64.
2. Outbox or change data capture (lesson 64). The change is recorded in the same transaction as the data. A small indexer program reads the changes and sends them to the search server in batches. A batch may arrive twice. Saving a document under its id again gives the same result, so the repeat is safe (lesson 61).
3. Full rebuild. Build a new index from the database. Then move an alias, a name that points at an index, to the new one. Use it for a new mapping or to repair a difference.

The copy is a little late (lesson 40). A dish that was sold out a moment ago may still show. So the app reads the final facts, price and stock, from the database.

When the data is small and the queries are simple, Postgres full-text search (a tsvector column with a GIN index) may be enough. It has no second system and no sync.

SwadKart searches its dish listings.

Assumptions (made up to teach with, not real data):

• 2,000,000 dish listings of 1 KB each: 2 GB.
• A full scan reads 1 GB per second (as in lesson 20).
• An id takes 4 bytes. Real engines compress the lists, so real lists are smaller.
• "special" is in 600,000 dishes.
• The index and stored text together are 2 times the raw size: 4 GB. In two years the data is 10 times bigger.

Step 1: the LIKE query. It reads 2 GB. At 1 GB per second that is 2 seconds. With 200 searches per second, the database would need 200 x 2 = 400 seconds of reading every second. That is not possible.

Step 2: the inverted index. The "paneer" list has 40,000 ids x 4 bytes = 160 KB. The "butter" list has 30,000 x 4 = 120 KB. Together 280 KB. A scan reads 2 GB = 2,000,000 KB, which is 2,000,000 / 280 = 7,143 times more. The walk takes at most 40,000 + 30,000 = 70,000 steps. This answers the predict box: about 70,000.

Step 3: ranking. IDF = log10(2,000,000 / n):

• paneer: log10(2,000,000 / 40,000) = log10(50) = 1.70
• butter: log10(2,000,000 / 30,000) = log10(66.7) = 1.82
• special: log10(2,000,000 / 600,000) = log10(3.33) = 0.52

The query is "special butter paneer". Dish A is "Paneer butter masala". Dish B is "Special special special thali". With term frequency times IDF, A scores 1.70 + 1.82 = 3.52. B scores 3 x 0.52 = 1.57. A wins, because it has two rare words.

BM25 slows the gain from repeated words. With k1 = 1.2 and an average-length text, the term factor for 1, 2, 3 and 10 mentions is 1.00, 1.375, 1.571 and 1.964. It never goes above k1 + 1 = 2.2. Dish B now scores 1.571 x 0.52 = 0.82.

Step 4: shards. The index is 4 GB today and 40 GB in two years. The number of primary shards is fixed. We choose 3. Each shard is 4 / 3 = 1.3 GB today. In two years it is 40 / 3 = 13.3 GB, inside the advice of 10 to 50 GB. With one replica each there are 6 shard copies, 2 on each of 3 servers. One search asks 3 shard copies, one for each shard. Each returns its top 10, and the coordinating node merges 30 results into 10. For page 1,000, each shard returns its top 10,000, and the coordinating node sorts 3 x 10,000 = 30,000. Page 1,001 would pass the limit of 10,000.

Step 5: keeping it in step. Assume 5% of the listings change each day: 100,000 changes, which is 100,000 / 86,400 = 1.2 per second. The indexer sends a batch every second, and the refresh takes about 1 second. So a change is searchable in about 2 seconds, plus any delay of the change feed. A restaurant uploads 50,000 dishes. Assumption: the server takes 5,000 documents per second. That takes 50,000 / 5,000 = 10 seconds. A full rebuild takes 2,000,000 / 5,000 = 400 seconds, about 6.7 minutes. Then the alias moves to the new index.

• A search server solves finding by words and ranking at low cost: 280 KB read instead of 2 GB. It costs a second system, a copy that is a little late, and extra work on every change. I would use Postgres full-text search first when the data is small.
• More shards solve size and write speed. They cost a slower search, because every search asks every shard, and a fixed number. I would choose shards for the size in two years, and rebuild into a new index when the number must change.
• Ranking by words only solves the first version. It costs poor results when popularity or distance matters. I would add business signals.

"Elasticsearch can be my main database." The index is a copy with a refresh delay. Keep the truth in the database.

"More shards make search faster." A search asks every shard. In the example, 3 shards meant 3 requests for each search. Many tiny shards slow it down.

"The dish with the most mentions of the word is the best match." In the example, a rare word scored 1.70 and a common word 0.52. Repeats also count less each time.

1. What is an inverted index? What does IDF say about a word?
2. A site has 5,000,000 documents of 1 KB. A scan reads 1 GB per second. One word is in 25,000 documents and another in 10,000. (a) How long does a scan take? (b) How many KB of ids (4 bytes each) must the search read for both words? (c) Which word has the higher IDF? Use log10.
3. A seller marks a dish as sold out. It still shows in search for 10 minutes. Why can this happen, and what do you change?