DBMS-Optimizer

阅读更多

1 Overview

优化器涉及到的优化点包括：

• Limit合并
• Limit下推
• 子查询重写
• 各种表达式的重写和化简
• 列裁剪
• 谓词下推
• 聚合合并
• 等价谓词推导（常量传播）
• Outer Join转Inner Join
• 常量折叠
• 公共表达式复用（CTE）
• 子查询重写
• Lateral Join化简
• 分区分桶裁剪
• Empty Node优化
• Empty Union, Intersect, Except裁剪
• Intersect Reorder
• Count Distinct相关聚合函数重写
• GroupBy Reordering

2 Subquery Rewrite

Roadmap of subquery

子查询分类

• 按子查询所在的位置进行分类
  • WHERE子句
  • SELECT子句
  • GROUP BY子句
  • ORDER BY子句
  • HAVING子句
• 按是否相关进行分类
  • Correlated Subquery，即相关子查询
  • Non-correlated Subquery，即非相关子查询
• 按产生的数据特征来分类
  • Scalar Subquery，即标量子查询
    • 聚合子查询
    • 非聚合子查询
  • Existential Test Subquery，存在性检测子查询，如EXISTS子查询
  • Quantified Comparation Subquery，集合比较子查询，如ANY/SOME/ALL子查询
    • x = SOME(statement) -> IN (statement)
    • x <> ALL(statement) -> NOT IN (statement)
    • 

上述不同分类均可自由组合

下面的讨论都基于如下的数据集：

DROP TABLE IF EXISTS `S`;
CREATE TABLE IF NOT EXISTS `S` (
  `s_id` int(11) NULL,
  `s1` int(11) NULL,
  `s2` int(11) NULL,
  `s3` int(11) NULL
) ENGINE=OLAP
DUPLICATE KEY(`s_id`)
DISTRIBUTED BY HASH(`s_id`) BUCKETS 10
PROPERTIES (
 "replication_num" = "1"
);

INSERT INTO `S` (s_id, s1, s2, s3) values
    (1, 1, 2, 3),
    (2, 1, 2, 3),
    (3, 4, 5, 6),
    (4, 4, 5, 6),
    (5, 7, 8, 9),
    (6, 10, NULL, 12),
    (7, 13, 14, 15),
    (8, 16, 17, 18);

DROP TABLE IF EXISTS `R`;
CREATE TABLE IF NOT EXISTS `R` (
  `r_id` int(11) NULL,
  `r1` int(11) NULL,
  `r2` int(11) NULL,
  `r3` int(11) NULL
) ENGINE=OLAP
DUPLICATE KEY(`r_id`)
DISTRIBUTED BY HASH(`r_id`) BUCKETS 10
PROPERTIES (
 "replication_num" = "1"
);

INSERT INTO `R` (r_id, r1, r2, r3) values
    (1, 1, 2, 3),
    (2, 1, 2, NULL),
    (3, 4, 55, 6),
    (4, 7, NULL, 9),
    (5, 7, 8, 9),
    (6, 10, NULL, 12),
    (7, 13, 14, NULL),
    (8, 19, 20, 21);

2.1 Scalar Subquery

对于在WHERE Clause中的Scalar Subquery，一般用Outer Join来进行转换。下面用一个例子来说明，原SQL如下，其含义是，针对S表中的每一行，在R表中找出满足S.s_id = R.r_id的那个R.r3（只能有一行，否则会报错），并作为S表的谓词

SELECT S.s1, S.s2
FROM S
WHERE S.s3 = (
  SELECT R.r3 FROM R
  WHERE S.s_id = R.r_id
)

重写后的SQL如下：

SELECT tmp.s1, tmp.s2 FROM (
  SELECT * FROM
  S LEFT OUTER JOIN R
  ON S.s_id = R.r_id
) tmp
WHERE tmp.s3 = tmp.r3

对于在SELECT Clause中的Scalar Subquery，同样用Outer Join来进行转换。下面用一个例子来说明，原SQL如下，其含义是，针对S表中的每一行，在R表中找出满足S.s_id = R.r_id的那个R.r3（只能有一行，否则会报错），并作为S表的表达式

