Part 9 · Derived views

Analytics and Query-Execution Internals

Lesson 20 established the architecture: one system of record, many derived views, each rebuildable from a log. The analytical data warehouse is the largest derived view most companies run — a columnar copy of the business's facts, rebuilt by batch jobs, that an analyst queries interactively. Which raises the question this lesson answers: a query over a billion rows returns in seconds. How? Lesson 04 gave half the answer — columnar storage reads only the columns you project. This lesson gives the other half: the query-execution engine on top of that layout — how a SQL string becomes a plan, how the optimizer picks join order, and the three tricks (vectorized execution, code generation, compression-aware operators) that make scanning billions of rows feel instant. A warehouse is a derived view; here is the machinery that makes it fast.

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 3 (Storage and Retrieval) — the column-oriented storage and data-warehousing section (star/snowflake schemas, data cubes, column compression, vectorized processing) — extended with standard query-execution practice (parse → plan → cost-based optimizer, Volcano vs vectorized vs compiled execution, predicate pushdown, late materialization). Original synthesis; no DDIA prose or figures reproduced.

Linear position

Prerequisite: Lesson 04 — columnar storage (bytes laid out by column, so a scan reads only projected columns; run-length and dictionary compression; sort order for block-skipping) and the OLTP-vs-OLAP split. Lesson 20 — a derived view is a deterministic function of the system of record, rebuildable from a log. We build the execution engine on top of the columnar layout 04 introduced; we do not re-derive that layout.
New capability: Explain why a warehouse feels fast — trace a SQL query through parse → logical plan → cost-based optimizer → physical plan, and name the execution techniques (vectorized batches, query compilation, late materialization, compression-aware operators) that turn a billion-row scan into a few seconds — and model analytical data with star/snowflake schemas and data cubes.

The plan

Five moves. (1) Model the data: the star schema (one central fact table of measures + dimension tables around it), the normalized snowflake variant, and data cubes / materialized aggregates that precompute rollups. (2) Trace the query-execution pipeline: SQL → parse → logical plan → physical plan, and the cost-based optimizer that uses statistics to pick join order and algorithms. (3) The first speed trick: vectorized execution — process a column batch per operator call instead of a row at a time — with a worked throughput number against the row-at-a-time (Volcano) model. (4) Two more tricks: query compilation (codegen the plan to machine code) and compression-aware / late-materialized execution (work on encoded data; fetch wide columns only after filtering). (5) Failure modes, the checklist, "Where is truth?" for the warehouse, and the hand-off to search and vector indexes.

1 · Modeling analytical data: star, snowflake, and cubes

Lesson 04 answered how to store analytical data (by column); the prior question is how to shape it. An OLTP database normalizes aggressively — split data into many narrow tables, store each fact once, join at read time — to keep small updates cheap. A warehouse optimizes the opposite workload: a few queries, each scanning enormous numbers of rows but touching a handful of columns. So warehouse modeling deliberately denormalizes for scan-friendly joins, and it converges on a recurring shape: the star schema.

One central fact table holds the events or measurements — one row per click, sale, impression, or sensor reading — each row mostly foreign keys plus a few numeric measures (revenue, quantity, latency). Around it sit dimension tables: the descriptive context a fact points at — who, what, when, where (the user, the product, the date, the store). The fact table is long and thin (billions of rows, few columns); each dimension is short and wide (thousands to millions of rows, many descriptive columns). Drawn out, facts sit at the center with dimensions radiating off — hence “star.”

Star schema — one fact table in the center, dimensions around it dim_date dim_user [date_key, day, [user_key, name, month, quarter] country, segment] \ / \ / +------------------+ | FACT_SALES | <- one row per sale | date_key (FK) | mostly foreign keys | user_key (FK) | + numeric measures | product_key(FK) | | store_key (FK) | | revenue, qty | <- the measures you aggregate +------------------+ / \ / \ dim_product dim_store [product_key, name, [store_key, city, category, brand] region, format]

