System design · 7 of 20

Search, analytics and data pipelines

Inverted indexes, BM25 ranking, vector search, OLTP against OLAP, columnar storage, the lakehouse, and batch and streaming pipelines.

Updated 2026-09-18

On this page

The storage article is about answering "give me row 41" quickly. This one is about the two questions a B-tree cannot answer: "which documents are about storage engines, best first" and "what did revenue do by country last quarter". Both need a different index, a different file layout, and usually a different machine.

The map

Read this first when short on time. Every branch is a section below.

Figure 1. The whole article on one page. Every branch is a section below; fold what you know, open what you do not.

The inverted index: finding documents by word

A B-tree maps a key to a row. Full-text search needs the opposite: a map from every word to every document containing it. That is the inverted index, and it is the reason a search over ten million documents takes milliseconds while LIKE '%storage%' takes minutes.

Each term points at a postings list: the documents that contain it, with the count in each one and the positions where it appeared. Counts drive ranking; positions make phrase queries possible, because "storage engine" means the two terms adjacent rather than merely both present.

storage  -> [ doc 3 (tf 2, pos 11, 48), doc 9 (tf 1, pos 5), doc 12 ... ]
engine   -> [ doc 3 (tf 1, pos 12),     doc 7 (tf 4, pos 2, 19, 40, 55) ]

"storage engine" as a phrase: intersect the two lists, keep doc 3,
where a position of engine is exactly one past a position of storage.

Doc ids are stored in increasing order and delta-encoded, so a list of millions compresses to a fraction of its size, and skip lists let an intersection jump forward instead of walking every entry. An AND query is an intersection of postings, an OR a union.

Text is not indexed as typed. An analyzer runs the same chain at index time and query time, and a mismatch between the two is the classic reason a search returns nothing.

flowchart TD
  D["document text: Running the Storage Engines"] --> T["tokenize: Running, the, Storage, Engines"]
  T --> N["normalize: running, the, storage, engines"]
  N --> S["stem: run, the, storag, engin"]
  S --> I[["inverted index: term to postings list"]]

Figure 2. The analyzer chain. Stemming is what makes a search for "run" match a document that says "running", and the same chain must run over the query.

Index files are immutable segments. A new document goes into a small new segment; a delete writes a tombstone; a background merge combines small segments into large ones and drops the deleted rows. Nothing is edited in place, which is what makes the index safe to read while it is being written. Elasticsearch makes new documents visible on a refresh, one second by default, which is why it is called near-real-time rather than real-time.

In the wild

Apache Lucene is the index underneath Elasticsearch, OpenSearch and Solr; the segment and analyzer model described here is Lucene's.
Postgres ships the same idea as tsvector columns with a GIN index, which is enough for most applications and avoids running a second datastore.
SQLite FTS5 puts a full inverted index with BM25 ranking inside a single file, which is how mobile applications search offline.

Postings list: The compressed list of documents a term appears in, with frequencies and positions.
Analyzer: The text pipeline — tokenize, normalize, stem, expand synonyms — applied identically when indexing and when querying.
Segment: An immutable chunk of index. Writes create new ones, merges consolidate them, deletes are tombstones until a merge.

Ranking: why BM25 replaced TF-IDF

A database filters, returning every matching row. A search engine ranks, returning the best matches first, because a query for "storage engine" matches thousands of documents and only the first ten will ever be read. Ranking, not matching, is what makes search hard.

The classic signal is TF-IDF: a term matters more the more often it appears in this document (term frequency) and the rarer it is across the whole corpus (inverse document frequency). That second half is what stops "the" from dominating every result.

BM25 is TF-IDF with two corrections learned from practice, and it is the default in every modern engine. The first is saturation: the tenth occurrence of a word adds far less than the second, controlled by k1, around 1.2. The second is length normalization: a match in a short title counts for more than the same match buried in a long page, controlled by b, 0.75 by default. Both defaults survive because they are hard to beat without tuning for a specific corpus.

Text score is rarely the final order. Real ranking blends field boosts (a title hit outweighs a body hit), recency, popularity, stock availability, and personalization. At scale this is two stages: a cheap retrieval pass takes the top few hundred by BM25, then an expensive model reranks only those.

Watch out

Relevance cannot be judged by looking at one query. Keep a set of judged query-and-result pairs and measure with precision, recall and NDCG, or every tuning change is guesswork that fixes one search and breaks twenty.

In the wild

