Oracle Scratchpad

January 30, 2012

Index Hash

Filed under: CBO,Indexing,Oracle,Troubleshooting — Jonathan Lewis @ 6:12 pm BST Jan 30,2012

You might think from the title that this little note is going to be about the index hash join – you would be half right, it’s also about how the optimizer seems to make a complete hash of dealing with index hash joins.

Let’s set up a simple data set and a couple of indexes so that we can take a closer look:

create table t1
as
with generator as (
	select	--+ materialize
		rownum id
	from dual
	connect by
		level <= 10000
)
select
	rownum			id,
	mod(rownum-1,20)	flag,
	lpad(rownum,10,'0')	v10,
	lpad(rownum,20,'0')	v20,
	lpad(rownum,30,'0')	v30,
	rpad('x',100)		padding
from
	generator	v1,
	generator	v2
where
	rownum <= 100000
;

-- gather stats, compute, no histograms

alter table t1 add constraint t1_pk primary key(id)
	using index (create index t1_pk on t1(id))
;

create index t1_flag on t1(flag);

create index t1_ia on t1(id, v20);
create index t1_ib on t1(id, v10);
create index t1_ic on t1(id, v30);

The indexing is a little unusual, but does represent the sort of thing I see from time to time. In particular, the “primary key plus one more column” can be helpful to make critical queries visit only the index and not visit the table; having three such indexes is a bit over the top. Look carefully and you’ll notice that the ia, ib, ic indexes look a little out of order compared to the v20, v10, v30 columns they are built on.

Now try running the following SQL with autotrace enabled:

select /*+ index_ffs(t1 t1_pk) */ count(*) from t1;
select /*+ index_ffs(t1 t1_ia) */ count(*) from t1;
select /*+ index_ffs(t1 t1_ib) */ count(*) from t1;
select /*+ index_ffs(t1 t1_ic) */ count(*) from t1;
select /*+ index_ffs(t1 t1_flag) */ count(*) from t1 where flag is not null;

These are the results I got from 11.2.0.3 (and this test reproduces under 10.2.0.3 and 11.1.0.7). I’ve shown the full plan for the first query, but only the critical operation with its cost for the rest of them:

-------------------------------------------------------
| Id  | Operation             | Name  | Rows  | Cost  |
-------------------------------------------------------
|   0 | SELECT STATEMENT      |       |     1 |    35 |
|   1 |  SORT AGGREGATE       |       |     1 |       |
|   2 |   INDEX FAST FULL SCAN| T1_PK |   100K|    35 |
-------------------------------------------------------

|   2 |   INDEX FAST FULL SCAN| T1_IA |   100K|    80 |
|   2 |   INDEX FAST FULL SCAN| T1_IB |   100K|    59 |
|   2 |   INDEX FAST FULL SCAN| T1_IC |   100K|   101 |

|*  2 |   INDEX FAST FULL SCAN| T1_FLAG |   100K|   292K|    31 |

As you might expect, the longer the “extra” column, the higher the cost. It’s an interesting little detail that the queries that didn’t need to look at a data column didn’t report a “bytes” column in the execution plan – just one clue that there’s a special optimisation for the generic “count everything” query.

Finally, we can get to the index hash join.

select	sum(id)
from
	t1
where
	flag = 0;
;

Clearly, this query could do a full tablescan, but it could do a hash join between the t1_flag index and one of the other indexes. Given that the primary key index has the lowest fast full scan cost at 35, and the index fast full scan on the t1_flag index is 31, we might hope to see an index hash join with a cost of about 66. Here’s the default plan:

-----------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost  |
-----------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |     8 |   380 |
|   1 |  SORT AGGREGATE    |      |     1 |     8 |       |
|*  2 |   TABLE ACCESS FULL| T1   |  5000 | 40000 |   380 |
-----------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("FLAG"=0)

It’s a full tablescan, with a cost of 380. So let’s hint an index hash join with the two indexes we hoped to see, and find out what happens. I added the hint /*+ index_join(t1) */ and got the following execution plan:

----------------------------------------------------------------------------
| Id  | Operation               | Name             | Rows  | Bytes | Cost  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |                  |     1 |     8 |   533 |
|   1 |  SORT AGGREGATE         |                  |     1 |     8 |       |
|*  2 |   VIEW                  | index$_join$_001 |  5000 | 40000 |   533 |
|*  3 |    HASH JOIN            |                  |       |       |       |
|*  4 |     INDEX RANGE SCAN    | T1_FLAG          |  5000 | 40000 |    10 |
|   5 |     INDEX FAST FULL SCAN| T1_IA            |  5000 | 40000 |   645 |
----------------------------------------------------------------------------

Note three anomalies:
a) Oracle has obeyed the index_join directive, but it’s used the “wrong” index
b) the cost of the query (533) is less than the cost of one of its operations (645 at line 5)
c) the cost of an index fast full scan on t1_ia has jumped from 80 (previous test) to 645

