Build a distributed search engine (Elasticsearch / OpenSearch style) (12 scenes)
Scene 01

Five million books, under 100 ms — SQL LIKE scans and the document-term flip

Substring scans on a million-row table cannot serve ranked search at interactive latency, so the relation between document and term has to be flipped before any other mechanism is worth discussing.

Scene 01

Five million books, under 100 ms

  1. Watch
  2. Try it
  3. Predict
  4. Capture
SQLSELECT * FROM books WHERE body LIKE '%distributed systems%'#1The Cat in the HatDr. Seuss#2Distributed SystemsMaarten van Steen#3Designing Data-Intensive ApplicationsMartin Kleppmann#4Lucene in ActionOtis Gospodnetic#5The Old Man and the SeaErnest Hemingway… 4,999,995 more rows(each one will be examined character by character)read headWALL CLOCK0 mselapsed100 ms targetROWS SCANNED0of 5,000,000MATCHES0rows where body LIKE matchedLEVERS (visible only — outcome unchanged)b-treecores: 1limit: all …NVMeScanning… one row at a time.
What to watch for

The query 'distributed systems' starts a row-by-row sweep over 5,000,000 books. Watch the wall-clock meter and the rows-scanned meter climb together — and watch the 100 ms line fly by.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

naive_scan(query)
row-by-row LIKE '%...%' — every byte of every body is examined
def naive_scan(query):
    results = []
    for book in books:                  # 5,000,000 rows
        if not contains(book.body, query.terms):
            continue                    # most rows go here
        results.append(book)
    return results                      # cost: O(rows), not O(matches)

Where this sits in Build a distributed search engine (Elasticsearch / OpenSearch style)

Scene 01 of 12. 5M books, a search box, and a 100ms budget — the naive scan-every-row plan never crosses the line, no matter the cores or the disk.

Up next. Scanning every book asks 'does this row contain the term?' five million times. Asking the inverse — 'which rows contain this term?' — makes the answer fall out in two lookups, if you build the right table.

All 12 scenes in Build a distributed search engine (Elasticsearch / OpenSearch style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build a distributed search engine (Elasticsearch / OpenSearch style) builds on the one before it.All 12 Build a distributed search engine (Elasticsearch / OpenSearch style) scenes