Elasticsearch switched its default similarity from TF-IDF to BM25 in version 5 and has not moved since.
Amazon and Airbnb both rank with business signals layered over text relevance, which is why an exact title match is not always first.
Learning to rank plugins for Elasticsearch and Solr implement the two-stage pattern directly, reranking the top N with a trained model.

Vector search: finding things by meaning

An inverted index can only match words that were written. A query for "laptop overheats" will not find a document that says "notebook runs hot", because they share no terms. Vector search fixes that by turning text into an embedding, a few hundred numbers positioning it in a space where similar meanings are near each other, and searching by distance instead of by term.

Comparing a query to every stored vector is exact but linear: a million vectors of 768 dimensions is hundreds of millions of multiplications per query. Approximate nearest neighbour indexes trade a little recall for orders of magnitude of speed.

Index	How it works	Trade-off
HNSW	A layered graph: search starts on a sparse top layer and descends, following edges toward closer neighbours	Highest recall and speed, but the graph lives in memory and building it is expensive
IVF	Cluster the vectors, then search only the few clusters nearest the query	Cheap and compact; recall depends on how many clusters you probe
Product quantization	Compress each vector into a short code, usually on top of IVF	Cuts memory by an order of magnitude at some loss of precision

flowchart TD
  Q["query: laptop overheats"] --> E["embedding model"]
  E --> V["vector, 768 numbers"]
  V --> A["ANN index: approximate nearest neighbours"]
  A --> C["top 200 candidates"]
  B["BM25 over the inverted index"] --> C
  C --> R["rerank, then return the top 10"]

Figure 3. Hybrid retrieval. Vectors find things worded differently, keywords find exact names and codes, and the fused candidate set is reranked.

Vectors are not a replacement. They are bad at exact tokens — a part number, an error code, a rare surname — which BM25 handles perfectly. Production systems run both and fuse the two result lists, commonly with reciprocal rank fusion, which needs no score calibration between them.

In the wild

pgvector adds HNSW and IVF indexes to Postgres, which is the right first choice when the corpus fits on one machine.
Elasticsearch and OpenSearch added native kNN fields so hybrid search runs in one query against one system.
FAISS from Meta is the library most dedicated stores — Pinecone, Qdrant, Milvus, Weaviate — either use or imitate.

OLTP and OLAP: two shapes of a query

Transactional and analytical workloads pull a storage engine in opposite directions, which is why almost every company ends up running two.

	OLTP	OLAP
Query shape	Read or write a handful of rows by key	Scan billions of rows, read three columns, aggregate
Concurrency	Thousands of small transactions per second	A few large queries at a time
Latency target	Single-digit milliseconds	Seconds to minutes
Layout	Rows together, many indexes	Columns together, few or no indexes
Data	Current state, edited in place	History, append-only
Systems	Postgres, MySQL, DynamoDB	BigQuery, Snowflake, Redshift, ClickHouse, DuckDB

The layout row is the one that decides everything else. In a row store, the whole record sits together, so reading three columns out of eighty still pulls all eighty off disk. For a point lookup that is ideal — one seek gets the record — and for a scan of a hundred million rows it is a twenty-fold waste.

Watch out

Running the monthly report against the production database is the standard way to cause an incident. A single large scan evicts the buffer cache that the transactional queries depend on, holds a snapshot open so old row versions cannot be cleaned up, and saturates disk. Send analytics to a read replica at minimum, and to a warehouse once it matters.

In the wild

Postgres and MySQL serve the application; a CDC pipeline copies their changes into the warehouse, which is the arrangement in most companies.
ClickHouse answers aggregate queries over billions of rows in under a second, which is why it sits behind so many product analytics dashboards.
DuckDB puts a columnar engine in a library, so a laptop can analyse a Parquet file that would once have needed a cluster.

Columnar storage: why analytics needs a different file

A columnar file stores all values of one column together instead of all values of one row. That single rearrangement is where analytical speed comes from, and it pays off in four separate ways.

Figure 4. The same three rows, two layouts. A query summing amount by city touches only the two highlighted blocks, while the row layout has to read every byte of all three records.

Less to read. The query names three columns, so the engine fetches three column chunks and nothing else. Better compression. A column holds one type and often few distinct values, so dictionary encoding, run-length encoding and bit packing typically shrink it five to twenty times — and less data is less I/O. Faster execution. Values of one type sit contiguously, so the engine processes them in batches of thousands with SIMD instructions rather than row by row.