A typical query joins the fact table to a few dimensions, filters on dimension columns (“last quarter,” “in Europe”), and aggregates a measure (“sum revenue grouped by category”). Because the fact table is columnar (lesson 04), the scan reads only the foreign-key columns and the measure it sums — back to the ~3%-of-bytes win. The denormalization (carrying foreign keys flat on every fact row rather than chasing a chain of joins) is exactly what keeps that scan cheap.

The snowflake schema is the variant where dimensions are themselves normalized: instead of one wide dim_product carrying category and brand as text, dim_product points to a separate dim_category table, which may point to dim_department, and so on — dimensions branching into sub-dimensions like a snowflake's arms. It saves a little storage and removes redundancy but adds joins back to the read path, the very cost a warehouse was avoiding. The usual call: keep the fact table denormalized always, and only snowflake a dimension when it is genuinely large or shared.

Data cubes and materialized aggregates. Even with columnar scans, summing a billion fact rows on every dashboard refresh is wasteful when the same rollups are asked for again and again. A data cube (or OLAP cube) precomputes aggregates — sums, counts, averages — across combinations of dimensions, so “revenue by country by month” is a lookup into a small precomputed grid rather than a fresh scan. A materialized aggregate (or materialized view, lesson 20) is the same idea in a relational warehouse: store the grouped-and-summed result and read it directly. The trade is storage and flexibility for speed: you pay storage to hold the grid and lose the ability to drill into a dimension you did not precompute, in exchange for instant rollups on the ones you did. Warehouses often keep raw facts for ad-hoc queries and a few materialized aggregates for the hot dashboard paths (lesson 34).

These tables do not appear by magic: building the fact and dimension tables from raw event logs is a batch job — a deterministic transform over a bounded input — which is exactly lesson 18, and it is what makes the warehouse a derived view.

2 · The query-execution pipeline: SQL to a physical plan

You type a SQL string; the engine must turn it into machine work. The pipeline has four stages, and the interesting decisions happen in the third.

1Parse — turn the SQL text into an abstract syntax tree, checking syntax and resolving names (does revenue exist? which table is it on?). Pure mechanical translation; no choices yet.

2Logical plan — a tree of relational operators describing what to compute, not how: scan, filter, join, aggregate, project. SELECT category, SUM(revenue) FROM fact JOIN dim_product ... WHERE quarter='Q1' GROUP BY category becomes Aggregate(Join(Filter(Scan fact), Scan dim_product)). Many physical plans can satisfy one logical plan.

3Optimize — the cost-based optimizer rewrites and re-orders the logical plan and assigns a concrete algorithm to each operator, choosing the variant it estimates to be cheapest. This is where the work is. Detailed below.

4Physical plan — an executable tree: which join algorithm (hash join, sort-merge, nested-loop), which join order, which scans, where filters run. This is what actually executes.

What the optimizer decides. Two choices dominate, and both depend on statistics — precomputed summaries of each table (row counts, distinct-value counts per column, min/max, histograms) that the engine refreshes periodically:

Join order. Joining A, B, C can be done as (A⋈B)⋈C or A⋈(B⋈C) or others. The intermediate result sizes differ enormously: join the two tables that produce the smallest intermediate first, so every later operator handles fewer rows. The optimizer estimates each intermediate's row count from statistics and searches for the cheapest order.
Join algorithm. A hash join builds an in-memory hash table on the smaller input then probes it with the larger — great when one side fits in memory. A sort-merge join sorts both sides and merges — better when inputs are already sorted or too big to hash. A nested-loop join is fine only for tiny inputs. The optimizer picks per join, from the estimated sizes.

Statistics are the optimizer's eyes — and its blind spot

A cost-based optimizer is only as good as its statistics. If they are stale (the table grew 100× since the last refresh) or wrong (a column the optimizer thinks is uniform is actually skewed), it picks a bad join order or a hash join whose “small” side does not fit in memory and spills to disk. The single most common warehouse-performance bug is not a missing index — it is stale statistics on a table that recently changed shape. ANALYZE the table.

The plan is a tree of operators. The remaining sections are about how each operator is implemented — because the same physical plan can run 10× to 100× faster depending on the execution model.

