Practice: five levels

Assignments

Five levels. Do them in order. Answers are in "Solutions" at the end, so try first.

Level 1: Think (no code)

A. True or false? Explain in one line.

1. A B-tree index on title makes WHERE title LIKE '%kerala%' fast.
2. The same analyzer must be used for indexing and for queries.
3. For "database internals", you should intersect starting from the longer posting list.
4. In BM25, a word repeated ten times scores ten times as much as once.
5. Elasticsearch should be the primary store for orders.

B. Which fix? Pick: analyzer change, synonyms, trie or edge n-grams, CDC, more replicas, field boost.

1. Searching "DB" doesn't find "database" books.
2. Books updated in the admin panel take hours to show new prices in search.
3. Search is correct but slow at peak, with CPU maxed on every shard.
4. A book with "databases" only in the description outranks one with it in the title.
5. The search box needs suggestions after two letters.

Level 2: Calculate

1. LIKE '%word%' scans 2 million rows of about 1 KB, at 500 MB/s. How long per search? How many searches per second could one database do this way?
2. Each book has about 200 words after analysis. How many postings (word-in-book entries) does the index hold, at most?
3. "kerala" appears in 50 books and "recipes" in 20,000. If you intersect by checking each item of one list against the other, which list do you walk, and how many checks is that?
4. A search cluster has 3 primary shards, each with 2 replicas. How many shard copies exist in total? If one copy handles 200 queries per second, roughly what's the cluster's query capacity?

Level 3: Build

In Python:

1. analyze(text): lowercase, split on non-letters, drop stop words, a simple stemmer.
2. An InvertedIndex with add(doc_id, text), remove(doc_id), search_and(query) and search_phrase(phrase) using positions.
3. tfidf(query) and bm25(query); show that repeating a word gives TF-IDF a 3× score but BM25 much less.
4. A Trie with insert(word, popularity) and complete(prefix, k).
5. apply_change((doc_id, version, text)) that ignores out-of-order events and handles deletes.

Level 4: Debug

Customers say: "I searched Database and got nothing. But you sell 'Database Internals'!" The code:

1. Find the bug and explain exactly why "Database" returns nothing.
2. Fix it, including multi-word queries.

Level 5: Design

Design search for the bookstore: about 2 million books, titles and descriptions in English, customers expecting results in under 200 ms, filters by price and category, autocomplete, and admins updating prices and stock all day.

Deliver:

1. Where search data comes from and how it stays in sync with the database.
2. The analyzer and the ranking (which fields, what boosts, which business signals).
3. How autocomplete works.
4. How the index is sharded and replicated, with your reasoning.
5. What happens when the search cluster is down.