Enhanced Subquery Optimizations in Oracle

在前面的文章中，介绍了Oracle是如何做cost-based query transformation的，其中也包含Oracle基于rules/cost所做的若干种常见的query rewrite。对于CBQT的极简描述是对一个query做deep copy后，尝试一系列transform并利用physical optimizer计算cost，如果cost更低则保留该变换，否则抛弃。详细介绍可以参考之前的文章。

这篇paper算是之前那篇的后续，把重点放在了对subquery的处理上。subquery是一种在分析型query中非常常见的SQL construct，非常便于表达一些语义因此被广为使用。例如Decision support benchmark TPC-H的查询中，有近一半使用了subquery(Query 2, 4, 11, 15, 16, 17, 18, 20, 21, 22)，其中大多数是相关子查询且包含聚集函数。

paper中主要介绍的是更为先进的Oracle 11g，其中包含了一些新的transformation。(subquery coalescing/subquery removal/filter join elimination...) 此外还介绍了一些parallel execution技术，这些并行技术提高了query执行的扩展性，并可以和transformation结合在一起。

Subquery处理概述

对于相关子查询，其最朴素的执行语义就是针对外表一行，将相关列的值带入内层子查询，并执行子查询计算结果，在用结果对外表进行过滤，这是一种类似Nested-loop的执行方式，如果不做unnesting，则无法考虑更多的access path/join order/join method的可能。

Oracle对子查询的unnesting主要分为2类：

1. 转换为derived table
   
2. merge到外层query block中
   

前者是基于cost来决策的，后者则基于启发式规则。

如果将non-scalar的subquery merge到外层，一般会形成semi join/anti join，Oracle会使用3种执行方式来做join: index-lookup / hash / merge

1. 如果在内层表有索引可以使用，可以使用index lookup
   
2. 否则如果是等值join时，会使用hash的执行方式
   

对于以上2种方式，当left table中有很多duplicate时，会针对这些duplicate行，将semi/anti join的结果cache起来，从而避免了反复计算，算是一个局部执行优化。

3. 如果是 > ANY, < ALL 这样的非等值join，就使用sort merge join。

4. 对于 NOT IN, <> ALL 这样的subquery，在10g中是无法merge到外层的，在11g中引入了null-aware anti join，实现了merge，这篇paper也对NAAJ进行了介绍。

5. 在某些情况下，会使用window function对subquery进行消除，其思路和之前一篇文章介绍的DB2的WinMagic如出一辙

Subquery coalescing

这里针对的subquery首先是作为outer query的filter条件存在的，可以将多个这样的filter中，等价的subquery合并为一个，这样就减少了subquery本身的执行次数和代价。虽然合并是要两两进行的，但可以反复执行，从而将多个subquery合并在一起。

如果两个subquery，可以产生相同的multi-set(bag) result，则认为他们是语义上等价的，在结构/语法上完全相同(identical)通常就意味着两者的等价。

如果其中一个qb2，相对于另一个qb1，除了包含有更多的AND谓词p2外，其余是完全identical的(一定是AND!!)，则其结果必然是qb1的结果的子集，则认为qb1包含qb2，两者具有包含关系。

在11g中，Oracle支持对Exist/Not Exist出现在AND/OR中的多种组合情况的合并。

极简情况

如果两个subquery是相同的(identical)，则无论是AND还是OR，都可以直接消除其中一个。

subquery具有相同类型

假设qb1包含qb2，qb2有更多的谓词条件p2，因此包含更少的结果数据（更严格）。

1. EXIST qb1 AND EXIST qb2 =>  EXIST qb2，这个很容易推导，因为qb2更严格，满足它必然满足qb1。
   
2. NOT EXIST qb1 OR NOT EXIST qb2 => NOT EXIST qb2，这个和1等价。
   
3. EXIST qb1 OR EXIST qb2 => EXIST qb1，这个也容易推导，qb1满足条件时，即为true，qb1不满足时，qb2因为数据更少更无法满足，因此为false。
   
4. NOT EXIST qb1 AND NOT EXIST qb2 => NOT EXIST qb1，这个和3等价。
   

对于EXIST qb1 OR EXIST qb2 / NOT EXIST qb1 AND NOT EXIST qb2这样的谓词形态，即使qb1,qb2之间不存在包含关系，但他们只在某些conjunctive谓词上有所区别，例如qb1有p1，qb2有p2，但除去不同部分，其余是等价的，则两个subquery也可以合并。这其实是OR-expansion的反过程。

