CS PAPERS DEEP-READ · PAPER 23

Dremel: Interactive Queries over Trillions of Rows

Melnik et al. · Google · VLDB 2010

What did this paper do?

In 2010, Google described an internal system called Dremel. It let an engineer casually type a query against a table of trillions of rows — "which web pages got the most clicks in the last hour?" — and get the answer back in seconds. At the time that felt like magic: the same job on the earlier batch tool (MapReduce) took minutes or hours. Today's public BigQuery on Google Cloud is built on it.

First, the pain

Once data gets big, "asking a question" gets slow. Traditional databases store data row by row: all of one record's fields (URL, title, click count, time…) sit together. But the thing you want to compute is usually just one column (say "sum of clicks over all pages"). Storing row by row forces the machine to read every whole record off disk just to pick out that one number — most of what it reads is wasted, like flipping through every full page of a book just to check the page numbers.

Idea one: store by column, not by row

Dremel flips it: keep all values of one column together. Every page's "click count" in one long strip, every "title" in another. Now summing clicks means reading only that one strip and touching nothing else — you read exactly what you need. And since values in one column look alike (all numbers, all URLs), they compress beautifully when packed together, so reading is even faster.

The hard part: Google's data isn't a tidy table but is deeply nested — a page record holds "several authors," and each author holds "several languages," like a Russian doll, or a checklist with sub- and sub-sub-items. How do you shred such "nesting-doll data" into flat columns and still reassemble it exactly afterward? Dremel's trick: attach two little tags to each value in a column — one saying "which nesting level it belongs to," one saying "is it the start of a new group, or a continuation of the last." With those two tags, the scattered columns can be losslessly rebuilt into the original nested shape. This encoding is its most technical — and most widely copied — contribution.

Idea two: spread the query across thousands of machines

Columns alone aren't fast enough. Dremel borrows the shape of a search engine: a query arrives at a "root server," which splits the work and hands it down to a batch of "intermediate servers," which hand it further down to thousands of "leaf servers" — each chewing on a small slice of the whole dataset and computing its own local answer ("the click-sum for my slice"). Those partial answers then flow back up the tree, merging layer by layer, until the root assembles the final result. With thousands of machines working at once, trillions of rows get scanned in seconds.

What it gave us

