数据库内核月报－ 2022/10 - PolarDB · 功能特性 · 嵌套子查询优化的性能分析 - 《数据库内核月报》

PolarDB · 功能特性 · 嵌套子查询优化的性能分析
背景
包含聚集函数的子查询的优化方法
不同变换方式的性能分析
结论

PolarDB · 功能特性 · 嵌套子查询优化的性能分析

Author: zhilin

背景

嵌套子查询的性能问题一直是数据库优化的核心问题，原因也很明显，由于子查询的嵌套导致子查询被重复执行多次，尤其当主查询的数据量比较大时，由于子查询的嵌套迭代执行导致的性能问题就越发明显，因此优化器在优化过程中会根据子查询的特点，分别进行针对性的优化改写，提升查询的性能。下面我们就PolarDB对嵌套子查询的优化做一些详细的分析，让用户更深入理解PolarDB在性能优化方面的成就，让用户使用的更放心更安心。

包含聚集函数的子查询的优化方法

子查询优化的方法有很多，比如单值子查询的优化，SEMI-JOIN优化等，本文主要介绍的针对包含聚集函数的相关子查询的优化方法。下面是一个示例:


1. SELECT
2. SUM(l_extendedprice) / 7.0 AS avg_yearly
3. FROM
4. lineitem,
5. part
6. WHERE
7. p_partkey = l_partkey
8. AND p_brand = 'Brand#55'
9. AND p_container = 'JUMBO CASE'
10. AND l_quantity < (
11. SELECT
12. 0.2 * AVG(l_quantity)
13. FROM
14. lineitem
15. WHERE
16. l_partkey = p_partkey
17. )
18. LIMIT 1;

这是一个TPCH测试中一条件查询语句Query 17, 查询中包含了一个相关子查询，并且子查询中有聚集函数AVG，正常执行时，当主查询中lineitem表和part执行JOIN后产生的每一行数据都要将子查询执行一遍，然后才能做WHERE条件的过滤，得到最终的结果。显然，当主查询的行数非常大时，执行子查询的次数也自然很多，查询效率自然不高。

对此PolarDB提供了两种更好的优化方法，一种是首先对子查询按关联键进行分组执行聚集，将子查询转为一个Derived Table，然后将其提到主查询中，与主查询中的lineitem，part直接JOIN，避免子查询的无数次重复执行，实现性能优化的目的。这种优化方法可以简称为group by + Derived Table变换，下面我们通过改写的SQL来示意它的变换过程。


1. SELECT
2. SUM(l_extendedprice) / 7.0 AS avg_yearly
3. FROM
4. lineitem,
5. part,
6. (SELECT
7. l_partkey as dt_partkey, 0.2 * AVG(l_quantity) as avg_quantity
8. FROM
9. lineitem
10. GROUP BY l_partkey
11. ) dt

13. WHERE
14. p_partkey = l_partkey
15. AND p_brand = 'Brand#55'
16. AND p_container = 'JUMBO CASE'
17. AND p_partkey = dt.dt_partkey
18. AND l_quantity < dt.avg_quantity
19. LIMIT 1;

通过提前将lineitem按l_partkey分组，计算出每组l_partkey的平均值，然后和外层查询中的表进行JOIN，就可以直接得到对应的平均值，然后执行Where条件过滤即可得到最终结果。

除此之外，还有另外一种变换方法，是通过window function计算每组l_partkey的值，然后再使用Where条件过滤，得到最终的结果。这种优化方法可以简单为Window function + Derived Table变换，下面我们通过改写的SQL来示意它的变换过程。


1. SELECT
2. SUM(l_extendedprice) / 7.0 AS avg_yearly
3. FROM
4. (SELECT
5. l_quantity,
6. l_extendedprice,
7. (0.2 * AVG(l_quantity) OVER (PARTITION BY l_partkey)) as avg_quantity
8. FROM
9. lineitem,
10. part
11. WHERE
12. p_partkey = l_partkey
13. AND p_brand = 'Brand#55'
14. AND p_container = 'JUMBO CASE'
15. ) win
16. WHERE
17. l_quantity < avg_quantity
18. LIMIT 1;

通过Window function将每组l_partkey的平均值计算出来，与group by + Derived Table变换不同的是，无需再多加一次JOIN，就可以直接过滤得到最终结果。

不同变换方式的性能分析

