论文摘要
在数据库系统中,查询优化器是一个很重要的模块,它决定了一个查询的执行。而选择性估算算法在查询优化器中扮演着非常关键的角色。不正确的选择性估算结果可能导致查询优化器选择了差的查询执行计划,与最优的查询执行计划相比,一个差的执行计划往往需要花费几倍甚至几十倍的时间。本文主要研究基于直方图的选择性估算方法。直方图的构造是基于直方图的选择性估算方法中最基本的问题之一。构造直方图是基于某个目标函数的优化问题,即在给定数量的存储空间里,要求尽量准确地描述给定数据空间的数据分布。通常,这个目标函数要求:直方图模型和真实数据分布之间误差尽可能小,或者基于直方图模型进行查询估计的误差尽可能小。这里,不同的算法和应用对误差的定义可能有所不同。本文采用了一种新的误差概念,即聚合误差(AggregateError),来构造直方图。具体地,我们基于相对聚合误差(Relative Aggregate Error)来构造直方图,要求构造出来的直方图和真实数据分布之间的聚合误差最小化。我们通过对真实数据集和仿真数据集上的实验测试证实了本文方法的可行性。在较低维的情况下(维度≤4),用本文方法构建的直方图进行选择性估算的结果优于已有方法。另外,本文提出几种基于取样和直方图的混合选择性估算方法。基于直方图的选择性估算方法和基于取样的选择性估算方法都有各自的优缺点。对于低维度的数据,基于直方图的选择性估算方法有较好的准确率,优于取样的方法。但是对于高维度的数据,基于直方图的方法准确率直线下降,而取样方法的结果保持了很高的稳定性。因此,本文将基于直方图的方法和取样方法混合起来,期望在各个数据维度都有较高选择性估算准确率。在文中分别提出了基于相同取样率的混合方法,部分均匀取样的混合方法,与方差成比例取样的混合方法,查询优化取样的混合方法以及基于高斯分布描述的混合方法。通过大量的仿真实验证明,本文的混合方法大大减小了选择性估算的误差,并且有较好的数据维度适应性和可扩展性。