SELECT o_orderpriority, COUNT(*)
FROM orders
WHERE o_orderdate >= '1993-07-01' AND
      EXISTS (SELECT *
              FROM lineitem
              WHERE l_orderkey = o_orderkey AND
                    l_returnflag = 'R')  OR
      EXISTS (SELECT *
              FROM lineitem
              WHERE l_orderkey = o_orderkey AND
                    l_receiptdate > l_commitdate)
GROUP BY o_orderpriority;
=>
SELECT o_orderpriority, COUNT(*)
FROM orders
WHERE o_orderdate >= '1993-07-01' AND
      EXISTS (SELECT *
              FROM lineitem
              WHERE l_orderkey = o_orderkey AND
                    (l_returnflag = 'R' OR
                     l_receiptdate > l_commitdate))
GROUP BY o_orderpriority;

如上例，将2个EXISTS中的subquery，”求同存异“，不同的部分predicate被OR了起来。

subquery具有不同类型

仍假设qb1包含qb2，qb2有更多的谓词条件p2，因此包含更少的结果数据（更严格）。

1.EXIST qb2 and not EXIST qb1

外表的一行，如果可以满足qb2的p2（更严格），则一定满足qb1，所以后者为false，总体为false。如果不能满足qb2，直接为false。因此总体一定为false。

2.EXIST qb1 and not EXIST qb2

外表的一行，如果在qb1中，存在可以满足qb1的p1的行，且能满足qb2的p2条件，则结果为false。如果存在可以满足qb1的p1的行，但这些行都不满足qb2的p2，则为true。

将以上2种情况结合在一起考虑的话，等价的结果是：

如果存在满足qb1中p1的行，但都不满足qb2中的p2，则可以为true，但其中有任一行满足p2，则为false。

这个等价的语义可以用如下合并来描述：

EXIST common_qb(where p1=true having sum(case when p2=true then 1 else 0) == 0)

<=>

只有当满足p1的所有行，都不满足p2，having才返回true，才能有结果，否则having过滤掉所有行！

SELECT s_name
FROM supplier, lineitem L1
WHERE s_suppkey = l_suppkey AND
      EXISTS (SELECT *
              FROM lineitem L2
              WHERE l_orderkey = L1.l_orderkey AND
                    l_suppkey <> L1.l_suppkery)
      AND NOT EXISTS (SELECT *
                      FROM lineitem L3
                      WHERE l_orderkey = L1.l_orderkey AND
                            l_suppkey <> L1.l_suppkery AND
                            l_receiptdate > l_commitdate);
=>
SELECT s_name
FROM supplier, lineitem L1
WHERE s_suppkey = l_suppkey AND
      EXISTS (SELECT 1
              FROM lineitem L2
              WHERE l_orderkey = L1.l_orderkey AND
                    l_suppkey <> L1.l_suppkery
              HAVING SUM(CASE WHEN l_receiptdate > l_commitdate
                         THEN 1 ELSE 0 END) == 0);

观察上例，第一个EXIST子查询qb1比第二个NOT EXIST子查询qb2只少一个条件p2: l_receiptdate > l_commitdate。基于上面的等价变换，将这个条件放入having中对整个子查询结果进行过滤，这样只有当所有满足qb1的行都不满足p2时，having才会为true，整个子查询才为true，否则为false。

与其他transformation的交互

和其他rewrite一样，subquery coalescing也会影响到其他的transformation，例如上例中的查询改写后，还可以做unnesting，转换为inline view(derived table)。

SELECT s_name
FROM supplier, lineitem L1
WHERE s_suppkey = l_suppkey AND
      EXISTS (SELECT 1
              FROM lineitem L2
              WHERE l_orderkey = L1.l_orderkey AND
                    l_suppkey <> L1.l_suppkery
              HAVING SUM(CASE WHEN l_receiptdate > l_commitdate
                         THEN 1 ELSE 0 END) == 0); 
=>
SELECT s_name
FROM supplier, lineitem L1,
     (SELECT LX.rowid as xrowid
      FROM lineitem L2, lineitem LX
      WHERE L2.l_orderkey = LX.l_orderkey AND
            L2.l_suppkey <> LX.l_suppkery
      GROUP BY LX.rowid
      HAVING SUM(CASE WHEN L2.l_receiptdate > L2.l_commitdate
                         THEN 1 ELSE 0 END) == 0) V
WHERE s_suppkey = l_suppkey AND L1.rowid = V.xrowid;

这个变换将外层的相关表L1推入内层子查询中变为LX，并需要加入group by子句来保证针对LX的每一行，计算一个聚集结果。

完成unnesting后，生成了derived table，因此可以进一步考虑view merging：