如下所示，对同一种SQL，有两种变换方式，那么到底应该选择哪一种变换方式呢？有没有可能不变换的性能更好呢？下面就这个问题进行详细的分析，首先进行一个测试，如下所示：

测试方法

创建2个表，一个表是小表，其主键是另一个表的外键，查询中会利用这个主外键做关联进行子查询的关联查询。


1. CREATE TABLE part (
2. p_partkey INT PRIMARY KEY
3. );

5. CREATE TABLE partsupp (
6. ps_partkey INT,
7. ps_supplycost DECIMAL(10,2),
8. INDEX i1 (ps_partkey)
9. );

我们在part表中插入100000条数据。在每一轮实验中，针对每一个p_partkey值，在partsupp表中插入不同factor（1,2,4,8,16,32）条数据来模拟不同关联条数的重复值的影响。通过过滤条件中不同的@selectivity（0.1~1）来模拟选择率的影响。

测试语句为一个类似Query 17的嵌套子查询:


1. SELECT COUNT(*) FROM part, partsupp
2. WHERE p_partkey = ps_partkey
3. AND ps_partkey <= 100000 * @selectivity
4. AND ps_supplycost >= (
5. SELECT AVG(ps_supplycost) FROM partsupp WHERE p_partkey = ps_partkey);

这里为了测试不同选择率对性能的影响，使用了一个@selectivity变量，它是一个session级的变量，并且为了测试选择率的影响，分别选择了两种模式，一种是这个影响选择率的条件在变换后不能下推到Derived Table中；另一种是这个影响选择率的条件在变换后可以下推到Derived Table中。 影响选择率的条件不能下推的Group by + Derived Table的变换示意如下：


1. SELECT COUNT(*) FROM
2. part, partsupp,
3. (select ps_partkey, AVG(ps_supplycost) as avg_supplycost
4. from partsupp group by ps_partkey) ps2
5. WHERE p_partkey = partsupp.ps_partkey
6. AND partsupp.ps_partkey <= 100000 * @selectivity
7. AND p_partkey = ps2.ps_partkey
8. AND partsupp.ps_supplycost >= avg_supplycost;

影响选择率的条件不能下推的Window function + Derived Table的变换示意如下： 在window function + Derived Table变换中，如果存在session变量不能下推的情况，PolarDB默认是不做Window function变换的，因为这种变换的性能可能会变差，测试中通过在子查询添加hint来强制Window function变换。


1. SELECT COUNT(*) FROM part, partsupp
2. WHERE p_partkey = ps_partkey
3. AND ps_partkey <= 100000 * @selectivity
4. AND ps_supplycost >= (
5. SELECT /*+ UNNEST(WINDOW_FUNCTION) */
6. AVG(ps_supplycost)
7. FROM partsupp
8. WHERE p_partkey = ps_partkey);

Window function + Derived Table变换后的查询：


1. SELECT COUNT(*) FROM
2. (
3. select ps_partkey, ps_supplycost, AVG(ps_supplycost) over(partition by ps_partkey) as avg_supplycost
4. from part, partsupp
5. where p_partkey = partsupp.ps_partkey
6. ) win
7. where
8. win.ps_supplycost > win.avg_supplycost
9. AND ps_partkey <= 100000 * @selectivity;

影响选择率的条件可以下推的Group by + Derived Table的变换示意如下：


1. SELECT COUNT(*) FROM
2. part, partsupp,
3. (SELECT ps_partkey, AVG(ps_supplycost) as avg_supplycost
4. FROM partsupp
5. WHERE ps_partkey <= 100000 * 0.2
6. GROUP BY ps_partkey
7. ) ps2
8. WHERE p_partkey = partsupp.ps_partkey
9. AND partsupp.ps_partkey <= 100000 * 0.2
10. AND p_partkey = ps2.ps_partkey
11. AND partsupp.ps_supplycost >= avg_supplycost;

影响选择率的条件可以下推的Window function + Derived Table的变换示意如下：


1. SELECT COUNT(*) FROM
2. (
3. select ps_partkey, ps_supplycost, AVG(ps_supplycost) over(partition by ps_partkey) as avg_supplycost
4. from part, partsupp
5. where p_partkey = partsupp.ps_partkey AND ps_partkey < 100000 * 0.2
6. ) win
7. where
8. win.ps_supplycost > win.avg_supplycost;