SELECT S.s1, S.s2, S.s3 = (
  SELECT R.r3 FROM R
  WHERE S.s_id = R.r_id
)
FROM S

重写后的SQL如下：

SELECT tmp.s1, tmp.s2, tmp.s3 = tmp.r3 FROM (
  SELECT * FROM
  S LEFT OUTER JOIN R
  ON S.s_id = R.r_id
) tmp

2.2 Exists Subquery

2.2.1 Implement with Semi Join(Where Clause)

对于在WHERE Clause中的Exists Subquery，一般用Semi Join来进行转换。下面用一个例子来说明，原SQL如下，其含义是，针对S表中的每一行，在R表中找出满足S.s3 = R.r3的所有行，并提取出R.r2作为结果集A，看结果集A是否存在非空元素，并以此作为过滤条件，过滤S的数据

SELECT S.s1, S.s2
FROM S
WHERE EXISTS (
  SELECT R.r2
  FROM R
  WHERE S.s3 = R.r3
)

重写后的SQL如下：

SELECT S.s1, S.s2
FROM S LEFT SEMI JOIN R
ON S.s3 = R.r3

2.2.2 Implement with Outer Join(Select Clause)

对于在SELECT Clause中的Exists Subquery，一般用Outer Join来进行转换。下面用一个例子来说明，原SQL如下，其含义是，针对S表中的每一行，在R表中找出满足S.s3 = R.r3的所有行，并提取出R.r2作为结果集A，看这个结果集A是否存在非空元素

SELECT S.s1, EXISTS (
  SELECT R.r2
  FROM R
  WHERE S.s3 = R.r3
)
FROM S;

重写后的SQL如下：

SELECT S.s1, R_GroupBy.r3_Row IS NOT NULL FROM
S LEFT JOIN (
  SELECT R.r3, COUNT(1) AS r3_Row FROM
  R GROUP BY R.r3
) AS R_GroupBy
ON S.s3 = R_GroupBy.r3;

2.3 In Subquery

2.3.1 Implement with Semi Join(Where Clause)

对于在WHERE Clause中的In Subquery，一般用Semi Join来进行转换。下面用一个例子来说明，原SQL如下，其含义是，针对S表中的每一行，在R表中找出满足S.s3 = R.r3的所有行，并提取出R.r2作为结果集A，看S.s2是否在这个结果集A中，并以此作为过滤条件，过滤S的数据

SELECT S.s1, S.s2
FROM S
WHERE S.s2 IN
(
  SELECT R.r2
  FROM R
  WHERE S.s3 = R.r3
)

重写后的SQL如下：

SELECT S.s1, S.s2
FROM S LEFT SEMI JOIN R
ON S.s2 = R.r2 AND S.s3 = R.r3

2.3.2 Implement with Outer Join(Select Clause)

对于在SELECT Clause中的In Subquery，一般用Outer Join来进行转换。下面用一个例子来说明，原SQL如下，其含义是，针对S表中的每一行，在R表中找出满足S.s3 = R.r3的所有行，并提取出R.r2作为结果集A，看S.s2是否在这个结果集A中

SELECT S.s1, S.s2 IN
(
  SELECT R.r2
  FROM R
  WHERE S.s3 = R.r3
)
FROM S;

• 若S.s2为NULL，那么返回NULL
• 若结果集A为空，那么返回false
• 对于当前行（固定S.s3的值），若R表中不存在满足R.r3 = S.s3的行，那么返回false

重写后的SQL如下：

WITH R_CTE AS (SELECT R.r2, R.r3 FROM R)
SELECT S.s1,
       CASE 
           WHEN R_CountRow.R_Rows IS NULL THEN FALSE
           WHEN S.s2 IS NULL THEN NULL
           WHEN R_GroupBy.r2 IS NOT NULL THEN TRUE
           WHEN R_CountRow.r2_NotNulls < R_CountRow.R_Rows THEN NULL
           ELSE FALSE
       END
FROM S
LEFT OUTER JOIN
  (
    SELECT R_CTE.r2, R_CTE.r3
    FROM R_CTE
    GROUP BY R_CTE.r2, R_CTE.r3
  ) AS R_GroupBy 
  ON S.s2 = R_GroupBy.r2
  AND S.s3 = R_GroupBy.r3
