[reading review] How Good Are Query Optimizers, Really?

导读

在数据库中，找到一个好的连接顺序（join order）对查询性能是至关重要的。论文介绍并引入了JOB基准测试，并研究了经典的查询优化器的架构。本文研究发现，基数估计（Cardinality Estimation），代价模型（Cost Model）和计划空间枚举算法（plan enumeration techniques）都会对查询性能带来一定的影响。

引言

找到一个好的连接顺序是数据库领域中最重要的问题之一。下图展示了经典的基于代价的查询优化器架构：

为了得到一个高效的查询计划，查询优化器会枚举（enumeration）一些有效的连接顺讯（join order）的子集，例如使用动态规划的方法。用基数估计（cardinality estimation）的结果作为其原则上的输入，再结合代价模型（cost model），从而从语义相等的执行计划中选择出最便宜的一个。

论文主要研究了经典查询优化器架构中的三个主要组成部分，来回答以下问题：

• 基数估计的结果有多好，糟糕的估计何时会导致查询速度变慢？
• 精确的代价模型对整个查询优化过过程有多重要？
• 枚举的计划空间需要有多大？ 基于上述问题，论文做出的主要贡献如下：
• 设计了一个基于IMDB数据集的具有挑战性的工作负载（workload），名为Join Order Benchmark (JOB)。该基准是公开的，以促进进一步的研究。
• 论文首次使用真实世界的数据集和实际查询对连接排序问题进行了端到端研究。
• 通过量化基数估计，成本模型以及计划枚举算法对查询性能的贡献，论文为查询优化器的完整设计提供了指南。同时还表明许多灾难性计划可以被轻松的避免。

背景介绍和方法论

论文使用基于真实数据集的工作负载和广泛使用的PostgreSQL系统进行实验。PostgreSQL是一个有相当传统架构的关系型数据库系统，此外它的开源特性允许人们观察和改变它的内部结构。 IMDB数据集 许多查询处理和优化的研究论文都使用标准的基准测试（benchmark）例如TPC-H，TPC-DS或者SSB。虽然这些基准测试集已经证明了它们在评估查询引擎方面的价值，但是论文认为对于基数估计而言，这些并不是足够好的基准测试集。因为这些基准测试的数据都是基于非常简单的假设生成的（均匀，独立等）。但是相比而言，真实世界的数据集充满了相关性，并且有不均匀的数据分布，这会使得基数估计更加困难。 JOB查询 因此，论文选择了IMDB数据集，包含了大量关于电影，相关演员，导演已经制作公司的信息。像其他大多数真实世界的数据集一样，这些信息之间充满了相关性，并且不是均匀分布的。基于IMDB数据集，论文作者构建了一系列分析SQL查询。因为最关注的查询优化问题是连接顺序（join ordering），论文设计的查询包含了3-16个连接操作（join），平均每个查询有8个连接操作。其中一个典型的查询如下所示：

作者们设计的JOB基准测试33种查询结构，每种结构有2-6个变体，最终共计有113个查询。这些查询对基数估计任务是十分具有挑战性的，因为其中包含的大量的join操作和数据之间的相关性。 PostgreSQL PostgreSQL采用了传统的教科书风格的优化器架构。连接顺序（join order）的选择支持浓密树，通过动态规划进行枚举。基表（base table）的基数估计通过直方图计算频率得出。当一个相同的表有多个and谓词时，PG只简单的假设了各谓词之间的独立性。PG使用如下公式计算join操作结果的大小：

其中，T1 和 T2是任意表达式，dom(x) 是属性x的基数（x的不同取值的个数）。总的来说，PG的基数估计假设了数据是均匀分布且互相独立的。PG的查询引擎采用了火山模型，join的执行可以通过nested loop，in-memory hash join或者merge join来实现，具体采用哪种算法是由优化器决定的并且在运行时无法更改。 基数提取和注入 本文把IMDB数据集分别载入了PG，Hyper，和三个商用数据库中。论文使用每个数据库系统默认的设置来生成数据库相关的统计信息（直方图或样本等），以供之后的基数估计算法使用。论文作者修改了PG，使得可以将任意join表达式的基数注入，这也就使PG的优化器可以使用其他系统的基数估计值或者真实的基数值。这样就可以直接比较不同系统的基数估计的结果对查询性能带来的影响。 实验设置 论文实验使用的机器有64GB的内存，确保整个IMDB数据集都能被载入内存中，并且任何中间的查询结果（例如哈希表等）也都可以轻松载入到内存中。同时将PG中每个算子的内存限制（work_mem）设为2GB，缓冲池（shared_buffers）大小设为4GB，PG使用的操作系统缓存（Effective_cache_size）设为32GB。然而这三个参数在PG的默认设置中都非常低，通常计算单位是MB，不是GB。