3 · Why warehouses are fast I: vectorized execution

The classic execution model is Volcano (also called the iterator or row-at-a-time model): every operator exposes next(), which returns one row; an operator calls next() on its child to pull the next row, processes it, and returns it up. The whole plan is a chain of next() calls, and a query over a billion rows makes on the order of a billion calls per operator. It is elegant and composable — and slow, because of per-row overhead.

Every next() call costs a (often virtual/indirect) function call; every operator does a branch (“is this row null? does it pass the predicate?”); and one row touches a few bytes, defeating the CPU cache and the SIMD units that want to chew through contiguous arrays. The actual work — comparing an integer, adding to a sum — is dwarfed by the bookkeeping around it.

Vectorized execution fixes this by changing the unit of work from one row to a batch — typically about 1,024 values of a single column. next() now returns a batch, and each operator runs a tight loop over that batch: a filter compares 1,024 integers in one cache-friendly pass, often using SIMD (one CPU instruction over 8 or 16 lanes at once). The function-call and dispatch overhead is paid once per 1,024 rows instead of once per row, and the inner loop is exactly the array-crunching shape modern CPUs are built for. This pairs naturally with columnar storage (lesson 04): a column is already a contiguous typed array, so a batch is just a slice of it.

Worked number — overhead amortized over a 1,024-row batch

Suppose the useful work to filter one row (load value, compare, decide) is ~1 ns, and the per-row overhead in the Volcano model — the virtual next() call, the branch misprediction, the cache miss from row-at-a-time access — is ~4 ns. Row-at-a-time cost per row:

1 ns work + 4 ns overhead = 5 ns/row

Vectorized: the same ~4 ns of dispatch overhead is paid once per batch of 1,024 rows, and the per-value work drops too (tight loop, SIMD packs ~4 comparisons per step, call it ~0.3 ns/row):

0.3 ns work + (4 ns / 1,024) overhead ≈ 0.3 ns + 0.004 ns ≈ 0.30 ns/row

That is roughly 5 / 0.30 ≈ 16× faster on the filter, before any other trick. Over a billion rows: 1,000,000,000 × 5 ns = 5 s row-at-a-time versus 1,000,000,000 × 0.30 ns ≈ 0.3 s vectorized. The plan is identical — only the operator implementation changed. This is why ClickHouse, DuckDB, and modern Spark/Photon are vectorized, and why a billion-row scan returns interactively rather than in minutes.

4 · Why warehouses are fast II: compilation, pushdown, and encoded operators

Vectorization is the biggest lever; three more compound it.

Query compilation (codegen). Even a vectorized engine spends cycles interpreting the plan — walking the operator tree, dispatching on operator type, branching on column types. Query compilation removes that layer: the engine generates source (or LLVM IR) specialized to this exact query — the filter constant, the column types, the aggregation function all baked in as literals — and compiles it to machine code, then runs that. There is no interpreter loop and no per-row type dispatch; the query becomes a purpose-built program. Systems like Spark's whole-stage codegen and HyPer/Umbra take this route. The trade is compilation latency (tens of milliseconds to build the code), which is negligible for a query that scans billions of rows but can dominate for tiny ones — so engines often compile only the heavy stages.

Predicate pushdown and late materialization. Two layout-aware tricks that cut bytes touched:

Predicate pushdown — push the filter as close to the scan as possible, ideally into the storage layer. A Parquet file (lesson 04) stores per-block min/max stats; if a block's quarter range is entirely outside 'Q1', the engine skips the whole block without reading it. The filter that logically sits above the scan is evaluated during the scan, so disqualified data never enters the pipeline.
Late materialization — when a query filters on one column and projects wide columns, do not stitch full rows up front. Run the filter on the narrow column first, carry only the surviving row-ids, and fetch the wide columns (bio, payload) only for the rows that passed. If a filter keeps 1% of rows, late materialization reads 1% of the wide column instead of 100% — the wide fetch shrinks by 100×.

