Cost-based query transformation in Oracle

这篇paper主要介绍了Oracle从10g开始引入的CBQT(Cost Based Query Transformation)框架。虽然以Oracle历来的风格，无法期待它在paper中讨论很多细节，不过这篇还是可以让我们一窥Oracle对于query rewrite的处理思路和很多非常实用的query rewrite模式，对于开发优化器的同学很有参考意义。

值得一提的是，PolarDB目前也在做这方面的工作，而主要的参考正是这篇paper。此外这篇paper的思路和MemSQL optimizer中对query rewrite的处理思路非常接近，关于MemSQL optimizer的介绍可以看下这篇文章。

介绍

传统上，查询的等价变换有两种主流的处理思路。

• 一种是类似DB2这种老牌关系数据库的2-pass方式，将查询优化分为2个阶段：基于heuristic的RBO + 基于cost的CBO，而query rewrite则发生在RBO阶段。这种方案有2个主要的问题：
  

1. 完全基于手写代码的查询变换，使得对于transformation的应用不够灵活，也不容易扩展新的变换形式。如果你看过MySQL/PG的代码，就能深刻的体会这一点，从代码逻辑上就写死了：a变换 -> b变换 -> ....，想加入新的变换x，就需要手工实现新变换逻辑和原有代码结构的融合，非常麻烦，此外没法做a -> x -> b这样的尝试，只能依次完成。这对于复杂度更高的商业数据库来说，是个更突出的问题。
   
2. 很多变换并不一定使得查询更优，因此需要基于代价进行评估。
   

• 为解决以上问题，Graefe提出了Volcano/Cascades的优化器模型，在做plan enumeration的过程中同时考虑query transformation，但由于很多rewrite复杂度很高（or-expansion/subquery unnesting...)，如果在search的过程中同时做这些变换，会极大扩展search space，导致本来就在优化时间上饱受诟病的Cascades框架更为不可控。因此一般情况下，实际实现中(calcite/orca)只会考虑某些特定的不很复杂的transformation rules加入search过程中，而把其他的rewrite在前面的一个阶段提前完成，等于退化回了RBO -> CBO的模式。
  

Oracle原本优化流程也是经典的logical -> physical的2-pass，logical是基于heuristic的query rewrite，physical则是以query block为单位计算cost，选最优的access path / join order / join method等。而针对以上提到的2-pass的缺点，这篇paper提出了新的解决思路，可以在不修改physical optimizer的同时，实现对rewrite进行代价计算。

其基本思想是，将query rewrite后的形态描述为一个state，因此多种rewrite的可能组合，会形成一个state space，并考虑如何在state space中做search，以及当rewrite之间有相互影响时如何处理。

Oracle中的transformation(rewrite)分为heuristic / cost 两类，前者认为总是更优，因此一旦可能一定apply，后者则不一定更优，需要基于代价做决定。

transformation基于query tree(逻辑)，而不是operator tree(物理)，query tree -> operator tree在physical optimization过程中发生。paper中列举了一些Oracle中使用的heuristic-based/cost-based的transformation。

Heuristic Transformation

Oracle中的rule-based rewrite的基本的目标是： 消除无用的SQL construct (query block/join…)，或者尽早的过滤掉无用数据(filter predicate pushdown/projection pushdown …)。