A Parquet or ORC file is organised as row groups of roughly 128 MB, each holding one chunk per column, each chunk split into pages, with a footer carrying statistics. Those statistics are the fourth win: a filter on month = '2026-02' reads each row group's minimum and maximum and skips the ones that cannot match, without decompressing anything. Sorting the data by the column you filter on makes that skipping dramatically more effective, which is why a sort key is the single most important physical design choice in an analytical table.

In the wild

Parquet on object storage is the default interchange format: Spark, Trino, DuckDB, Athena and pandas all read it.
ClickHouse MergeTree keeps data sorted by a primary key and merges parts in the background, so its skipping indexes stay effective as data arrives.
BigQuery's Capacitor and Snowflake's micro-partitions are the same idea inside proprietary engines, with statistics used for automatic pruning.

Row group: A horizontal slice of a columnar file — the unit that statistics describe and that a reader can skip.
Predicate pushdown: Sending the filter down to the storage layer so it can skip blocks instead of returning rows to be discarded.
Vectorized execution: Processing a batch of column values per operator call rather than one row, which keeps the CPU pipeline full.

Warehouse, lake and lakehouse

Where the analytical data lives has moved through three designs, and the third is the one most new systems adopt.

A warehouse is a managed SQL database for analytics: you define a schema, load clean data into it, and query. Schema on write keeps it tidy and makes it fast, but everything must be modelled before it is useful, and storing raw logs there is expensive. A data lake inverts that: dump files onto object storage, decide the schema when you read. It is cheap and accepts anything, which is also how it becomes a swamp of files nobody can interpret.

The lakehouse keeps the lake's cheap files and adds a table format on top — Apache Iceberg, Delta Lake or Hudi. The format is a metadata layer that tracks which files make up a table right now, so a commit that swaps a set of files is atomic. From that one property come ACID transactions over object storage, snapshot isolation for readers, time travel to any previous snapshot, safe schema evolution, and background compaction of small files.

flowchart TD
  S["sources: databases, events, files"] --> O["object storage: Parquet files"]
  O --> M["table format: Iceberg or Delta metadata"]
  M --> E1["Spark: heavy transforms"]
  M --> E2["Trino or Athena: interactive SQL"]
  M --> E3["Flink: streaming writes"]

Figure 5. The lakehouse. Storage is one copy of the data and compute is whatever engine suits the job, because the table format is the shared contract between them.

Underneath all three sits the same structural change: storage and compute are separate. Data rests on object storage at object-storage prices; a cluster starts when a query runs and stops afterwards; two teams can run different engines against the same bytes without copying. That is also what makes a warehouse bill surprising, since compute is charged by the second or by the byte scanned.

In the wild

Netflix built Iceberg because Hive's directory-listing table layout could not give atomic commits or correct results on object storage at their scale.
Databricks built Delta Lake for the same reasons and coined the term lakehouse.
Snowflake and BigQuery are the managed end of the same architecture, and both can now read external Iceberg tables directly.

Pipelines: getting the data there, repeatedly

None of the above matters until data arrives reliably and can be recomputed when the logic changes. That is the pipeline, and its defining requirement is that running it twice must be safe.

The old shape was ETL: extract, transform on a separate machine, then load the clean result, because warehouse compute was scarce and expensive. The modern shape is ELT: load the raw data first, then transform it inside the warehouse with SQL, because that compute is now cheap and elastic. ELT keeps the raw layer, so a bug in the transform is fixed by rerunning it rather than by re-extracting from a source that may have changed.

flowchart TD
  S["sources: CDC, events, APIs"] --> R["raw: loaded exactly as it arrived"]
  R --> T["staging: typed, deduplicated, tested"]
  T --> M["marts: one model per question"]

Figure 6. The ELT layering. Raw is never edited, so every layer below it can be dropped and rebuilt from it.

The work is scheduled as a DAG of tasks with declared dependencies, so a task runs only once its inputs are ready and a failure retries just that node. The discipline that makes this survivable is partitioning by time: each run owns one date's partition and replaces it wholesale rather than appending. A rerun then produces the same result as the first run, a late-arriving correction is handled by reprocessing that one date, and a backfill is the same code applied over a range of old partitions.

Freshness decides the shape. Batch on a schedule gives data that is hours old for a fraction of the cost. Streaming gives seconds, at the price of a permanently running job and harder debugging. The older lambda architecture ran both and merged them, and maintaining the same logic twice is exactly why teams moved to a kappa shape: one streaming pipeline, and reprocessing done by replaying the log from the beginning.

