Tuesday Apr 26, 2011

Optimizer Transformations: Table Expansion

The table expansion transformation was introduced in 11gR2, to improve performance of a specific category of queries. If you understand how the transformation works, you can tailor your indexing scheme to improve plans. We added the transformation based on a few key observations:[Read More]

Wednesday Apr 20, 2011

How do I drop an existing histogram on a column and stop the Auto Stats gathering job from creating it in the future?

Before answering this question, I want to provide a bit more background to this scenario. The person who submitted this question has a table with a VARCHAR2 column called ID whose data distribution is skewed. When the Auto Stats job kicks in for this table a histogram is automatically created on this column as it is used in nearly every SQL statement and it has a data skew. However, the values in the ID column are extremely long and the first 32 characters in each ID are identical.[Read More]

Tuesday Apr 19, 2011

Upcoming events : ODTUG Kaleidoscope 2011

ODTUG Kaleidoscope 2011, June 26 - June 30 Long Beach CA is a great conference for Oracle developers and architects, offering the best content by renowned experts. I will be delivering two Optimizer sessions this year, 'Explaining the Explain plan' and 'Oracle Optimizer- Top Tips to get Optimal SQL Execution'. In the Explain the Explain plan session we will discuss each aspect of an execution plan (from selectivity to parallel execution), explain what information you should be getting from the plan, and how it affects the execution. While in the Top tips session, I will show you how to identify and resolving the most common SQL execution performance problems including, poor cardinality estimations, wrong access method being used, and much more. This session is packed with clear how-to examples making it accessible for even the most novice of Oracle Users.

ODTUG is a great conference where you can learn lots in a fun and casual atmosphere. Looking forward to seeing some of you there!

Monday Apr 11, 2011

Optimizer Transformations: OR Expansion

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.[Read More]

Monday Mar 28, 2011

What happened to the Optimizer white papers on OTN?

We have gotten a lot of questions recently about what happened to the Optimizer white papers that use to be on OTN. The white papers are still there but the URL has changed slightly, which is causing the problem. Here are new URL's for the most recent Optimizer white papers:

SQL Plan Management in Oracle Database 11g

Upgrading from Oracle Database 9i to 10g: What to expect from the Optimizer

Upgrading from Oracle Database 10g to 11g: What to expect from the Optimizer

Thursday Mar 24, 2011

How do I know what extended statistics are needed for a given workload?

In our previous post we introduced extended statistics, which help the Optimizer improve the accuracy of cardinality estimates for SQL statements that contain predicates involving a function wrapped column (e.g. UPPER(LastName)) or multiple columns from the same table used in filter predicates, join conditions, or group-by keys. So extended statistics are extremely useful but how do you know which extended statistics should be created?

In Oracle Database 11.2.0.2 we introduced Auto Column Group Creation, which automatically determines which column groups are required for a table based on a given workload. Please note this functionality does not create extended statistics for function wrapped columns it is only for column groups. Auto Column Group Creation is a simple three step process:

[Read More]

Thursday Mar 17, 2011

Extended Statistics

In real-world data, there is often a relationship or correlation between the data stored in different columns of the same table. For example, in the customers table, the values in the cust_state_province column are influenced by the values in the country_id column, as the state of California is only going to be found in the United States. Until now, the Optimizer had no way of knowing about these real-world relationships and could potentially miscalculate the cardinality estimate if multiple columns from the same table are used in the where clause of a statement. With extended statistics you now have an opportunity to tell the Optimizer about these real-world relationships between the columns.[Read More]

Wednesday Mar 16, 2011

Oracle OpenWorld 2011 Call For Papers

The Oracle OpenWorld 2011 call for papers is now open. Oracle customers and partners are encouraged to submit proposals to present at this year's Oracle OpenWorld conference, which will be held October 2-6, 2011 at the Moscone Center in San Francisco. Details and submission guidelines are available on the Oracle OpenWorld Call for Papers web site. The deadline for submissions is Sunday, March 27 2011 at 11:59 pm PDT. We look forward to checking out your sessions on the Optimizer, SQL Plan Management, and statistics!

Friday Feb 25, 2011