Compression-aware execution. Lesson 04's run-length and dictionary encodings are not just for storage — operators can work on the encoded data directly. To count rows where country = 'US' in a run-length-encoded column stored as “US × 4,000,” the engine adds 4,000 in one step instead of comparing 4,000 values. A GROUP BY country can group on the small dictionary codes (1 byte) rather than the strings, and only decode to text for the final output. The operator never decompresses the bulk of the column — it computes on the compact form and decodes lazily, so compression saves CPU as well as I/O.

A vectorized scan -> filter -> project -> aggregate pipeline (one column batch of ~1,024 values flows through each operator) Parquet column chunks (compressed, with min/max stats) | v [ SCAN ] predicate pushdown: skip blocks whose min/max | can't match WHERE quarter='Q1' (no I/O for them) v [ FILTER ] vectorized: compare 1,024 'quarter' codes per call | output = surviving ROW-IDS only (late materialization) v [ PROJECT ] fetch 'revenue' + 'category' ONLY for surviving row-ids | (wide columns never read for filtered-out rows) v [ AGGREGATE ] hash on dictionary CODE for 'category' (1 byte), | SUM(revenue) per group; decode codes to text at the end v result rows (a few; the billion never left the scan loop)

5 · Failure modes, the checklist, and where truth lives

Failure modes

Stale statistics. The optimizer picks a bad join order or a hash join whose build side no longer fits memory and spills; a query that ran in seconds now runs in minutes. Refresh stats after big loads.
Exploding intermediate joins. A bad join order materializes a billion-row intermediate before the filter that would have cut it. Usually a statistics or missing-filter problem; check the plan's estimated vs actual row counts.
SELECT * defeats columnar. Projecting every column makes the scan read all columns of every row — the lesson-04 row-store cost, on a column store. Project only what you aggregate.
Materialized aggregate drift. A precomputed cube reflects yesterday's facts; a dashboard shows stale numbers while raw-fact queries show fresh ones. The cube is a derived view (lesson 20) and needs a refresh path and a freshness budget.
Tiny queries pay compilation tax. Codegen latency dominates a query that touches a few rows; compile only heavy stages, or fall back to a vectorized interpreter for small inputs.
OLTP query on the warehouse. A point lookup of one row scans column chunks and reconstructs a row — slow. Point reads belong on the OLTP source (lesson 04), not the analytical copy.

Decision checklist

Is the model a star schema — one denormalized fact table, dimensions around it? Snowflake only the large/shared dimensions.
Are the hot dashboard rollups served by materialized aggregates / a cube, with a defined freshness budget?
Are table statistics refreshed after each major load so the optimizer's join-order estimates are sound?
Is the engine vectorized (column batches) — and does the plan use predicate pushdown and late materialization (read the EXPLAIN)?
Does the query project only the columns it needs, never SELECT *?
Is the warehouse explicitly a derived view, with a rebuild path from the source/lake and reconciliation against it?

Where is truth?

System of record: the OLTP source databases and the raw event log / data lake — the authoritative facts. Copies / derived views: the warehouse itself (fact + dimension tables) and every cube / materialized aggregate are derived — columnar copies rebuilt by batch/ETL jobs (lesson 18), never written to directly by users. Freshness budget: ETL lag — how far behind the source the warehouse is allowed to fall (e.g. hourly micro-batches ⇒ up to ~1 h stale); cubes add their own refresh lag on top. Owner: the data/analytics-engineering team that owns the ETL pipeline and the schema. Deletion path: a user deletion (lesson 25) must propagate from the source through the next ETL run into the warehouse and every cube — deletion is not done until the derived copies drop it too. Reconciliation / repair: rerun the batch job to rebuild a table or partition from the source — the whole point of “derived” (lesson 20). Evidence it is correct: row-count and aggregate reconciliation — sum a measure in the warehouse and compare to the same sum computed from the source/lake; a mismatch beyond the freshness window is a pipeline bug, not stale data. Storage for the underlying files is itself a subsystem (lesson 24).

Checkpoint exercise

Try it