(Addendum, Mar 2012: this test followed my usual “repeatability” setup – 8KB block size, locally managed uniform extents at 1MB, freelist management and (see comment below) CPU costing disabled)

So let’s add a hint to get the right index used:

select
	/*+
		qb_name(main)
		index_join(@main t1 t1_flag t1_pk)
	*/
	sum(id)
from
	t1
where
	flag = 0
;

This makes no difference, Oracle still uses index t1_ia instead of t1_pk. It’s only when I include an undocumented hint that Oracle does what I want:

explain plan for
select
	/*+
		qb_name(main)
		outline_leaf(@main)
		index_join(@main t1 t1_flag t1_pk)
	*/
	sum(id)
from
	t1
where
	flag = 0
;

select * from table(dbms_xplan.display(null,null,'outline'));

----------------------------------------------------------------------------
| Id  | Operation               | Name             | Rows  | Bytes | Cost  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |                  |     1 |     8 |   240 |
|   1 |  SORT AGGREGATE         |                  |     1 |     8 |       |
|*  2 |   VIEW                  | index$_join$_001 |  5000 | 40000 |   240 |
|*  3 |    HASH JOIN            |                  |       |       |       |
|*  4 |     INDEX RANGE SCAN    | T1_FLAG          |  5000 | 40000 |    10 |
|   5 |     INDEX FAST FULL SCAN| T1_PK            |  5000 | 40000 |   279 |
----------------------------------------------------------------------------

Outline Data
-------------
  /*+
      BEGIN_OUTLINE_DATA
      INDEX_JOIN(@"MAIN" "T1"@"MAIN" ("T1"."FLAG") ("T1"."ID"))
      OUTLINE(@"MAIN")
      OUTLINE_LEAF(@"MAIN")
      OUTLINE_LEAF(@"SEL$998059AF")
      ALL_ROWS
      OPT_PARAM('_optimizer_cost_model' 'io')
      DB_VERSION('11.2.0.3')
      OPTIMIZER_FEATURES_ENABLE('11.2.0.3')
      IGNORE_OPTIM_EMBEDDED_HINTS
      END_OUTLINE_DATA
  */

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("FLAG"=0)
   3 - access(ROWID=ROWID)
   4 - access("FLAG"=0)

You might note that with the right index in play
a) The cost of the plan is now lower than the cost of the tablescan
b) The total cost of the plan is still lower than the cost of the fast full scan
c) The cost of the fast full scan in the hash join is much higher than the cost of a standalone fast full scan

Analysis

I’ve said many times that I hardly ever look at a 10053 trace. The trouble is, when I do have to look at a 10053 I usually want to tell everyone how clever I’ve been; this means that I can give people the impression that the only way to solve optimizer problems is to look at 10053 traces – it’s not, but this time around it seemed like a good idea.

Problem 1: in the calculation for the cost of the fast full scan for an index hash join, the optimizer starts by calculating the cost of an index full scan, then adds the original cost of the fast full scan to that figure.

Problem 2: when considering the index hash join, the optimizer looks at the indexes in alphabetical order of name, and selects the first legal candidate. This is why my tests had 3 extra candidates with three different sizes. Try dropping index t1_ia and Oracle will use t1_ib; alernatively change the name of t1_ia to t1_id and, again, Oracle will use t1_ib. The primary key didn’t have a chance, being way down the alphabet at t1_pk. (In passing, I also tried re-arranging column orders – with the same results, the anomaly is not dependent on the index starting with the important column(s)).

Problem 3: why is the whole smaller than the sum of its parts ? Why worry about the little detail when the big picture is smashed ?

Conclusion

As I pointed out, I’ve run these tests on 10.2.0.3, 11.1.0.7 and 11.2.0.3 – the index hash join arithmetic is wrong. This means the optimizer may be missing opportunities where the index hash join is a good execution path. Keep an eye open for this, you may want to hint some of your SQL (and then switch the hints into SQL Baselines, if you’re running 11g). The trouble is, if you’ve got multiple candidate indexes you may sometimes have to choose between renaming indexes (to get the right one chosen “by accident”) or using an undocumented hint (and in more complex queries you’ll have to look at the outline to find out which query blocks the hint should reference).

