An Approach Based on Bayesian Networks for Query Selectivity Estimation
An Approach Based on Bayesian Networks for Query Selectivity Estimation
复制标题
基于贝叶斯网络的查询选择性估计方法
DOI：
10.1007/978-3-030-18579-4_1
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
F. Morvan
中科院分区：
文献类型：
--
作者：
Max Halford;Philippe Saint;F. Morvan
查询执行计划的效率取决于成本模型提供给查询优化器的选择性估计的准确性。成本模型简化了假设，以便及时产生上述估计。这些假设会导致选择性估计错误，从而对结果查询执行计划的质量产生巨大影响。当前成本模型中普遍存在的一个方便的假设是假设属性彼此独立。然而，它忽略了可能对成本模型的准确性产生巨大负面影响的潜在相关性。本文试图在不不合理地降低成本模型准确性的前提下，放宽属性值独立假设。我们提出了一种基于特定类型的贝叶斯网络（称为Chow-Liu树）的新方法来近似数据库中每个关系中属性值的分布。我们在TPC-DS基准测试上的结果表明，我们的方法比其他方法精确一个数量级，同时在时间和空间方面保持合理的效率。
The efficiency of a query execution plan depends on the accuracy of the selectivity estimates given to the query optimiser by the cost model. The cost model makes simplifying assumptions in order to produce said estimates in a timely manner. These assumptions lead to selectivity estimation errors that have dramatic effects on the quality of the resulting query execution plans. A convenient assumption that is ubiquitous among current cost models is to assume that attributes are independent with each other. However, it ignores potential correlations which can have a huge negative impact on the accuracy of the cost model. In this paper we attempt to relax the attribute value independence assumption without unreasonably deteriorating the accuracy of the cost model. We propose a novel approach based on a particular type of Bayesian networks called Chow-Liu trees to approximate the distribution of attribute values inside each relation of a database. Our results on the TPC-DS benchmark show that our method is an order of magnitude more precise than other approaches whilst remaining reasonably efficient in terms of time and space.