Chapter 8: Interactive Analytics
Readings:
最近几十年大多数数据库 workload 已分为两类：
- 许多小的“事务执行”查询，他们在大型数据库中查找和更新很小的一部分数据
- 更少的大“分析”查询，汇总大量数据以供分析。
本节关注加速第二种查询——特别是以交互的速度回应查询，并允许对数据进行汇总、探索和可视化。
多年来，业界出现了大量的流行语，用来描述部分或全部的一种工作负载，从“决策支持系统”(DSS)到“在线分析处理”(OLAP)，从“商业智能”(BI)到“Dashboards”，更普遍的说法是“Analytics”。随着时间的推移，数十亿美元的收入与这些标签相关联，因此营销人员和行业分析师多年来努力定义、区分并有时试图颠覆它们。现在的命名有点混乱。
在这里，我将尽量使事情简单，并在一定程度上以技术为基础。
人类的认知不能处理大量的原始数据。为了让人类理解数据，数据必须以某种方式“提炼”成一组相对较小的记录或视觉标记(visual marks)。通常，这是通过对数据进行分区并在分区上运行简单的算术聚合函数来实现的，可以将SQL的“GROUP by”功能看作一个典型模式。随后，通常需要将数据可视化，以便用户将其与手头的任务关联起来。
我们在本章中解决的主要挑战是使大规模分组/聚合查询以交互速度运行——即使在无法迭代与查询相关的所有数据的情况下也是如此。
我们如何在比查看数据更短的时间内运行查询？实际上只有一个答案：我们在不查看（所有）数据的情况下回答查询。这个想法出现了两种变体：
预计算：如果我们事先知道一些关于查询的工作量，我们可以通过各种方式提炼数据，使我们能够支持对某些查询的快速回答（无论是准确的还是近似的）。这个想法的最简单版本是预先计算一组查询的答案，并且只支持这些查询。我们在下面讨论更复杂的答案。采样。如果我们不能提前预测查询，我们唯一的选择就是在查询时查看数据的一个子集。这相当于从数据中抽样，并根据抽样来近似计算出真正的答案。
本节的论文主要讨论这两种方法中的一种或两种。
我们的前两篇论文讨论了数据库领域所谓的“Data cubes”[DataCubes]。Data cubes 最初是由称为联机分析处理(OLAP)系统的独立查询/可视化工具支持的。这个名字是由关系型先驱Ted Codd命名的，他被聘为顾问来推广早期的OLAP供应商Essbase(最近被Oracle收购)。这并不是Codd一个更为学术的工作。
早期的OLAP工具使用了一种纯粹的 “预计算 “方法。他们获取一个表，并计算和存储对该表的一系列GROUP BY查询的响应：每个查询对不同的列的子集进行分组，并对未分组的数字列计算汇总的结果。例如，在一个汽车销售表中，它可以显示按品牌划分的总销售量、按型号划分的总销售量、按地区划分的总销售量，以及按这些属性中任何2或3的组合划分的总销售量。一个图形化的用户界面允许用户以交互方式浏览所产生的分组查询空间—这个查询空间就是所谓的数据立方体2。最初，OLAP系统被认为是独立的 “多维数据库”，与关系型数据库有着本质的区别。然而，Jim Gray和一个关系型行业的作者联盟解释了数据立方体的概念是如何适应关系型背景的[4]，随后这个概念作为一个单一的查询结构被迁移到SQL标准中。”CUBE BY”。还有一种SQL的标准替代方法叫MDX，对于OLAP的目的来说，MDX不那么冗长。一些来自于数据立方体的术语已经成为通用术语，特别是 “向下钻取 “到细节和 “向上滚动 “到更粗略的总结的想法。
用于预计算完整数据立方体的简单关系预计算方法伸缩性不好。对于具有k个可能的分组列的表，这种方法必须通过查询运行并存储2的k次方组的结果，每个查询对应一个列子集。每个查询都需要完整的表遍历。
Harinarayan，Rajaraman，Ull-man的第一篇论文缩减了这个空间:它在立方体中选择了一个值得预先计算的查询子集;然后，它使用这些查询的结果来计算多维数据集中任何其他查询的结果。这篇论文是该领域被引用最多的论文之一，部分原因是它很早就注意到数据立方体问题的结构是一个集包含格。这种点阵结构构成了它们的解的基础，并在其他许多关于数据集的论文(包括我们的下一篇论文)以及某些数据挖掘算法(如关联规则(又称频繁项集)[7])中进行了递归。在OLAP领域工作的每个人都应该阅读这篇论文。
我们的第二篇论文由Zhao、Deshpande和Naughton撰写，重点关注立方体中结果的实际计算。这篇论文使用了一种 “基于数组 “的方法：也就是说，它假设数据存储在类似Essbase的稀疏数组结构中，而不是关系表结构，并提出了一种利用这种结构的非常快速的算法。然而，它提出了一个令人惊讶的观点：即使是关系表，为了运行这个算法，把表转换成数组也是值得的，而不是运行一个（效率低得多的）传统关系算法。这大大拓宽了查询引擎的设计空间。其含义是，你可以将你的数据模型与你的查询引擎的内部模型解耦。因此，一个特殊用途的 “引擎”（这里指的是多维OLAP）可以通过嵌入一个更通用的引擎（这里指的是关系型）来增加价值。在OLAP战争的几年后，Stonebraker开始争论，对于数据库引擎来说，”一个尺寸并不适合所有”，因此，专门的数据库引擎（与Essbase不一样）确实很重要[6]。本文是一个例子，说明了这种推理方式有时是如何进行的：聪明的专门技术被开发出来，如果它们足够好，它们也可以在更普遍的情况下得到回报。多年来，在这条线的两边—专业化和通用化—上的创新导致了良好的研究结果。同时，任何建立查询引擎的人都应该牢记，数据和操作的内部表示可能是API表示的超集。
与这个问题相关的是，由于数据库内的压缩，以及摩尔定律的推进，分析型数据库在过去十年中变得更加高效。Stonebraker向我断言，列存储使OLAP加速器变得无关紧要。这是一个值得考虑的论点，尽管还没有得到市场的验证。供应商仍然在建立立方体引擎，BI工具通常将其作为关系数据库和Hadoop之上的加速器来实现。当然，我们第一篇论文中的缓存技术仍然适用。但是高性能分析数据库技术和数据立方技术之间的实时查询处理权衡可能值得重新审视。
我们关于“在线聚合”的第三篇论文从 OLAP 领域的另一端开始探索，试图通过逐步改进近似答案来快速处理临时查询而无需预先计算。这篇论文的灵感来自人们每天在收集证据以做出决定时进行的分类；与其预先指定硬性期限，我们通常会就何时停止评估和采取行动做出定性决定。具体的以数据为中心的例子包括选举报道中提供的“早期回报”，或通过低带宽连接的多分辨率图像传输——在这两种情况下，我们都对在流程完成之前很长时间可能发生的事情有足够的了解。
在线聚合通常利用抽样来实现渐进式的完善结果。这并不是第一次（或最后一次）使用数据库采样来提供近似的查询答案。(Frank Olken的论文[5]是早期数据库抽样的一个很好的必要参考。) 但是，在线聚合帮助拉开了近似查询处理工作的序幕，这种工作一直持续到现在，而且在当前的大数据和使用中的结构时代特别有意义。
我们在这里包含了第一篇关于在线聚合的论文。要欣赏这篇论文，重要的是要记住，当时的数据库长期以来一直在“正确性”的神话中运作，这在当今的研究环境中有点难以理解。直到大约 21 世纪，普通民众和商业界都将计算机视为准确、确定性计算的引擎。发明了诸如“垃圾进，垃圾出”之类的短语是为了提醒用户将“正确”的数据放入计算机，以便计算机完成其工作并产生“正确”的输出。一般来说，计算机不会产生“草率”的近似结果。
因此，本文中的第一场战斗是，大规模分析查询中的完全准确性并不重要，用户应该能够以灵活的方式平衡准确性和运行时间。这种思路很快导致了三个需要协调工作的研究方向：快速查询处理、统计近似和用户界面设计。这三个主题的相互依赖构成了一个有趣的设计空间，研究人员和产品今天仍在探索。
我们在此处包含的初始论文探讨了如何将此功能嵌入到传统 DBMS 中。它还为样本上的标准 SQL 聚合提供了统计估计器，并展示了如何通过“索引跨步”使用标准 B 树实现分层采样，从而使 GROUP BY 查询中的不同组能够以不同的速率进行采样。该领域的后续论文探讨了将在线聚合与查询处理中的许多其他标准问题集成在一起，其中许多问题非常棘手：连接、并行、子查询，以及最近的大数据系统（如 MapReduce 和 Spark）的细节。
在20世纪90年代末，IBM和Informix都在追求在线聚合的商业努力，微软也在近似查询处理方面有一个研究议程。这些努力都没有进入市场。当时的一个原因是 “数据库客户不会容忍错误的答案 “这一固步自封的想法3。一个更有说服力的原因是用户界面与查询引擎和近似处理的耦合问题。在那个时候，许多商业智能供应商是独立于数据库供应商的。因此，数据库厂商并不 “拥有 “一般的最终用户体验，也不能通过标准的API直接向用户提供在线聚合功能。例如，传统的查询游标API不允许同一查询的多个近似值，也不支持与聚合列相关的置信区间。当时的市场结构方式并不支持横跨后端和前端的积极的新技术。
今天，这些因素中的许多已经发生了变化，在线聚合在研究和工业中得到了新的关注。第一个动机，毫不奇怪，是对大数据的兴趣。大数据不仅数量大，而且格式和用途也很 “多样”，这意味着在用户想要分析之前，可能无法对其进行解析和理解。对于大数据的探索性分析来说，大量的数据和使用中的模式相结合，使得预先计算不具吸引力或不可能。但是，即时取样仍然是廉价和有用的。
此外，自20世纪90年代以来，工业界的结构及其接口已经发生了变化。从下往上看，今天的查询引擎标准往往是通过开源开发出现和发展的，获胜的项目（如Hadoop和Spark）接近于垄断，成为了事实标准，其API可以决定客户端的设计。同时，从上往下看，云中的托管数据可视化产品通常是垂直集成的: 前端体验是主要关注点，并由(通常是专用的)后端实现驱动，而不考虑标准化问题。在这两种情况下，都有可能通过从引擎到应用的堆栈提供像在线聚合这样的独特功能。
在这种背景下，我们在 BlinkDB 上发表了该领域最近被广泛阅读的论文之一。该系统利用 Olken 所说的“物化样本视图”：在基本表上预先计算的样本，存储起来以加速近似的查询回答。与早期的 OLAP 论文一样，BlinkDB 认为只需预先计算少数 GROUP BY 子句即可在（稳定）工作负载上获得良好性能。早期 AQUA 项目的作者就近似查询 [1] 提出了类似的论点，但他们专注于预先计算的概要（“草图”）而不是物化样本视图作为其潜在的近似机制。 BlinkDB 论文还在其观点中提出了分层以捕获小群体的理由，这让人想起在线聚合论文中的 Index Striding。 BlinkDB 引起了业界的兴趣，Spark 团队最近提议通过动态采样来增强其预先计算的样本——这是一种明智的混合技术，可以尽可能高效地实现在线聚合。最近的商业 BI 工具如 ZoomData 似乎也使用在线聚合（他们称之为“查询锐化”）。
通过对在线聚合的所有讨论，有必要了解一下当前的市场现状。在它被广泛引入后的 25 年里，OLAP 风格的预计算支撑了现在价值数十亿美元的 BI 行业。相比之下，用户界面上的近似实际上是不存在的。因此，对于那些根据创收在家里进行评分的人来说，预先计算的简单解决方案是当前的赢家。近似值何时以及是否会在实践中成为一种基本的技术仍然是一个悬而未决的问题。在技术层面，抽样的基本好处似乎不可避免地有用，围绕数据增长和探索性分析的技术趋势使其在大数据市场中引人注目。但今天，这仍然是一项超前的技术。
最后的算法说明：事实上，通过草图进行的近似查询如今已被该领域的工程师和数据科学家广泛用作分析的构建块。除了这里介绍的系统工作之外，阅读广泛的数据库学生应该熟悉CountMin草图、HyperLogLog草图、Bloom过滤器等技术。该领域的综合调查可以在[3]中找到；可以在许多在线语言中找到各种草图的实现，包括第 11 章中提到的 MADlib 库中的用户定义函数。
References:
[1] Acharya, S., Gibbons, P.B., Poosala, V. and Ramaswamy, S. The Aqua approximate query answering system. SIGMOD, 1999.
[2] Agrawal, R., Imieliński, T. and Swami, A. Mining association rules between sets of items in large databases. SIGMOD, 1993.
[3] Cormode, G., Garofalakis, M., Haas, P.J. and Jermaine, C. Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases. 4, 1-3 (2012), 1-294.
[4] Gray, J., Chaudhuri, S., Bosworth, A., Layman, A., Reichart, D., Venkatrao, M., Pellow, F. and Pirahesh, H. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data Mining and Knowledge Discovery. 1, 1 (1997), 29-53.
[5] Olken, F. Random sampling from databases. Ph.D. Thesis, University of California at Berkeley, 1993.
[6] Stonebraker, M. and Çetintemel, U. “One size fits all”: An idea whose time has come and gone. ICDE, 2005.
若有收获，就点个赞吧
0 人点赞