LEFT OUTER JOIN
  (
    SELECT r3,
          count(*) AS R_Rows,
          count(R_CTE.r2) AS r2_NotNulls
    FROM R_CTE
    GROUP BY R_CTE.r3
  ) AS R_CountRow 
  ON  S.s3 = R_CountRow.r3;

• R_GroupBy：通过Left Outer Join将谓词IN调整谓词==
• R_CountRow：用于统计R表中各分组（by r3）下的总行数以及R.r2非NULL的行数
• CASE WHEN语句分析：
  • CASE WHEN 1：若R_CountRow.R_Rows IS NULL，我们知道count(*)是不会产生空值的，因此该空值一定是Left Outer Join产生的，意味着对于当前行（固定S.s3的值），R表中不存在满足R.r3 = S.s3的行，即集合A为空。因此根据ANY_OR_NULL IN (empty) -> false，谓词IN的结果就是false
  • 否则，意味着对于当前行（固定S.s3的值），R表中存在满足R.r3 = S.s3的行，即集合A不为空
  • CASE WHEN 2：若S.s2 IS NULL。因此根据NULL IN (ANY_OR_NULL...) -> NULL，谓词IN的结果就是NULL
  • 否则，意味着S.s2 IS NOT NULL
  • CASE WHEN 3：若R_GroupBy.r2 IS NOT NULL，意味着对于当前行（固定S.s3的值），集合A中至少存在一个元素满足S.s2 = R.r2，因此根据X IN (X, [ANY_OR_NULL...]) -> true，谓词IN的结果就是true
  • 否则，意味着R_GroupBy.r2 IS NULL
  • CASE WHEN 4：若R_CountRow.r2_NotNulls < R_CountRow.R_Rows，意味着对于当前行（固定S.s3的值），集合A中一定存在NULL元素。因此根据X IN (NULL, [NOT_X_OR_NULL...]) -> NULL，谓词IN的结果就是NULL
  • 否则，意味着R_CountRow.r2_NotNulls = R_CountRow.R_Rows，则集合A中不存在NULL元素，因此根据X IN (NOT_X...) -> false，谓词IN的结果就是false

2.4 Generic Decorrelation Algorithm

Complex Query Decorrelation

下面用一个例子来解释该算法：

• Dept：部门信息，其中building字段表示该部门的主要办公地点（意味着，该部门下的员工也可以在其他地点办公）
• Emp：员工信息

下面这个SQL的业务含义是，找出预算小于10000，且主要办公地点无法容纳该部门所有员工的部门

SELECT D.name
FROM Dept D
WHERE D.budget < 10000 
AND D.num_emps > (
    SELECT COUNT(*) FROM Emp E WHERE D.building = E.building
)

2.4.1 FEED Stage

请结合论文中的Figure 2看如下的分析

2.4.1.1 step a

初始状态。显然，Child_1与CurBox存在关联

-- CurBox
SELECT Q1.name
FROM Dept Q1, Temp_1 Q2
WHERE Q1.budget < 10000
AND Q1.num_emps > Q2.$1;

-- Temp_1 如下
SELECT COUNT(*) FROM Child_1;

-- Child_1 如下
SELECT * FROM Emp Q3
WHERE Q1.building = Q3.building;

2.4.1.2 step b

将谓词Q1.budget < 10000下推，构造出Supp替换原来的Dept

-- CurBox
SELECT Q1.name
FROM Supp Q1, Temp_1 Q2
WHERE Q1.num_emps > Q2.$1;

-- Supp 如下
SELECT * FROM Dept
WHERE Dept.budget < 10000;

-- Temp_1 如下
SELECT COUNT(*) FROM Child_1;

-- Child_1 如下
SELECT * FROM Emp Q3
WHERE Q1.building = Q3.building;

2.4.1.3 step c

接着，从Supp中构造出Magic_1

-- CurBox
SELECT Q1.name
FROM Supp Q1, Temp_1 Q2
WHERE Q1.num_emps > Q2.$1;

-- Supp 如下
SELECT * FROM Dept
WHERE Dept.budget < 10000;

-- 新构造的 Magic_1 如下
SELECT DISTINCT(building) FROM Supp;

-- Temp_1 如下
SELECT COUNT(*) FROM Child_1;

