第 8 章 交互式分析（Interactive Analytics）

原文：Readings in Database Systems, Fifth Edition (2015)，Chapter 8: Interactive Analytics，Introduced by Joe Hellerstein。原书文本采用 CC BY-NC-SA 4.0 许可；本译文按同一许可发布。

导读：Joe Hellerstein

选读论文

• Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman. “Implementing Data Cubes Efficiently.” SIGMOD, 1996.
• Yihong Zhao, Prasad M. Deshpande, Jeffrey F. Naughton. “An Array-Based Algorithm for Simultaneous Multidimensional Aggregates.” SIGMOD, 1997.
• Joseph M. Hellerstein, Ron Avnur, Vijayshankar Raman. “Informix under CONTROL: Online Query Processing.” Data Mining and Knowledge Discovery, 4(4), 2000, 281-314.
• Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, Ion Stoica. “BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data.” EuroSys, 2013.

几十年来，大多数数据库工作负载被划分为两类：第一，许多小型“事务处理”查询，它们在大型数据库中的少量项上进行查找和更新；第二，数量较少的大型“分析”查询，它们汇总大量数据以进行分析。本节关注的是加速第二类查询的思想，尤其是让它们能够以交互速度回答，并支持数据的汇总、探索和可视化。

多年来，业界围绕后一类工作负载进行了大量 buzzword bingo，从 “Decision Support Systems”（DSS）到 “Online Analytic Processing”（OLAP），再到 “Business Intelligence”（BI）、“Dashboards”，以及更一般的 “Analytics”。随着时间推移，这些标签关联了数十亿美元收入，因此营销人员和行业分析师多年来努力定义、区分，有时也试图重新塑造它们。到现在，术语已经有点混乱。有兴趣的读者可以查看 Wikipedia，并评估关于这些 buzzword 后来含义及其差异的传统看法；但要提醒你，这不会是一次在科学上令人满足的练习。

在这里，我会尽量保持简单，并且稍微立足于技术。

人类认知无法处理大量原始数据。为了让人理解数据，必须以某种方式把数据“蒸馏”为相对较小的一组记录或视觉标记。通常，这通过对数据分区，并在分区上运行简单的算术聚合函数来完成；可以把 SQL 的 “GROUP BY” 功能看作一个经典模式。随后，数据通常需要被可视化，让用户把它与手头任务联系起来。

本章讨论的主要挑战，是让大规模分组/聚合查询以交互速度运行，即使在无法遍历与查询相关的所有数据时也是如此。

如何让查询在少于查看数据所需的时间内运行？真正只有一个答案：我们在不查看全部数据的情况下回答查询。这个思想产生两个变体：

预计算：如果我们提前知道一些查询工作负载信息，就可以用多种方式蒸馏数据，使我们能够快速回答某些查询，无论答案是准确的还是近似的。这个思想最简单的版本，是预先计算一组查询的答案，并且只支持这些查询。下面我们会讨论更复杂的答案。

采样：如果我们无法很好地提前预测查询，那么查询时唯一选择就是查看数据的一个子集。这相当于从数据中采样，并基于样本近似真实答案。

本节论文关注这两种方法中的一种或两种。

我们的前两篇论文讨论数据库社区称为 “data cubes” 的内容 [DataCubes]。数据立方体最初由被称为 On Line Analytic Processing（OLAP）系统的独立查询/可视化工具支持。这个名称来自关系模型先驱 Ted Codd；他曾被聘为顾问，推广一个名为 Essbase 的早期 OLAP 厂商，该公司后来被 Oracle 收购。这并不是 Codd 更具学术色彩的工作之一。

早期 OLAP 工具使用纯“预计算”方法。它们摄取一张表，并计算和存储该表上一族 GROUP BY 查询的答案：每个查询基于不同的列子集分组，并在未分组的数值列上计算汇总聚合。例如，在一张汽车销售表中，它可能展示按 Make 的总销售额、按 Model 的总销售额、按 Region 的总销售额，以及这些属性中任意 2 个或 3 个组合下的总销售额。图形用户界面允许用户交互式浏览由 group-by 查询形成的结果空间；这个查询空间后来被称为 data cube。最初，OLAP 系统被宣传为独立的“多维数据库”，与关系数据库有根本不同。不过，Jim Gray 和关系数据库行业的一组作者解释了数据立方体概念如何适配到关系语境中 [68]，随后这个概念以单一查询构造 “CUBE BY” 的形式进入 SQL 标准。还有一个名为 MDX 的 SQL 标准替代语言，对 OLAP 用途来说更简洁。来自数据立方体的一些术语已经成为通用说法，尤其是“drilling down” 到细节，以及 “rolling up” 到更粗粒度汇总。

