Index Hash

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:

rem
rem     Script:         index_hash.sql
rem     Author:         Jonathan Lewis
rem     Dated:          Sept 2011
rem

create table t1
as
with generator as (
        select
                rownum id 
        from dual 
        connect by 
                level <= 1e4  -- > comment to avoid wordpress format issue
)
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 <= 1e5  -- > comment to avoid wordpress format issue
;


begin
        dbms_stats.gather_table_stats(
                ownname          => user,
                tabname          =>'T1',
                estimate_percent => 100,
                method_opt       => 'for all columns size 1'
        );
end;
/

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 |


-----------------------------------------------------------------
| Id  | Operation             | Name    | Rows  | Bytes | Cost  |
-----------------------------------------------------------------
|*  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).

Update Sept 2019

This problem is still present in 18.3 and 19.3