这篇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个主要的问题:
-
完全基于手写代码的查询变换,使得对于transformation的应用不够灵活,也不容易扩展新的变换形式。如果你看过MySQL/PG的代码,就能深刻的体会这一点,从代码逻辑上就写死了:a变换 -> b变换 -> ....,想加入新的变换x,就需要手工实现新变换逻辑和原有代码结构的融合,非常麻烦,此外没法做a -> x -> b这样的尝试,只能依次完成。这对于复杂度更高的商业数据库来说,是个更突出的问题。
-
很多变换并不一定使得查询更优,因此需要基于代价进行评估。
-
为解决以上问题,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,但有几个例外
-
subquery在OR条件中
-
某些ALL subquery有多个投影列,且列中包含NULL值(10g中还不支持null-aware anti join,11g中支持)
-
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中,这种变换只在如下情况才会考虑:
-
外层query中有针对rownum的过滤谓词
-
内层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个区别
-
集合操作中,null值的比较是可以相等的,join中则是不等的
-
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
基本组件
如上图所示,其包含的主要组件:
-
transformation的算法
-
由于各种transformation应用于query tree中的各个elements,形成的state space
-
在state space中做search的算法
-
对query tree的整体或部分,做deep copy,相对于生成新的query tree来尝试
-
调用physical optimizer计算cost
-
记录最终transform决策的directives和cost annotation
总体的执行流程是:
-
对每个特定transformation,在query tree中以bottom-up的方式,考虑可能影响的各个element(比如query block/view/predicates…),形成一个state space并基于某个search算法进行搜索。
-
顺序考虑下一个transformation,针对其所影响的element,再次search。
-
除非transformation之间有相互影响,否则依次考虑和应用各个transform : T1 -> T2 -> T3….
针对某一个transformation T的具体search过程如上图,也就是针对每一个特定的state:
-
deep copy target query tree,copy必要的query block或element。
-
应用目标transform
-
physical optimizer计算该state下的cost
-
针对当前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,其丰富的变换可以探索很多更优的计划形态,从中可以体会到沉淀已久的商业优化器的强大。