一般认为在消除query block时(subquery unnesting/view merging），通过将内外层的join tables合并到一起，会形成新的join order可能，可能找到更优的plan，因此如果在变换过程中，不涉及到group by/distinct的引入/复制/移动，则变换总是更优的。

Subquery unnesting

如果不做unnesting，根据相关子查询的语义，会遵循类似NestedLoop的执行方式，对外层每一行数据，带入相关变量值执行一遍子查询。

Oracle几乎能对所有subquery做unnesting，但有几个例外

1. subquery在OR条件中
   
2. 某些ALL subquery有多个投影列，且列中包含NULL值(10g中还不支持null-aware anti join，11g中支持）
   
3. subquery的相关性不在本层query block中
   

对于unnesting的处理有两种方案，一种是转换为inline view(MySQL中的derived table)，一种是将subquery merge到外层query block中。前者是基于代价决定，后者则基于规则。

这里说的merge适用于SPJ(Select-Project-Join) subquery，MySQL也实现了相同的merge机制，无论对于view还是subquery。

select /*+ qb_name (e1_outer) */ * from
emp e1
where 
salary >
(select/*+ qb_name (e2_inner) */ avg(salary)
 from emp e2, dept d1
where e1.dept_id = e2.dept_id and
e2.dept_id = d1.dept_id and
  exists
 (select /*+ qb_name (l1_inner) */ 1
from locations l1
          where l1.location_id=d1.location_id))
  and e1.hire_date > sysdate - (10*365);
=>
select /*+ qb_name (e1_outer) */ * from
emp e1
where 
salary >
(select/*+ qb_name (e2_inner) */
avg(salary) from
emp e2, dept d1, locations l1
where e1.dept_id = e2.dept_id and
 e2.dept_id = d1.dept_id and
 l1.location_id S= d1.location_id)
and e1.hire_date > sysdate - (10*365));
这里S= 表示semi-join的join condition

merge到外层后可以形成semi-join/anti-join/null-aware anti-join。对于semi-join，Oracle也有类似MySQL的first match的执行机制，或者将内层表做distinct去重物化，然后转换为inner join（类似MySQL SJM scan）。这些都是在物理优化时基于代价决定的具体执行方式。

Join elimination

对于主外键join，如果query中不涉及主表的任何字段，可以去掉与主表的join。

SELECT e.name, e.salary
FROM department d, employees e
WHERE d.dept_id = e.dept_id;
=>
SELECT e.name, e.salary
FROM employees e;

以上查询中，e.dept_id是reference d.dept_id的外键，而投影列中不包含d的任何列，department表可以被消除。

注意：由于NULL值是不会join上的，如果e.dept_id可能为NULL值，则需要加入“e.dept_id is not NULL”来消除列中的NULL值。

Filter predicate move around

例如把inexpensive的filter推入到view中，尽早过滤无用数据（MySQL在8.0.23中也支持了该功能）。这里专门指inexpensive的谓词，因为尽早做evaluation意味着可能需要做更多次，因此谓词计算本身成本不能太高。

Group pruning

如果在外层的query block中，有对内层的group by列的filter predicate，可以把filter条件尽可能推入到离group by view最近的query block，尽早过滤无用的group，例如：

SELECT sum_sal, country_id, state_id, city_id
FROM (SELECT SUM(e.salary) sum_sal,
      l.country_id, l.state_id, l.city_id
      FROM employees e, department d, locations l
      WHERE d.dept_id = e.dept_id and d.location_id = l.location_id
      GROUP BY ROLLUP (country_id, state_id, city_id)
WHERE city_id = 'San Francisco';

这个rewrite是在“Filter predicate move around”之后进行，因此可以将city_id移入到inline view里面，而在city_id列上的过滤条件可以过滤掉rollup产生的group(country_id)和group(country_id, state_id)。

Cost-based transformation

有很多的变换，由于影响因素很多，无法直接确定其是否会改善执行计划，因此需要计算必要的cost信息来决定。

Subquery unnesting

仍然是对相关子查询的处理，就像上一节中提到的，如果EXIST/NOT EXIST中涉及的是多个表，或者是带有aggregation的相关子查询，则可以转为inline view的形式，但这种转换不一定更优。

不转换更优：如果外层query的行数比较少（有选择性很强的过滤条件），且内层在相关列上有index，则nest-loop index lookup的执行方式很有可能更优。

转换更优： 转换后，inline group by view的分组+聚集只需要计算一次。

在Oracle 10g引入CBQT前，这种转换是基于heuristic的，只要外层query有filter predicate，且内层在相关列上有索引，就不做unnesting的转换。

select /*+ qb_name (e1_outer) */ * from
emp e1
where 
salary >
(select/*+ qb_name (e2_inner) */ 
avg(salary) from
emp e2, dept d1, locations l1
where e1.dept_id = e2.dept_id and
 e2.dept_id = d1.dept_id and
 l1.location_id S= d1.location_id)
and e1.hire_date > sysdate - (10*365));
=>
select /*+ qb_name (e1_outer) */ e1.* from
emp e1,
 (select/*+ qb_name (e2_inner) */
 avg(salary) avg1, 
e2.dept_id item_0
         from emp e2, dept d1, locations l1
where e2.dept_id = d1.dept_id and
l1.location_id S= d1.location_id
         group by e2.dept_id) vw_sq_1
where e1.salary > vw_sq_1.avg1
 and
e1.hire_date > sysdate - (10*365)
and e1.dept_id = vw_sq_1.item_0;

上面的示例SQL中，通过将在where条件中的标量相关子查询转换为一个inline view vw_sq_1，来实现相同的语义，即

原始语义：

将外层每一行的e1.dept_id带入内层中，对应内层e2的相关列dept_id的每一个特定值（构成一个分组），做聚集计算。

转换后等价语义：

将内层e2中所有针对dept_id的各个分组，各自聚集，结果先物化为一个view，再与外层按照相关列dept_id做join。

这个优化在PolarDB和MySQL社区也分别进行了实现，MySQL社区的主要目标是为了Heatwave分析引擎，由于它无法支持相关子查询，因此通过这种转换来消除。而PolarDB则是独立实现为一种优化，并与自研的CBQT框架结合来决定其最优性。

Group by/distinct view merging

上一节描述的view merging主要针对SPJ view，因此是基于规则的，而如果view中包含group by，则需要基于代价决定。

本质上就是group by pullup，由group by -> join变为join -> group by，这使得优化器可以考虑更多的join可能和更多access path，同时延迟了group by + aggregation的计算。

不转换更优： aggregation在view中时，聚集行数不多，且参与外层join的行数明显减少。

转换更优：  aggregation在join之后才做，join + filter减少了参与聚集的行数。

两者之间存在trade-off，因此需要基于数据的具体情况，计算代价决定。

select /*+ qb_name (e1_outer) */ e1.* from
emp e1,
 (select/*+ qb_name (e2_inner) */
 avg(salary) avg1, 
e2.dept_id item_0
         from emp e2, dept d1, locations l1
where e2.dept_id = d1.dept_id and
l1.location_id S= d1.location_id
         group by e2.dept_id) vw_sq_1
where e1.salary > vw_sq_1.avg1
 and
e1.hire_date > sysdate - (10*365)
and e1.dept_id = vw_sq_1.item_0;
=>
select /*+ qb_name (e1_outer) */ e1.* from
emp e1, emp e2, dept d1, locations l1
where 
e1.dept_id = e2.dept_id and
      e1.hire_Date >sysdate@!-3650 and
e2.dept_id = d1.dept_id and
      l1.location_id S= d1.location_id
Group by 
e2.Dept_id, e1.hire_date, e1.salary , e1.dept_id, 
e1.emp_name, e1.emp_id
Having e1.salary > avg(e2.salary);

如上例所示，如果把视图vw_sq_1做merge，需要把外层表（e1）的唯一列加入到group by key中，本例中是e1.emp_id，而由于e1.* 在投影列中都需要，因此都加入到group by key中，当然由于存在functional dependency:

e1.emp_id-> e1.*

所以从正确性的角度是不需要这些列的，只是后续计算的需求而已。

关于group by pullup的正确性保证，请参看 ，后续我会专门写文章介绍这篇paper。

Join predicate pushdown

这个是Oracle比较特殊的一种transform，通过把外层table和view的join条件，推入到view当中，引入了相关性！变成了一个相关view(lateral table)，这样使得查询可以按照之前提到的Nested-loop index lookup的方式来执行，反而更为高效。

从语义上，和上上节提到的subquery unnesting是相反的流程。因此如果view中有group by，且join条件就是在内层的所有group by列上，则内层的group by可以消除！（注意：aggregation不能消除）

SELECT e1.employee_name, j.job_title,
       e2.employee_name as mgr_name
FROM employee e1, job_history j, employee e2,
     (SELECT DISTINCT dept_id,
      FROM departments d, locations l
      WHERE d.loc_id = l.loc_id and l.country_id in ('US', 'UK')) V
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e1.mgr_id = e2.emp_id and
      e2.dept_id = V.dept_id;
=>
SELECT e1.employee_name, j.job_title,
       e2.employee_name as mgr_name
FROM employee e1, job_history j, employee e2,
     (SELECT dept_id,
      FROM departments d, locations l
      WHERE d.loc_id = l.loc_id and l.country_id in ('US', 'UK') 
      and e1.dept_id = e2.dept_id) V
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e1.mgr_id = e2.emp_id;

可以看到，通过将外层join条件e1.dept_id = e2.dept_id，下推进到view当中，view具有了相关性，同时由于dept_id就是内层的group by列(distinct)，可以把这个group by消除！

这时如果在department.dept_id上有主键索引且外层join的行数也不是很多，则可以高效执行，但这需要基于统计信息+代价决定。

在Oracle中，这种join predicate pushdown，可以应用于各种view中，包括mergeable view或者unmergeable view。

Group by placement

前面已经提到了group by pullup，这里的placement专指group by pushdown，推入到join的下方，相当于eager aggregation，是group by view merging的反过程。

在Oracle 10g中，对group by的处理是先做pullup，然后再考虑各种可能的pushdown（原本在query block中就存在group by的，则不考虑pushdown到这个query block中，避免重复），在做pushdown的变换时，可能会pushdown到多层中，导致产生多个group by view。

select avg(salary), dept_id item_1
from
emp e2, 
dept d1, 
locations l1
where 
e2.dept_id = d1.dept_id and
      d1.location_id S= l1.lcation_id
group by dept_id;

这个原始查询可以用下图表示

通过不同的pushdown位置，可以产生很多种变换结果：

select vw_gbc_2.dept_id, avg_salary
from
( select avg(salary) avg_salary, dept_id item_1
      from emp e2
      group by dept_id) vw_gbc_2,
dept d1,
locations l1
where
 vw_gbc_2.dept_id = d1.dept_id and
      d1.location_id = l1.location_id;

可见group by 被推导了一个first join table e2上。

select 
sum(e2.salary*vw_gbf_3.item_2)/
       sum(decode(e2.salary, null, 0, vw_gbf_3.item_3))
       avg(salary), 
e2.dept_id item_1
from
( select d1.dept_id item_1, count(*) item_2,
count(*) item_3
from dept d1, locations l1
      where l1.location_id = d1.location_id
      group by d1.dept_id) vw_gbf_3,
emp e2
where e2.dept_id = vw_gbf_3.item_1
group by e2.dept_id;

这次group by 被推导了后面两个表的join上方，形成一个view vw_gbf_3。但由于原始SQL是针对e2.dept_id做分组，而不是针对dept join locations的结果，因此在group by推入的同时，外部仍然需要做一次group by e2.dept_id，来保证结果正确性，有关正确性推导请参考 。

Join Factorization

这也是Oracle比较独特的一种transformation。把在UNION ALL的各个branch中，都参与join的common tables，从UNION ALL中提取出来，相当于提取公因子。这些common table join本身就只需要执行一次，而原来的UNION ALL则变为一个view!

SELECT e.first_name, e.last_name, job_id,
       d.department_name, l.city
FROM employee e, departments d, locations l
WHERE e.dept_id = d.dept_id and
      d.location_id = l.location_id
UNION ALL
SELECT e.first_name, e.last_name, j.job_id,
       d.department_name, l.city
FROM employee e, job_history j, departments d, locations l
WHERE e.emp_id = j.emp_id and
      j.dept_id = d.dept_id and
      d.location_id = l.location_id
=>
SELECT V.first_name, V.last_name, V.job_id,
       d.department_name, l.city
FROM departments d, locations l,
     (SELECT e.first_name, e.last_name,
             e.job_id, e.dept_id
      FROM employees e
      UNION ALL
      SELECT e.first_name, e.last_name,
             j.job_id, j.dept_id
      FROM employees e, job_history j
      WHERE e.emp_id = j.emp_id) V
WHERE d.dept_d = V.dept_id and
      d.location_id = l.location_id;

上例中，common tables就是

departments d, locations l WHERE d.location_id = l.location_id

注意这里common table是指 table + join条件一起，需要table + join条件都相同才行。

Predicate pullup

将view中的expensive的predicate上拉到view外面，是filter predicate pushdown的反向操作。这里只对expensive的谓词做上拉(Oracle中，expensive指带有sp/udf/subquery的谓词！)。

在10g中，这种变换只在如下情况才会考虑：

1. 外层query中有针对rownum的过滤谓词
   
2. 内层view中包含expensive predicate和blocking operator(group by/order by)
   

只所以有这样的前提是认为外层的rownum可以有效过滤join产生的数据，因此再做谓词计算时，可以明显减少计算量。(为啥要有blocking operator??)

SELECT *
FROM (SELECT document_id
      FROM product_docs
      WHERE contains(summary, "optimizer", 1) > 0
      ORDER BY create_date) V
WHERE rownum < 20;
=>
SELECT *
FROM (SELECT document_id
      FROM product_docs
      ORDER BY create_date) V
WHERE contains(summary, "optimizer", 1) > 0 and
      rownum < 20;

Set operator into join

把minus/intersection转换为anti join/inner join的形式，但语义上两者有2个区别

1. 集合操作中，null值的比较是可以相等的，join中则是不等的
   
2. set操作是去重的，join则不去重，因此如果转换为join，去重操作是在join之前做，还是join之后做，要基于cost决定！
   

如上图所示，左侧是原始的query，其中2个近似的子查询做集合的交集操作。而右侧则是转换之后的等价结果join query。

可以看到，中间方框中描述了2个原始集合做交集操作时所需要的，在各自投影列上的对应相等性，sys_op_map_nonull这个函数用来起到NULL值比较也可相等的作用。而下方方框则是原有查询中已有的过滤条件，把他们组合在了一起。

Disjunction into UNION ALL

也就是常说的OR-expansion，于 OR 条件的各个部分，各自转换为UNION ALL的一个branch进行计算。

不转换更优： 如果OR条件很多，则会产生大量分支，等于查询反复执行多次。或者单个branch本身就有data skew，是所有branch中的短板，可能效果和执行OR会差不多。

转换更优：disjunction只能作为post-filter对join结果做过滤，因此会形成笛卡尔积。此外如果不再有or条件，则可以更好的使用index来加速对表的访问。

CBQT framework

基本组件

如上图所示，其包含的主要组件：

1. transformation的算法
   
2. 由于各种transformation应用于query tree中的各个elements，形成的state space
   
3. 在state space中做search的算法
   
4. 对query tree的整体或部分，做deep copy，相对于生成新的query tree来尝试
   
5. 调用physical optimizer计算cost
   
6. 记录最终transform决策的directives和cost annotation
   

总体的执行流程是：

1. 对每个特定transformation，在query tree中以bottom-up的方式，考虑可能影响的各个element（比如query block/view/predicates…），形成一个state space并基于某个search算法进行搜索。
   
2. 顺序考虑下一个transformation，针对其所影响的element，再次search。
   
3. 除非transformation之间有相互影响，否则依次考虑和应用各个transform : T1 -> T2 -> T3….
   

针对某一个transformation T的具体search过程如上图，也就是针对每一个特定的state:

1. deep copy target query tree，copy必要的query block或element。
   
2. 应用目标transform
   
3. physical optimizer计算该state下的cost
   
4. 针对当前search选出的最优transform决策，记录在directive中，传递给original query tree
   

Search算法

即使是一个transformation，对可能涉及的N个object需要进行组合考虑（例如N个view都可能做group by pullup这一个变换)，也会有 种可能选择，可以用一个N bit的array来表示。

