CMSC724: Dremel and Nested Columnar Storage

Instructor: Amol Deshpande

This chapter follows “Dremel: Interactive Analysis of Web-Scale Datasets” (Melnik et al., VLDB 2010) and its ten-year retrospective, “Dremel: A Decade of Interactive SQL Analysis at Web Scale” (VLDB 2020), written for the paper’s test-of-time award.

Dremel does several things — in-situ processing, a distributed serving tree — but the part that mattered, and the part we focus on, is the nested columnar storage format. It led directly to Parquet, which is the most common storage format in data lakes and warehouses today.

Passages marked as editorial extensions were written by the notes generator and go beyond the source slides and class discussion.

1. The Problem

Dremel is about fourteen years old, and its motivation was specific.

MapReduce is good for analyzing large volumes of data — image data and the like — but it does badly at small queries. If you just want a count of a few things, batch analysis is the wrong tool.

Meanwhile, much of Google’s data was hierarchical and nested — JSON-like, though the term was not yet common — and sparse. But, critically:

The data does have a schema. The entire format is built on using that schema to encode the data.

So the target was interactive, aggregate-style queries over enormous volumes of nested, sparse, schema-bearing data.

Why not just store the documents?

MongoDB stores JSON. PostgreSQL stores JSON. But in both cases the document is stored as a single blob — one binary or text object per document. That is fine for retrieving documents, and useless for analytics: to compute an aggregate over one field you must read and parse every document in full.

For analytics you want columnar storage. The question is how to make a columnar layout work when the data is nested.

2. The Schema: Protocol Buffers

Dremel uses protocol buffers, another Google technology, as its schema format. Think of it as schema-bearing JSON. Each field is one of:

required — must be present exactly once.
optional — may be absent.
repeated — a list, with any number of entries.

Fields can be grouped into nested structures, and groups themselves can be repeated, so you can represent lists, dictionaries, and lists of dictionaries.

The running example is a Document:

DocId is required.
Links is an optional group, containing Backward and Forward, both repeated.
Name is a repeated group, containing a repeated Language group (with Code required and Country optional) and an optional Url.

So a document may have three names, one of which has two languages, one of which has a country. The ordering is fixed by the schema: Backward always precedes Forward, and within a language Code precedes Country. That means the schema carries the ordering information, so the data does not have to.

Why does a message format have a schema at all? Because the schema is not sent with the message. Google’s messaging system uses the schema to optimize reading: you transmit only the data, and the receiver uses its copy of the schema to reconstruct the document.

Avro works the same way, and Facebook had its own equivalent. All of them separate the schema from the data.

3. Columnizing Nested Data

Here is the exercise worth doing before reading the paper. Given those two example documents, how would you store them column-wise?

The obvious move is to make one column per leaf path:

Column	Values, in order
`DocId`	10, 20
`Links.Forward`	20, 40, 60, 80
`Links.Backward`	10, 30
`Name.Language.Code`	en-us, en, en-gb

…and similarly for Name.Language.Country and Name.Url.

That is the easy half. The hard half is:

How do you get from the columns back to the documents? Reconstructing the nested structure is exactly what Dremel and the formats after it provide.

How are variable-length values handled? These are typically strings, so you would either null-separate them or store a length prefix before each. You might also dictionary-encode them to compress. Nothing exotic is required.

Repetition levels

Start with the easier case: Links.Forward holds 20, 40, 60, 80. Which belong to document 10 and which to document 20?

The answer is to store, alongside each value, a number that says where a new record starts. A 0 means “this begins a new document”; a 1 means “this repeats within the current one.”

So Forward gets 0, 1, 1, 0 — read a 0, then all following 1s belong to that document; the next 0 starts the next document. That is essentially all there is to it for a single level of repetition.

Nulls

Links.Backward is harder, because document 10 has no backward links at all. The 0/1 scheme cannot express absence — there is no value to attach a level to.

So you need a NULL. But storing nulls explicitly is expensive:

If values are 64-bit and the column is an array, every null consumes a full 64-bit slot. With many nulls — and this data is sparse — that is a great deal of wasted space.

One option is a separate bitmap marking which positions are null: one bit instead of 64. As we will see, Dremel ends up not needing a separate bitmap, because the definition levels it needs anyway already carry the information.

Could you use a Bloom filter instead of a bitmap? Bloom filters are a good idea nearly anywhere you can use them — but you must handle false positives. Here that means you might be told a value exists when it does not, which for reconstruction is not acceptable without a verification step.