Optimizer Transformations: Join Factorization

We continue our series on optimizer transformations with a post that describes the Join Factorization transformation. The Join Factorization transformation was introduced in Oracle 11g Release 2 and applies to UNION ALL queries. Union all queries are commonly used in database applications, especially in data integration applications. In many scenarios the branches in a UNION All query share a common processing, i.e, refer to the same tables. In the current Oracle execution strategy, each branch of a UNION ALL query is evaluated independently, which leads to repetitive processing, including data access and join. The join factorization transformation offers an opportunity to share the common computations across the UNION ALL branches. Currently, join factorization only factorizes common references to base tables only, i.e, not views.

Consider a simple example of query Q1.

Q1:
    select t1.c1, t2.c2
    from t1, t2, t3
    where
t1.c1 = t2.c1 and t1.c1 > 1 and t2.c2 = 2 and t2.c2 = t3.c2 
  union all
    select t1.c1, t2.c2
    from t1, t2, t4
    where t1.c1 = t2.c1 and t1.c1 > 1 and t2.c3 = t4.c3;

Table t1 appears in both the branches. As does the filter predicates on t1 (t1.c1 > 1) and the join predicates involving t1 (t1.c1 = t2.c1). Nevertheless, without any transformation, the scan (and the filtering) on t1 has to be done twice, once per branch. Such a query may benefit from join factorization which can transform Q1 into Q2 as follows:

Q2:
    select t1.c1, VW_JF_1.item_2
    from t1, (select t2.c1 item_1, t2.c2 item_2
                   from t2, t3
                   where t2.c2 = t3.c2 and t2.c2 = 2                 
                 union all
                   select t2.c1 item_1, t2.c2 item_2
                   from t2, t4 
                   where t2.c3 = t4.c3) VW_JF_1
    where t1.c1 = VW_JF_1.item_1 and t1.c1 > 1;


