OR Dear Me!  When Cost Based OR  Expansion Gets it Wrong – Part 1

The Cost Based OR Expansion transformation allows the optimizer to generate execution plans which often perform better than could be otherwise achieved. But sometimes, as in a case I have been recently investigating, it can cause things to go wrong.  I have modeled the behavior and will demonstrate in it this article.  Planned subsequent articles will drill into the calculations both with and without the transformation, and potential work-arounds.
I’m not going to waste time on describing the basics of the transformation itself, if that’s what you need I suggest you check out articles by Nigel Bayliss, Nenad Noveljic and Mohamed Houri.

SQL> CREATE TABLE t (c NUMBER(2, 0) NOT NULL,
  2*                 p VARCHAR2(4000));
Table T created.
SQL> INSERT /*+append*/ INTO t
  2      SELECT
  3          mod(ROWNUM, 100) c,
  4          rpad('X', 4000)  padding
  5      FROM
  6          dual
  7      CONNECT BY
  8*         ROWNUM <= 100000;
100 000 rows inserted.
SQL> exec dbms_stats.gather_table_stats(null, 't', method_opt=>'for all columns size 1');
PL/SQL procedure successfully completed.

So we have a table containing 100,000 rows, and that column C contains 100 distinct values, ranging from 0 to 99.  For simplicity I have not created  histogram on C, but the existance of a histogram does not significantly affect the behaviour I will demonstrate.

SQL> SELECT /*+gather_plan_statistics*/ DISTINCT trim(p) p FROM t WHERE
  2          (c BETWEEN  0 AND  1) OR (c BETWEEN  2 AND  3) OR (c BETWEEN  4 AND  5) OR (c BETWEEN  6 AND  7) OR (c BETWEEN  8 AND  9)
  3       OR (c BETWEEN 10 AND 11) OR (c BETWEEN 12 AND 13) OR (c BETWEEN 14 AND 15) OR (c BETWEEN 16 AND 17) OR (c BETWEEN 18 AND 19)
  4       OR (c BETWEEN 20 AND 21) OR (c BETWEEN 22 AND 23) OR (c BETWEEN 24 AND 25) OR (c BETWEEN 26 AND 27) OR (c BETWEEN 28 AND 29)
  5       OR (c BETWEEN 30 AND 31) OR (c BETWEEN 32 AND 33) OR (c BETWEEN 34 AND 35) OR (c BETWEEN 36 AND 37) OR (c BETWEEN 38 AND 39)
  6       OR (c BETWEEN 40 AND 41) OR (c BETWEEN 42 AND 43) OR (c BETWEEN 44 AND 45) OR (c BETWEEN 46 AND 47) OR (c BETWEEN 48 AND 49)
  7       OR (c BETWEEN 50 AND 51) OR (c BETWEEN 52 AND 53) OR (c BETWEEN 54 AND 55) OR (c BETWEEN 56 AND 57) OR (c BETWEEN 58 AND 59)
  8       OR (c BETWEEN 60 AND 61) OR (c BETWEEN 62 AND 63) OR (c BETWEEN 64 AND 65) OR (c BETWEEN 66 AND 67) OR (c BETWEEN 68 AND 69)
  9       OR (c BETWEEN 70 AND 71) OR (c BETWEEN 72 AND 73) OR (c BETWEEN 74 AND 75) OR (c BETWEEN 76 AND 77) OR (c BETWEEN 78 AND 79)
 10       OR (c BETWEEN 80 AND 81) OR (c BETWEEN 82 AND 83) OR (c BETWEEN 84 AND 85) OR (c BETWEEN 86 AND 87) OR (c BETWEEN 88 AND 89)
 11*      OR (c BETWEEN 90 AND 91) OR (c BETWEEN 92 AND 93) OR (c BETWEEN 94 AND 95) OR (c BETWEEN 96 AND 97) OR (c BETWEEN 98 AND 99);
   P
____
X
SQL> SELECT * FROM dbms_xplan.display_cursor(format=>'allstats last -bytes -cost -predicate');
...
----------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |
----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |      1 |00:00:01.18 |     100K|    100K|
|   1 |  HASH UNIQUE       |      |      1 |      1 |      1 |00:00:01.18 |     100K|    100K|
|   2 |   TABLE ACCESS FULL| T    |      1 |  77857 |    100K|00:00:01.35 |     100K|    100K|
----------------------------------------------------------------------------------------------

