Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates
Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates
复制标题
每一行都很重要：结合草图和采样以准确估计分组结果
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Thomas Neumann
中科院分区：
文献类型：
--
作者：
M. Freitag;Thomas Neumann
数据库系统严重依赖基数估计来查找有效的执行计划，估计错误很容易对查询执行时间产生很大的影响。一个特别困难的问题是估计group-by算子的结果大小，或者一般来说，估计一组属性的不同组合的数量。与估计简单过滤器谓词的选择性相反，如果不检查完整的输入，则无法可靠地预测所得到的组数。因此，大多数现有系统对不同群体的数量估计都很差。然而，在优化时扫描整个关系在实践中是不可行的。此外，无法为每个可能的属性组合预先计算精确的组计数。在实际应用中，需要一种廉价的机制来高效、高精度地处理任意属性组合。在这项工作中，我们提出了一种新的估计框架，该框架将单个列的草图完整信息与随机抽样相结合，以纠正属性之间的相关偏差。这种组合可以几乎完美地估计单个列的组计数，并且可以高精度地估计任意列组合的组计数。大量的实验表明，这些优秀的结果适用于合成数据集和真实世界的数据集。我们演示了该机制如何以低开销集成到现有系统中，以及如何通过有效的样本扫描算法使估计时间可以忽略不计。
Database systems heavily rely upon cardinality estimates for finding efficient execution plans, and estimation errors can easily affect query execution times by large factors. One particularly difficult problem is estimating the result size of a group-by operator, or, in general, the number of distinct combinations of a set of attributes. In contrast to, e. g., estimating the selectivity of simple filter predicates, the resulting number of groups cannot be predicted reliably without examining the complete input. As a consequence, most existing systems have poor estimates for the number of distinct groups. However, scanning entire relations at optimization time is not feasible in practice. Also, precise group counts cannot be precomputed for every possible combination of attributes. For practical purposes, a cheap mechanism is thus required which can handle arbitrary attribute combinations efficiently and with high accuracy. In this work, we present a novel estimation framework that combines sketched full information over individual columns with random sampling to correct for correlation bias between attributes. This combination can estimate group counts for individual columns nearly perfectly, and for arbitrary column combinations with high accuracy. Extensive experiments show that these excellent results hold for both synthetic and real-world data sets. We demonstrate how this mechanism can be integrated into existing systems with low overhead, and how estimation time can be kept negligible by means of an efficient algorithm for sample scans.