Optimizer Transformations: OR Expansion

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.

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.

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.

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.