对完整数据立方体进行预计算的天真关系预计算方法扩展性很差。对于有 k 个潜在分组列的表，这种方法必须运行并存储 2^k 个 GROUP BY 查询的结果，也就是每个列子集一个查询。每个查询都需要完整扫描表。

我们的第一篇论文由 Harinarayan、Rajaraman 和 Ullman 撰写，它缩小了这个空间：选择立方体中一个明智的查询子集进行预计算，然后使用这些查询的结果计算立方体中任何其他查询的结果。这篇论文是该领域引用最多的论文之一，部分原因是它很早就观察到数据立方体问题的结构是一个集合包含格。这个格结构支撑了他们的解决方案，并反复出现在许多其他关于数据立方体的论文中，包括我们的下一篇论文，也出现在某些数据挖掘算法中，例如 Association Rules，也称 Frequent Itemsets [7]。每个在 OLAP 领域工作的人都应该读过这篇论文。

我们的第二篇论文由 Zhao、Deshpande 和 Naughton 撰写，关注立方体结果的实际计算。论文使用“基于数组”的方法：也就是说，它假设数据存储在类似 Essbase 的稀疏数组结构中，而不是关系表结构中，并提出了一种利用该结构的非常快速的算法。不过，它提出了一个令人惊讶的观察：即使对于关系表，也值得把表转换成数组来运行这个算法，而不是运行一种效率低得多的传统关系算法。这显著扩大了查询引擎的设计空间。其含义是，你可以把数据模型与查询引擎的内部模型解耦。因此，一个专用“引擎”（在这里是 Multidimensional OLAP）可以通过嵌入更通用的引擎（在这里是关系引擎）来增加价值。OLAP 战争几年后，Stonebraker 开始主张数据库引擎 “one size doesn't fit all”，因此专用数据库引擎（与 Essbase 并非完全不同）确实很重要 [149]。这篇论文展示了这种推理有时如何展开：聪明的专用技术被开发出来，如果足够好，也能在更通用的语境中获得回报。多年来，在这条线的两侧创新，也就是专用化与通用化，都产生了很好的研究结果。与此同时，任何构建查询引擎的人都应记住：数据和操作的内部表示可以是 API 表示的超集。

与这个问题相关的是，过去十年中，由于数据库内压缩和摩尔定律推进，分析数据库变得高效得多。Stonebraker 曾向我断言，列存储使 OLAP 加速器变得无关紧要。这是一个值得考虑的有趣论点，尽管尚未被市场验证。厂商仍然构建立方体引擎，BI 工具也通常把它们实现为关系数据库和 Hadoop 之上的加速器。当然，我们第一篇论文中的缓存技术仍然相关。但高性能分析数据库技术与数据立方体技术之间的实时查询处理权衡，也许值得重新审视。

我们的第三篇关于 “online aggregation” 的论文，从 OLAP 相反的一侧开始探索，试图在没有预计算的情况下快速处理 ad hoc 查询，方式是产生逐步精化的近似答案。这篇论文受到人们每天为了收集证据并做决策而执行的 triage 的启发；我们通常不会预先指定硬截止时间，而是会对何时停止评估并采取行动做定性决定。具体以数据为中心的例子包括选举报道中提供的“早期回报”，或者低带宽连接上的图像多分辨率交付；在这两种情况下，远在过程完成之前，我们就已经对可能发生什么有足够好的判断。

Online aggregation 通常利用采样来实现逐步精化的结果。这不是第一次，也不会是最后一次，使用数据库采样来提供近似查询答案。（Frank Olken 的论文 [122] 是数据库采样的一个很好的早期必读参考。）但 online aggregation 推动了一系列持续至今的近似查询处理工作，在当前大数据和 structure-on-use 时代尤其有趣。

我们在这里收录第一篇关于 online aggregation 的论文。要欣赏这篇论文，重要的是记住，当时数据库长期运行在一种“正确性”神话之下，而在今天的研究环境中，这种神话有点难以体会。大约直到 21 世纪之前，普通大众和商业社区都把计算机视为准确、确定性计算的引擎。“Garbage In, Garbage Out” 这样的短语被发明出来，用来提醒用户把“正确”数据放入计算机，这样计算机就可以完成自己的工作并产生“正确”输出。一般来说，人们并不期望计算机产生“粗糙”的近似结果。

因此，这篇论文打的第一场战斗，就是大型分析查询中的完全准确性并不重要，用户应该能够以灵活方式在准确性和运行时间之间取得平衡。这个思路很快引向三个需要协同工作的研究方向：快速查询处理、统计近似和用户界面设计。这三个主题之间的相互依赖，形成了一个有趣的设计空间，研究人员和产品至今仍在探索。