如果是M个transformations，组合就会非常多，可以用M * N的bit matrix来描述。transform之间如果有相互影响，则会更加复杂。

参考在做大量table的join permutation时，为了optimization时间的考虑，经常会采用随机化/贪婪算法，来减少优化时间，获得一个相对不错的join order，在state space中的搜索也是类似的思路，可以有4种search方式：

1. 穷尽式

考虑所有可能组合，这种无疑复杂度最高，但state space覆盖最全。

2. 迭代式

为了避免穷尽式的搜索占用太多时间，可以采用这种iterative的方法对state space做一些剪枝，思路类似于random walk，从一个intial state出发，不断考虑使cost更低的state，从而在state space中追求一个局部cost最低点。然后再从另一个intial state出发，再做尝试，直到满足阈值要求，或迭代次数足够多。

3. 线性

借鉴Dynamic programming的思路，每个子问题就是N个object的子集，选中子集的最优后，就不再改变，加入一个新的object再考虑新object的决策，因此一共需要考虑N+1次即可，这种比较适合于object之间没有关联的情况。

4. 2-pass

这种是最简的，对于当前transformation，要么全部应用于N个object，要么全部不应用，只考虑这两种情况。

注意：这里描述的一个state space search，是针对 [1 transformation + N object] 的组合

