GPOrca中连接查询的快速优化

开源项目

2021-03-03

连接优化是查询优化器的核心。它包括选择一个好的连接顺序，正确的连接算法（哈希连接，嵌套循环连接等）等众多事项。选项数量增长迅速，因此需要一种称为动态规划（Dynamic Programming）的方法，将连接的搜索工作维持在合理的范围内。但是，即使使用动态规划，优化时间也会随着连接表的数量呈指数增长。

因此，在GPDB 6.13的ORCA优化器中，如果连接次数在10次以内，则使用动态规划算法。如果连接次数超过10次，采用“贪心”优化方法，该方法速度更快，但优化效果相对于动态规划则较差。

在GPDB 6.14中，我们引入了一种全新的方法，该方法可以为大型连接执行计划带来更快的优化时间和/或更好的大型连接执行计划。

加速枚举

随着要考虑的选择项呈指数增长，尽可能在每个选择项上花费更少的时间是非常重要的，这就是GPDB 6.14的改进之一。（请注意，如果您正在使用其他版本的GPDB，您仍然可以从本文中提到的的功能中受益，请参见下面的详细信息）。

与传统的自下而上（bottom-up)的优化器不同，ORCA是自上而下驱动（top-down ）的优化器。但是，对于枚举连接（enumerating joins）的任务，我们借用了一种自底向上（top-down）的方法，该方法对于查询优化的这一部分更为有效。我们仍然保留了自顶向下方法的所有优点，例如能够将其他运算符（例如分组依据和窗口函数）集成到优化过程中。

包括外连接

您可能已经注意到，具有外连接的大型查询会花费更长的时间进行优化。这是因为外连接使用了一种不同的算法，这个算法比内连接的计算强度更高。从GPDB 6.14开始，内连接和外连接共享一个全新的，更有效的算法。这也意味着，即使包含外连接，我们仍然可以使用穷举法对连接次数少于10次的查询进行优化。我们将在下面的示例中对此进行说明。

动态分区消除

许多用例在很大程度上依赖于动态分区消除，即与另一个表连接用于消除不需要的分区。为此，我们需要生成一个连接顺序，以允许进行动态分区消除（DPE）。尽管优化器一直在制定这样的计划，但现在我们更加侧重生成适合DPE的连接顺序。下面是一个使用DPE的计划的示例，您可以看到分区选择是在哈希连接的另一侧完成的：

# explain (costs off)
# select *
# from sales join date_dim on sales.sale_date_id = date_dim.date_id
# where date_dim.d_year = 2020 and date_dim.d_month = 12;
                                  QUERY PLAN
--------------------------------------------------------------------
 Gather Motion 3:1
 ->  Hash Join
     Hash Cond: (sales.sale_date_id = date_dim.date_id)
   ->  Dynamic Seq Scan on sales (dynamic scan id: 1)
   ->  Hash
     ->  Partition Selector for sales (dynamic scan id: 1)
       ->  Broadcast Motion 3:3
         ->  Seq Scan on date_dim
             Filter: ((d_year = 2020) AND (d_month = 12))

示例

示例1：

对于较小的查询，例如5向连接（5-way joins)，在行为上没有太大的区别。但是，假设我们有两个查询，一个10路内连接（10-way inner join）和一个11路内连接（11-way inner join）。在6.13中，11路连接（11-way join）的优化时间将明显短于10路连接（10-way join），但是计划质量也会下降。在6.14中，这种从穷举法（exhaustive enumeration）到贪心法（greedy approach）的过渡变得更加高效和平滑。您应该看到优化时间逐渐增加，而计划质量逐渐降低，而不是10张表上的飞跃。请注意，随着复杂度的上升，任何查询优化器都会相应的降低执行计划质量以节约时间，这样的计划质量下降是在接受范围内的。

示例2：

对于一个具有7个内连接（inner join）和7个外连接（outer-join）运算符的查询（总共15个表），在GPDB 6.13中，8路内连接（8-way inner join）位于10个表的阈值以下，因此我们使用穷举法进行优化，但是具有外连接（outer join）的另外7个表将花费大量的额外时间，因此此查询的优化相对较慢。在GPDB 6.14中，我们浏览组合的内连接和外连接（15向连接/15-way join），并且不进行完整的枚举。因此，此查询应花费更少的时间进行优化，但其计划质量可能会略有下降，这与15向内连接（15-way inner join）所看到的情况非常相似。在大多数情况下，获得的查询计划时间应该超过最佳查询计划可能导致的执行时间增加。

尽管默认的连接枚举算法在大多数情况下可以正常工作，但是在某些情况下，您可能需要在优化和执行时间之间进行权衡。对于这种情况，您可以使用一些配置参数。

optimizer_join_order参数允许您指定连接枚举算法。有关详细信息，请参见文档（https://gpdb.docs.pivotal.io/6-12/ref_guide/config_params/guc-list.html）。我们仅简要讨论此参数的三个可能值：

“Greedy”是指贪心搜索（greedy search），搜索速度很快，但会导致计划不理想。
“Exhaustive”是6.13及更早版本中的默认设置，它是适用于最多10路内连接（10-way inner join)的较慢的穷举方法，贪婪方法（greedy method）远超于此。
“ exhaustive2”（6.14中的默认值）是我们在本文中描述的新方法。请注意，6.14中更改的都是默认值。您可以尝试从6.11.1版本开始以及从5.28.2开始的GPDB 5中尝试这种新方法。较早的版本也可能具有“ exhaustive2”参数设置，但应视为实验性的。

到目前为止，我们已经说过，穷举枚举的阈值是10向连接（10-way join），但是也可以通过将optimizer_join_order_threshold参数设置为非10的值来更改该阈值。此参数也适用于“exhaustive”的硬限制和“exhausitive2”的逐步过渡。

绩效评估

我们以上面的示例为例，尝试了一系列查询，这些查询的内连接和外连接的数量大致相同。下表显示了使用旧（exhaustive）算法和新（exhaustive2）算法在ORCA中优化这些查询所花费的时间。

请注意，旧算法的时间呈指数增长，最多是10个内连接（共20-way join），当切换到贪心算法时下降。新算法起初也呈指数增长，但总体上效率更高。

这是一个极端的例子。当我们仅使用内连接时，两种方法之间的差异要小得多，但是您会看到另一个区别：新算法为较大的连接探索了更大的搜索空间，从而导致更长的优化时间，但缩短了查询执行时间。请注意，此第二张图的垂直比例是第一张图的1/10。