基数估计

基数估计是找到一个好的查询计划的最重要的步骤之一。如果基数估计的结果不够准确，就算枚举完所有的连接顺序，有一个完美且精确的代价模型也是没有意义的。然而众所周知的是，基数估计的结果有时会有数量级的错误，这样的错误会导致查询速度变慢。 基表的估计 为了衡量基表（base table）基数估计的质量，论文引入了q-error，这是一个衡量估计值和真实基数之间差距的因子。例如，如果一个表达式基数的真实值是100，那么估计值为10或1000的q-error都为10。

表1展示了629个基表的q-error的第50，第90，第95和第100分位数。可以看到所有系统的q-error的中位数都接近最优值1，说明大多数选择语句的基数都能被正确估计。然而所有系统都会对某些查询产生错误的估计，并且基数估计的质量在不同系统之间差别很大。

论文发现DBMS A和Hyper甚至能较好地预测复杂的谓词例如LIKE查询子串操作。位了预测基表的选择率，Hyper使用随机采样的方法，从每个表中随机选择1000行作为样本，然后将谓词作用在该样本上。这样做可以得到任何基表的精准预测值（在选择率不太低的情况下）。当DBMS A和Hyper的q-error大于2时，大多数都是因为极低的选择率（10-5或10-6）。其他系统的估计预测值更糟并且似乎是基于表中的每个属性的直方图进行预测的，这在谓词较多的时候无法准确预测，并且不能很好的检测到不同属性之间的相关性。 join的估计 估计join的中间结果的基数是更有挑战性的，采样法或直方图都没办法完美做到这一点。下图总结了超过十万条基数估计的结果：

横坐标为join操作的个数，纵坐标为基数的估计值和真实值之间的差异。我们可以看到除了DBMS B，其他系统的基数估计性能接近。值得注意的是，所有被测试的系统都趋于系统性地低估包含多个join操作的的查询的结果大小。对于论文中的查询集，的确随着连接操作数的增加，中间结果的估计值趋于下降，因为更多的join操作意味着更多的基表选择。从前文PG估算join操作结果的大小的简单公式，以及上图其仍可与商业数据库系统相比的结果来看，我们可以推断出现在的join结果大小估算都是基于独立性假设的，还没有系统能够检测到交叉连接（join-crossing）的相关性。 TPC-H上的估计 正如作者在设计JOB基准测试时所言，TPC-H对基数估计任务来说太过简单。下图展示了PG在JOB和TPC-H上进行基数估计的估计错误情况：

从图中可以看到，TPC-H没有给基数估计任务造成太大的挑战。而作者设计的JOB测试集会导致较为严重的高估或低估错误，因此JOB基准测试可以被看作是基数估计任务的一个很有挑战性的benchmark。

什么时候糟糕的基数估计会导致查询变慢？ 尽管之前章节中出现的较大的估计错误是令人沮丧的，但大的错误不是一定会导致慢的查询计划。最重要的发现是查询优化是和数据库的物理设计密切相关的：索引的类型和数量对计划搜索空间有很大影响，因此会影响系统对基数错误估计的敏感程度。 依赖估计的风险 为了测量基数估计对查询性能的影响，论文作者将不同系统的基数估计注入到PG中并执行最后的查询计划。使用相同引擎是为了能够单独评价基数估计对查询性能带来的影响。作者同时还将真实的基数值注入到PG中，以得到最优计划来比较基数估计对查询性能带来的影响。下表展示了相比用真实基数值得到的计划的执行时间，用基数估计值得到的执行计划会对查询性能带来的损失：

