Cost-based query transformation in Oracle

Enhanced Subquery Optimizations in Oracle

Cost-based query transformation in Oracle

本文介绍Oracle的查询优化框架,

先描述,Oracal分别在RBO和CBO做了哪些事情,为什么要这样做

Heuristic Transformation

先看下RBO的部分,RBO部分的Rule基本都是确定可以带来优化的

Subquery Unnesting

子查询消除,子查询如果用apply的方式的话,文中称TIS,Tuple iteration semantics,基本等同于nested loop方式,比较低效

消除的方法分成两大类,

1. 把子查询 merge 到外部查询里面去

如下面的例子,把exists变成semi-join

查询优化 In Oracle-LMLPHP

查询优化 In Oracle-LMLPHP

2. 产生inline views,或derived table的方式,这种方式会放到CBO里面,所以后面给出例子

Join Elimination

消除无用的Join

其中Q4,dept_id是foreign key,所以每个employee都必须有一个dept,这里join起不到filter的作用

查询优化 In Oracle-LMLPHP查询优化 In Oracle-LMLPHP

Filter Predict Move Around 

Filter下推,尽早的过滤数据,前提是这里的Filter是inexpensive的

查询优化 In Oracle-LMLPHP

Group Pruning

删掉在外层查询中不需要的group

下面的例子,在外层查询中,过滤city,那么city其实就决定了state,country,子查询中的group by 就没有必要了

查询优化 In Oracle-LMLPHP

Cost-Based Transformations

这里讲到重点,看下哪些Transformation应该在CBO里面去做的

Subquery Unnesting

第一个仍然是子查询消除,前面说了,如果是产生inline view的方式,需要用CBO

下面的例子,从Q1到Q10,产生了inline view或派生表 V

查询优化 In Oracle-LMLPHP查询优化 In Oracle-LMLPHP

这里产生inline view的方式不一定会比nested loop的方式更好,如果filter出的row很少,而索引建的很好,很可能nested loop的方式更优

查询优化 In Oracle-LMLPHP

所以这种不确定的情况下,需要CBO来判断

Group-by and Distinct View Merging

右称为,Groupby Pull-up,如果join会大幅降低数据量,那么把groupby上提是核算的,因为groupby一般都是聚合,比较expensive的操作

比如下面Q11的例子,

把计算平均salary的inline view,挪到了外部查询的group by

可以看到把group by移到外面后,group by的field需要加上join key

查询优化 In Oracle-LMLPHP查询优化 In Oracle-LMLPHP

Group-by Placement

对应于上面说的Pull Up,这里是Push Down

查询优化 In Oracle-LMLPHP

Join Predicate Pushdown

把外部查询的join predicate下推到子查询中,

一般套路都是uncorrelation,这里反之,不是所有情况都可以这样下推

查询优化 In Oracle-LMLPHP

例子,

查询优化 In Oracle-LMLPHP查询优化 In Oracle-LMLPHP

Join Factorization

将公共的 join tables 上提

查询优化 In Oracle-LMLPHP

查询优化 In Oracle-LMLPHP

Predicate Pullup

将Expensive的Predicate进行上提,

查询优化 In Oracle-LMLPHP

Set Operator Into Join

查询优化 In Oracle-LMLPHP

Disjunction Into Union All

查询优化 In Oracle-LMLPHP

Framework For Cost-based Transformation

State Space Search Tech

CBO有个关键的问题是,如果Transformation持续变多,那么搜索空间是成指数级别上升的

查询优化 In Oracle-LMLPHP

针对这样的问题,比较可行的方式是引入随机算法,

查询优化 In Oracle-LMLPHP

Oracle的搜索算法如下,

Exhaustive,穷尽法

Iterative,局部最优,每次选择不同的初始点,有点像退火

Linear,动态回归

Two-pass,强行降低搜索空间

查询优化 In Oracle-LMLPHP查询优化 In Oracle-LMLPHP

然后这里比较有借鉴意义,针对不同的search规模,我们应该选用不同的搜索算法

查询优化 In Oracle-LMLPHP

Transformation执行的方式

Oracle中按照顺序的方式去执行Transformations,

这里给出各个分类的执行顺序

查询优化 In Oracle-LMLPHP

当然有些情况下光顺序执行是不够的,

3.3里面提到了,

Interleaving方式,有些rule需要交叉的执行

查询优化 In Oracle-LMLPHP

举得例子是,Unnesting和View merging

查询优化 In Oracle-LMLPHP

Juxtaposition的方式,

查询优化 In Oracle-LMLPHP

Enhanced Subquery Optimizations in Oracle

本文讨论Oracle对于子查询的优化方法

Subquery Coalescing

子查询合并,把多个子查询合并成一个

这里提出,Container和Contained的概念

直观上,如果A contain B

A and B,就可以remove A

A or B,就可以removeB

查询优化 In Oracle-LMLPHP

Coalescing Subqueries of The Same Type

SameType,类型一样,要不都是Exist,要不都是Not Exist

和上面说的一致,只是这里加上Exist和Not Exist,有点绕

总之conjunction留小的,contained,disjunctive留大的,container

查询优化 In Oracle-LMLPHP

对于不满足Containment Property的子查询,仍然可能进行coalescing,

只要他们除了filter和predicates以外是equivalent的

这个很直观,因为如果只是Predicate不一样,是可以合并的

查询优化 In Oracle-LMLPHP

例子,虽然没有containment关系,但是仅仅只有predict不一样

查询优化 In Oracle-LMLPHP

可以看到,可以直接把Exists间的OR,转化为predict之间的OR,很直觉

查询优化 In Oracle-LMLPHP

Coalescing Subqueries of Different Type

不同的Type,Exist和Not Exist之间的

可以看TPC-H的Q21,

两个子查询是满足Containment关系的,但是类型不一样

这里的感觉就要从Container中挖去Contained的那块

查询优化 In Oracle-LMLPHP

是这样转换的,

用Having,对满足条件的case求sum,然后过滤,好tricky

查询优化 In Oracle-LMLPHP

Coalescing and Other Transformations

Q5加上外层的Join就是Q6

查询优化 In Oracle-LMLPHP

这里做的转换是,View merging,就是Groupby Pullup

但是GroupBy的Pull up还是Push down,需要通过cost-based来决定

查询优化 In Oracle-LMLPHP

Subquery Removal Using Window Functions

Oracle有窗口函数,可以用于替换子查询,论文里说,对于TCP-H,性能会有10倍提升

这里有subsume的概念,outer query包含子查询中的所有tables和predicates

查询优化 In Oracle-LMLPHP

这个例子,满足Subsume关系,在子查询中主要为了做AGG

查询优化 In Oracle-LMLPHP

所以这里用窗口函数就可以简单的remove掉子查询

查询优化 In Oracle-LMLPHP

Correlated Subsumed Subquery

相关子查询,在TCP-H中的代表是Q2,Q17

Q2,子查询中主要为了求min

查询优化 In Oracle-LMLPHP查询优化 In Oracle-LMLPHP

用窗口函数,改造后

查询优化 In Oracle-LMLPHP

对于Q17,微软提出的是SegmentApply的方案,这里用窗口函数改造后,

底下关于Duplicate rows,没太懂

说是窗口函数必须within a view,没看出和上面的区别

查询优化 In Oracle-LMLPHP

Uncorrelated Subsumed Subquery

非相关子查询,TCP-H,Q15

查询优化 In Oracle-LMLPHP查询优化 In Oracle-LMLPHP

用窗口函数转化为,因为是非相关子查询,所以OVER里面是空的,不需要PBY

查询优化 In Oracle-LMLPHP


05-28 09:45