Watch out

A pipeline that appends instead of replacing a partition cannot be rerun without duplicating rows, which means every failure needs manual cleanup at the worst possible moment. Make the write idempotent — replace the partition, or write to a temporary location and swap atomically — before adding any other feature.

In the wild

Airflow came out of Airbnb and made the scheduled DAG the standard unit; Dagster reframes the same thing around the assets produced rather than the tasks run.
dbt owns the transform layer in most ELT stacks: SQL models with declared dependencies, tests and generated lineage.
Fivetran and Debezium cover ingestion, the latter streaming database changes as described in the messaging article.

Partition: A slice of a table, usually one date, that a pipeline run owns entirely and can replace.
Backfill: Running current pipeline code over historical partitions to rebuild them after a change.
Lineage: The recorded graph of which tables and columns feed which, used to trace a wrong number back to its source.

Recap

An inverted index maps each term to a postings list of documents, frequencies and positions. Positions give phrase queries, delta encoding and skip lists keep intersections fast.
The analyzer chain — tokenize, normalize, stem — must be identical at index time and query time, or queries silently match nothing.
Index segments are immutable: writes add segments, deletes are tombstones, merges consolidate. Visibility is on refresh, so search is near-real-time.
Search ranks rather than filters. BM25 is TF-IDF plus term saturation and length normalization, and it is the default everywhere.
Real ranking blends text score with boosts, recency and popularity, usually as cheap retrieval followed by an expensive rerank of the top few hundred.
Vector search matches meaning through embeddings and approximate indexes — HNSW for recall, IVF and quantization for memory — and is fused with BM25 because exact tokens still need keywords.
OLTP wants point access to rows, OLAP wants scans of a few columns over billions of rows. A row store reads every column it stores, so the two need different engines.
Columnar storage wins four ways: fewer columns read, far better compression, vectorized execution, and row-group statistics that skip data entirely. Sorting by the filtered column multiplies the last one.
A lakehouse is cheap object storage plus a table format — Iceberg, Delta, Hudi — whose atomic metadata commit gives ACID, time travel and schema evolution over files.
Storage and compute are separate everywhere now: one copy of the data, engines started per query, and a bill driven by bytes scanned.
ELT loads raw and transforms in the warehouse. Pipelines are DAGs partitioned by date, every run replaces its partition, and that idempotency is what makes reruns and backfills safe.

Questions

Try answering each one out loud before opening it. Lead with the one-line answer, then the reasoning, then one detail from a real system.

Why can a B-tree index not serve full-text search?

A B-tree is ordered by whole key values, so it can find a row whose column equals or starts with a string, but a document contains hundreds of words and a query must find it by any of them; that needs a map from every term to every document, which is an inverted index.

A leading wildcard search cannot use a B-tree at all and degrades to a full scan.
The inverted index also stores frequencies and positions, which a B-tree has no place for.
Ranking needs corpus-wide statistics that only the inverted structure provides.

Postgres exposes both: a B-tree on the column for equality, a GIN index over a tsvector for search.

What is in a postings list, and what does each part buy you?

The document ids containing the term, the frequency in each document, and the positions of each occurrence: ids answer the match, frequencies feed ranking, positions make phrase and proximity queries possible.

Ids are ascending and delta-encoded, so the list compresses well and intersects cheaply.
Skip lists let an intersection jump ahead rather than walk every entry.
Offsets are stored too when the engine must highlight the matched text.

Dropping positions roughly halves index size, which some engines offer for fields that will never be phrase-searched.

A search for "Running" returns nothing although the document says "running". What happened?

The index-time and query-time analyzers do not match: the document was normalized and stemmed on the way in, and the query was not, so the query term no longer exists in the index.

Any mismatch causes this — different stemmer, missing lowercase filter, different tokenizer.
Engines expose an analyze endpoint that shows exactly which terms a string produces.
Changing the analyzer requires reindexing, since existing segments hold the old terms.

It is the most common search bug, and it presents as zero results rather than as an error.

Why does search use immutable segments instead of updating an index in place?

Because an inverted index is expensive to modify — a single new document touches the postings list of every term it contains — so engines write a small new segment instead and merge in the background.

Immutability means readers never block on writers and caches stay valid.
Deletes are tombstones, and the space is only reclaimed at merge time.
The cost is that a document is visible only after a refresh, typically one second.