The optimizer estimated (E-Rows) that only 77,857 rows would need to be retrieved, whereas in reality (as should be obvious by comparing the query with the data) all 100,000 rows needed to be retrieved. While the estimate is not perfect, it’s reasonably close,  and as the database doesn’t have any alternatives choses to perform a full table scan, on my test system completing in about a second.

Contrast that behaviour with what happens after an index is created.

SQL> CREATE INDEX i ON t (c);
Index I created.
SQL> SELECT /*+gather_plan_statistics*/ DISTINCT trim(p) p FROM t WHERE
  2         (c BETWEEN  0 AND  1) OR (c BETWEEN  2 AND  3) OR (c BETWEEN  4 AND  5) OR (c BETWEEN  6 AND  7) OR (c BETWEEN  8 AND  9)
  3      OR (c BETWEEN 10 AND 11) OR (c BETWEEN 12 AND 13) OR (c BETWEEN 14 AND 15) OR (c BETWEEN 16 AND 17) OR (c BETWEEN 18 AND 19)
  4      OR (c BETWEEN 20 AND 21) OR (c BETWEEN 22 AND 23) OR (c BETWEEN 24 AND 25) OR (c BETWEEN 26 AND 27) OR (c BETWEEN 28 AND 29)
  5      OR (c BETWEEN 30 AND 31) OR (c BETWEEN 32 AND 33) OR (c BETWEEN 34 AND 35) OR (c BETWEEN 36 AND 37) OR (c BETWEEN 38 AND 39)
  6      OR (c BETWEEN 40 AND 41) OR (c BETWEEN 42 AND 43) OR (c BETWEEN 44 AND 45) OR (c BETWEEN 46 AND 47) OR (c BETWEEN 48 AND 49)
  7      OR (c BETWEEN 50 AND 51) OR (c BETWEEN 52 AND 53) OR (c BETWEEN 54 AND 55) OR (c BETWEEN 56 AND 57) OR (c BETWEEN 58 AND 59)
  8      OR (c BETWEEN 60 AND 61) OR (c BETWEEN 62 AND 63) OR (c BETWEEN 64 AND 65) OR (c BETWEEN 66 AND 67) OR (c BETWEEN 68 AND 69)
  9      OR (c BETWEEN 70 AND 71) OR (c BETWEEN 72 AND 73) OR (c BETWEEN 74 AND 75) OR (c BETWEEN 76 AND 77) OR (c BETWEEN 78 AND 79)
 10      OR (c BETWEEN 80 AND 81) OR (c BETWEEN 82 AND 83) OR (c BETWEEN 84 AND 85) OR (c BETWEEN 86 AND 87) OR (c BETWEEN 88 AND 89)
 11*     OR (c BETWEEN 90 AND 91) OR (c BETWEEN 92 AND 93) OR (c BETWEEN 94 AND 95) OR (c BETWEEN 96 AND 97) OR (c BETWEEN 98 AND 99);
   P
____
X
SQL> SELECT * FROM dbms_xplan.display_cursor(format=>'allstats last -bytes -cost -predicate');
                                          