SELECT s_name
FROM supplier, lineitem L1,
     (SELECT LX.rowid as xrowid
      FROM lineitem L2, lineitem LX
      WHERE L2.l_orderkey = LX.l_orderkey AND
            L2.l_suppkey <> LX.l_suppkey
      GROUP BY LX.rowid
      HAVING SUM(CASE WHEN L2.l_receiptdate > L2.l_commitdate
                         THEN 1 ELSE 0 END) == 0) V
WHERE s_suppkey = l_suppkey AND L1.rowid = V.xrowid;
=>
SELECT s_name
FROM supplier, lineitem L1, lineitem L2
WHERE s_suppkey = L1.l_suppkey AND
      L2.l_orderkey = L1.l_orderkey AND
      L2.l_suppkey <> L1.l_suppkey
GROUP BY L1.rowid, supplier.rowid, s_name
HAVING SUM(CASE WHEN L2.l_receiptdate > L2.l_commitdate
                         THEN 1 ELSE 0 END) == 0);

将view merge到外层后，group by需要加入外层表的rowid，这里由于LX和L1是同一个表，self join可以去掉LX。

所有这些变换都有可能发生，需要基于cost决定采用其中哪些。

执行侧优化

这里介绍了一个对group by + aggregation的小优化，例如上面示例中的HAVING子句中，对一个分组来说，只要有一行满足了L2.l_receiptdate > L2.l_commitdate这个条件，having就会将这整个分组过滤掉，因此可以考虑在执行中一旦遇到这样的行，直接将整组扔掉，避免无谓的计算。类似的early stop策略对于SUM(xx) < 10，MIN(*) < 5 这样的过滤条件都适用。

这个策略在并行执行中也生效，关于Oracle的并行执行策略请看这篇文章。

简略来说，Oracle采用如下的并行方式：

先在join本地，针对数据做local aggregation，这样有利于对抗data skew，也可以减少后续传输的数据量，然后再在group by key上做repartition/range distribution，然后并行完成二次group by + aggregation，得到最终结果。那么可以把这种early stop的条件下压到local aggregation中，尽早丢弃掉不用的分组。

Group by view elimination

这里主要介绍了一种叫做filtering table elimination的技术，利用的是filtering join的思想。

定义filtering join： 如果是semi-join，或者等值inner join且一侧的join列是unique key，这样对于另一侧来说，实际上是起到了filtering的效果，该表的cardinality不会增加。

对于这种filtering join，如果用在AND谓词的后方，且前面有更为严格的筛选条件保证filtering一定为true，则filter join整个可以去除。

假设R是一个row source(derived table/base table)，T1和T2是两个实例，但T1带有更严格的谓词条件p1，T2更宽松。unique key用前缀u来表示，semi join用S=来表示：

• R.x = T1.uy AND R.x = T2.uy， 则后者可以删除
  

这个很好理解，对R.x，如果满足 == T1.uy，则一定满足== T2.uy，因为前者数据是后者的子集。

• R.x = T1.y AND R.x S= T2.y ，则后者可以删除
  

R.x 与T1中y列如果有相同值，由于T1是T2的子集，则R.x一定与T2中y列有相同值，后面子条件一定为true。

• R.x S= T1.y AND R.x S= T2.y，后者可以删除
  

与上面是一个道理

SELECT o_orderkey, c_custkey, SUM(l_quantity)
FROM orders, lineitem L1, customers
WHERE o_orderkey = l_orderkey AND
      c_custkey = o_custkey AND
      o_orderkey IN
      (SELECT l_orderkey
       FROM lineitem l2
       GROUP BY l_orderkey
       HAVING sum(l_quantity) > 30)
GROUP BY o_orderkey, c_custkey;
=>
SELECT o_orderkey, c_custkey, SUM(l_quantity)
FROM orders, lineitem L1, customers
     (SELECT l_orderkey
       FROM lineitem l2
       GROUP BY l_orderkey
       HAVING sum(l_quantity) > 30) V2
WHERE o_orderkey = l_orderkey AND
      c_custkey = o_custkey AND
      o_orderkey = V2.l_orderkey
GROUP BY o_orderkey, c_custkey;

上面原始查询先做了一次subquery unnesting，生成derived table V2

通过group by placement变形，将V2中的group by pullup，再推入到L1中，形成另一个view

SELECT o_orderkey, c_custkey, SUM(l_quantity)
FROM orders, lineitem L1, customers
     (SELECT l_orderkey
       FROM lineitem L2
       GROUP BY l_orderkey
       HAVING sum(l_quantity) > 30) V2
WHERE o_orderkey = l_orderkey AND
      c_custkey = o_custkey AND
      o_orderkey = V2.l_orderkey