测试结果如下所示： 相同选择率不同重复值的测试结果

● 红色曲线是不变换的查询性能，受重复值的影响最大，当重复值大越多，性能越差。 ● 蓝色曲线是groupby变换，并且条件可以pushdown的场景，性能最好。 ● 绿色曲线是window变换，并且条件可以pushdown的场景，性能次优。 ● 浅蓝色曲线是group by变换，但条件不能pushdown的场景，性能又稍差。 ● 紫色曲线是window变换，但条件不能pushdown的场景，性能也不好很好，当重复值小于14左右，性能最差，之后略好于不变换的查询性能。

相同重复值不同选择率的测试结果

● 红色曲线表示不做任何变换的查询，性能会随着选择率的增长，性能越来越差，当超过80%时，最差。 ● 蓝色曲线表示groupby变换，并且条件可以pushdown，性能最好，由于测试精度问题，当选择率为100%时，应该和条件不pushdown的性能相当，此处显示会略好，只是2次测试之间的误差问题，因为本身执行时间就比较短，只有0.5s左右。 ● 绿色曲线表示window变换，并且条件可以pushdown，性能次优，随着选择率趋进于100%，和不能pushdown的性能相当。 ● 浅蓝色曲线表示groupby变换，但条件不能pushdown，性能在条件不能pushdown中是最优的。 ● 紫色曲线表示window变换，但条件不能pushdown，相比同样是window变换，但条件可以pushdown的性能相关比较大，当条件不能pushdown时，条件对性能的影响几乎可以忽略不记。

初步的性能分析结论

根据以上的测试和分析，发现这个性能结果出乎我们的意料之外，window变换很多情况下应该是最优的，但实际的测试结果和数据分析结果都与其相违背。而且对于TPCH中的Q2/Q17，window变换相比groupby变换有明显优势，到底问题出在哪里呢？因此后续对Q17又做了一些对比测试。

Q17的性能分析

为了解决上面测试出现的疑问，有必要对Q2/Q17的变换做深入分析，以解决上面结论中的问题。下面以Q17为例进行性能分析和测试。测试数据集为10s，数据特点为对于partkey，lineitem中的重复值大约为30，比较大。另外Q17的选择率比较小，大约是0.11%。通过Explan analyze得到Q17执行过程中的性能数据：

Group by+Derived table变换


1. | -> Limit: 1 row(s)  (actual time=12512.366..12512.366 rows=1 loops=1)
2. -> Aggregate: sum(lineitem.l_extendedprice)  (actual time=12512.365..12512.365 rows=1 loops=1)
3. -> Nested loop inner join  (actual time=12338.854..12511.773 rows=2644 loops=1)
4. -> Nested loop inner join  (cost=40928.12 rows=58923) (actual time=0.198..153.232 rows=6688 loops=1)
5. -> Filter: ((part.p_container = 'JUMBO CASE') and (part.p_brand = 'Brand#55'))  (cost=20305.00 rows=1980) (actual time=0.087..137.618 rows=222 loops=1)
6. -> Table scan on part  (cost=20305.00 rows=198000) (actual time=0.027..94.947 rows=200000 loops=1)
7. -> Index lookup on lineitem using l_partkey_idx (l_partkey=part.p_partkey)  (cost=7.44 rows=30) (actual time=0.052..0.063 rows=30 loops=222)
8. -> Filter: (lineitem.l_quantity < derived_1_2.Name_exp_1)  (actual time=1.847..1.847 rows=0 loops=6688)
9. -> Index lookup on derived_1_2 using <auto_key2> (Name_exp_2=part.p_partkey)  (actual time=0.001..0.001 rows=1 loops=6688)
10. -> Materialize  (actual time=1.846..1.847 rows=1 loops=6688)
11. -> Group aggregate: avg(lineitem.l_quantity)  (actual time=0.263..12091.061 rows=200000 loops=1)
12. -> Index scan on lineitem using l_partkey_idx  (cost=607940.30 rows=5953163) (actual time=0.239..10743.582 rows=6001215 loops=1)

Window function+Derived table变换


