We continue our series on Optimizer transformations with OR expansion.
Note that Oracle Database 12c Release 2 replaces the OR expansion with the Cost Base 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:
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.
Consider the following query Q1 that contains a simple disjunction.
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.
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 18.104.22.168, 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.
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:
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.
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.
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.
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.
When the disjunctive predicates are filters of the same table, bitmap OR can be used on the disjunctive predicate. Consider query Q1 again.
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.
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.
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.
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.
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.
Select * From products Where prod_id in (17, 21, 13);
The plan using INLIST iterator is shown below.
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.