GROUP BY o_orderkey, c_custkey;
=>
SELECT o_orderkey, c_custkey, SUM(l_quantity)
FROM orders, customers,
     (SELECT l_orderkey, SUM(l_quantity)
       FROM lineitem L1
       GROUP BY l_orderkey
       HAVING sum(l_quantity) > 30) V2,
      (SELECT l_orderkey, SUM(l_quantity)
       FROM lineitem L1
       GROUP BY l_orderkey) V1
WHERE o_orderkey = V1.l_orderkey AND
      o_orderkey = V2.l_orderkey
      c_custkey = o_custkey
GROUP BY o_orderkey, c_custkey;

经过这些变换后可以看到，V1和V2是两个基本相同的view，只是V2包含更为严格的过滤条件，此外由于V1/V2与order表的join条件都是基于其group by列l_orderkey的，等于在V1/V2中，l_orderkey具有唯一性，这两个join都是filtering join!!

因此可以利用前面讲到的消除机制1，将更为宽松的view V1消除掉！得到如下query:

SELECT o_orderkey, c_custkey, SUM(l_quantity)
FROM orders, customers,
     (SELECT l_orderkey, SUM(l_quantity)
       FROM lineitem L1
       GROUP BY l_orderkey
       HAVING sum(l_quantity) > 30) V2,
      (SELECT l_orderkey, SUM(l_quantity)
       FROM lineitem L1
       GROUP BY l_orderkey) V1
WHERE o_orderkey = V1.l_orderkey AND
      o_orderkey = V2.l_orderkey
      c_custkey = o_custkey
GROUP BY o_orderkey, c_custkey;
=>
SELECT o_orderkey, c_custkey, SUM(l_quantity)
FROM orders, customers,
     (SELECT l_orderkey, SUM(l_quantity)
       FROM lineitem L1
       GROUP BY l_orderkey
       HAVING sum(l_quantity) > 30) V2
WHERE o_orderkey = V2.l_orderkey
      c_custkey = o_custkey
GROUP BY o_orderkey, c_custkey;

通过这个例子，详细大家已经感受到了transformation之间相互作用所带来的神奇作用和复杂性，这在MySQL甚至PostgreSQL这样的开源数据库系统中是很难想象的。

Subquery Removal using window function

相关子查询

针对相关子查询进行remove，使用的思路和DB2的WinMagic完全一致，大致来说就是：

如果外层qb，包含有内层qb的所有table + predicates，则外层qb subsume内层qb，只有满足subsume条件的subquery(相关/非相关)，才能用window function替换，且subquery中有数值型聚集函数(min/max/sum...)，这些聚集函数有window function的等价函数。

相关子查询的通用形式：

SELECT T1.x
FROM T1, T2 
WHERE T1.y = T2.y
AND T1.z relop (
    select AGG(T2.w)
    FROM T2
    WHERE T1.y = T2.y
  );

这里T1,T2可以是derived table/base table/多个表join，因此可以表示很复杂的查询。

T1.y是主键，T2.y是外键

这是相关子查询可以用window function替代的通用pattern : 外层的join条件和内层的相关条件相同，且内层有aggregation函数，外层用这个aggr函数结果做过滤。

原理基于相关子查询的执行语义：

对于T1的一行T1.y，可以和T2.y join产生rowset1，这个rowset1，和内层代入T1.y产生的rowset是完全相同的(subsume的作用)，在内层这个rowset1用来做aggr后得到X，对外层的T1.y做过滤。所以可以用wf等价为，对T1的每一行，用相关列T2.y做partition列，在partition内做aggregation得到相同的X，附在每一行T1.y后面，基于这个结果对每行过滤即可。

SELECT V.x
FROM (T1.x, T1.z SELECT AGG(T2.w) over (PARTITION BY T2.y) as agg_win
    FROM T1, T2
    WHERE T1.y = T2.y) V
WHERE V.z relop V.agg_win;

如果T1.y不是主键，也没关系，从语义上，只要PARTITION BY T1.pkey, T2.y，就可以了。

这里讲的有些粗略，具体细节请看这篇文章。

非相关子查询

对于具有subsumed关系的非相关子查询，处理起来会更简单些。直接看例子

WITH V AS (SELECT l_suppkey,
           SUM(l_extprice) revenue
           FROM lineitem
           WHERE l_shipdate >= '1996-01-01'
           GROUP BY l_suppkey)
SELECT s_suppkey, s_name, V.revenue
FROM supplier, V
WHERE s_suppkey = V.l_suppkey AND
      V.revenue = (SELECT MAX(V.revenue) FROM V);