我们这里收录的初始论文探索了如何把这个功能嵌入传统 DBMS 中。它还为样本上的标准 SQL 聚合提供统计估计器，并展示如何通过 “index striding” 使用标准 B-tree 实现分层采样，使 GROUP BY 查询中的不同组能够以不同速率被采样。该领域后续论文探索了把 online aggregation 与查询处理中的许多其他标准问题集成起来，其中许多问题出乎意料地棘手：连接、并行性、子查询，以及最近的 MapReduce 和 Spark 等大数据系统细节。

IBM 和 Informix 在 20 世纪 90 年代末都追求过 online aggregation 的商业化努力，Microsoft 也有近似查询处理方面的研究议程。这些努力都没有进入市场。当时的一个原因，是一种顽固想法：“数据库客户不能容忍错误答案”。考虑到某些厂商提供的采样支持是有偏的（按块而不是按元组采样），这尤其讽刺。一个更有说服力的原因，与用户界面、查询引擎和近似之间的耦合有关。当时，许多 BI 厂商独立于数据库厂商。因此，数据库厂商总体上并不“拥有”终端用户体验，也无法通过标准 API 把 online aggregation 功能直接交付给用户。例如，传统查询游标 API 不允许同一查询有多个近似结果，也不支持与聚合列关联的置信区间。当时市场结构不支持跨后端和前端的激进新技术。

今天，许多这些因素已经改变，online aggregation 正在研究和工业界重新获得关注。第一个动机毫不意外，是对大数据的兴趣。大数据不仅体量大，而且格式和用途具有广泛“variety”，这意味着它可能直到用户想要分析时才会被解析和理解。对于大数据上的探索式分析，大体量和 schema-on-use 的组合使预计算缺乏吸引力，甚至不可能。但即时采样仍然便宜且有用。

此外，自 20 世纪 90 年代以来，行业结构及其接口也已经改变。自底向上看，今天查询引擎标准经常通过开源开发出现和演化，获胜项目，例如 Hadoop 和 Spark，会变得接近垄断，以至于它们的 API 能够支配客户端设计。与此同时，自顶向下看，云中的托管数据可视化产品通常是垂直集成的：前端体验是首要关注点，并由一种通常专用的后端实现驱动，而不关心标准化。在这两种情况下，都有可能把 online aggregation 这样的独特功能从引擎一路通过栈交付到应用。

在这个语境下，我们呈现该领域近期阅读较广的一篇论文：BlinkDB。该系统使用 Olken 称为“物化样本视图”的机制：在基表上预计算样本，并存储起来以加速近似查询回答。和早期 OLAP 论文一样，BlinkDB 论证了对于稳定工作负载，只需预计算少量 GROUP BY 子句，就能获得良好性能。早期 AQUA 近似查询项目的作者也提出了类似论点 [5]，但他们关注预计算概要（“sketches”），而不是把物化样本视图作为底层近似机制。BlinkDB 论文还主张在视图中进行分层，以捕获小组，这让人想起 online aggregation 论文中的 Index Striding。BlinkDB 在工业界获得了关注，Spark 团队最近提出用即时采样增强其预计算样本；这是对各种技术的合理混合，旨在尽可能高效地实现 online aggregation。ZoomData 等近期商业 BI 工具似乎也使用 online aggregation（他们称之为 “query sharpening”）。

讨论了这么多 online aggregation，值得给当前市场现实拍一张快照。自 OLAP 风格预计算被广泛引入以来的 25 年里，它已经支撑起如今价值数十亿美元的 BI 行业。相比之下，用户界面中的近似几乎不存在。因此，对那些在家按收入生成来记分的人来说，预计算这个简单解决方案目前遥遥领先。近似是否以及何时会在实践中成为日常技术，仍然是开放问题。在技术层面，采样的根本好处看起来必然有用，而围绕数据增长和探索式分析的技术趋势，使它在大数据市场中很有吸引力。但今天，这仍然是一项超前于时代的技术。

最后做一个算法层面的说明：通过 sketches 实现的近似查询，事实上今天已经被工程师和数据科学家作为分析构建块广泛使用。在这里讨论的系统工作之外，优秀的数据库学生应该熟悉 CountMin sketches、HyperLogLog sketches、Bloom filters 等技术。文献 [44] 中有该领域的综合综述；各种 sketches 的实现可以在网上许多语言中找到，包括作为第 11 章提到的 MADlib 库中的用户定义函数。