Monday, February 22, 2010

Oracle Range Join Cardinality Latest Changes

In this post I’d like to describe the latest changes in the cardinality calculation for joins of tables.  All the changes are checked for the Oracle version 11.2.0.1.  The version of Oracle 10g which I cite to throughout the passage is 10.2.0.4. The ideas of how it works in Oracle 10g were taken from the book “Cost-Based Oracle Fundamentals” by Jonathan Lewis.

t2.join1 > t1.join1
Let’s take a glance at the next query:
SELECT t1.v1, t2.v1
  FROM t1, t2
 WHERE t1.filter = 1 -- 25 unique values
   AND t2.join1 > t1.join1 -- 40 and 30 unique values correspondingly
   AND t2.filter = 1 -- 50 unique values
;
This is an example from J. Lewis’ book. In the comments you can see the numbers of unique values in conformable columns. Both tables have 10 000 rows, so after filtering t2 has 200 rows, and t1 has 400 rows. The t2.join1 column has 40 unique values from 1 to 40, and the t1.join1 column has correspondingly 30 unique values from 1 to 30. According to the book, Oracle 10g uses static selectivity 5% to calculate the cardinality of this query. Here’s the execution plan:
------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost  | 
------------------------------------------------------------ 
|   0 | SELECT STATEMENT    |      |  4000 |   132K|   155 | 
|   1 |  MERGE JOIN         |      |  4000 |   132K|   155 | 
|   2 |   SORT JOIN         |      |   200 |  3400 |    77 | 
|*  3 |    TABLE ACCESS FULL| T2   |   200 |  3400 |    30 | 
|*  4 |   SORT JOIN         |      |   400 |  6800 |    78 | 
|*  5 |    TABLE ACCESS FULL| T1   |   400 |  6800 |    30 | 
------------------------------------------------------------ 
Predicate Information (identified by operation id): 
--------------------------------------------------- 
   3 - filter("T2"."FILTER"=1) 
   4 - access(INTERNAL_FUNCTION("T2"."JOIN1")>INTERNAL_FUNCTION("T1"."JOIN1")) 
       filter(INTERNAL_FUNCTION("T2"."JOIN1")>INTERNAL_FUNCTION("T1"."JOIN1")) 
   5 - filter("T1"."FILTER"=1)
As you can see, the cardinality is 4000, which is equal to 200 * 400 * 0.05. Now let’s take a look at the execution plan for the same query executed in Oracle 11g:
------------------------------------------------------------ 
| Id  | Operation           | Name | Rows  | Bytes | Cost  | 
------------------------------------------------------------ 
|   0 | SELECT STATEMENT    |      | 49000 |  1626K|    82 | 
|   1 |  MERGE JOIN         |      | 49000 |  1626K|    82 | 
|   2 |   SORT JOIN         |      |   200 |  3400 |    38 | 
|*  3 |    TABLE ACCESS FULL| T2   |   200 |  3400 |    28 | 
|*  4 |   SORT JOIN         |      |   400 |  6800 |    39 | 
|*  5 |    TABLE ACCESS FULL| T1   |   400 |  6800 |    28 | 
------------------------------------------------------------ 
Predicate Information (identified by operation id): 
--------------------------------------------------- 
   3 - filter("T2"."FILTER"=1) 
   4 - access(INTERNAL_FUNCTION("T2"."JOIN1")>INTERNAL_FUNCTION("T1"."JOIN1")) 
       filter(INTERNAL_FUNCTION("T2"."JOIN1")>INTERNAL_FUNCTION("T1"."JOIN1")) 
   5 - filter("T1"."FILTER"=1)
As you can see, Oracle 11g thinks it’s going to be 49 000 rows returned which is way much more then 10g’s assumption.
Let me explain how I think Oracle calculates this number and the cardinality for such queries in general.

Boring Math
Let’s take a look at the picture. You can see there two lines which represent unique values in columns t2.join1 (left bold vertical line) and t1.join1 (right bold vertical line). Also you can notice than the high_value in t2.join1 is greater than the high_value in t1.join1, that the low_value of t2.join1 is greater than the low_value in t1.join1, and finally that the low_value in t2.join1 is lower than the high_value in t1.join1. The horizontal intermittent lines, drawn through high_values and low_values, mark out three sectors: A, B, and C. This is the most common case of correlation between low_lalues and high_values I could make up as there’re all three segments. If you move those two lines against each other you can achieve existing of two adjacent sectors or even only one of them at all. As you can foresee, the cardinality in every sector is being calculated separately.

Sector A
Logically, for every t2 value for the sector A there should be picked out every value from t1.join1:
Cardinality of A = (high_value(t2) – high_value(t1)) * num_rows(t1) * num_rows(t2) / num_distinct(t2)
Of course it’s relevant only if the condition high_value(t2) – high_value(t1) > 0 is met.