You run a recommender's analytics warehouse. The query is “click-through rate by ad category for last week” over a 2-billion-row fact_impressions table (80 columns) joined to a small dim_ad table. (1) Sketch the star schema and the logical plan. (2) The query touches 4 columns; estimate the bytes scanned versus a row store, and explain where predicate pushdown and late materialization help. (3) The query suddenly slows 20× one morning with no code change — give the two most likely causes and how you would confirm each from the query plan. (4) State which store is the source of truth and how you would prove the warehouse's CTR number is correct.

Where this points next

We can now explain why scanning a billion structured rows feels instant: a scan-friendly star schema, a columnar layout, an optimizer that orders the joins, and operators that crunch compressed column batches in compiled, vectorized loops. But a warehouse answers “sum revenue where category = electronics” — exact, structured predicates. It cannot answer “find documents about wireless earbuds” or “find the 10 product embeddings nearest this query vector.” Those need a different derived view with a different index. Lesson 22 builds it: search and vector indexes — inverted indexes for full-text, approximate-nearest-neighbor structures for embeddings, and how they power retrieval-augmented generation (RAG). Same “derived view rebuilt from the source” discipline, a fundamentally different access pattern.

Takeaway

A data warehouse is the biggest derived view a company runs — a columnar copy of its facts, rebuilt by batch ETL from the source of truth (lesson 18, 20). It is modeled as a star schema (one denormalized fact table of measures + dimension tables; the snowflake variant normalizes dimensions back into joins), often with data cubes / materialized aggregates that trade storage and flexibility for instant rollups. A query runs SQL → parse → logical plan → cost-based optimizer (which uses table statistics to pick join order and join algorithm) → physical plan. It feels fast because of the execution engine on top of lesson 04's columnar layout: vectorized execution processes ~1,024-value column batches per operator call (amortizing dispatch overhead for a ~16× win over the row-at-a-time Volcano model), query compilation removes interpreter overhead, and predicate pushdown, late materialization, and compression-aware operators ensure the engine reads and decodes only the bytes that survive the filter. Its correctness is provable by reconciling aggregates against the source.

Interview prompts

Contrast star and snowflake schemas; when do you snowflake a dimension? (§1 — star: one denormalized fact table of measures + foreign keys, dimensions radiating off; snowflake normalizes dimensions into sub-dimensions, saving storage but adding joins to the read path; keep the fact denormalized, snowflake only large/shared dimensions.)
What is a data cube / materialized aggregate, and what does it trade? (§1 — precomputed rollups across dimension combinations so a rollup is a lookup not a scan; trades storage and drill-down flexibility for instant queries on the precomputed grouping.)
Walk a SQL query through the execution pipeline; what does the optimizer decide? (§2 — parse → logical plan (what) → cost-based optimizer → physical plan (how); optimizer chooses join order and join algorithm (hash/sort-merge/nested-loop) using table statistics.)
Why is vectorized execution faster than row-at-a-time, and roughly how much? (§3 — Volcano makes one next() call + branch per row, so per-row overhead dominates the work; vectorized processes ~1,024-value column batches, amortizing dispatch once per batch and enabling SIMD — about a 16× win in the worked example, e.g. 5 s → 0.3 s over a billion rows.)
What does query compilation buy, and when is it a bad idea? (§4 — codegen specializes the plan to this query as machine code, removing interpreter/type-dispatch overhead; the compilation latency is wasted on tiny queries, so compile only heavy stages.)
Explain predicate pushdown and late materialization. (§4 — pushdown evaluates filters at/inside the scan using per-block min/max stats to skip blocks with no I/O; late materialization carries surviving row-ids and fetches wide columns only for rows that passed the filter, so a 1%-selective filter reads ~1% of the wide column.)
A warehouse query slows 20× overnight with no code change — diagnose. (§2, §5 — most likely stale statistics after a big load causing a bad join order or a hash join that now spills; confirm by comparing the plan's estimated vs actual row counts and re-running ANALYZE.)
Is the warehouse a source of truth? How do you prove its numbers are right? (§5 — no; it is a derived view rebuilt by ETL from the OLTP source/lake, with freshness = ETL lag; prove correctness by reconciling row counts and aggregate sums against the source, and repair by rerunning the batch job.)