1. | -> Limit: 1 row(s)  (actual time=170.197..170.197 rows=1 loops=1)
2. -> Aggregate: sum(derived_1_2.Name_exp_3)  (actual time=170.195..170.195 rows=1 loops=1)
3. -> Filter: (derived_1_2.Name_exp_2 < derived_1_2.Name_exp_1)  (actual time=165.699..169.697 rows=2644 loops=1)
4. -> Table scan on derived_1_2  (actual time=0.001..0.873 rows=6688 loops=1)
5. -> Materialize  (actual time=165.696..168.067 rows=6688 loops=1)
6. -> Window aggregate with buffering  (actual time=144.326..162.817 rows=6688 loops=1)
7. -> Sort: <temporary>.l_partkey  (actual time=144.243..145.376 rows=6688 loops=1)
8. -> Stream results  (actual time=0.229..142.414 rows=6688 loops=1)
9. -> Nested loop inner join  (cost=40928.12 rows=58923) (actual time=0.226..139.011 rows=6688 loops=1)
10. -> Filter: ((part.p_container = 'JUMBO CASE') and (part.p_brand = 'Brand#55'))  (cost=20305.00 rows=1980) (actual time=0.109..121.276 rows=222 loops=1)
11. -> Table scan on part  (cost=20305.00 rows=198000) (actual time=0.071..78.989 rows=200000 loops=1)
12. -> Index lookup on lineitem using l_partkey_idx (l_partkey=part.p_partkey)  (cost=7.44 rows=30) (actual time=0.062..0.072 rows=30 loops=222)

其中，根据实际的数据估算，sel%=0.11，dup大约为30，40%为最终l_quantity < 0.8 * avg的选择率，TPCH原来为0.2，为了数据量更大，测试时调整为了0.8.

最终的性能分析结论

通过Q17的性能数据，可以发现window变换后的性能远远高于group by的变换，再经过详细的分析数据发现，写之前测试结论不同的原因主要有2点：

Q17中的选择率非常低，大约在0.11%，而我们之前测试的至少都在10%左右，当选择率可以下推时，影响比较大。
另外一个更重要的一点是Q17在group by + Derived Table变换后的IO非常高，但在之前的测试中group by+Derived Table变换后IO并不是非常高，这也是导致性能相关较大的最主要的原因。通过深入分析发现，Q17的子查询中使用的是索引扫描，选择率的过滤条件在Q17中是通过filter来实现的，所以即使条件pushdown到子查询中后，仍需要扫描全表，而之前的测试是通过索引做range scan，并且ICP条件pushdown实现的，这样就导致在子查询中IO会大量减少，对group by+Derived Table变换的影响非常大，如果group by+Derived Table变换后不能使用索引来做range scan，条件也不能ICP下推，那么IO会非常大，是整个大表如lineitem表，或partsupp表的行数。而采用range scan+icp，就会直接是fitler过后的io，当filter很小时，IO就会非常小。当使用windows变换时，首先是在小表part表中过滤，然后通过索引lookup大表lineitem表，这样IO只是part表的行数，以及过滤过的partkey对应在lineitem中的lookup的行数，因此io与lineitem的大小关系不大。

结论

通过以上的测试和性能分析结果，可以得出这样的结论，通过优化器的查询变换大多数情况下都可以提升性能，但在一些特殊场景下，无论是group by+Derived Table变换还是window+Derived Table变换有可能导致变换后的性能回退，不同变换的性能差异也比较明显，甚至不做变换反而性能是最优的。其中有几个因素对性能有比较大的影响：

影响外查询的选择率的条件，尽可能的下推到子查询中，当不能下推时，外查询的选择率越低，性能回退的可能性越高。
子查询中大表中包含关联列的重复值影响也很大，当重复值越大，变换后的性能提升越明显，这主要是因为提前做AGG聚集操作有利于减少中间结果；
子查询中是否可以将影响选择率的条件下推到存储层，当可以在存储层过滤大量数据时，group by+Derived Table变换的性能会更优，否则window + Derived Table变换的性能更优。
当条件不能pushdown到子查询中时，在重复值较小时，不变换性能更优；重复值稍大时，group by + Derived Table变换更优。当重复值超过某个阀值时，不变换的性能最差。

总之，对于包含聚集操作的嵌套子查询来说，采用什么样的变换方式需要根据实际的COST来决定，不同场景下数据集的特点相差很大，不同的场景下的查询选择率也相差很大，不能简单指定某个规则就应用于所有场景。

原文：http://mysql.taobao.org/monthly/2022/10/06/