从表中可以看到，小于0.9的部分，即是用基数真实值会比使用估计值更慢，这部分是由代价模型的误差引起的。而其他大部分如我们的预期一样，使用基数估计值时查询会变得更慢。通过观察使用预估值并且在一定时间内未执行完的查询，我们可以发现原因是PG的优化器决定使用nested-loop join，当基数估计值较低时。这也符合作者前文的判断，基数估计中系统性的低估是非常频繁的，而这也会导致PG引入nested-loop join，从而降低查询性能。 PG选择nested-loop join的根本原因是它会纯粹的基于代价来选择join算法。例如，一个执行计划使用nested-loop join的代价是1,000,000，而使用hash join的代价是1,000,001，PG将会选用nested-loop join。然而nested-loop join的复杂度是O(n2)，hash join的复杂度是O(n)，并且低估时常发生，这种情况下选择nested-loop join其实是很有风险的。即使估计偶尔准确，nested-loop join相比于hash join潜在的性能提升也是非常小的。 所以本文在之后的实验中都禁用了nested-loop join，如下图所示：

在不会选择nested-loop join的情况下重跑之前的查询，就不会再出现超时的情况了。同时没有查询的执行速度比之前更慢也证实了作者之前的假设：nested-loop join基本没有优势。但是这样做并没有解决任何问题，因为还有很多查询比使用基数真实值的查询慢了十倍以上。作者发现还有一个原因是这些查询大多数都有一个hash join，但是哈希表的输入被低估了。因为9.4版本之前的PG会基于基数值确定哈希表的大小，对基数的低估会导致哈希表较小，从而导致哈希冲突后的哈希链过长，进而影响查询性能。修正这一误差后，从图中可以看到只有不到4%的使用基数估计值的查询会比使用真实值的查询慢两倍以上了。 Good Plans Despite Bad Cardinalities 不同连接顺序的查询计划的执行时间往往有数量级的差距。到目前为止所有的实验只使用了主键索引，即使在基数估计较差的情况下，大部分查询的性能仍接近使用基数的真实值时的性能，这是相当积极的结果。主要的原因是，当不使用外键索引时，大多数较大的表都会使用全表扫描，这样会减弱不同的连接顺序带来的影响。 复杂访问路径

为了检测引入更多索引时查询优化问题是否会变得更复杂，论文作者另外在外键属性上创建了索引，从上图可以看出，40%的查询性能比之前慢了两倍还多，这意味着更多的索引的确会是查询优化问题变得更加复杂。

交叉连接相关性

当前的数据库社区达成了一种共识：当有相关的查询谓词时，估计中间结果的基数是查询优化研究领域的前沿问题。本文设计并提出的JOB基准测试的查询中就包含很多相关谓词。本文实验集中于单表子查询基数估计的质量，展示了使用表采样技术的数据库系统（Hyper和DBMS A）在有相关谓词的情况下，也能达到接近完美的估计结果。所以基数估计研究的挑战性在于，当相关性谓词作用于从不同表的列，且由join连接时的查询优化。本文作者称之为“交叉连接相关性”（join-crossing correlations）。交叉连接相关性还是数据库研究中的一个开放性议题，它包括了数据库的物理设计，查询执行和查询优化之间的相互作用。

代价模型

代价模型指导了从搜索空间中对不同的执行计划进行选择。之前三十多年的研究主要集中在基于硬盘的系统。例如，PG的代价模型由超过4000行C语言代码组成，并且会根据不同的条件进行微妙的处理。因此，研究一个复杂的代价模型究竟会对最后的查询性能带来多少提升是十分有趣的。 PostgreSQL的代价模型 PG基于硬盘的代价模型包含了CPU和I/O的代价，并给两者不同的权重。具体来说，一个算子的代价和其访问的硬盘页数还有内存中处理的数据量有关。一个查询计划的代价是其包含的所有算子的代价之和。权重参数的默认值由优化器的设计者设定，并且是为了反映随机访问，顺序访问和CPU运算代价之间的相对区别。PG的官方文档指出，随意更改这些参数是十分冒险的行为。 代价和运行时间 代价函数最主要的价值是在给定基数估计的情况下，它可以判断出在一些等价的查询计划中哪个是最快的，也即性能最好的。所以代价模型和查询执行时间的相关性是很重要的，下图展示了PG的代价和执行时间之间的关系：

作者同时将基数的真实值注入到PG中，并进行了线性回归分析，图中蓝色直线即为线性回归模型的结果。可以看到较差的基数估计会导致很多异常点（outlier）的出现。只有使用基数的真实值才能使PG对运行时间的预测更加可靠。

