Dremel: Interactive Analysis of Web-Scale Datasets
📜 Abstract
Dremel is a scalable, interactive ad-hoc query system for analysis of read-only nested data. By combining multi-level execution trees and columnar data layout, it is capable of running aggregation queries over trillion-row tables in seconds. The system scales to thousands of CPUs and petabytes of data, and has thousands of users at Google. In this paper, we describe the architecture and implementation of Dremel, and explain how it complements MapReduce-based computing. We present a novel columnar storage representation for nested records and discuss experiments on few-thousand node instances of the system.
✨ Summary
Summary
Dremel presents a distributed system for interactive, ad-hoc analysis of very large, read-only datasets containing nested records. Its design combines three central ideas: column-oriented storage for selective reading and compression, a multi-level serving tree for parallel query execution and aggregation, and a SQL-like language that operates directly on nested data without first normalizing it or translating queries into MapReduce jobs. The system is intended to complement MapReduce: batch pipelines can produce datasets, while Dremel supports rapid exploration, debugging, and aggregation over their outputs. (static.googleusercontent.com)
The paper’s principal storage contribution is a lossless representation of nested records using repetition levels and definition levels. Repetition levels identify the repeated ancestor at which a value occurs, while definition levels encode the presence or absence of optional and repeated ancestors. These levels allow nested records to be split into independent column stripes and later reconstructed, including when only a subset of fields is retrieved. The paper also describes algorithms for column generation, record assembly through finite-state machines, and direct select-project-aggregate evaluation that avoids record materialization during query execution. (static.googleusercontent.com)
The execution architecture distributes table partitions across leaf servers and performs partial aggregation at intermediate levels before combining results at a root server. A dispatcher schedules work, redistributes slow tablets, and uses replicated data to tolerate failures. Experiments on datasets ranging from billions to more than a trillion records report interactive execution times, near-linear scaling across thousands of servers for suitable scan-based workloads, and substantial advantages from reading only the required columns. The results also identify record assembly, parsing, and stragglers as important performance costs. (static.googleusercontent.com)
The paper had concrete influence on subsequent analytical storage systems. Apache Parquet explicitly uses the Dremel encoding with definition and repetition levels for nested columns, and Apache Arrow documentation identifies the Dremel paper as the detailed description of the relevant reconstruction algorithm. (parquet.apache.org) Google later described Dremel’s architectural principles—including in-situ analysis, columnar storage for semistructured data, and separation of storage and computation—as foundations for the evolution of Google BigQuery. (research.google)