...
-----------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                              | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |
-----------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                       |                 |      1 |        |      1 |00:00:05.81 |     100K|    100K|
|   1 |  HASH UNIQUE                           |                 |      1 |      1 |      1 |00:00:05.81 |     100K|    100K|
|   2 |   VIEW                                 | VW_ORE_1B35BA0F |      1 |  26653 |    100K|00:00:10.36 |     100K|    100K|
|   3 |    UNION-ALL                           |                 |      1 |        |    100K|00:00:08.46 |     100K|    100K|
|   4 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   2010 |   2000 |00:00:01.52 |    2005 |   2004 |
|   5 |      INDEX RANGE SCAN                  | I               |      1 |   2010 |   2000 |00:00:00.02 |       5 |      4 |
|   6 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   2950 |   2000 |00:00:02.81 |    2006 |   2004 |
|   7 |      INDEX RANGE SCAN                  | I               |      1 |   2950 |   2000 |00:00:00.02 |       6 |      4 |
|   8 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   2832 |   2000 |00:00:02.35 |    2006 |   2004 |
|   9 |      INDEX RANGE SCAN                  | I               |      1 |   2832 |   2000 |00:00:00.02 |       6 |      4 |
|  10 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   2666 |   2000 |00:00:02.30 |    2006 |   2004 |
|  11 |      INDEX RANGE SCAN                  | I               |      1 |   2666 |   2000 |00:00:00.02 |       6 |      4 |
|  12 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   2462 |   2000 |00:00:01.71 |    2006 |   2004 |
|  13 |      INDEX RANGE SCAN                  | I               |      1 |   2462 |   2000 |00:00:00.02 |       6 |      4 |
|  14 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   2231 |   2000 |00:00:01.95 |    2006 |   2004 |
|  15 |      INDEX RANGE SCAN                  | I               |      1 |   2231 |   2000 |00:00:00.05 |       6 |      4 |
|  16 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   1985 |   2000 |00:00:01.84 |    2006 |   2004 |
|  17 |      INDEX RANGE SCAN                  | I               |      1 |   1985 |   2000 |00:00:00.02 |       6 |      4 |
|  18 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   1736 |   2000 |00:00:01.71 |    2006 |   2004 |
|  19 |      INDEX RANGE SCAN                  | I               |      1 |   1736 |   2000 |00:00:00.02 |       6 |      4 |
|  20 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   1492 |   2000 |00:00:02.08 |    2006 |   2004 |
|  21 |      INDEX RANGE SCAN                  | I               |      1 |   1492 |   2000 |00:00:00.02 |       6 |      4 |
|  22 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   1262 |   2000 |00:00:01.93 |    2005 |   2003 |
|  23 |      INDEX RANGE SCAN                  | I               |      1 |   1262 |   2000 |00:00:00.02 |       5 |      3 |
|  24 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |   1051 |   2000 |00:00:02.01 |    2006 |   2004 |
|  25 |      INDEX RANGE SCAN                  | I               |      1 |   1051 |   2000 |00:00:00.02 |       6 |      4 |
|  26 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    863 |   2000 |00:00:02.04 |    2006 |   2004 |
|  27 |      INDEX RANGE SCAN                  | I               |      1 |    863 |   2000 |00:00:00.04 |       6 |      4 |
|  28 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    698 |   2000 |00:00:01.52 |    2006 |   2004 |
|  29 |      INDEX RANGE SCAN                  | I               |      1 |    698 |   2000 |00:00:00.02 |       6 |      4 |
|  30 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    557 |   2000 |00:00:01.59 |    2006 |   2004 |
|  31 |      INDEX RANGE SCAN                  | I               |      1 |    557 |   2000 |00:00:00.02 |       6 |      4 |
|  32 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    439 |   2000 |00:00:01.56 |    2006 |   2004 |
|  33 |      INDEX RANGE SCAN                  | I               |      1 |    439 |   2000 |00:00:00.02 |       6 |      4 |
|  34 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    343 |   2000 |00:00:01.69 |    2006 |   2004 |
|  35 |      INDEX RANGE SCAN                  | I               |      1 |    343 |   2000 |00:00:00.02 |       6 |      4 |
|  36 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    264 |   2000 |00:00:02.02 |    2006 |   2004 |
|  37 |      INDEX RANGE SCAN                  | I               |      1 |    264 |   2000 |00:00:00.02 |       6 |      4 |
|  38 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    202 |   2000 |00:00:01.59 |    2006 |   2004 |
|  39 |      INDEX RANGE SCAN                  | I               |      1 |    202 |   2000 |00:00:00.03 |       6 |      4 |
|  40 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    153 |   2000 |00:00:01.41 |    2006 |   2005 |
|  41 |      INDEX RANGE SCAN                  | I               |      1 |    153 |   2000 |00:00:00.02 |       6 |      5 |
|  42 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |    115 |   2000 |00:00:01.42 |    2005 |   2003 |
|  43 |      INDEX RANGE SCAN                  | I               |      1 |    115 |   2000 |00:00:00.02 |       5 |      3 |
|  44 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     86 |   2000 |00:00:01.60 |    2006 |   2004 |
|  45 |      INDEX RANGE SCAN                  | I               |      1 |     86 |   2000 |00:00:00.02 |       6 |      4 |
|  46 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     64 |   2000 |00:00:01.40 |    2006 |   2004 |
|  47 |      INDEX RANGE SCAN                  | I               |      1 |     64 |   2000 |00:00:00.02 |       6 |      4 |
|  48 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     47 |   2000 |00:00:01.47 |    2006 |   2004 |
|  49 |      INDEX RANGE SCAN                  | I               |      1 |     47 |   2000 |00:00:00.02 |       6 |      4 |
|  50 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     35 |   2000 |00:00:01.46 |    2006 |   2004 |
|  51 |      INDEX RANGE SCAN                  | I               |      1 |     35 |   2000 |00:00:00.02 |       6 |      4 |
|  52 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     26 |   2000 |00:00:01.44 |    2006 |   2004 |
|  53 |      INDEX RANGE SCAN                  | I               |      1 |     26 |   2000 |00:00:00.02 |       6 |      4 |
|  54 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     19 |   2000 |00:00:01.47 |    2006 |   2004 |
|  55 |      INDEX RANGE SCAN                  | I               |      1 |     19 |   2000 |00:00:00.02 |       6 |      4 |
|  56 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     14 |   2000 |00:00:01.37 |    2006 |   2004 |
|  57 |      INDEX RANGE SCAN                  | I               |      1 |     14 |   2000 |00:00:00.02 |       6 |      4 |
|  58 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |     10 |   2000 |00:00:01.35 |    2006 |   2004 |
|  59 |      INDEX RANGE SCAN                  | I               |      1 |     10 |   2000 |00:00:00.04 |       6 |      4 |
|  60 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      8 |   2000 |00:00:01.39 |    2006 |   2004 |
|  61 |      INDEX RANGE SCAN                  | I               |      1 |      8 |   2000 |00:00:00.02 |       6 |      4 |
|  62 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      6 |   2000 |00:00:01.40 |    2006 |   2004 |
|  63 |      INDEX RANGE SCAN                  | I               |      1 |      6 |   2000 |00:00:00.03 |       6 |      4 |
|  64 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      4 |   2000 |00:00:01.53 |    2005 |   2003 |
|  65 |      INDEX RANGE SCAN                  | I               |      1 |      4 |   2000 |00:00:00.02 |       5 |      3 |
|  66 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      3 |   2000 |00:00:01.41 |    2006 |   2004 |
|  67 |      INDEX RANGE SCAN                  | I               |      1 |      3 |   2000 |00:00:00.02 |       6 |      4 |
|  68 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      2 |   2000 |00:00:01.42 |    2006 |   2005 |
|  69 |      INDEX RANGE SCAN                  | I               |      1 |      2 |   2000 |00:00:00.03 |       6 |      5 |
|  70 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      2 |   2000 |00:00:01.72 |    2006 |   2004 |
|  71 |      INDEX RANGE SCAN                  | I               |      1 |      2 |   2000 |00:00:00.03 |       6 |      4 |
|  72 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.45 |    2006 |   2004 |
|  73 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.03 |       6 |      4 |
|  74 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.51 |    2006 |   2004 |
|  75 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  76 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.42 |    2006 |   2004 |
|  77 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  78 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.56 |    2006 |   2004 |
|  79 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  80 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.64 |    2006 |   2004 |
|  81 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  82 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.42 |    2006 |   2004 |
|  83 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  84 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.56 |    2006 |   2004 |
|  85 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  86 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.39 |    2005 |   2003 |
|  87 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       5 |      3 |
|  88 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.41 |    2006 |   2004 |
|  89 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.03 |       6 |      4 |
|  90 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.52 |    2006 |   2004 |
|  91 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.03 |       6 |      4 |
|  92 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.45 |    2006 |   2004 |
|  93 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  94 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.45 |    2006 |   2004 |
|  95 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
|  96 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.41 |    2006 |   2005 |
|  97 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.03 |       6 |      5 |
|  98 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.42 |    2006 |   2004 |
|  99 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
| 100 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.43 |    2006 |   2004 |
| 101 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
| 102 |     TABLE ACCESS BY INDEX ROWID BATCHED| T               |      1 |      1 |   2000 |00:00:01.41 |    2006 |   2004 |
| 103 |      INDEX RANGE SCAN                  | I               |      1 |      1 |   2000 |00:00:00.02 |       6 |      4 |
-----------------------------------------------------------------------------------------------------------------------------

After adding the index, the estimated number of rows that to be fetched has dropped from 77,857 to 26,653, and the rows are now fetched using the index, resulting in an execution plan that takes either 6 or 8 seconds (depending on which line of the plan you choose to believe) to complete.

In the next article we will drill into how the original cardinality estimate of 77,857 came about, before we see how the Cost Based OR Expansion caused things to go wrong.

1 thought on “OR Dear Me!  When Cost Based OR  Expansion Gets it Wrong – Part 1”

  1. Pingback: OR Dear Me!  When Cost Based OR  Expansion Gets it Wrong – Part 2 | jolliffe.hk

Leave a Comment

Your email address will not be published. Required fields are marked *