In Q2, t1 is "factorized" and thus the table scan and the filtering on t1 is done only once (it's shared). If t1 is large, then avoiding one extra scan of t1 can lead to a huge performance improvement.

Another benefit of join factorization is that it can open up more join orders. Let's look at query Q3.

Q3:
    select *
    from t5,
(select t1.c1, t2.c2
                  from t1, t2, t3
                  where t1.c1 = t2.c1 and t1.c1 > 1 and t2.c2 = 2 and t2.c2 = t3.c2 
                union all
                  select t1.c1, t2.c2
                  from t1, t2, t4
                  where t1.c1 = t2.c1 and t1.c1 > 1 and t2.c3 = t4.c3) V;

   where t5.c1 = V.c1

In Q3, view V is same as Q1. Before join factorization, t1, t2 and t3 must be joined first before they can be joined with t5. But if join factorization factorizes t1 from view V, t1 can then be joined with t5. This opens up new join orders. That being said, join factorization imposes certain join orders. For example, in Q2, t2 and t3 appear in the first branch of the UNION ALL query in view VW_JF_1. T2 must be joined with t3 before it can be joined with t1 which is outside of the VW_JF_1 view. The imposed join order may not necessarily be the best join order. For this reason, join factorization is performed under cost-based transformation framework; this means that we cost the plans with and without join factorization and choose the cheapest plan.

Note that if the branches in UNION ALL have DISTINCT clauses, join factorization is not valid. For example, Q4 is NOT semantically equivalent to Q5. 

Q4:
     select distinct t1.* 
     from t1, t2
     where t1.c1 = t2.c1
  union all
     select distinct t1.*
     from t1, t2
     where t1.c1 = t2.c1

Q5:
    select distinct t1.* 
    from t1, (select t2.c1 item_1 
                  from t2
                union all 
                  select t2.c1 item_1
                  from t2) VW_JF_1 
    where t1.c1 = VW_JF_1.item_1

Q4 might return more rows than Q5. Q5's results are guaranteed to be duplicate free because of the DISTINCT key word at the top level while Q4's results might contain duplicates.  

The examples given so far involve inner joins only. Join factorization is also supported in outer join, anti join and semi join. But only the right tables of outer join, anti join and semi joins can be factorized. It is not semantically correct to factorize the left table of outer join, anti join or semi join. For example, Q6 is NOT semantically equivalent to Q7.

Q6:
    select t1.c1, t2.c2
    from t1, t2
    where t1.c1 = t2.c1(+) and t2.c2 (+) = 2 
 union all
    select t1.c1, t2.c2
    from t1, t2 
    where t1.c1 = t2.c1(+) and t2.c2 (+) = 3

Q7: 
    select t1.c1, VW_JF_1.item_2
    from t1, (select t2.c1 item_1, t2.c2 item_2

                  from t2
                  where t2.c2 = 2
                union all
                  select t2.c1 item_1, t2.c2 item_2
                  from t2                                                                                  

                  where t2.c2 = 3) VW_JF_1     
  where t1.c1 = VW_JF_1.item_1(+)                                                                 

However, the right side of an outer join can be factorized. For example, join factorization can transform Q8 to Q9 by factorizing t2, which is the right table of an outer join.

Q8:
    select t1.c2, t2.c2
    from t1, t2

    where t1.c1 = t2.c1 (+) and t1.c1 = 1
 union all
    select t1.c2, t2.c2
    from t1, t2
    where t1.c1 = t2.c1(+) and t1.c1 = 2

Q9:
   select VW_JF_1.item_2, t2.c2
   from t2,

           (select t1.c1 item_1, t1.c2 item_2
            from t1
            where t1.c1 = 1
           union all
            select t1.c1 item_1, t1.c2 item_2
            from t1
            where t1.c1 = 2) VW_JF_1
   where VW_JF_1.item_1 = t2.c1(+)

All of the examples in this blog show factorizing a single table from two branches. This is just for ease of illustration. Join factorization can factorize multiple tables and from more than two UNION ALL branches. 

Summary
Join factorization is a cost-based transformation. It can factorize common computations from branches in a UNION ALL query which can lead to huge performance improvement. 

[Read More]

Monday Feb 21, 2011

Upcoming events : Hotsos Symposium 2011

This year for the first time, I will present at the Hotsos Symposium in Dallas Texas, March 7 - 9. I will present on two topics Top tips for Optimal SQL Execution and Implement Best Practices for Extreme Performance with Oracle Data Warehousing.

I am really looking forward to attending some excellent sessions at the conference from folks like Tom Kyte, Cary Millsap, Doug Burns, and Dan Fink. Hope to see you there!

Tuesday Feb 15, 2011

How do I deal with a third party application that has embedded hints that result in a sub-optimal execution plan in my environment?

I have gotten many variations on this question recently as folks begin to upgrade to Oracle Database 11g and there have been several posts on this blog and on others describing how to use SQL Plan Management (SPM) so that a non-hinted SQL statement can use a plan generated with hints. But what if the hint is supplied in the third party application and is causing performance regressions on your system?

[Read More]

Thursday Feb 10, 2011

New "How do I ..." series

Over the last year or so the Optimizer development team has presented at a number of conferences and we got a lot of questions that start with "How do I ...". Where people were looking for a specific command or set of steps to fix a problem they had encountered. So we thought it would be a good idea to create a series of small posts that deal with these "How do I" question directly. We will use a simple example each time, that shows exactly what commands and procedures should be used to address a given problem. If you have an interesting "How do I .." question you would like to see us answer on the blog please email me and we will do our best to answer them! Watch out for the first post in this series which addresses the problem of "How do I deal with a third party application that has embedded hints that result in a sub-optimal execution plan in my environment?"

Friday Jan 28, 2011

Concurrent Statistics Gathering

Gathering optimizer statistics is one of life's necessary evils even if it can take an extremely long time to complete. In this blog post, we discuss one remedy to improve the efficiency of statistics gathering.[Read More]

Monday Jan 03, 2011

Optimizer Transformation: Join Predicate Pushdown

Happy New Year to all of our readers! We hope you all had a great holiday season. We start the new year by continuing our series on Optimizer transformations. This time it is the turn of Predicate Pushdown. I would like to thank Rafi Ahmed for the content of this blog.

Normally,a view cannot be joined with an index-based nested loop (i.e., index access) join, since a view, in contrast with a base table, does not have an index defined on it. A view can only be joined with other tables using three methods: hash, nested loop, and sort-merge joins.[Read More]

Thursday Nov 04, 2010

Optimizer Transformations: Star Transformation

Star transformation was introduced in Oracle 8i to process star queries efficiently. These queries are commonly used in data warehouse applications that follow the Star Schema data model. The Star Schema is so called because the data model diagram resembles a star. The center of the star consists of one or more fact tables and the points of the star are the dimension tables.

star_model.PNG
The basic idea of this transformation is to steer clear of using a full table scan access method on large tables, referred to as fact tables in the Star Schema. In a typical star query, the fact table is joined to several much smaller dimension tables. The fact table typically contains one key (referred to as foreign key) for every dimension table as well as a number of measure columns such as sales amount. The corresponding key in the dimension table is referred to as the primary key. The join is based on a foreign key of the fact table with the corresponding primary key of the dimension table. The query also contains filter predicates on other columns of the dimension tables that typically are very restrictive. The combination of these filters help to dramatically reduce the data set processed from the fact table.  The goal of star transformation is to access only this reduced set of data from the fact table.


Consider the following star query Q1. The query is to find the total sales amount in all cities in California for quarters Q1 and Q2 of year 1999 through the Internet.

Q1:

SELECT c.cust_city, t.calendar_quarter_desc, SUM(s.amount_sold) sales_amount

FROM sales s, times t, customers c, channels ch

WHERE s.time_id = t.time_id

AND s.cust_id = c.cust_id

AND s.channel_id = ch.channel_id

AND c.cust_state_province = 'CA'

AND ch.channel_desc = 'Internet'

  AND t.calendar_quarter_desc IN ('1999-01','1999-02')

GROUP BY c.cust_city, t.calendar_quarter_desc;

Sales is the fact table while the other tables are considered as dimension tables. The Sales table contains one row for every sale of a product and thus it may contain billions of sales records. However only a few of them are sold to customers in California through the Internet for the specified quarters. The query is transformed into Q2.

Q2:

SELECT c.cust_city, t.calendar_quarter_desc, SUM(s.amount_sold) sales_amount

FROM sales s, times t, customers c

WHERE s.time_id = t.time_id

  AND s.cust_id = c.cust_id

  AND c.cust_state_province = 'CA'

  AND t.calendar_quarter_desc IN ('1999-01','1999-02')

  AND s.time_id IN (SELECT time_id
                            FROM times 
                            WHERE calendar_quarter_desc IN('1999-01','1999-02'))

  AND s.cust_id IN (SELECT cust_id
                           FROM customers
                           WHERE cust_state_province='CA')

  AND s.channel_id IN (SELECT channel_id  
                                 FROM channels 
                                 WHERE channel_desc = 'Internet')

GROUP BY c.cust_city, t.calendar_quarter_desc;


Star transformation is essentially about adding subquery predicates corresponding to the constraint dimensions. These subquery predicates are referred to as bitmap semi-join predicates. The transformation is performed when there are indexes on the fact join columns (s.timeid, s.custid...). By driving bitmap AND and OR operations (bitmaps can be from bitmap indexes or generated from regular B-Tree indexes) of the key values supplied by the subqueries, only the relevant rows from the fact table need to be retrieved.  If the filters on the dimension tables filter out a lot of data, this can be much more efficient than a full table scan on the fact table.  After the relevant rows have been retrieved from the fact table, they may need to be joined back to the dimension tables, using the original predicates. In some cases, the join back can be eliminated. We will discuss this situation later. 

Table 1 shows the query plan for the transformed query. Note that the sales table has a bitmap access path instead of a full table scan. For each key value coming from the subqueries (lines 11, 16, 21), the bitmaps are retrieved from the fact table indexes (lines 12, 17, 22).  Each bit in the bitmap corresponds to a row in fact table. The bit is set if the key value from the subquery is same as the value in the row of fact table.  For example, the bitmap [1][0][1][0][0][0]...(all 0s for remaining rows) indicate that rows 1 and 3 of fact table has matching key value from subquery.  Lets say the above bitmap is for a key value from customers table subquery.

The operations in lines 9, 14, 19 iterates over the keys from the subqueries and get the corresponding bitmaps. Lets say the customers subquery produces one more key value with the  bitmap [0][1][0][0][0][0]...

The bitmaps for each subquery are merged (ORed) (lines 8, 13 and 18). In the above example, it will produce a single bitmap [1][1][1][0][0][0]... for customers subquery after merging the two bitmaps.

The merged bitmaps are ANDed (line 7). Lets say the bitmap from channels is [1][0][0][0][0][0]...  If you AND this bitmap with the bitmap from customers subquery it will produce [1][0][0][0][0]...

The corresponding rowids of the final bitmap are generated (line 6).  The fact table rows are retrieved using the rowids (line 5).  In the above example, it will generate only 1 rowid corresponding to the first row and fetches only a single row instead of scanning the entire fact table.

The representation of bitmaps in the above example is for illustration purpose only. In oracle, they are represented and stored in a compressed form.


Table 1: The plan of the transformed query

Id

Operation

Name

0

SELECT STATEMENT

1

HASH GROUP BY

2

HASH JOIN

3

HASH JOIN

4

PARTITION RANGE SUBQUERY

5

TABLE ACCESS BY LOCAL INDEX ROWID

SALES

6

BITMAP CONVERSION TO ROWIDS

7

BITMAP AND

8

BITMAP MERGE

9

BITMAP KEY ITERATION

10

BUFFER SORT

11

TABLE ACCESS FULL

CHANNELS

12

BITMAP INDEX RANGE SCAN

SALES_CHANNEL_BIX

13

BITMAP MERGE

14

BITMAP KEY ITERATION

15

BUFFER SORT

16

TABLE ACCESS FULL

TIMES

17

BITMAP INDEX RANGE SCAN

SALES_TIME_BIX

18

BITMAP MERGE

19

BITMAP KEY ITERATION

20

BUFFER SORT

21

TABLE ACCESS FULL

CUSTOMERS

22

BITMAP INDEX RANGE SCAN

SALES_CUST_BIX

23

TABLE ACCESS FULL

CUSTOMERS

24

TABLE ACCESS FULL

TIMES


Join back elimination

The subqueries and their bitmap tree only filter the fact table based on the dimension filters, so it may still be necessary to join to the dimension table.  The join back of the dimension table is eliminated when all the predicates on dimension tables are part of the semijoin subquery predicate, the column(s) selected from the subquery are unique and the dimension columns are not in select list, group by etc. In the above example, the table channels is not joined back to the sales table since it is not referenced outside and channel_id is unique.

Temporary table transformation

If the join back is not eliminated, Oracle stores the results of the subquery in a temporary table to avoid re-scanning the dimension table (for bitmap key generation and join back). In addition to this, the results are materialized if the query is run in parallel, so that each slave can select the results from the temporary tables instead of executing the subquery again.

For example, if Oracle materializes the results of the subquery on customers into a temporary table, the transformed query Q3 will be as follows.

Q3:
SELECT t1.c1 cust_city, t.calendar_quarter_desc calendar_quarter_desc, 
              sum(s.amount_sold) sales_amount

FROM sales s, sh.times t, sys_temp_0fd9d6621_e7e24 t1

WHERE s.time_id=t.time_id

   AND s.cust_id=t1.c0

   AND (t.calendar_quarter_desc='1999-q1' OR t.calendar_quarter_desc='1999-q2')

   AND s.cust_id IN (SELECT  t1.c0 FROM sys_temp_0fd9d6621_e7e24 t1)

   AND s.channel_id IN (SELECT  ch.channel_id 
                                     FROM channels ch
                                     WHERE ch.channel_desc='internet')

  AND s.time_id IN (SELECT t.time_id
                               FROM times t
                               WHERE t.calendar_quarter_desc='1999-q1'
                                   OR t.calendar_quarter_desc='1999-q2')

GROUP BY t1.c1,  t.calendar_quarter_desc


Note that customers is replaced by the temporary table sys_temp_0fd9d6621_e7e24 and references to columns cust_id and cust_city are replaced by the corresponding columns of the temporary table. The temporary table will be created with 2 columns -  (c0 number, c1 varchar2(30)). These columns corresponds to cust_id and cust_city of customers table. The table will be populated using the following query Q4 at the beginning of the execution of the statement Q3.

Q4:
SELECT c.cust_id, c.cust_city FROM customers WHERE c.cust_state_province = 'CA'

Table 2 shows the plan for the transformed query.

Table 2: Plan with temporary table transformation


0

SELECT STATEMENT



1

TEMP TABLE TRANSFORMATION



2

LOAD AS SELECT

sys_temp_0fd9d6621_e7e24


3

TABLE ACCESS FULL

CUSTOMERS



4

HASH GROUP BY



5

HASH JOIN



6

HASH JOIN



7

PARTITION RANGE SUBQUERY



8

TABLE ACCESS BY LOCAL INDEX ROWID

SALES



9

BITMAP CONVERSION TO ROWIDS



10

BITMAP AND



11

BITMAP MERGE



12

BITMAP KEY ITERATION



13

BUFFER SORT



14

TABLE ACCESS FULL

CHANNELS



15

BITMAP INDEX RANGE SCAN

SALESCHANNELBIX



16

BITMAP MERGE



17

BITMAP KEY ITERATION



18

BUFFER SORT



19

TABLE ACCESS FULL

TIMES



20

BITMAP INDEX RANGE SCAN

SALESTIMEBIX



21

BITMAP MERGE



22

BITMAP KEY ITERATION



23

BUFFER SORT



24

TABLE ACCESS FULL

sys_temp_0fd9d6621_e7e24



25

BITMAP INDEX RANGE SCAN

SALESCUSTBIX



26

TABLE ACCESS FULL

sys_temp_0fd9d6621_e7e24



27

TABLE ACCESS FULL

TIMES


The lines 1,2 and 3 of the plan materialize the customers subquery into the temporary table. In line 24,  it scans the temporary table (instead of the subquery) to build the bitmap from the fact table. Line 26 is for scanning the temporary table for joining back instead of scanning customers. Note that the filter on customers is not needed to be applied on the temporary table since the filter is already applied while materializing the temporary table.


Enabling the transformation

Star transformation is controlled by the star_transformation_enabled parameter.  The parameter takes 3 values.

  • TRUE - The Oracle optimizer performs transformation by identifying fact and constraint dimension tables automatically. This is done in a cost-based manner, i.e. the transformation is performed only if the cost of the transformed plan is lower than the non-transformed plan. Also the optimizer will attempt temporary table transformation automatically whenever materialization improves performance.

  • FALSE - The transformation is not tried.

  • TEMP_DISABLE - This value has similar behavior as TRUE except that temporary table transformation is not tried.

The default value of the parameter is FALSE. You have to change the parameter value and create indexes on the joining columns of the fact table to take advantage of this transformation.


Summary
Star transformation improves the performance of queries with a very big fact table joined to multiple dimension tables when the dimension tables have very selective predicates. The transformation avoids the full scan of  the fact table. It fetches only relevant rows from the fact table that will eventually join to the constraint dimension rows. The transformation is performed based on cost - only when the cost of the transformed plan is lower than that of the non-transformed plan.  If the dimension filters do not significantly reduce the amount of data to be retrieved from the fact table, then a full table scan is more efficient.

In this post we have tried to illustrate the basic ideas behind star transformation by showing  simple example queries and plans. Oracle can do star transformation in more complex cases. For example, a query with multiple fact tables, snowflakes (dimension is a join of several normalized tables instead of denormalized single table), etc.

[Read More]
About

The Oracle Optimizer blog is written by members of the Optimizer development team. The goal of this blog is to provide an insight into the workings of the Optimizer and the statistics it relies on. The views expressed on this blog are our own and do not necessarily reflect the views of Oracle and its affiliates. The views and opinions expressed by visitors on this blog are theirs solely and may not reflect ours.

Search

Archives
« May 2016
SunMonTueWedThuFriSat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
    
       
Today