ACM通信
研究突出了
技术视角:关系查询优化:数据管理满足统计估计
关系型系统使得在一个数据库中查询大量数据成为可能声明风格通过语言，如SQL。查询被翻译成由关系操作组成的表达式，但不引用任何实现细节。支持这种声明式编程风格需要一个关键组件，那就是查询优化器。优化器将查询表达式作为输入，并确定如何最好地执行该查询。这相当于在复杂的搜索空间上进行组合优化:在与给定查询表达式等价的所有计划中找到一个低成本的执行计划(考虑操作符的可能顺序、逻辑操作符的替代实现以及索引等物理结构的不同使用)。如果没有查询优化技术的创新，关系数据库今天在支持复杂决策支持查询方面所获得的成功就不可能成为现实。
在试图确定良好的执行计划时，查询优化器必须了解定义查询的数据的统计属性，因为这些统计属性会极大地影响执行查询的成本。此类统计属性的示例包括关系中的行总数、关系的属性值的分布以及属性的不同值的数量。因为优化器需要为给定的查询在许多备选执行计划中进行搜索，并试图选择一个成本较低的执行计划，因此它不仅需要对输入关系进行统计估计，还需要对它认为是组合搜索一部分的许多子表达式进行统计估计。事实上，子表达式的统计属性指导查询优化器对备选方案的研究。由于访问大型数据集的成本很高，因此通过执行这些子表达式中的每个来确定其子表达式的统计属性是不可行的。在面对数据更新时，能够有效地维护这些统计信息也很重要。这些需求要求在评估的质量和进行评估的开销之间进行明智的权衡。
早期的商业关系系统使用使用总结结构的估计技术，例如对关系属性的简单直方图。直方图的每个桶表示一个值范围。直方图捕获了直方图中每个桶的总行数和不同值的数量。对于较大的查询表达式，直方图是由其子表达式上的直方图以一种特殊的方式导出的。自20世纪90年代中期以来，统计估计在查询优化背景下的独特挑战吸引了许多有算法和统计背景和兴趣的研究人员。我们看到了利用随机算法(如概率计数)来解决这些统计估计问题的原则性方法的发展。根据数据库研究与数据库产业密切联系的长期传统，其中一些解决方案已被采用在商业数据库产品中。
Beyer等人的以下论文展示了查询优化背景下统计估计的最新进展。它重新审视了高效估计属性中不同值数量的难题，并在利用随机算法的过去工作的基础上做出了许多贡献。它提出了不同值的无偏估计，具有较低的均方误差，比先前提出的基于单次扫描数据的估计。作者提出了一个总结结构(剧情简介)，这样在一组关系上使用多集并集、多集交集和多集差分操作的查询中不同值的数量就可以从基关系的概要中估计出来。此外，如果一个关系的多个分区中只有一个被更新，则必须重新构建该分区的概要，以获得整个关系的不同值估计。
作者展示了查询优化背景下统计估计的最新进展。
从System-R定义查询优化框架到现在已经30年了，关系查询优化在商业上取得了巨大的成功。然而，查询表达式的统计估计问题仍然是一个需要取得重大进展的领域，以实现查询优化技术的下一个大飞跃。最近，研究人员正在试图了解如何从过去的执行中最好地收集关于数据和查询的统计属性的额外知识，以增强核心的统计估计能力。虽然我强调了查询优化，但这种统计估计技术在其他领域也有潜在的应用，如数据分析和近似查询处理。我邀请您阅读下面的论文，以示例数据库管理系统、统计和算法的交叉子领域。
©2009 acm 0001-0782/09/1000 $10.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2009 ACM, Inc.
没有发现记录