可以看到，从1 -> 4，搜索的复杂度逐渐降低，具体选择哪种在优化中自适应决定，主要取决于所涉及object的数量，transformation自身的特性，以及整个query的复杂度等。

Transformation interaction

一般情况下transformation之间无关联，因此可以顺序应用+search state space。但如果有关联则可能会影响获取最优plan，有如下两种情况:

依赖 (Interleaving)

例如subquery unnesting 产生 view，才可能应用view merging。

定义上，如果一个transform的发生要取决于前面的transform必须应用，就可能出现unnesting时不是最优的，但view merging后形成了最优Plan，而由于独立考虑unnesting时不最优就没有做，会导致错过全局最优plan，因此需要interleave的考虑，一次性考虑多个transformation的结合！

互斥(juxtaposition)

例如view merging 导致view消失，无法执行join predicate pushdown。

定义上，如果一个transform的发生阻碍了后续的transform的应用，可能导致后续的transformtion被漏掉了，因此需要在考虑前序的transform时，同时考虑后面有互斥关系的transform，并列考虑多种可能，从中选一个！

这两种相互关系会增加在search state space时的复杂度，但可以用如下方法缓解：

如果被依赖的transform发生了，则后续的transform可以推迟到顺序应用时被考虑，而不会被漏掉，这时就不用提前考虑了。