-- Child_1 如下
SELECT * FROM Emp Q3
WHERE Q1.building = Q3.building;

2.4.1.4 step d

这一步比较复杂，引入DCO(Decorrelated Output) Box以及CI(Correlated Input) Box

• CiBox_1与CurBox存在关联，但这个相关性可以通过Eq Join解除

  • 对于CiBox_1，每个building只有一条数据

  SELECT Q1.name
  FROM Supp Q1 JOIN CiBox_1 Q2
  ON Q1.building = Q2.building
  WHERE Q1.num_emps > Q2.$1;

• Child_1与CurBox存在关联，但由于Magic_1的存在，Child_1与DcoBox_1也存在关联。因此，关联关系就被下推了

• 于是CurBox的相关性就被解除了

-- CurBox
SELECT Q1.name
FROM Supp Q1, CiBox_1 Q2
WHERE Q1.num_emps > Q2.$1;

-- Supp 如下
SELECT * FROM Dept
WHERE Dept.budget < 10000;

-- Magic_1 如下
SELECT DISTINCT(building) FROM Supp;

-- CiBox_1 如下
SELECT * FROM DcoBox_1 Q3
WHERE Q3.building = Q1.building;

-- DcoBox_1 如下
SELECT Q4.building, Q5.$1
FROM Magic_1 Q4, Temp_2 Q5;

-- Temp_2 如下
SELECT COUNT(*) FROM Child_1;

-- Child_1 如下
SELECT * FROM Emp Q3
WHERE Q1.building = Q3.building;

2.4.2 ABSORB Stage

ABSORB阶段的目标是将相关性整个除去。紧接着FEEE Stage的step d继续流程，此时CurBox指向的是Temp_2

2.4.2.1 non-SPJ Box

情况1，即CurBox指向的不是一个SPJ Box，比如是一个Aggregate Box

2.4.2.1.1 step a

该状态等同于FEEE Stage的step d，只不过CurBox下移了

2.4.2.1.2 step b

此时，可以进一步对CurBox的父节点使用FEEE Stage的流程

-- DcoBox_1 如下
SELECT Q4.building, Q5.$1
FROM Magic_1 Q4, Temp_2 Q5;

-- Magic_2 如下
SELECT DISTINCT(building) FROM Magic_1;

-- Temp_2 如下
SELECT COUNT(*) FROM CiBox_2 Q6;

-- CiBox_2 如下
SELECT * FROM DcoBox_2 Q7
WHERE Q4.building = Q7.building;

-- DcoBox_2 如下
SELECT * FROM Magic_2 Q8, Temp_3 Q9;

-- Temp_3 如下
SELECT * FROM Emp Q3 
WHERE Q8.building = Q3.building;

2.4.2.1.3 step c

此时，DcoBox_1与CiBox_2存在相关性，但是CiBox_2可以从其孩子节点中获取相关性，因此DcoBox_1与CiBox_2的相关性是冗余的，可以通过LOJ直接移除

-- DcoBox_1 如下
SELECT Q4.building, Coalesce(Q5.count, 0)
FROM Magic_1 Q4 LEFT OUTER JOIN Temp_2 Q5
ON Q4.building = Q5.building;

-- Magic_2 如下
SELECT DISTINCT(building) FROM Magic_1;

-- Temp_2 如下
SELECT Q6.building, COUNT(*) as count
FROM CiBox_2 Q6
GROUP BY Q6.building;

-- CiBox_2 如下
SELECT * FROM DcoBox_2 Q7;

-- DcoBox_2 如下
SELECT * FROM Magic_2 Q8, Temp_3 Q9;

-- Temp_3 如下
SELECT * FROM Emp Q3 
WHERE Q8.building = Q3.building;

2.4.2.1.4 step d

这一步比较简单，移除冗余的CiBox_2即可

-- DcoBox_1 如下
SELECT Q4.building, Coalesce(Q5.count, 0)
FROM Magic_1 Q4 LEFT OUTER JOIN Temp_2 Q5
ON Q4.building = Q5.building;

-- Magic_2 如下
SELECT DISTINCT(building) FROM Magic_1;