复杂的代价模型真的有必要吗？ 如上文提到过的，PG的代价模型十分复杂。这种复杂性应该反映出影响查询性能的多个因素，例如硬盘搜索和读取的速度和CPU的处理速度等。为了探究这样的复杂度在基于内存的数据库系统中是否还是必须的，本文作者将复杂的代价模型与一个非常简单的代价函数做比较。因为这个代价函数是面向基于内存的系统设计的，所以不需要考虑I/O的开销，只计算查询执行过程中每个算子处理数据的数量，该函数如下所示：

其中，R是一个基本关系，并且该函数会对hash join和index-nested loop join进行区分。使用该函数进行实验的结果如图8的e和f所示。可以看到，即使是这个简单的代价模型，也可以在使用基数的真实值时对查询的执行时间进行很好地预测。从实验结果中可以得出：对查询优化的性能的影响而言，基数估计的正确性远比代价模型的复杂度更加重要。

计划空间 除了基数估计和代价模型，最后一个查询优化的重要组成部件是计划枚举算法，可以用来探索语义等价的不同连接顺序。本章节将会研究为了找到一个好的执行计划需要多大的搜索空间。本节的实验使用一个独立运行的查询优化器，该优化器实现了动态规划和一系列启发式连接枚举算法。 连接顺序有多重要？ 本文使用Quickpick算法来可视化不同连接顺序的开销。Quickpick是一种简单的随机的算法，它会随机地选择join顺序，直到所有join操作被选中。每次执行该算法会产生一个正确的，但通常较慢的执行计划。通过对每个查询执行该算法10000次，可以得出近似的计划空间的代价分布，如下图所示：

图中针对三种数据库系统设计进行试验：无索引，主键索引和主键+外键索引。上图中对横坐标进行了对数处理，清晰地展现了连接顺序的重要性：最慢的或者甚至中位数的开销，都要比最优的连接顺序的性能慢上好几个数量级。不使用索引和只使用主键索引的分布很接近，而主键+外键索引的最优计划在分布图较左侧出现峰值，这也意味着该索引下更快的查询速度。 浓密树真的有必要吗？ 大多数确定连接顺序的算法都不会枚举所有可能的树的形状。事实上，几乎所有的优化器都会忽视在笛卡尔积上的连接顺序，这样做对查询性能带来的影响微乎其微，但是可以极大地缩短优化时间。本文作者在做实验时修改动态规划算法，使其只考虑左深树，右深树和锯齿形树（zig-zag trees）。除了对树的形状的限制，还对连接方法的选取进行了限制：使用hash join时，右深树基于每个关系创建哈希表，然后使用pipeline的方式进行探查（probing）。而左深树会在每个join操作后创建一个新的哈希表。锯齿形树是左深树和右深树的超集，每个join算子至少有一个输入是一个基本的关系。 使用基数的真实值，作者得出了这三种形状受限的树的最优查询计划的开销，并与不限制形状的最优树（可以是任意形状，包括浓密树）的开销进行比较，结果如下表所示：

从表中可以看到，锯齿形的树几乎可以提供接近完美的查询性能，左深树性能稍差，但仍有较为不错的性能。然后右深树却要差得多，这是由于大量的中间哈希表的创建所导致的。 启发式算法是否足够好？ 到目前为止，本文一直使用动态规划来计算最优连接顺序。在这节作者比较了动态规划，随机算法，和贪婪的启发算法，比较结果如下表所示：

从表中可以得知在基数估计有误差时，使用动态规划会得到最好的效果；当引入基数的真实值时，动态规划可以达到最优解，因为动态规划会遍历计划的搜索空间。但是基数估计的误差会对动态规划带来较大的性能损失。随机算法和贪婪的启发式算法在索引较少时可以得到较好的查询计划。总的来说，从良好的基数估计中可以获得的性能提升潜力远大于不同的join ordering算法所带来的提升。 总结与展望 本文对查询优化的各部分进行了详细的研究实验，表明查询优化是获得高效查询处理性能的必要条件，并且详尽的枚举算法能比启发式算法得出更优的执行计划。此外，本文也展示了关系型数据库随着join操作的增加会产生更大的估计误差，这些误差会更容易导致系统得出较差的查询计划。基数估计，代价模型和join ordering作为查询优化问题的主要组成部分，基数估计的好坏在三者中对查询性能的影响最大。 同时作者也提出两个提升查询性能的思路：一是在数据库系统中引入更先进的估计算法；二是在查询执行期间（runtime），提高优化器的参与程度，使其可以动态地根据执行期间的中间结果对查询进行优化。