我们用OR扩展来继续我们的优化器转换系列。
Oracle Database 12c Release 2中的一个注意事项
请注意Oracle Database 12c Release 2用基于成本的OR扩展转换替换了原先的OR扩展。这将是以后博客文章的主题，但现在，请记住，这种新的转换与OR扩展具有相似的好处，但也存在一些差异：
- 使用UNION-ALL替换了CONCATENATION .
- 如果可能话，UNION-ALL的每一个分支都可以做进一步的查询转换，而使用CONCATENATION 是不可能的.
- 并行查询，可以并发执行UNION-ALL中的分支，而这在CONCATENATION也是不可能的.
介绍
OR扩展是用来优化反意查询（包含OR子句的查询）的一种转换。OR扩展的基本思想是将包含反意的查询转换为两个或多个分支的UNION ALL查询的形式。这是通过拆分OR条件为UNION ALL查询中的相关分支来实现的。
采用OR扩展的理由很多。它允许更有效的访问路径（索引访问，分区裁剪），开放更多的连接方法选项（避免笛卡尔积）。下面，我们将使用SH SCHEMA（Oracle示例SCHEMA中的一个）上的样例来演示前面提及的每一个好处。
允许索引访问或分区裁剪
请看下面包含一个简单反意的查询Q1
Q1
Select *
From products
Where prod_category = 'Photo'
or prod_subcategory = 'Camera Media';
不用OR扩展，优化器将两个反意谓词视为在一个单元中，因此，它不会尝试使用在prod_subcategory列或者在 prod_category列上的索引。如下面的执行计划所示，优化器强制使用了全表扫描做为products表的访问路径，并将反意谓词做为全表扫描之后的过滤。
下在的查询Q2展示了如何用OR扩展改写Q1
Q2
Select *
From products
Where prod_subcategory ='Camera Media'
UNION ALL
Select *
From products
Where prod_category = 'Photo'
And lnnvl(prod_subcategory = 'Camera Media')
Q2中，优化器在第二个分支中添加了LNNVL()函数，以避免分支间产生重复记录。如果谓词计算为FALSE或者谓词涉及NULL，则LNNVL函数返回TRUE；否则返回FALSE。Q2的执行计划显示UNION ALL的两个分支都使用了索引访问，并且添加的LNNVL也被使用了。
从11.2.0.2起，Oracle支持将位图索引，B-tree索引,域索引和函数索引用于OR扩展。比如，我们在PRODUCTS表上，我们创建了两个函数索引。
查询Q3在我们刚刚创建的每个函数索引上，包含了反意过滤。
Q3
Select prod_id
From products
Where upper(prod_name) = 'Y Box'
or upper(prod_category) = 'Electronics';
当OR扩展被用于Q3时，我们刚刚创建的两个函数索引会被用到。
or_expansion3-1.PNG
注意：在Oracle Database 12c Release 2之前，执行计划中，你会发现CONCATENATION操作符替换了之前的UNION ALL。CONCATENATION在语义上等价于UNION ALL操作符。
类似的，OR扩展允许分区裁剪，请看下面的Q4查询：
Q4
Select *
From sales
Where prod_id = 10515
or time_id = '06-JAN-02';
在Q4中，SALES表在TIME_ID列上分区。使用OR扩展，分区裁剪被使用，在下面的执行计划的Pstart列上可以看到这一点。
避免笛卡尔积
下面的例子展示了当反意连接包含连接谓词时，OR扩展允许优化器使用各种连接类型，而不是使用固定连接顺序的，昂贵的被禁用的笛卡尔积。请看下面的查询Q5
Q5
Select *
From promotions pm,
products pt
Where pm.promo_id = pt.prod_id
or pm.promo_name = pt.prod_name;
在上例中，在反意连接中的每一个谓词均是连接条件。不用OR扩展，优化器无法使用反意连接谓词去关联两个表。因而会被迫使用笛卡尔积。下面的执行计划是一个不带任何连接谓词（执行计划下的谓词信息中无access谓词）的嵌套循环连接,反意谓词作为了连接后的过滤。
OR扩展Q5后得到Q6.这里，UNION ALL查询中的每一个分支，都关联于原始查询顶层中的反意连接中的一个连接条件。这让优化器有机会为每一个分支选择最高效的访问方法。
Q6
Select *
From promotions pm, products pt
Where pm.promo_name = pt.prod_name
UNION ALL
Select *
From promotions pm, products pt
Where pm.promo_id = pt.prod_id
And LNNVL(pm.promo_name = pt.prod_name);
Q6的执行计划显示如下，由于优化器可以为UNION ALL分支选择HASH连接和排序合并连接了， 其COST值从700多显著下降到53。
OR扩展 Vs Bitmap OR
当反意谓词是同一张表上的过滤时，Bitmap OR可以被用于反意谓词，再看一次查询Q1
Q1
Select *
From products
Where prod_category = 'xxx'
or prod_subcategory = 'yyy;
下面的执行计划显示在Products表上使用了Bitmap OR操作。这时，在反意连接的两个谓词均被用于驱动索引，其结果被转换为位图并使用OR合并。
那么，Bitmap OR和OR扩展有什么不同呢？大体上，有几种情况下OR扩展与Bitmap OR不同.
当反意连接中的过滤谓词来自于不同的表时，无法使用Bitmap OR，而OR扩展是可以使用的。比如，请看查询Q7。反意连接中有两个单表的过滤谓词，一个在表SALES上，另一个在表PRODUCTS上。由于他们涉及两个不同的表，位图访问路径是无法用于该反意连接的，而OR扩展则可以用于该场景。
Q7
Select *
From promotions pm, products pt
Where pm.promo_id = 33
or pt.prod_name = 'Y Box';
Q7的OR扩展执行计划如下所示：
当Bitmap被用于反意连接时，在连接前，可以使用多个索引。而OR扩展可以引入新的连接顺序。在这种竞争情况下，Oracle会基于成本来选择最好的执行计划。
比如，请看查询Q8。假设我们在SALES表上使用bitmap OR，那么在SALES表和COSTS表这间，只能有一种连接次序（因为SALES表和COSTS表的选择性是固定的）。但是，如果我们OR扩展反意连接，我们在SALES表上就会有不同的选择性。因此，我们最终在UNION ALL查询的两个分支中，有了两个不同的连接次序
Q8
select *
From sales s, costs c
Where (s.prod_id > 147 or s.promo_id = 33)
And s.time_id = c.time_id;
Q8 的OR扩展的执行计划如下所示，两个分支具用不同的访问路径和连接次序。
相较而言，bitmap OR会在与另一个表连接前，合并表上索引的结果。请看查询Q9。在这个查询中，bitmap OR被使用，且在SALES表上的两个过滤谓词分别驱动一个索引。结果被OR在一起，然后和COSTS表做连接。这时，我们仅有一种固定连接次序的连接，并且SALES表上的两个索引均被采用。
Q9
Select *
From sales s, costs c
Where (s.prod_id = 136
or
s.channel_id = '2074')
And s.time_id = c.time_id;
bitmap OR的执行计划如下所示
特殊反意连接
INLIST是一种特殊的反意连接。比如，查询Q10中，prod_id in (1,2,3)是基本上等价于 prod_id=1 or prod_id=2 or prod_id =3的。Oracle用INLIST迭代器来处理这类查询，而不是使用OR扩展。
Q10
Select *
From products
Where prod_id in (17, 21, 13);
使用INLIST迭代器的执行计划如下所示
总结
在本文中，我们用示例演示了使用OR扩展转换的好处。OR扩展允许索引访问和分区裁剪；可以避免两表的笛卡尔积。此外，我们还讨论了Bitmap OR和OR扩展之间的差异，以及INLIST迭代器作为处理反意谓词的特殊情况。最后，我们应意识到，做OR扩展并不总是有好处的。由于进行这一转换时，在UNION ALL查询的每个分支的初始查询块中，会有重复的表访问和连接，这是其缺点。因此，Oracle数据库是用基于成本的方式来使用OR扩展转换的。
原文链接：https://blogs.oracle.com/optimizer/post/optimizer-transformations-or-expansion
原文内容：
Optimizer Transformations: OR Expansion
January 1, 2020 | 9 minute read
Nigel Bayliss
Product Manager
We continue our series on Optimizer transformations with OR expansion.
A Note On Oracle Database 12c Release 2
Note that Oracle Database 12c Release 2 replaces the OR expansion with the Cost Based OR Expansion Transformation. This will be the subject of a later blog post but, for now, bear in mind that this new transformation has similar benefits to the OR expansion but there some differences:
- CONCATENATION is replaced with UNION-ALL.
- Each UNION-ALL branch can be subject to further query transformations, if applicable. This is not possible with CONCATENATION.
- Parallel queries can execute UNION-ALL branches concurrently. Again, this is not possible with CONCATENATION.
Introduction
OR expansion is a transformation that can be used to optimize disjunctive queries (queries that contain OR clauses). The basic idea in OR expansion is to transform a query containing disjunctions into the form of a UNION ALL query of two or more branches. This is done by splitting the disjunction into its components and associating each component with a branch of a UNION ALL query.
There are many reasons for performing OR expansion. It can enable more efficient access paths (index accesses, partition pruning), open up alternative join methods (avoid Cartesian product). Below, we will use examples on SH schema (one of oracle demo schemas) to illustrate each of the aforementioned benefits.
Enabling Index Access Path or Partition Pruning
Consider the following query Q1 that contains a simple disjunction.
Q1
Select *
From products
Where prod_category = 'Photo'
or prod_subcategory = 'Camera Media';
Without OR expansion, the optimizer treats the two disjunctive predicates as a single unit, therefore it cannot explore the index on either the prod_subcategory or prod_category column. As shown in the plan below, the optimizer is forced to use a full table scan as the access path for products and applies the disjunctive predicate as a post filter.
The query Q2 below shows how Q1 will be rewritten with OR-expanded.
Q2
Select *
From products
Where prod_subcategory ='Camera Media'
UNION ALL
Select *
From products
Where prod_category = 'Photo'
And lnnvl(prod_subcategory = 'Camera Media')
In Q2, the optimizer adds the LNNVL() function in the second branch in order to avoid duplicates being generated across branches. The LNNVL function returns TRUE, if the predicate evaluates to FALSE or if the predicate involves NULL; otherwise it will return FALSE. The execution plan for Q2 shows index accesses for both branches of the UNION ALL and the additional LNNVL filter being applied.
From 11.2.0.2, Oracle supports bitmap, b-tree, domain-index, and function-based index for OR expansion. For example, on the products table, we create two function indexes.
Query Q3 has a disjunction containing filters on each of the function-based index that we just created.
Q3
Select prod_id
From products
Where upper(prod_name) = 'Y Box'
or upper(prod_category) = 'Electronics';
When OR expansion is applied to Q3 both of the function-based indexes we just created can be used.
or_expansion3-1.PNG
Note: In the explain plan, you will see the CONCATENATION operator in place of the UNION ALL prior to Oracle Database 12c Release 2. Concatenation is semantically equivalent to the UNION ALL operator.
Similarly, OR expansion can enable partition pruning. Consider Q4 below:
Q4
Select *
From sales
Where prod_id = 10515
or time_id = '06-JAN-02';
In Q4 the sales table is partitioned on the time_id column. With OR expansion the partition pruning is enabled and can be seen in the Pstart column in the execution plan below.
or_expansion4-2.png
Avoiding Cartesian Product
The following example shows that if a disjunction contains join predicates, OR expansion can enable the optimizer to use various join types instead of the prohibitively expensive Cartesian product with a fixed join order. Consider query Q5 below.
Q5
Select *
From promotions pm,
products pt
Where pm.promo_id = pt.prod_id
or pm.promo_name = pt.prod_name;
In the above example, each predicate in the disjunction is a join condition. Without OR expansion, the optimizer cannot use the disjunctive predicates to join two tables. It is therefore forced to perform a Cartesian product, shown in the plan below as a nested loop without any join predicates (no access predicate in the Predicate Information under the plan). The disjunctive predicates are applied as a post join filter.
The OR expansion of Q5 yields Q6. Here each branch of the UNION ALL query is associated with one join condition from the top-level disjunction in the original query. This allows the Optimizer an opportunity to select the most efficient join method for each branch.
Q6
Select *
From promotions pm, products pt
Where pm.promo_name = pt.prod_name
UNION ALL
Select *
From promotions pm, products pt
Where pm.promo_id = pt.prod_id
And LNNVL(pm.promo_name = pt.prod_name);
The execution plan of Q6 is shown below, where the cost has dropped considerably from over 700 to 53 as the optimizer is now able to choose a HASH JOIN and a SORT MERGE join for the branches of the UNION ALL.
Or Expansion Vs Bitmap OR
When the disjunctive predicates are filters of the same table, bitmap OR can be used on the disjunctive predicate. Consider query Q1 again.
Q1
Select *
From products
Where prod_category = 'xxx'
or prod_subcategory = 'yyy;
The plan shown below uses the bitmap OR operator on the products table. This time, the two predicates in the disjunction are used as index drivers and the results are converted to bitmaps and OR’d together.
So, what are the differences between bitmap OR and OR expansion? Basically, there are several scenarios where OR expansion is distinct from bitmap OR.
When the filter predicates in a disjunction come from different tables, bitmap OR will not be applicable while OR expansion is applicable. For example, consider the query Q7. The disjunction has two single table filter predicates, one on the table sales, the other on the table products. Since they are associated with two different tables, bitmap access path will not be applicable to this disjunction. However, OR expansion applies in this scenario.
Q7
Select *
From promotions pm, products pt
Where pm.promo_id = 33
or pt.prod_name = 'Y Box';
The OR expansion plan for Q7 is shown below.
When bitmap is applicable to a disjunction, it can use multiple indexes before doing the join while OR expansion can introduce new join order. In such competing situation, Oracle chooses the best plan based on cost.
For example, consider query Q8. Suppose we use bitmap OR on the table sales, then there is only one join order between sales and costs (since the selectivity of sales and costs are fixed now). However, if we OR expand the disjunction, we have different selectivity on the sales table. Therefore, we end up having two different join orders in each branch of the UNION ALL query.
Q8
select *
From sales s, costs c
Where (s.prod_id > 147 or s.promo_id = 33)
And s.time_id = c.time_id;
The OR expansion plan of Q8 is shown below, where the two branches have different access paths and join orders.
In comparison, bitmap OR will combine the results from the indexes on one table before it joins with the other table. Consider query Q9. In this query, bitmap OR is applied and the two filter predicates on the sales table each acts as an index driver. The results are ORed together and then join with the costs table. Here we only have one join with a fixed join order and both indexes on the sales table are explored.
Q9
Select *
From sales s, costs c
Where (s.prod_id = 136
or
s.channel_id = '2074')
And s.time_id = c.time_id;
The bitmap OR plan is shown below.
Special Disjunct
Inlist is a special disjunct. For example, in query Q10, prod_id in (1,2,3) is essentially equivalent to prod_id=1 or prod_id=2 or prod_id =3. Instead of doing OR expansion, Oracle implements INLIST iterator to handle this class of queries.
Q10
Select *
From products
Where prod_id in (17, 21, 13);
The plan using INLIST iterator is shown below.
or_expansion10.png
Summary
In this post, we have used examples to illustrate the benefits of doing the OR expansion transformation. OR expansion can enable index access path and partition pruning; it can avoid Cartesian product between tables. Also, we have discussed the differences between bitmap OR and OR expansion, and the INLIST iterator as a special case to handle disjunct predicate. Last, it should be mentioned that it is not always beneficial to do OR expansion, since the drawback of doing this transformation is that it duplicates the tables and joins in the original query block in each of the branches of the UNION ALL query. Therefore, the OR-expansion transformation is applied in a cost-based manner in Oracle database.