-- Temp_2 如下
SELECT Q6.building, COUNT(*) as count
FROM DcoBox_2 Q6
GROUP BY Q6.building;

-- DcoBox_2 如下
SELECT Q8.building, Q9.* FROM Magic_2 Q8, Temp_3 Q9;

-- Temp_3 如下
SELECT * FROM Emp Q3 
WHERE Q8.building = Q3.building;

2.4.2.2 SPJ Box

此时CurBox继续下移，指向了step d中的Temp_3

2.4.2.2.1 step a

-- DcoBox_2 如下
SELECT Q8.building, Q9.* FROM Magic_2 Q8, Temp_3 Q9;

-- Magic_2 如下
SELECT DISTINCT(building) FROM Magic_1;

-- Temp_3 如下
SELECT * FROM Emp Q3 
WHERE Q8.building = Q3.building;

2.4.2.2.2 step b

Temp_3将Magic_2添加到其From Clause中，并改写Join On Predicate，于是DcoBox_2与Temp_3的相关性就被移除了

-- DcoBox_2 如下
SELECT Q8.building, Q9.* FROM Magic_2 Q8, Temp_3 Q9;

-- Magic_2 如下
SELECT DISTINCT(building) FROM Magic_1;

-- Temp_3 如下
SELECT Q3.* 
FROM Magic_2 Q10, Emp Q3 
WHERE Q10.building = Q3.building;

2.4.2.2.3 step c

Temp_3增加输出列Q10.building

-- DcoBox_2 如下
SELECT Q9.* FROM Temp_3 Q9;

-- Magic_2 如下
SELECT DISTINCT(building) FROM Magic_1;

-- Temp_3 如下
SELECT Q10.building, Q3.* 
FROM Magic_2 Q10, Emp Q3 
WHERE Q10.building = Q3.building;

2.4.2.2.4 step d

移除冗余的DcoBox_2

-- Magic_2 如下
SELECT DISTINCT(building) FROM Magic_1;

-- Temp_3 如下
SELECT Q10.building, Q3.* 
FROM Magic_2 Q10, Emp Q3 
WHERE Q10.building = Q3.building;

2.5 Subquery Elimination by Window Function

[Enhancement] Subquery elimination by window function

2.6 参考

• 子查询漫谈

3 GroupBy Reordering

Orthogonal Optimization of Subqueries and Aggregation

用$G_{A,F}(R)$表示GroupBy，其中A表示GroupBy列，F表示输出列

3.1 Filter

3.1.1 push down

$$\sigma_{p}G_{A,F}(R) \rightarrow G_{A,F}(\sigma_{p}R)$$

上述转换成立的条件如下：

• Filter中用到的列全部来自于GroupBy的输入列。换言之，不对GroupBy的输出列进行过滤

3.2 Join

3.2.1 push down

$$G_{A,F}(S \Join_{p} R) \rightarrow S \Join_{p} G_{A \cup columns(p)-columns(S),F}(R)$$

上述转换成立的条件如下：

• Join Predicate p中与R有关的列必须存在于GroupBy列中
• S的主键必须存在于GroupBy列中
• 聚合操作仅用到了R中的列

3.2.2 pull above

$$S \Join_{p} G_{A,F}(R) \rightarrow G_{A \cup columns(S),F}(S \Join_{p} R)$$

上述转换成立的条件如下：

• Join的表有主键
• Join没有用到聚合函数的结果列

3.3 Outer Join

3.3.1 push down

$$G_{A,F}(S ⟕_{p} R) \rightarrow \pi_{c}(S ⟕_{p} G_{A - columns(S),F}(R))$$

上述转换成立的条件如下（同Join push down）：

• Join Predicate p中与R有关的列必须存在于GroupBy列中
• S的主键必须存在于GroupBy列中
• 聚合操作仅用到了R中的列

可以发现，Outer Join与Join的差异是，多了一个$\pi_{c}$

• 当GroupBy列为NULL时，若聚合函数针对该NULL分组可以生成NULL时，比如sum，无需引入额外的$\pi_{c}$
• 当GroupBy列为NULL时，若聚合函数针对该NULL分组无法生成NULL时，比如count，则需引入额外的$\pi_{c}$，来产生相应的NULL值

下面用一个例子来说明