上面这个SQL是TPC-H Q15的简化版，观察一下其语义：

在supplier join V时，除了在suppkey的join条件外，还有个使用非相关子查询的过滤，过滤的条件是V的revenue要等于V中revenue列的最大值。

这就很容易想到，如果直接能获取到V中revenue列的最大值，作为V的额外一列附加上，这个过滤条件就只针对这列就可以了，因此可以变成如下形式：

SELECT s_suppkey, s_name, V.revenue
FROM supplier,
     (SELECT l_suppkey,
           SUM(l_extprice) revenue,
           MAX(SUM(l_extprice)) OVER() gt_rev
           FROM lineitem
           WHERE l_shipdate >= '1996-01-01'
           GROUP BY l_suppkey) V
WHERE s_suppkey = V.l_suppkey AND
      V.revenue = V.gt_rev;

这样就把非相关子查询消除了，使用了OVER()这样的window function，在Oracle中称为grand-total wf，即所有行作为一个partition，计算一个统一的结果（这里是max值）。

扩展性的parallel execution

由于window function在subquery消除中的重要性，Oracle对window function的并行执行进行了很多优化。

原始的执行方式是基于partition by key做hash distribution，然后对每个partition并行完成window function的计算。但这种方法的并行度受限于partition by key的NDV，对于grand-total这种wf则完全没法并行，因此提出了扩展性方式。

对于上例中的最终query形态，其并行执行方式为：

1. 先是在各个并行worker上，针对部分数据，做一个local的partion内聚集计算，得到结果后，把各个partition的local result，形成数组，发送到QC端
   
2. QC端只做汇总操作，计算各个partition的global aggregation result，再形成partition的数组，带着global result返回给各个worker
   
3. 各个worker将收到的数组和本地每行数据，按parition做一个sort-merge join，把global结果附加到了每行数据上，再发送给QC
   
4. QC收到数据按partition排好后发送即可
   

这样大部分的工作是在worker完成的，coordinator只做很少的聚集计算因为每个worker只会发送本地聚集的一行结果。

对于非grand-total的window function，也有办法扩展其并行度，思路与上面类似，但需要在worker和coordinator间交互更多信息，具体细节就不详述了，可以参看文章。

NULL-aware anti join(NAJJ)

众所周知SQL中对于NULL的处理是存在3值语义的：

TRUE/FALSE/UNKNOWN

任何value与NULL的计算都会是UNKNOWN结果，除非计算表达式是IS NULL / IS NOT NULL。而对于UNKNOWN的处理，不同系统有所不同，但肯定不会是TRUE。 

对于NOT IN subquery本质上存在如下等价形式：

NOT IN 
<=> NOT (o1 = inner.row1.i1 or o1 = inner.row2.i2 or o1 = inner.row3.i2 ...) 
<=> (o1 != inner.row1.i2 and o1 != inner.row2.i2 and o1 = inner.row3.i3 ...) 
注：这里ix只是表示第几行的相关列，都是同一列i

如果在相关列o1/i1上存在NULL值，则要特殊处理：

对外层的一行o1，这时如果内表中任一行ix是NULL，条件将是UNKNOWN。而antijoin的语义是，对外表一行，如果内表所有行，在join条件上都是FALSE，该行才能保留，现在join条件是UNKNOWN，则外表所有行都不能保留，结果是空。

而普通的anti-join没有处理内层有NULL值的情况(Oracle 10g)，需引入NAAJ(Oracle 11g)，其处理流程如下：

if (内表为空) {
  // condition 1
  外表所有行保留
} else if (内表任一行，在join列上有NULL值) {
  // condition 2
  结果为空(如上分析)
} else if (外表当前行在join列上是null值) {
  // condition 3
  当前行丢弃（同样道理，只不过外表一行为NULL）
} else if (外表当前行，对内表所有行，join条件都为false) {
  // condition 4
  当前行保留
} else {
  // default
  当前行丢弃
}

条件4从语义上包含了条件2、3，但2，3可以用来做快速计算。

总结

本篇基本详尽的描述了Oracle对于subquery的主要变换机制，还是非常复杂的，尤其涉及到transformation的相互影响时。这篇paper是我到阿里工作后最早接触的优化器论文之一，当时感觉相当艰深难以理解。

从paper中可以感受到，商业数据库在优化器的能力上要领先一般的开源数据库几个档次，即使是号称最先进的PostgreSQL也相差甚远。所以说，query optimizer才是商业数据库的宝贵财富，是他们多年沉淀与积累的核心竞争力。而作为PolarDB内核优化器的开发人员，我们还有很长的路要走。。。