It is the same log-structured trade-off that LSM-trees make in the storage article, for the same reason.

Explain BM25 as if to someone who knows TF-IDF.

BM25 keeps TF-IDF's two signals and fixes their behaviour at the extremes: term frequency saturates, so the tenth occurrence adds almost nothing, and document length is normalized, so a match in a short title outranks the same match in a long page.

k1, around 1.2, controls how fast the frequency saturates.
b, 0.75 by default, controls how strongly length is penalized.
Without saturation, keyword stuffing wins; without normalization, long documents win.

Lucene made BM25 the default similarity in version 6, and the defaults are rarely worth tuning without judged relevance data.

When would you add vector search, and would you remove keyword search?

Add vectors when users describe what they want in words the documents do not use, and keep keywords, because exact tokens like part numbers, error codes and names are precisely where embeddings are weakest.

Run both retrievers and fuse the ranked lists, commonly with reciprocal rank fusion so no score calibration is needed.
Approximate indexes trade recall for speed: HNSW for quality, IVF with quantization when memory is the constraint.
Embeddings must be regenerated for the whole corpus when the model changes, which is a real operational cost.

pgvector inside an existing Postgres is usually the right first step, before adopting a dedicated vector store.

Why is running analytics on the production database a bad idea?

Because one large scan competes with thousands of small transactions for the same buffer cache, disk and snapshot machinery, so the report degrades the application it is reporting on.

The scan evicts hot pages that point lookups depend on, so latency rises long after the query ends.
A long-running snapshot prevents cleanup of old row versions, bloating tables.
Row storage reads every column, so the scan is far more I/O than the query needs.

A read replica is the minimum fix and a columnar warehouse fed by CDC is the real one.

Explain why columnar storage is faster for aggregate queries.

Because it reads only the columns the query names, compresses each column far better since values share a type and domain, processes values in vectorized batches, and skips whole row groups using their stored minimum and maximum.

A row store must read all eighty columns to sum one of them.
Dictionary and run-length encoding commonly shrink a column five to twenty times, and less data is less I/O.
Statistics-based skipping only works well if the data is sorted by the filtered column.

That last point is why the sort key is the most consequential physical design decision in ClickHouse or an Iceberg table.

What does a table format like Iceberg add to a pile of Parquet files?

A metadata layer that records exactly which files constitute the table at each snapshot, so swapping that set is an atomic commit; from that follow ACID writes, consistent reads, time travel and safe schema evolution over object storage.

Directory listing, the older Hive approach, gives no atomicity and is slow and eventually consistent on object stores.
Readers pin a snapshot, so a compaction running underneath them cannot corrupt results.
Schema changes are recorded by field id, so renaming a column does not rewrite data.

Netflix built Iceberg for exactly this, after Hive tables produced wrong results at their file counts.

ETL or ELT, and why did the default change?

ELT, because warehouse compute became cheap and elastic, so it is better to land raw data first and transform it in SQL than to transform on a separate machine before loading.

Keeping the raw layer means a transform bug is fixed by rerunning, not by re-extracting from a source that has since changed.
Transformations in SQL are versioned, tested and lineage-tracked by tools like dbt.
ETL still wins when the data must be filtered or masked before it is allowed to land.

That exception matters for regulated data, where loading raw personal data into the warehouse is itself the problem.

What makes a data pipeline safe to rerun?

Partitioning by time and having each run replace its partition entirely rather than append, so a second run of the same date produces the same table as the first.

Appending duplicates rows on retry and forces manual cleanup during an incident.
Writing to a temporary location and swapping atomically gives the same property where partition replacement is not available.
Idempotent partitions are also what make a backfill a normal operation rather than a special project.

Orchestrators retry failed tasks automatically, so a non-idempotent task is guaranteed to be run twice eventually.

Design the data path for a product dashboard that must show yesterday's numbers and the last five minutes.

Land events on a log, stream them into a columnar store for the recent window, batch them into partitioned Parquet or Iceberg for history, and have the dashboard read one table that unions the two.

History is where the cost is, so it belongs in compressed columnar files partitioned by date.
The last few minutes come from a streaming job or a real-time store like ClickHouse, with a short retention.
The batch layer is the source of truth and eventually overwrites the streaming estimate for the same period.

Keeping the same aggregation logic in two engines is the weakness of this design, which is exactly the argument for a kappa-style single streaming pipeline.