DROP TABLE IF EXISTS `S`;
CREATE TABLE IF NOT EXISTS `S` (
  `s1` int(11) NOT NULL,
  `s2` int(11) NOT NULL
) ENGINE=OLAP
DUPLICATE KEY(`s1`)
DISTRIBUTED BY HASH(`s1`) BUCKETS 10
PROPERTIES (
 "replication_num" = "1"
);

INSERT INTO `S` (s1, s2) values
    (1, 2),
    (2, 4),
    (3, 6);

DROP TABLE IF EXISTS `R`;
CREATE TABLE IF NOT EXISTS `R` (
  `r1` int(11) NULL,
  `r2` int(11) NULL
) ENGINE=OLAP
DUPLICATE KEY(`r1`)
DISTRIBUTED BY HASH(`r1`) BUCKETS 10
PROPERTIES (
 "replication_num" = "1"
);

INSERT INTO `R` (r1, r2) values
    (1, 12),
    (2, 22);

-- Q1.1
SELECT r1, sum FROM S LEFT OUTER JOIN (SELECT sum(r2) AS sum, r1 FROM R GROUP BY r1)a ON s1 = r1;
-- Q1.2
SELECT r1, sum(r2) AS sum FROM (SELECT * FROM S LEFT OUTER JOIN R ON s1 = r1)a GROUP BY r1;

-- Q2.1
SELECT r1, cnt FROM S LEFT OUTER JOIN (SELECT count(r2) AS cnt, r1 FROM R GROUP BY r1)a ON s1 = r1;
-- Q2.2
SELECT r1, count(r2) AS cnt FROM (SELECT * FROM S LEFT OUTER JOIN R ON s1 = r1)a GROUP BY r1;
-- Q2.3
SELECT r1,
CASE
    WHEN r1 IS NULL
    THEN NULL
    ELSE count(r2)
END AS cnt
FROM (SELECT * FROM S LEFT OUTER JOIN R ON s1 = r1)a GROUP BY r1;

可以发现：

• Q1.1和Q1.2可以产生相同的输出，因为聚合函数sum对于NULL分组可以正常产生NULL值
• Q2.1和Q2.2无法产生相同的输出，因为聚合函数count对于NULL分组会输出0或1。因此这里我们通过case when语句来对输出列进行改写Q2.3，以达到纠正的目的

4 Table Prune

[Feature] Pruning tables in cardinality-preserving joins

For cardinality-preserving joins:

• A inner join B on A.fk = B.pk: each row in A matches B exactly once;
• A left join B on A.fk = B.pk: each row in A matches B at most once;

So the number of this join’s output rows is equivalent to A’s. if B’s columns is unused or it can be substituted by A’s column that equivalent to B’s column, then B can be pruned from this join.

5 Data Skew

• [Enhancement] Add GroupByCountDistinctDataSkewEliminateRule
• [Enhancement] optimize distinct agg
• [Enhancement] Support [skew] hints in group-by-multi-column-count-distinct-one-column

Given the following case, where column v1 has very limited cardinality, and column v2 has very large cardinality and severely skewed. For example, for v1 = 'x', a great number of distinct values of v2 within this group, but for other values of v1, the number of v2’s distinct value is much more smaller, this kind of data distribution will lead to poor execution performance.

SELECT v1, COUNT(DISTINCT v2) FROM t0 GROUP BY v1

This query can be optimized, as down below, by introducing another group by dimension(hash of v2) to make sure the processing of count distinct can be fully paralleled.

SELECT v1, SUM(CNT_IN_BUCKET) 
FROM (
     SELECT v1, (MURMUR_HASH3_32(v2)%1024) AS BUCKET, COUNT(DISTINCT v1) AS CNT_IN_BUCKET 
     FROM t0
     GROUP BY v1, BUCKET
) a
GROUP BY v1

6 Range Join

• support range optimize in join
• Extend non-equi join optimization to support range predicates

6.1 Reference

• How to speed up range joins joins in Snowflake by 300x
• What Is a Range Join and Why Is It So Fast?
• Range Joins in DuckDB

7 Property

7.1 HashProperty

Shuffle by v1可以满足Shuffle by v1, v2，只不过到了每个节点后，还需要再对v2进行一次shuffle