Definition levels

Now the genuinely hard case: Name.Language.Code.

Repetition levels tell you where a new document begins. But Code sits inside Language, which sits inside Name, and both are repeated. Given two consecutive codes, you cannot tell whether they are:

two languages inside the same name, or
two names, each with one language.

Repetition levels alone do not distinguish these, because the repetition happened at different depths. So Dremel stores a second number — the definition level — recording at what level in the schema the repetition or the definition stops. A repetition level of 2, for instance, says the repetition is happening at depth 2, which tells you the two languages are siblings inside one name rather than in two different names.

You need both the repetition level and the definition level to fully disambiguate the nested structure.

Definition levels are primarily there to handle nulls and absent nesting: a definition level below the depth of the field means the value is absent, and where it went absent tells you which enclosing group was missing. That is why a separate null bitmap is unnecessary — you need the definition level regardless.

Important

The paper never gives a proof that this works. They never present a formal argument that repetition and definition levels always suffice to reconstruct the original document. At this point it is safe to assume they do — the format has been in production for fifteen years — but it is worth noticing the gap.

If you want the mechanics in more detail than the paper provides, there is a very good blog post by the Parquet authors (then at Twitter), who took the Dremel paper and reimplemented it as Parquet. They explain this considerably better than the original does.

An alternative: offsets. Instead of repetition levels, you can store offsets — “the first three values belong to document 10, the next one to document 20.” The goal is the same: mark where one record ends and the next begins.

Offsets are better if you want to extract a specific record quickly, since you can jump directly rather than scanning. ORC and Arrow use this approach. It is close to indexing, though people just call it offsets.

Doesn’t finding one record require a linear scan? Yes — and that is fundamental to columnar storage, not specific to Dremel. Reading a specific tuple is expensive in any column store, and here it is worse, because you do not know where the 0s are without scanning.

You could keep a map of where each record begins, and that would help, though it gets messy for deeply nested fields. But point queries are not the use case Parquet is designed for. If that is your goal, you should not be using Parquet.

4. Record Reconstruction

Dremel’s reconstruction mechanism is genuinely elegant. They build a finite state automaton that reads all the column files simultaneously and emits documents one at a time.

Walk through it. Imagine all six column files open at once, and you jump between them according to the automaton’s state:

Start at DocId, read 10, and read its repetition level 0.
On that 0, jump to Links.Backward. Loop there until you see a 0. Here you read a null, then a 0 — so backward links are absent. Note that you have reconstructed the fact of absence, which is itself information.
On the 0, jump to Links.Forward. Here the automaton loops on 1: read values while the repetition level is 1, stopping at the next 0. So you read 20, 40, 60.
Jump to Name.Language.Code, then Name.Language.Country, and so on, following the schema order.

The automaton captures, based on the repetition levels it observes, exactly how to move among the six column files to rebuild one document. Then it does the next.

This is not easily parallelizable — you are stepping through files in a data-dependent order — so presumably later work addressed that.

The payoff: partial reconstruction

Here is the property that makes the whole design worthwhile:

You can build an automaton that reads only the columns you need, and it will reconstruct partial documents containing just those fields.

If you only care about DocId and Country, you open only those two files. You get documents that are missing every other field — which is fine, because your query never asked for them.

That is the entire point of columnar storage carried into the nested case: read the minimum number of columns required. Dremel’s contribution is showing that nesting does not cost you this.

And if your target is an in-memory format rather than a JSON document, the same automaton can be modified to emit that directly — which is what the Arrow developers have done.

The design here is worth naming as a general technique, because it recurs whenever structure has to survive a lossy-looking decomposition.

Columnizing nested data destroys two things: which record a value belongs to, and where in the nesting it sat. Dremel’s answer is not to keep the structure alongside the data, which is what storing the documents would amount to, but to keep the minimum number of integers from which the structure can be recomputed, given that the schema is already known to both writer and reader.

That last clause is what makes it cheap. The schema supplies field order, nesting shape, and which fields can repeat; the per-value levels supply only what the schema cannot determine — where records break and how deep each value actually sat. Splitting the structural information into a static part shared once and a dynamic part stored per value is why two small integers suffice where a naive encoding would need explicit delimiters at every level.

The cost is that reconstruction becomes a computation rather than a read, which is exactly why the automaton exists and why it does not parallelize easily.

