IT 论文精读 · PAPER 23
Melnik 等 · Google · VLDB 2010
2010 年，谷歌公开了内部一个叫 Dremel 的系统。它能让工程师对着一张上万亿行的巨表随手敲一句查询——「过去一小时哪些网页被点得最多？」——然后几秒钟就把答案端上来。这在当时几乎是魔法：同样的活，用之前的批处理工具（MapReduce）得跑上几分钟甚至几小时。今天谷歌云上人人可用的 BigQuery，底子就是它。
数据大了以后，「问一个问题」变得很慢。传统数据库是一行一行存的：一条记录的所有字段（网页地址、标题、点击数、时间……）挨在一起。可你想算的往往只是某一列（比如「所有网页的点击数之和」）。一行一行地存，就逼着机器把每条记录整条读进来、再从里面抠出那一个数——绝大部分读进来的东西都白读了，像为了看一本书里的页码，把每一页整页都翻一遍。
Dremel 反过来：把同一列的值全都集中放在一起。所有网页的「点击数」排成一长条、所有「标题」排成另一长条。这样算「点击数之和」时，机器只去读那一条、其它列碰都不碰——该读的一点不少，不该读的一点不碰。而且同一列的数长得像（都是数字、都是网址），挨在一起特别好压缩，读起来更快。
难点在于：谷歌的数据不是规规矩矩的表格，而是层层嵌套的——一个网页记录里套着「多个作者」，每个作者又套着「多种语言」，像一个俄罗斯套娃、又像一份带二级三级子目录的清单。这种「套娃数据」怎么拆成一条条平整的列、事后还能原样拼回去？Dremel 的办法是：给列里每个值额外记两个小标签，一个记「它属于第几层套娃」、一个记「它是新一组的开头、还是上一组的续」。靠这两个标签，散开的列随时能无损还原成原来的套娃结构。这套编码是它最硬核、也最被后人抄去的贡献。
光按列存还不够快。Dremel 借了搜索引擎的架子：一句查询进来，先到「根服务器」，它把活拆开、往下发给一批「中间服务器」，再往下发给成千上万台「叶子服务器」——每台只啃整份数据的一小片、各算各的局部答案（比如「我这片的点击数之和」）。然后局部答案顺着这棵树一层层往上汇总、合并，到根服务器就拼成最终结果。几千台机器同时开工，万亿行于是几秒扫完。
它让「查大数据」从「提交任务、去喝杯咖啡等结果」变成了「敲一句、看一眼、再改一句」的交互式探索。数据分析师第一次能像用小数据库那样，对着 PB 级的数据来回追问。它催生了 BigQuery，也把那套「嵌套数据的列式编码」变成了整个大数据界的通用格式（如今开源的 Parquet、ORC 都是这条路）。
诚实一句：Dremel 快，是因为它只擅长一件事——大规模「扫一遍、做统计」的只读分析；它不改数据、不做事务，早期也几乎不支持大表之间的复杂关联，不是用来替代普通数据库的。
把嵌套数据按列拆开存（配两个小标签保证能无损拼回）、再借搜索引擎的多级树把查询摊到几千台机器并层层汇总——于是万亿行也能几秒出结果，把「查大数据」变成了交互式探索。这就是 BigQuery 的地基。
想看列式编码的两个「层级」标签怎么工作、执行树长什么样、跑多快？ → 切到精读版
Dremel 把两样东西拼在一起——面向嵌套数据的列式存储（用「重复层级 + 定义层级」两个整数把套娃式记录无损打散成列、再无损拼回）与借自分布式搜索引擎的多级执行树（查询从根往下摊到成千上万台叶子服务器、局部结果层层向上汇总）——从而能对万亿行只读嵌套数据跑秒级的交互式聚合查询，扩展到数千 CPU、PB 级数据。它是谷歌 BigQuery 的前身，其嵌套列式编码后来成了 Parquet、ORC 等开源格式的思想源。
GROUP BY）等。分析场景的主力，也是 Dremel 优化的对象。作者是 Sergey Melnik、Andrey Gubarev 等谷歌工程师，论文发在 VLDB 2010，但系统 2006 年起就在谷歌内部生产运行、服务上千用户。它和 Percolator（增量索引）、Pregel（图计算）并称谷歌分布式系统的「新三驾马车」，都诞生在老三件套（GFS / MapReduce / Bigtable）之后、面向更专门的负载。往下，它 2012 年被产品化为公有云的 BigQuery；其嵌套列式编码被 Apache Parquet / ORC 继承，成为 Spark、Hadoop 生态的存储标准。谷歌 2020 年还发过一篇《Dremel: A Decade of Interactive SQL Analysis》回顾它十年的演进。
2000 年代后期，谷歌内部积累了海量只读的大数据：网页爬取结果、爬虫元数据、垃圾邮件分析、地图路况、应用崩溃日志……工程师需要随手探索这些数据——「哪类页面异常多？」「这个字段的分布长啥样？」这类问题往往边想边改、要反复试。
当时的主力工具是 MapReduce，但它是为批处理设计的：每个作业要调度、启动、把中间结果落盘，延迟以分钟乃至小时计。你问一句、等十分钟、发现问错了、再改再等——探索的节奏被彻底打断。人们要的是交互式：敲一句、几秒出结果、马上追下一句。
更麻烦的是数据形状。谷歌的数据大量以 Protocol Buffers 存储，是嵌套、带重复字段的树状记录，不是关系数据库那种规整的二维表。而传统列式存储（如更早的 C-Store）是给扁平的表设计的。怎么把嵌套记录也享受上列存的好处，是核心技术难题。
先说为什么要列存。分析查询通常只碰几百个字段里的几个。行存下，机器为了读那几个字段，得把整条记录都从磁盘捞上来，绝大部分 I/O 是浪费。列存把同一字段路径的所有值连续存成一条「列条（column stripe）」，查询只读它用得到的列——I/O 直接砍到「按需」；而且同一列数据同质，压缩率极高，读得更省。
难点是嵌套 + 重复。扁平表里「第 5 行的点击数」位置一目了然；可当 Author 能有多个、每个 Author 的 Lang 又能有多个时，把所有 code 值排成一条列后，你怎么知道某个 code 属于哪条记录的哪个作者？又怎么区分「这里本来就没有 Lang（空缺）」和「这里是新一组的开始」？Dremel 的答案是：给列里每个值配两个整数——
r=0 表示一条新记录的开始，r=1 表示同一记录里换了一个新 Author，r=2 表示同一 Author 里又多了一门 Lang。一句话：r 告诉你「新的一组从哪儿断开」。Author 但该作者没填 Lang，就用一个不带真实值、只带 d 的占位来记录「它在第几层就空了」。一句话：d 告诉你「空值（NULL）是在哪一层空的」。有了 (r, d)，散在各列里的值就能被一台有限状态机按顺序无损拼回原始的嵌套记录——不丢结构、不丢空缺信息。这套「repetition/definition level」编码是全文最硬核、也影响最深远的一招：它让列存第一次能优雅地吃下嵌套数据，后来被 Parquet 几乎原样继承。（论文还给出了只读部分列就能重组「记录子集」的高效算法，让查询按需组装。）
列存省了 I/O，但要在几秒内扫完万亿行，还得靠大规模并行。Dremel 直接搬来分布式搜索引擎的架构：一棵多级执行树（serving tree）。
一句 SQL 进来，先到根服务器（root）：它读表的元数据、把查询改写成可下发的子查询，往下丢给一层中间服务器（intermediate）；中间服务器继续改写、再往下丢，最终落到成千上万台叶子服务器（leaf）。叶子是唯一真正读数据的一层——每台只负责整表的一小片（一个 tablet），在自己那片列数据上做扫描与局部聚合（比如「我这片里 GROUP BY country 的计数」）。然后局部结果顺着树逐层向上合并：中间层把下面几十台的结果并成一份、根服务器再并成最终答案。
为什么这样快？因为像 COUNT、SUM、GROUP BY 这类聚合天然可分而合之：各片先算局部、上层再合并，通信量小、并行度极高。几千台叶子同时扫，万亿行于是被摊成每台几亿行、几秒钟的活。
Dremel 不搬数据：列数据就原地躺在共享存储（GFS）上，查询直接去那儿读，省掉了「先导入专用数据库」的漫长步骤——这叫 in-situ（原地）分析。代价是它只读、不为写优化。
几千台机器一起跑，总会有几台特别慢（straggler）拖后腿。Dremel 用一个查询调度器：每个 tablet 一般有多个副本，某台叶子迟迟不返回，就把这片活改派给另一副本。它还支持近似早停——比如已经处理了 99% 的分片、剩下 1% 迟迟不来，可以提前收工返回一个足够准的近似结果。对「看趋势、做探索」的分析，这种「用一点点精度换一大截延迟」通常非常划算。
论文用生产系统的真实负载说话：
Dremel 证明了一件当时很多人不信的事：不建索引、纯靠「列式 + 大规模并行暴力扫描」，也能对海量数据做到交互式查询。它把数据分析的工作方式从「提交批作业、等结果」改成了「敲一句、秒回、再追问」，让 PB 级探索性分析第一次变得顺手。
两条影响线尤其深远：一是它 2012 年被产品化为 BigQuery，开创了「Serverless 数据仓库」这一云产品品类，用户只管写 SQL、不管机器；二是它的嵌套列式编码被 Apache Parquet、ORC 继承，成为 Spark、Hadoop、乃至现代数据湖的事实存储标准——你今天在开源大数据栈里存的每个 Parquet 文件，血缘都能追到这篇论文的 (r, d) 编码。
① 一句话：列式存储（吃嵌套数据）+ 多级执行树（摊到几千台机器），对万亿行只读数据做秒级交互式聚合查询。
② 痛点：MapReduce 批处理延迟以分钟计，打断探索；且谷歌数据是嵌套 + 重复的树状记录，传统列存只会扁平表。
③ 核心一（编码）：用重复层级 r（新的一组从哪断开）+ 定义层级 d（NULL 在哪层空）两个整数，把嵌套记录无损打散成列、又能无损拼回——全文最硬核、被 Parquet 继承。
④ 核心二（执行）：借搜索引擎的多级树，根→中间→叶子逐层下发；叶子读分片做局部聚合、结果层层上汇合并；聚合天然「分而合之」，故并行度极高。
⑤ 工程点：in-situ 原地读 GFS，不搬数据；副本改派治 straggler；近似早停用精度换延迟。
⑥ 结果：85 亿行/87TB 表上列式快一个数量级以上；万亿行秒级返回；约三千节点、PB 级、上千用户；远快于 MapReduce。
⑦ 影响：产品化为 BigQuery，开创 Serverless 数据仓库；嵌套列式编码成 Parquet/ORC 的思想源，是现代数据湖存储标准。
⑧ 局限：只读聚合专才、不做事务；早期几乎不做大表 JOIN（后加 shuffle）；无索引故点查也得扫；编码工程门槛高。