Sector B
For simplicities sake, I’ve separated calculation of cardinality below the sector A in two different sectors even though its not quite right. Why it’s not, because essentially it’s left to count the cardinality for the only segment high_value(t2) – low_value(t2). On the other hand, intersecting that segment with the t1’s values line we’ll get two sectors: one with common values (sector B), and one without (Sector C). Apparently, for each t2.jon1 value there should be counted some number of t1.join1 values from sector B plus all the t1.join1 values from sector C.
Let’s count the B’s cardinality as if there’s no sector C at all (the number of values for t2.join1 values between high_value(t2) and low_value(t2) in terms of values from t1.join1 that are in the sector B). In that case for every value of t2.join1 there should be picked out all the values of t1.join1 that are less that the current t2.join1 value. For instance, if high_value(t1) = 5, low_value(t2) = 1, then for t2.join1 = 5 the t1.join1 values are 4, 3, 2, and 1 (there’re four of them). For t2.join1 = 4 there are one fewer of t1.join1 values (three of them), and so forth. Ultimately, we have a descending number of values from t1 for t2’s values with one fewer on each next step. The whole number of t1.join1’s values can be calculated by the formula for summing of arithmetic progressions:
Sn = ((An + A1) / 2) * n
Where An is the nth element of progression, and A1 – first element. In our case A1 always equals to 1, while An = high_value(t1) – low_value(t2). Pay attention, that in that case we are interested in the NUMBER of values between high and low values rather that in the exact values. We need to know how many times every value will be counted during the final cardinality estimation. Correspondingly, n can be calculated in that way:
n = high_value(t1) – low_value(t2)
Knowing all the stuff above we are able to calculate the cardinality for the sector B:
Cardinality on B = (num_rows(t2) / num_distinct(t2)) * (num_rows(t1) / num_distinct(t1)) * (high_value(t1) – low_value(t2)) * (high_value(t1) – low_value(t2) + 1) / 2
that is, the number of rows for every value from t2.join1 for that sector multiply the number of rows for one value for t1.join1 multiply the number of such “entries”, which is the sum of the progression discussed above.

Sector C
If that sector exists, for every t2.join2 value from sector B you should also include all the values of t1.join1 which are below the low_value of t2:
Cardinality of C = (low_value(t2) – low_value(t1)) * (high_value(t1) – low_value(t2) + 1) * num_rows(t2) / num_distinct(t2) * num_rows(t1) / num_distinct(t1)

The Final Cardinality
Finally, let’s assemble the cardinality formula:
Cardinality of Join = Cardinality of A + Cardinality of B + Cardinality of C
To save space, let’s derive the selectivity formula dividing the sum by num_rows(t2) * num_rows(t1):
Selectivity of Join = (high_value(t2) – high_value(t1)) / num_distinct(t2) + 1 / num_distinct(t2)) * 1 / num_distinct(t1)) * (high_value(t1) – low_value(t2)) * (high_value(t1) – low_value(t2) + 1) / 2 + (low_value(t2) – low_value(t1)) * (high_value(t1) – low_value(t2) + 1) * 1 / num_distinct(t2) * 1 / num_distinct(t1)
After beautifying and generalizing we can get the final formula:
Cardinality of join = Filtered cardinality (t1) * Filtered Cardinality (t2) * Selectivity of Join
Selectivity of Join = (A + (B + C) / num_distinct(t1)) / num_distinct(t2)
A = high_value(t2) – high_value(t1), where high_value(t2) > high_value(t1). Otherwise A = 0
B = (least(high_value(t2), high_value(t1)) – great(low_value(t1), low_value(t2)) * (least(high_value(t2), high_value(t1)) – great(low_value(t1), low_value(t2)) + 1) / 2
C = (great(low_value(t1), low_value(t2)) – least(low_value(t1), low_value(t2))) * (least(high_value(t2), high_value(t1)) - great(low_value(t1), low_value(t2)) + 1), where low_value(t2) > low_value(t1). Otherwise C = 0
t2 is the table which is on the left side of the sigh “>”, and t1 is the table on the right side correspondingly

The Example
Let’s get back to the example in the beginning of the article and perform manual calculation of cardinality:
A = 40 – 30 = 10
B = (30 – 1) * (30 – 1 + 1) / 2 = 29 * 30 / 2 = 435
C = 0
Selectivity of Join = (10 + 435 / 30) / 40 = 0.6125
Cardinality of Join = 200 * 400 * 0.6125 = 49 000

t2.join1 >= t1.join1
I can’t finish this article without bringing up the “>=” range join. Essentially, addition of the equality sign should add num_rows(t2) / num_distinct(t2) * num_rows(t1) / num_distinct(t1) rows into the final cardinality. If you want not to forget about it, you can change the formula and add 1 to A if you have the equality sign. For instance, let’s apply it to the test query:
A = 40 – 30 + 1 = 11
B = … = 435
C = 0
Selectivity of Join = (11 + 435 / 30) / 40 = 0.6375
Cardinality of Join = 200 * 400 * 0.6375 = 51 000
Here’s the execution plan:
------------------------------------------------------------- 
| Id  | Operation            | Name | Rows  | Bytes | Cost  | 
------------------------------------------------------------- 
|   0 | SELECT STATEMENT     |      | 51000 |  1693K|    83 | 
|   1 |  WINDOW BUFFER       |      | 51000 |  1693K|    83 | 

|   2 |   MERGE JOIN         |      | 51000 |  1693K|    83 | 
|   3 |    SORT JOIN         |      |   200 |  3400 |    38 | 
|*  4 |     TABLE ACCESS FULL| T2   |   200 |  3400 |    28 | 
|*  5 |    SORT JOIN         |      |   400 |  6800 |    39 | 
|*  6 |     TABLE ACCESS FULL| T1   |   400 |  6800 |    28 | 
------------------------------------------------------------- 
Predicate Information (identified by operation id): 
--------------------------------------------------- 
   4 - filter("T2"."FILTER"=1) 
   5 - access(INTERNAL_FUNCTION("T2"."JOIN1")>=INTERNAL_FUNCTION("T1"."JOIN1")) 
       filter(INTERNAL_FUNCTION("T2"."JOIN1")>=INTERNAL_FUNCTION("T1"."JOIN1")) 
   6 - filter("T1"."FILTER"=1)

That is all I wanted to cover in this article. In a next one I am going to cover the between operation.