5. Query Execution

Dremel’s execution model is deliberately limited: only one-pass aggregation queries — no joins.

Aggregations parallelize easily. A large table is stored as many tablets — horizontal partitions — across a distributed file system, and a query is split across them. You push the aggregation down, compute partial aggregates per tablet, and combine. For a sum, sum each tablet and add. For an average, compute sum and count per tablet, bring those to one place, and divide at the end.

There is nothing deep here. What was impressive was the scale:

They could execute queries interactively — write a query, get an answer in real time — on datasets with a trillion records. MapReduce could do batch analysis at that scale; interactive was the challenge Dremel was answering.

6. The Ten-Year Retrospective

Dremel was published in 2010 as an industrial paper and won the test-of-time award at SIGMOD 2020, for which the authors wrote a retrospective.

Retrospective papers are always worth reading. They give you the authors’ view of what actually happened and what the impact was — but more valuably, they discuss what they got wrong. Ordinary research papers do not do this, even when the authors know; in a retrospective they feel freer, and they have ten more years of perspective.

The format landscape

Parquet is essentially Dremel, open-sourced. To a first approximation they are the same.
ORC made slightly different choices: it uses the offset approach discussed above, and stores explicit presence bits rather than relying on implicit information in the repetition and definition levels.
Arrow is a different animal — see below.

Note that a Parquet file stores data in blocks: documents are split into large chunks, and the whole encoding is applied per chunk rather than to the entire column at once. That helps a little with updates, but only a little.

Important

Parquet is fundamentally not an updatable format. To change anything you read the whole thing and write it back.

Two reasons. First, the data is heavily compressed — with something like gzip — and those are not updatable encodings; you must decompress, modify, and recompress. Second, the repetition and definition levels are hard to update: adding a new name group requires recomputing levels for a range of values, and you may have to decompress other data to work out what the correct levels are.

You could do it. It gets messy, and the use cases for Parquet do not involve updates.

Arrow, and the conversion pattern

Apache Arrow is a language-independent in-memory columnar format, written in Rust and designed for operation by vectorized engines. The key distinction:

	Parquet	Arrow
Location	On disk	In memory
Designed for	Maximum space efficiency	Vectorized execution
Compression	Yes	No — it must be directly operable

Because they serve different purposes, systems convert between them constantly, and this has become a standard pattern:

Read Parquet → convert to Arrow → process in Arrow → write back as Parquet.

DuckDB does this, DataFusion does this, Spark does something equivalent with its own internal representation.

Apache DataFusion is a query engine built around Arrow: point it at Parquet files, write SQL, and it reads them, converts to Arrow, executes vectorized, and can write results back as Parquet. It has become quite popular. There is an effort to use DataFusion to speed up Spark’s per-worker execution — Spark’s internal format is row-oriented — showing factors of three or four. That may not sound dramatic, but taking cloud costs from a million to half a million is not an insignificant saving.

Why is Parquet easy to adopt and Arrow hard? Because supporting Parquet only means supporting reading it — that is work at the edge of your system: read the file, convert to your internal format, done. PostgreSQL could do that.

Using Arrow means rewriting your execution engine to operate on Arrow’s layout. That is not something PostgreSQL is going to take on. (There is an accelerator effort using DataFusion alongside PostgreSQL for analytics — but that is a separate engine, not PostgreSQL adopting Arrow.)

Disaggregation

The retrospective’s other major theme, and a genuine buzzword in the industry over the past decade.

Disaggregation means taking a monolithic system and breaking it into independent pieces. Dremel separated storage from compute, going further than MapReduce had, and the trend has continued: Calcite does only query optimization, Parquet does only storage, DataFusion does only query execution with no storage layer and no updates. Even Snowflake mostly reads from data lakes.

The advantages: the system becomes composable, and you can scale the pieces independently. If you have enormous data but few queries, you need little compute — whereas in a monolithic system, growing storage usually forces you to grow compute too.

The authors are also clear about the cost:

Once things are fully separated, optimization becomes much harder. Point DataFusion at Parquet files and you have no statistics to optimize with, because the files do not carry enough. Systems work around this by computing and storing statistics — at the price of the flexibility that made disaggregation attractive.

And the honest admission: Dremel did not support joins, realized it needed to, and never found a good solution. Joins require shuffling data, which the architecture did not do. As queries became more complex they shifted toward a more centralized approach — simple queries execute across machines, complex ones have to be centralized.