It turned "querying big data" from "submit a job and go get a coffee" into "type a line, glance, tweak, repeat" — interactive exploration. For the first time, analysts could interrogate petabyte-scale data the way they'd use a small database. It became BigQuery, and its "columnar encoding for nested data" became the whole big-data world's standard (today's open-source Parquet and ORC walk the same path).

One honest note: Dremel is fast because it's good at one thing — large-scale, read-only "scan-and-aggregate" analysis. It doesn't update data, doesn't do transactions, and early on barely supported complex joins between big tables. It's not a replacement for an ordinary database.

Remember one thing

Shred nested data into columns (with two little tags that guarantee lossless reassembly), then borrow a search engine's multi-level tree to spread the query across thousands of machines and merge results back up — so even trillions of rows answer in seconds, turning big-data querying into interactive exploration. This is the foundation of BigQuery.

Want to see how the two "level" tags work, what the serving tree looks like, and how fast it runs? → switch to the deep read

In one sentence

Dremel combines two things — columnar storage for nested data (two integers, a "repetition level" and a "definition level," losslessly shred nesting-doll records into columns and reassemble them) and a multi-level serving tree borrowed from distributed search engines (a query fans down from a root to thousands of leaf servers, and partial results merge back up) — to run second-scale interactive aggregation queries over trillion-row, read-only nested data, scaling to thousands of CPUs and petabytes. It is the ancestor of Google BigQuery, and its nested columnar encoding is the intellectual source of open formats like Parquet and ORC.

Glossary

Row vs columnar storage: how a table is laid out on disk. Row storage keeps all of one record's fields together (good for "fetch a whole record"); columnar storage keeps all values of one field together (good for "compute a few columns," and it compresses well). Dremel is columnar.
Nested record: data where fields can contain sub-records and some fields can repeat multiple times, like JSON or Google's Protocol Buffers (a structured-data format). E.g. a "page" has several "authors," each author several "languages."
Aggregation query: a query that computes statistics — sum, count, average, group-and-count (GROUP BY). The workhorse of analytics, and what Dremel optimizes for.
OLAP vs OLTP: OLAP is "analytical" — big scans computing statistics, mostly read-only; OLTP is "transactional" — frequent reads/writes of single records with strong consistency. Dremel is OLAP; it does not do OLTP.
MapReduce: Google's earlier batch framework that abstracts large-scale parallelism into map + reduce; great for offline batch, but each job writes to disk and has startup overhead, so latency is in minutes — unsuited to interactive follow-up.
GFS (Google File System): Google's distributed file system, splitting data into chunks replicated across thousands of cheap machines. Dremel's column data lives on such shared storage.
Tablet / shard: a big table split horizontally into many pieces, each holding a range of rows, stored and read independently so many machines can work in parallel.
Straggler: the one unusually slow machine in a batch of parallel tasks; at a scale of thousands, some are always slow, and they drag out overall latency.

Where it sits

The authors are Sergey Melnik, Andrey Gubarev, and other Google engineers; the paper appeared at VLDB 2010, though the system had been in production inside Google since 2006, serving thousands of users. Alongside Percolator (incremental indexing) and Pregel (graph processing), it is one of Google's "second-generation" distributed systems — built after the founding trio (GFS / MapReduce / Bigtable), aimed at more specialized workloads. Downstream, it was productized in 2012 as the public-cloud BigQuery; its nested columnar encoding was inherited by Apache Parquet / ORC and became a storage standard across the Spark and Hadoop ecosystems. Google published a 2020 retrospective, "Dremel: A Decade of Interactive SQL Analysis," on how it evolved.

The problem and the motivation

By the late 2000s Google had amassed huge amounts of read-only data: crawl results, crawler metadata, spam analysis, map traffic, application crash logs. Engineers needed to explore it on a whim — "which kind of page shows the most anomalies?", "what's the distribution of this field?" — questions you refine as you go and try over and over.

The main tool then was MapReduce, but it was built for batch: every job schedules, starts up, and writes intermediate results to disk, so latency runs to minutes or hours. Ask a question, wait ten minutes, realize you asked it wrong, edit, wait again — the rhythm of exploration is destroyed. People wanted interactive: type a line, get an answer in seconds, immediately ask the next.

Worse was the shape of the data. Much of Google's data is stored as Protocol Buffers — nested, repeated-field tree records, not the tidy 2-D tables of a relational database. Traditional columnar stores (like the earlier C-Store) were designed for flat tables. Letting nested records also enjoy columnar benefits was the core technical challenge.

The core idea

Idea 1: losslessly shred nested records into columns

First, why columnar. An analytical query typically touches a few of hundreds of fields. In row storage, to read those few fields the machine must haul each whole record off disk — most of the I/O is waste. Columnar storage keeps all values of one field path contiguous as a "column stripe," so a query reads only the columns it uses — I/O drops to "on demand"; and since one column's data is homogeneous, it compresses extremely well, cutting reads further.

Fig 1 · Record shredding: a nested record is split into column stripes, one per leaf field; repeated/optional columns carry two level tags (r, d) that let them be reassembled losslessly.

The hard part is nesting + repetition. In a flat table, "row 5's click count" has an obvious position; but when Author can occur many times and each Author's Lang can too, after you line up all code values into one column, how do you know which record's which author a given code belongs to? And how do you tell "there simply was no Lang here (missing)" from "this is the start of a new group"? Dremel's answer: give each value two integers —

Repetition level (r): at which repeated field along the path this value continues from the previous one. r=0 marks the start of a new record, r=1 a new Author within the same record, r=2 another Lang within the same Author. In short: r tells you where a new group breaks off.
Definition level (d): how many of the optional/repeated fields along the path are actually present. If a record has an Author but that author filled in no Lang, a placeholder carrying only d records "it went empty at this level." In short: d tells you at which level a NULL is null.

With (r, d), the values scattered across columns can be replayed by a finite state machine and losslessly reassembled into the original nested record — no structure lost, no missing-value information lost. This "repetition/definition level" encoding is the paper's most technical and most far-reaching move: it let columnar storage gracefully swallow nested data for the first time, and was inherited almost verbatim by Parquet. (The paper also gives an efficient algorithm to reassemble a subset of records by reading only some columns, so queries assemble only what they need.)

Fig 2 · Two level tags: each column value carries (r, d). Those two integers alone reassemble the shredded columns into the nested record — r marks group boundaries, d marks the depth of a NULL.

Idea 2: a multi-level serving tree spreads the query across thousands of machines

Columnar storage saves I/O, but scanning trillions of rows in seconds still needs massive parallelism. Dremel lifts the architecture straight from distributed search engines: a multi-level serving tree.

A SQL query arrives at the root server: it reads the table's metadata, rewrites the query into dispatchable sub-queries, and passes them down to a layer of intermediate servers; they rewrite further and pass down again, until the work lands on thousands of leaf servers. Leaves are the only layer that actually reads data — each owns a small slice of the table (a tablet), scans its own column data, and does a local aggregation (say "the GROUP BY country counts within my slice"). Partial results then merge back up the tree, layer by layer: an intermediate server folds dozens of children into one, and the root folds those into the final answer.

Why is this fast? Aggregations like COUNT, SUM, GROUP BY are naturally divide-and-combine: each slice computes locally, upper layers merge, communication is small, parallelism is enormous. Thousands of leaves scan at once, so trillions of rows become a few-hundred-million-row, few-second job per machine.

Fig 3 · Multi-level serving tree: the query fans from the root down to thousands of leaf servers, each scanning + locally aggregating its shard; results merge up the tree into the final answer.

Idea 3: in-situ analysis + taming stragglers

Dremel doesn't move data: column data sits in place on shared storage (GFS), and queries read it right there, skipping the long "load into a dedicated database first" step — this is in-situ analysis. The cost is that it's read-only and not tuned for writes.

With thousands of machines running together, some are always unusually slow (stragglers) and hold everyone back. Dremel uses a query dispatcher: each tablet usually has several replicas, so if one leaf is slow to return, that slice is reassigned to another replica. It also supports approximate early termination — e.g., once 99% of shards are processed and the last 1% is lagging, it can finish early and return a good-enough approximate result. For "spot the trend / explore" analysis, trading a sliver of accuracy for a large cut in latency is usually well worth it.

Key results

The paper argues with real production workloads:

Columnar saves I/O: on a table of 85 billion records, ~87 TB, querying only a few of its fields, columnar reads beat record-oriented reads by more than an order of magnitude — the fewer fields you touch, the bigger the win.
Seconds over trillions: thanks to the serving tree, aggregation queries over trillion-row-scale tables return in seconds; most production queries finish within seconds to a dozen seconds — genuinely interactive.
Scale: experiments ran on about three thousand nodes; the system scales to thousands of CPUs and petabytes of data and served thousands of users at Google.
Beats batch: for the same aggregation, Dremel is far faster than running MapReduce over the same columnar data — compressing "minute-scale batch" into "second-scale interactive."

Why it mattered

Dremel proved something many then doubted: with no indexes, purely on "columnar + massively parallel brute-force scanning," you can query enormous data interactively. It changed how analysis is done — from "submit a batch job, wait for results" to "type a line, get a second-scale answer, ask again" — making petabyte-scale exploratory analysis fluent for the first time.

Two influence lines run especially deep. First, it was productized in 2012 as BigQuery, launching the "serverless data warehouse" category of cloud products, where users just write SQL and never manage machines. Second, its nested columnar encoding was inherited by Apache Parquet and ORC, becoming the de facto storage standard across Spark, Hadoop, and modern data lakes — every Parquet file you store in the open-source stack today traces its lineage to this paper's (r, d) encoding.

Limitations and criticism

A specialist, not a generalist: Dremel is only good at read-only, scan-style aggregate analysis (OLAP); it does no transactions and can't update single records, so it can't replace an OLTP database. Use it for the wrong job and it's a disaster.
Early on, barely any big-table JOINs: the original serving tree is friendly to "divide-and-combine" aggregation but weak on complex queries that produce huge intermediate results (especially joins between large tables); early on it handled only limited "broadcast small table" joins. Later (see the 2020 retrospective) a shuffle (repartition) mechanism was added to fill this gap, at the cost of higher latency and complexity.
The ceiling of brute-force scanning: no indexes means even highly selective point lookups (fetching very few rows) pay a substantial scan cost; its strength is "touch many rows, compute few columns," not "pinpoint a handful of rows."
Complex encoding, high engineering bar: the repetition/definition-level encoding is elegant but hard to implement and debug; handling every nesting + null edge case correctly is famously error-prone.
Coupled storage/compute and the approximation trade-off: the early tree bound storage and compute fairly tightly and was rigidly shaped; approximate early termination lowers latency but returns incomplete results, unsuitable when exact answers are required. All of this was gradually re-architected over the following decade (storage/compute disaggregation, vectorized columnar evaluation, etc.).

The essentials

① In one line: columnar storage (that swallows nested data) + a multi-level serving tree (spread over thousands of machines) → second-scale interactive aggregation over trillion-row read-only data.

② The pain: MapReduce batch latency runs to minutes and breaks exploration; and Google's data is nested, repeated, tree-shaped, while traditional columnar stores only knew flat tables.

③ Core 1 (encoding): two integers — repetition level r (where a new group breaks) + definition level d (at which level a NULL is null) — shred nested records into columns losslessly and reassemble them; the paper's most technical move, inherited by Parquet.

④ Core 2 (execution): a search-engine-style multi-level tree, root→intermediate→leaf; leaves read shards and aggregate locally, results merge up; aggregation is naturally divide-and-combine, so parallelism is huge.

⑤ Engineering: in-situ reads on GFS, no data movement; replica reassignment tames stragglers; approximate early termination trades accuracy for latency.

⑥ Results: columnar >10× faster on an 85-billion-row / 87 TB table; trillion-row queries return in seconds; ~3000 nodes, petabytes, thousands of users; far faster than MapReduce.

⑦ Impact: productized as BigQuery, launching serverless data warehouses; nested columnar encoding is the source of Parquet/ORC, the modern data-lake storage standard.

⑧ Limits: read-only aggregation specialist, no transactions; barely any big-table JOINs early (shuffle added later); no indexes so even point lookups scan; high engineering bar for the encoding.