15 Comments »

  1. Hi, I believe you meant “bytes column instead of “rows column” in the text : <>
    thanks.

    Comment by Lester — January 30, 2012 @ 6:24 pm BST Jan 30,2012 | Reply

    • text referenced = It’s an interesting little detail that the queries that didn’t need to look at a data column didn’t report a “rows” column in the execution plan

      Comment by Lester — January 30, 2012 @ 6:24 pm BST Jan 30,2012 | Reply

    • Lester,

      Thnks, you’re right.
      Now corrected.

      Comment by Jonathan Lewis — January 30, 2012 @ 9:14 pm BST Jan 30,2012 | Reply

  2. I’ve tested this on my db and got normal results:

    SQL> select * from v$version;
    
    BANNER
    --------------------------------------------------------------------------------
    Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - Production
    PL/SQL Release 11.2.0.1.0 - Production
    CORE    11.2.0.1.0      Production
    TNS for 32-bit Windows: Version 11.2.0.1.0 - Production
    NLSRTL Version 11.2.0.1.0 - Production
    
    SQL> set autot on
    SQL> select sum(id) from t1 where flag = 0;
    
       SUM(ID)
    ----------
     249955000
    
    
    Execution Plan
    ----------------------------------------------------------
    Plan hash value: 3584404466
    
    --------------------------------------------------------------------------------------------
    | Id  | Operation               | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
    --------------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT        |                  |     1 |     8 |   528   (1)| 00:00:07 |
    |   1 |  SORT AGGREGATE         |                  |     1 |     8 |            |          |
    |*  2 |   VIEW                  | index$_join$_001 |  5000 | 40000 |   528   (1)| 00:00:07 |
    |*  3 |    HASH JOIN            |                  |       |       |            |          |
    |*  4 |     INDEX RANGE SCAN    | T1_FLAG          |  5000 | 40000 |    10   (0)| 00:00:01 |
    |   5 |     INDEX FAST FULL SCAN| T1_IA            |  5000 | 40000 |   646   (1)| 00:00:08 |
    --------------------------------------------------------------------------------------------
    
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       2 - filter("FLAG"=0)
       3 - access(ROWID=ROWID)
       4 - access("FLAG"=0)
    
    
    Statistics
    ----------------------------------------------------------
              0  recursive calls
              0  db block gets
            534  consistent gets
              0  physical reads
              0  redo size
            424  bytes sent via SQL*Net to client
            416  bytes received via SQL*Net from client
              2  SQL*Net roundtrips to/from client
              0  sorts (memory)
              0  sorts (disk)
              1  rows processed
    
    SQL> select /*+ full(t1) */ sum(id) from t1 where flag = 0;
    
       SUM(ID)
    ----------
     249955000
    
    
    Execution Plan
    ----------------------------------------------------------
    Plan hash value: 3724264953
    
    ---------------------------------------------------------------------------
    | Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
    ---------------------------------------------------------------------------
    |   0 | SELECT STATEMENT   |      |     1 |     8 |   692   (1)| 00:00:09 |
    |   1 |  SORT AGGREGATE    |      |     1 |     8 |            |          |
    |*  2 |   TABLE ACCESS FULL| T1   |  5000 | 40000 |   692   (1)| 00:00:09 |
    ---------------------------------------------------------------------------
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       2 - filter("FLAG"=0)
    
    
    Statistics
    ----------------------------------------------------------
              1  recursive calls
              0  db block gets
           2500  consistent gets
              0  physical reads
              0  redo size
            424  bytes sent via SQL*Net to client
            416  bytes received via SQL*Net from client
              2  SQL*Net roundtrips to/from client
              0  sorts (memory)
              0  sorts (disk)
              1  rows processed
    
    SQL>

    I can send you 10053 for compare parameters used by CBO.

    Comment by Valentin Nikotin — January 30, 2012 @ 7:00 pm BST Jan 30,2012 | Reply

    • It seems that in my DB FTS more expansive than IJ for first alphabet index, thus CBO chooses it.

      Comment by Valentin Nikotin — January 30, 2012 @ 7:05 pm BST Jan 30,2012 | Reply

      • Valentin,

        I see you’ve worked out why your results didn’t match mine.
        Your CPU costing values have kicked in, giving the full scan and fast full scans much higher prices, and just tipping your example into the table scan.
        The most significant comparison, of course, is between the simple fast full scan and fast full scan as it appears in the join.

        Comment by Jonathan Lewis — January 30, 2012 @ 9:25 pm BST Jan 30,2012 | Reply

  3. Take a look at “Bug 5404130: INDEX JOIN IS NOT SELECTED EVEN THOUGH HINTING IT IS FASTER AND CHEAPER”

    Comment by Valentin Nikotin — January 30, 2012 @ 7:16 pm BST Jan 30,2012 | Reply

  4. Jonathan, what is the hint OUTLINE_LEAF? The hint itself is undocumented and I was unable to find any definition.

    Comment by Mladen Gogala — January 30, 2012 @ 8:32 pm BST Jan 30,2012 | Reply

    • Mladen,

      Since it’s not documented my interpretation is, inevitably, a guess.
      When you write a query it consists of one or more query blocks (essentially each appearance of the words select, insert, update, delete, merge, introduces a new query block). Your original query blocks appear in the outline text with the label outline(). THe optimizer then transforms the query, possibly in many different ways, to see which cost-based query transformation gives it the best plan. The transformation mechanism may result in a completely different set of query blocks being the things ultimately optimised – these query blocks appear with the lable outline_leaf().

      Comment by Jonathan Lewis — January 30, 2012 @ 9:27 pm BST Jan 30,2012 | Reply

  5. Until 11.2 it was possible to use the following analog of IJ:

    explain plan for
    select sum(b.id)
    from t1 a, t1 b
    where a.rowid = b.rowid
      and a.flag = 0;
    select * from table(dbms_xplan.display);
    
    ------------------------------------------------------------------
    | Id  | Operation              | Name    | Rows  | Bytes | Cost  |
    ------------------------------------------------------------------
    |   0 | SELECT STATEMENT       |         |     1 |    32 |    41 |
    |   1 |  SORT AGGREGATE        |         |     1 |    32 |       |
    |*  2 |   HASH JOIN            |         |  5000 |   156K|    41 |
    |*  3 |    INDEX RANGE SCAN    | T1_FLAG |  5000 | 75000 |    10 |
    |   4 |    INDEX FAST FULL SCAN| T1_PK   |   100K|  1660K|    23 |
    ------------------------------------------------------------------
    

    But from 11.2 CBO can eliminate join by rowid, and add ROWID IS NOT NULL predicate preventing consideration of IJ.
    Thus without _optimizer_join_elimination_enabled = false for the same query plan will be:

    -----------------------------------------------------------
    | Id  | Operation          | Name | Rows  | Bytes | Cost  |
    -----------------------------------------------------------
    |   0 | SELECT STATEMENT   |      |     1 |    20 |   387 |
    |   1 |  SORT AGGREGATE    |      |     1 |    20 |       |
    |*  2 |   TABLE ACCESS FULL| T1   |  5000 |    97K|   387 |
    -----------------------------------------------------------
    

    Comment by Valentin Nikotin — January 30, 2012 @ 10:25 pm BST Jan 30,2012 | Reply

    • Valentin,

      True; and this is just a general case of persuading Oracle that visiting a table many times is cheaper than visiting it once – provided the many visits don’t actually get as far as the table. I prefer use an inline view – often with a no_merge hint – to stabilise the effect in more complex examples.

      Rather than setting the hidden parameter, there’s a hint (possibly not documented, though) that came up in the comments of another posting I did on the same topic.

      Comment by Jonathan Lewis — January 31, 2012 @ 9:41 am BST Jan 31,2012 | Reply

  6. I’ve found the funny situation when CBO uses one unnecessary index to get 3 columns by index join. I haven’t dug it too deep, just send the pure testcase :

    -- drop table t033 purge;
    create table t033 (a not null, b not null, c not null, xxx) as 
    select level, level, level, lpad('x',1000,'x') from dual connect by level <= 1e4;
    create index i033_b on t033(b);
    create index i033_a_b on t033(a, b);
    create index i033_c on t033(c);
    exec dbms_stats.gather_table_stats(user, 't033', estimate_percent => 100, cascade => true)
    explain plan for select a,b,c from t033;
    select * from table(dbms_xplan.display);
    
    Plan hash value: 3894408680
     
    --------------------------------------------------------------------------------------------
    | Id  | Operation               | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
    --------------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT        |                  | 10000 |   117K|    96   (3)| 00:00:02 |
    |   1 |  VIEW                   | index$_join$_001 | 10000 |   117K|    96   (3)| 00:00:02 |
    |*  2 |   HASH JOIN             |                  |       |       |            |          |
    |*  3 |    HASH JOIN            |                  |       |       |            |          |
    |   4 |     INDEX FAST FULL SCAN| I033_B           | 10000 |   117K|    28   (0)| 00:00:01 |
    |   5 |     INDEX FAST FULL SCAN| I033_A_B         | 10000 |   117K|    35   (0)| 00:00:01 |
    |   6 |    INDEX FAST FULL SCAN | I033_C           | 10000 |   117K|    28   (0)| 00:00:01 |
    --------------------------------------------------------------------------------------------
     
    Predicate Information (identified by operation id):
    ---------------------------------------------------
     
       2 - access(ROWID=ROWID)
       3 - access(ROWID=ROWID)
    

    Comment by Valentin Nikotin — October 4, 2012 @ 10:10 am BST Oct 4,2012 | Reply

    • Valentin,
      Very strange – I may look at that on the plane home.
      Can you affect the plan by changing the names of the indexes so that sorting by name lists them in a different order ?

      Comment by Jonathan Lewis — October 4, 2012 @ 2:31 pm BST Oct 4,2012 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Theme: Rubric. Get a free blog at WordPress.com

Follow

Get every new post delivered to your Inbox.

Join 4,173 other followers