E-Commerce Search

The problem

"Design the search for a big online store." Shoppers type words, such as running shoes, then narrow the results with filters: brand, size, a price range, in stock only. Each filter shows how many results it would leave, like Nike (120). Results rank by what shoppers buy, prices and stock change all day, and "snekers" or "trainers" must still find sneakers.

This practice problem reuses the Search Engine's pattern. Suggestions while typing come from the Autocomplete lesson: a trie of popular searches with the top suggestions kept at each prefix. Park search by photo.

The numbers

From the interviewer: 100 million products, 10,000 searches a second at busy hours, and 1 billion price and stock changes a day. Round a day to 100,000 seconds.

what                 working
changes a second     1 billion ÷ 100,000 = 10,000 (about 11,600 with 86,400)
changes per product  1 billion ÷ 100 million = 10 a day
stock checks         10 results × 10,000 searches = 100,000 a second

The index changes about as often as it is read; the Search Engine took about 400 new pages a second against 10,000 searches. Two slips: dividing by a month's 2.6 million seconds gives about 400, by an hour's 3,600 about 280,000.

Filters: an index per field

A shopper searches running shoes and ticks Nike, size 10, under $100 and In stock. Keep an index per field next to the text index: each brand and each size has its sorted list of product ids, stock is one more list, and the price index is sorted by price, so under $100 is one range. In a tiny store where the words match products 1 to 8:

list            product ids
running shoes   1, 2, 3, 4, 5, 6, 7, 8
brand: Nike     1, 3, 4, 6, 8
size: 10        1, 2, 4, 5, 6
price < $100    1, 3, 5, 6, 7, 8
in stock        1, 2, 3, 5, 6, 7
on every list   1, 6

Walk all the lists together, as the Search Engine walks two words' lists: only products 1 and 6 pass, and only they get ranked. Ranking first and then dropping the top 10 that fail the filters can leave a page with one result or none. Filters as extra words fail too: 10 also matches "10% off", and a price range is not a word.

Counts next to each filter

Every match passes through its shard anyway, so count while matching: each shard tallies its matches by brand, size and price band, sends the tallies with its top 10, and the search service adds them up while it merges. Over the 8 matches above that gives Nike 5, Adidas 2, Asics 1. Counts follow the other filters: tick size 10 and Nike drops to 3.

A store-wide count of each brand's products answers the wrong question: Nike (120) must count the Nike shoes that match this search. One extra search per filter value is far too costly: say 50 brands, 15 sizes and 6 price bands, 71 more searches for one page.

Ranking: relevance, sales and margin

A store ranks for what shoppers buy. Say three shoes match, scored 0 to 5:

shoe   text match   sales   margin   3 × match + 2 × sales + margin
A      5            1       2        19
B      4            5       1        23
C      1            2       5        12

B, a good match and the best seller, ranks first. Relevance weighs most, sales show what shoppers actually pick, and margin only tips close calls: put the high-margin weak match C first and shoppers click less and buy less. Sales and margin are kept as fields in the index, refreshed daily, so each shard scores its own matches. Stores tune the weights with A/B tests on purchases per search.

Stock and prices that won't sit still

Filters and counts run on the index, so the index must know stock. A change stream carries each price or stock change to the field indexes within seconds; a change rewrites one product's field, not its text. Seconds can still be too old for a shoe that just sold out, so the page also checks the 10 results it shows against the inventory: about 100,000 lookups a second at busy hours, the load of one cache server.

Checking stock only at display time breaks the In stock filter and its count: the 10 best come back, the sold-out ones drop out, and the page shows 6. Rebuilding the index nightly shows a shoe that sold out at 9 a.m. as in stock, at yesterday's price, until midnight.

Typos and synonyms

Both are handled at search time. A word the index doesn't know, like snekers or addidas, is fixed to the nearest word it does know, one or two letters off, the more popular first. A word it knows stays as typed: boots is never "fixed" to boats. Synonyms come from a list the store team edits every week: trainers becomes trainers OR sneakers, tv adds television. Applied at search time, an edit works at once, with no reindexing of 100 million products.

Same pattern as the Search Engine

The inverted index carries over, split by product over shards, every search asking all of them and merging their top 10s. So do the fresh index for new products and the result cache, with entries that live only seconds, since stock moves. What's new sits around that core: fields beside the words, counts beside the results, and an index that changes as often as it is read.

Summary

• Numbers: about 10,000 changes a second, as many as searches.
• Filters: an index per field, intersected with the words' lists before ranking.
• Counts: tallied on each shard while matching, added up by the search service.
• Ranking: relevance first, then sales and margin, weights tested.
• Stock and price: streamed into the index within seconds; the 10 shown checked again.
• Typos and synonyms: fixed and expanded at search time.