SQL 优化的过程可以分为逻辑优化和物理优化两个部分。逻辑优化主要是基于规则的优化，简称 RBO(Rule-Based Optimization)。物理优化会为逻辑查询计划中的算子选择某个具体的实现，需要用到一些统计信息，决定哪一种方式代价最低，所以是基于代价的优化 CBO(Cost-Based Optimization)。
本文将主要介绍Kingbase数据库的逻辑优化规则。
- 准备数据：
-
- create table big(id int , bname varchar(20));
-
- create table middle(id int , bname varchar(20));
-
- create table small(id int , sname varchar(20));
-
- insert into big select generate_series(1 , 1000), dbms_random.string('l',5) ;
-
- insert into middle select generate_series(501 , 1000), dbms_random.string('l',5) ;
-
- insert into small select generate_series(951 , 1050), dbms_random.string('l',5) ;
逻辑优化分类
- [逻辑优化分类]
- |选择下推
- |谓词下推
- |逻辑分解优化 ⇒ |连接顺序交换
- | |等价类推理
- 逻辑优化 ⇒
- | |子查询提升
- |逻辑重写优化 ⇒ |子连接提升
- |表达式预处理
- |外连接消除
逻辑分解优化
选择下推
连接条件直接下推到自己所涉及的基表上。
- demo=# explain analyze select * from big b left join small s on b.id = s.id and s.id = 1000;
- QUERY PLAN
- --------------------------------------------------------------------------------------------------------------
- Hash Left Join (cost=2.26..22.02 rows=1000 width=20) (actual time=0.027..0.228 rows=1000 loops=1)
- Hash Cond: (b.id = s.id)
- -> Seq Scan on big b (cost=0.00..16.00 rows=1000 width=10) (actual time=0.010..0.079 rows=1000 loops=1)
- -> Hash (cost=2.25..2.25 rows=1 width=10) (actual time=0.012..0.013 rows=1 loops=1)
- Buckets: 1024 Batches: 1 Memory Usage: 9kB
- -> Seq Scan on small s (cost=0.00..2.25 rows=1 width=10) (actual time=0.008..0.010 rows=1 loops=1)
- Filter: (id = 1000)
- Rows Removed by Filter: 99
- Planning Time: 0.077 ms
- Execution Time: 0.276 ms
- (10 行记录)
谓词下推
谓词下推 Predicate Pushdown(PPD):简而言之,就是在不影响结果的情况下,尽量将过滤条件提前执行。
- demo=# explain analyze select * from big b left join small s on b.id = s.id and b.id = 1000;
- QUERY PLAN
- ------------------------------------------------------------------------------------------------------------------
- Hash Left Join (cost=3.25..24.25 rows=1000 width=20) (actual time=0.035..0.304 rows=1000 loops=1)
- Hash Cond: (b.id = s.id)
- Join Filter: (b.id = 1000)
- Rows Removed by Join Filter: 49
- -> Seq Scan on big b (cost=0.00..16.00 rows=1000 width=10) (actual time=0.010..0.091 rows=1000 loops=1)
- -> Hash (cost=2.00..2.00 rows=100 width=10) (actual time=0.020..0.020 rows=100 loops=1)
- Buckets: 1024 Batches: 1 Memory Usage: 13kB
- -> Seq Scan on small s (cost=0.00..2.00 rows=100 width=10) (actual time=0.004..0.009 rows=100 loops=1)
- Planning Time: 0.078 ms
- Execution Time: 0.365 ms
- (10 行记录)
规则：
1：连接条件下推之后会变成过滤条件，过滤条件下推之后仍然是过滤条件。
2：如果连接条件引用了 Nonnullable-side 的表，那么连接条件不能下推；如果连接条件只引用了 Nullable-side 的表，那么连接条件可以下推。
3：如果过滤条件只引用了 Nonnullable-side 的表，那么这个过滤条件能够下推到表上；如果过滤条件引用了 Nullable-side
的表且过滤条件是严格的，那么会导致外连接消除，外连接消除之后变成内连接，过滤条件也是能下推的。
连接顺序交换
优化器对表的连接顺序进行重新排列。
- demo=# explain analyze select * from big b left join middle m on true left join small s on m.id = s.id ;
- QUERY PLAN
- ------------------------------------------------------------------------------------------------------------------------------
- Nested Loop Left Join (cost=3.25..6281.38 rows=500000 width=30) (actual time=0.043..84.884 rows=500000 loops=1)
- -> Seq Scan on big b (cost=0.00..16.00 rows=1000 width=10) (actual time=0.009..0.200 rows=1000 loops=1)
- -> Materialize (cost=3.25..16.62 rows=500 width=20) (actual time=0.000..0.020 rows=500 loops=1000)
- -> Hash Left Join (cost=3.25..14.12 rows=500 width=20) (actual time=0.029..0.135 rows=500 loops=1)
- Hash Cond: (m.id = s.id)
- -> Seq Scan on middle m (cost=0.00..8.00 rows=500 width=10) (actual time=0.004..0.036 rows=500 loops=1)
- -> Hash (cost=2.00..2.00 rows=100 width=10) (actual time=0.020..0.020 rows=100 loops=1)
- Buckets: 1024 Batches: 1 Memory Usage: 13kB
- -> Seq Scan on small s (cost=0.00..2.00 rows=100 width=10) (actual time=0.003..0.008 rows=100 loops=1)
- Planning Time: 0.149 ms
- Execution Time: 99.958 ms
- (11 行记录)
规则：
假设 A、B、C 为参与连接的基表，Pab 代表引用了 A 表和 B 表上的列的谓词(连接条件)。
- LEFT JOIN 相关的连接顺序交换等式：
1.1 等式 1： ( A left join B on (Pab)) inner join C on (Pac) = ( A inner join C on (Pac)) left join b on (Pab)
1.2 等式 2： ( A left join B on (Pab)) left join C on (Pac) = ( A left join C on (Pac)) left join b on (Pab)
1.3 等式 3： ( A left join B on (Pab)) left join C on (Pbc) = A left join ( B left join C on (Pbc)) on (Pab)
&Pbc 必须是严格的筛选条件
- Semi Join 有关的连接顺序交换等式：
( A semi Join B on (Pab)) innerjoin/leftjoin/semijoin/antijoin C on (Pac) =
( A innerjoin/leftjoin/semijoin/antijoin C on (Pac)) semi Join B on (Pab)
- Anti Join 有关的连接顺序交换等式：
( A anti Join B on (Pab)) innerjoin/leftjoin/semijoin/antijoin C on (Pac) =
( A innerjoin/leftjoin/semijoin/antijoin C on (Pac)) anti Join B on (Pab)
等价类推理
等值查询时，检索条件a.id = b.id and a.id = 1 ,会将检索条进行推理为a.id = 1 and b.id = 1
- demo=# explain analyze select * from big b ,small s where b.id = s.id and b.id = 100;
- QUERY PLAN
- --------------------------------------------------------------------------------------------------------
- Nested Loop (cost=0.00..20.76 rows=1 width=20) (actual time=0.271..0.272 rows=0 loops=1)
- -> Seq Scan on big b (cost=0.00..18.50 rows=1 width=10) (actual time=0.046..0.261 rows=1 loops=1)
- Filter: (id = 100)
- Rows Removed by Filter: 999
- -> Seq Scan on small s (cost=0.00..2.25 rows=1 width=10) (actual time=0.008..0.008 rows=0 loops=1)
- Filter: (id = 100)
- Rows Removed by Filter: 100
- Planning Time: 0.123 ms
- Execution Time: 0.330 ms
- (9 行记录)
逻辑重写优化
Kingbase数据库基于子查询所在的位置和作用的不同，将子查询细分成了两类，一类称为子连接(SubLink)，另一类称为子查询(SubQuery)。通常而言，
如果它是以“表”的方式存在的，那么就称为子查询，如果它以表达式的方式存在，那么就称为子连接。
子连接和子查询的区别：出现在 FROM 关键字后的子句是子查询语句，出现在 WHERE/ON 等约束条件中或投影中的子句是子连接语句。
相关子连接和非相关子连接：
相关子连接：指在子查询语句中引用了外层表的列属性，这就导致外层表每获得一个元组，子查询就需要重新执行一次。
非相关子连接：指子查询语句是独立的，和外层的表没有直接的关联，子查询可以单独执行一次，外层表可以重复利用子查询的执行结果。
子查询提升
- demo=# explain analyze select * from big b ,(select * from small s where s.id > 100) s where b.id = s.id ;
- QUERY PLAN
- ------------------------------------------------------------------------------------------------------------------
- Hash Join (cost=3.50..24.25 rows=100 width=20) (actual time=0.203..0.220 rows=50 loops=1)
- Hash Cond: (b.id = s.id)
- -> Seq Scan on big b (cost=0.00..16.00 rows=1000 width=10) (actual time=0.011..0.089 rows=1000 loops=1)
- -> Hash (cost=2.25..2.25 rows=100 width=10) (actual time=0.029..0.029 rows=100 loops=1)
- Buckets: 1024 Batches: 1 Memory Usage: 13kB
- -> Seq Scan on small s (cost=0.00..2.25 rows=100 width=10) (actual time=0.006..0.016 rows=100 loops=1)
- Filter: (id > 100)
- Planning Time: 0.091 ms
- Execution Time: 0.245 ms
- (9 行记录)
子连接提升
将子连接提升为子查询。
- demo=# explain analyze select * from big b where exists (select * from small s where b.id = s.id) ;
- QUERY PLAN
- -----------------------------------------------------------------------------------------------------------------
- Hash Semi Join (cost=3.25..22.99 rows=100 width=10) (actual time=0.168..0.180 rows=50 loops=1)
- Hash Cond: (b.id = s.id)
- -> Seq Scan on big b (cost=0.00..16.00 rows=1000 width=10) (actual time=0.010..0.073 rows=1000 loops=1)
- -> Hash (cost=2.00..2.00 rows=100 width=4) (actual time=0.025..0.025 rows=100 loops=1)
- Buckets: 1024 Batches: 1 Memory Usage: 12kB
- -> Seq Scan on small s (cost=0.00..2.00 rows=100 width=4) (actual time=0.005..0.012 rows=100 loops=1)
- Planning Time: 0.078 ms
- Execution Time: 0.200 ms
- (8 行记录)
规则：
- EXISTS 类型的相关子连接会被提升(需要是“简单”的子连接 )
- EXISTS 非相关子连接会形成子执行计划单独求解
- ANY 类型的非相关子连接可以提升(需要是“简单”的子连接)，且可以通过物化的方式进行优化
- ANY 类型的相关子连接目前还不能提升
- 相关子连接提升上来之后可以避免那种 O(N^2) 式的子计划的执行方式(参照上面的借助参数执行的情况)，例如提升上来之后借助哈希表实现优化
- 不能提升的一种情况是非相关子连接，因为只需要执行一次就能反复利用它的执行结果
- 另一种不能提升的情况是对于外连接，它需要满足的是和 Nullable 端相关，而非和 Nonnullable 端相关
“简单”子连接：不包含通用表达式(CTE), 集合操作、聚集操作、HAVING 子句等的子连接叫作“简单”子连接。
注意：
子句中如果包含通用表达式(CTE)，子连接不能提升。如果子句中包含集合操作、聚集操作、HAVING子句等，子连接不能提升，否则子连接中的子句进行简化。
表达式预处理
对表达式进行处理，简化约束条件
- demo=# explain analyze select * from big b where b.id > 100 and 1 = 2;
- QUERY PLAN
- ------------------------------------------------------------------------------------
- Result (cost=0.00..0.00 rows=0 width=0) (actual time=0.001..0.001 rows=0 loops=1)
- One-Time Filter: false
- Planning Time: 0.040 ms
- Execution Time: 0.011 ms
- (4 行记录)
外连接消除
通过对连接条件限制，消除外连接，转换为内连接处理
- demo=# explain analyze select * from big b left join small s on b.id = s.id where s.id is not null ;
- QUERY PLAN
- ------------------------------------------------------------------------------------------------------------------
- Hash Join (cost=3.25..24.00 rows=100 width=20) (actual time=0.278..0.292 rows=50 loops=1)
- Hash Cond: (b.id = s.id)
- -> Seq Scan on big b (cost=0.00..16.00 rows=1000 width=10) (actual time=0.010..0.134 rows=1000 loops=1)
- -> Hash (cost=2.00..2.00 rows=100 width=10) (actual time=0.037..0.037 rows=100 loops=1)
- Buckets: 1024 Batches: 1 Memory Usage: 13kB
- -> Seq Scan on small s (cost=0.00..2.00 rows=100 width=10) (actual time=0.020..0.028 rows=100 loops=1)
- Filter: (id IS NOT NULL)
- Planning Time: 0.148 ms
- Execution Time: 0.339 ms
- (9 行记录)
总结：
Kingbase数据库逻辑优化方式，通过找出SQL等价的变换形式让 SQL 执行效率更高效。这些规则背后的原理就是关系代数的等价变换，其中典型的规则包括：列剪裁，谓词下推等,对查询进行重写。SQL 的查询重写包括了子查询优化、等价谓词重写、视图重写、条件简化、连接消除和嵌套连接消除等。各种逻辑优化技术依据关系代数和启发式规则进行。