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 表上的列的谓词(连接条件)。
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 必须是严格的筛选条件
( 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)
( 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 行记录)
规则:
“简单”子连接:不包含通用表达式(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 的查询重写包括了子查询优化、等价谓词重写、视图重写、条件简化、连接消除和嵌套连接消除等。各种逻辑优化技术依据关系代数和启发式规则进行。