如果互斥的transform没有被选中，则后续被阻碍的transform也可以推迟到顺序应用时考虑，而不会被漏掉，这时也就不用提前考虑了。

Optimization性能优化

这种复杂的CBQT，明显要消耗很多memory(query tree deep copy/多份optimizer structure...）和time (反复physical optimization），因此要有一些优化方式

Cost cut-off

在一次search算法中（针对一个transformation)，如果在当前state优化中，发现cost已经超过了之前best state的cost阈值，则可以终止，直接考虑next state。

Reuse of Query subtree cost annotation

由于每个transformation可能影响的是一个query tree的局部，而不一定是整体，因此理论上，只需要对受影响的部分，做re-optimize，其余部分的cost可以重用！！

利用cost标注这种方式做重用，可以很大节省计算量，但对physical optimizer有较高要求。

上图是一个极简版的query block标记和cost记录， 是外层query block，Qs1/Qs2是内部包含的两个query blocks。T是某种变换，T(Qsi)表示变换后的新query block。

可以看到Qs1/T(Qs1)/Qs2/T(Qs2)各出现了2次，因此通过一个table记录下每个query block以及对应的cost信息，就不需要重复计算了（注意 必须重复算，因为每次内部状态都不相同）。

Oracle中实际的cost annotation要复杂得多，片段如下：

可以看到query block的描述要复杂的多，此外要计算的信息也多很多。映射table如下：

Memory management

Oracle原本会在每次optimize结束时释放掉query tree/optimizer structure等相关内存，但如果是CBQT，则需要在每个transform的决定确定后就立即释放，避免占用过多，但cost annotation不释放(reuse)。

Caching

Physical optimizer在优化中会有一些比较复杂的计算（比如对没有统计信息/有多个可能相关列的filter predicates的table，做cardinality/selectivity估计时，要做dynamic sampling），这个过程比较昂贵，因此需要将采样结果cache下来，在多次optimize之间重用。

总结

本篇介绍了Oracle中应用的各种Rule-based transformation和Cost-based transformation，此外重点讲解了其cost-based query transformation的框架和设计。paper中这些有趣的transformation很有启发性，对比简陋的MySQL，其丰富的变换可以探索很多更优的计划形态，从中可以体会到沉淀已久的商业优化器的强大。