Execution plans

Jonathan Lewis's picture

Index Join – 3

I’ve recently been writing about the index join mechanism and ways of emulating it. Those notes were originally inspired by an example of an index join that appeared on OTN a little while ago.

It was a plan that combined “bitmap/btree conversion” with the basic index join strategy so, with hindsight, it was an “obvious” and brilliant execution plan for a certain type of query. The query in the original posting was a simple select (with no predicates) against a huge table in a data warehouse – presumably extracting a small number of columns from a much wider row.

SELECT DISTINCT
	ECP_ITEM_MASTER_DIM.ORGANIZATION_ID,
	ECP_ITEM_MASTER_DIM.INV_MFG_PRODUCTION_LINE,
	ECP_ITEM_MASTER_DIM.INV_PRODUCT_FAMILY,
	ECP_ITEM_MASTER_DIM.INV_SEGMENT_3,
	ECP_ITEM_MASTER_DIM.INV_SEGMENT_4,
	ECP_ITEM_MASTER_DIM.INV_SEGMENT_5
FROM
	ecp.ECP_ITEM_MASTER_DIM
;

(I really hate reading SQL where the whole table name has been repeated as the alias all the way through the SQL – it makes the code so hard to read, especially when it’s all in upper case. It’s important to use aliases, of course, but 3 or 4 letters is a sensible length.)

Here’s the execution plan:


---------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                          | Name                         | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                   |                              |  1799K|    42M|       | 51279   (1)| 00:10:16 |
|   1 |  HASH UNIQUE                       |                              |  1799K|    42M|   151M| 51279   (1)| 00:10:16 |
|   2 |   VIEW                             | index$_join$_001             |  1799K|    42M|       | 38227   (1)| 00:07:39 |
|*  3 |    HASH JOIN                       |                              |       |       |       |            |          |
|*  4 |     HASH JOIN                      |                              |       |       |       |            |          |
|*  5 |      HASH JOIN                     |                              |       |       |       |            |          |
|*  6 |       HASH JOIN                    |                              |       |       |       |            |          |
|*  7 |        HASH JOIN                   |                              |       |       |       |            |          |
|   8 |         BITMAP CONVERSION TO ROWIDS|                              |  1799K|    42M|       |   485   (1)| 00:00:06 |
|   9 |          BITMAP INDEX FULL SCAN    | ECP_ITEM_MASTER_DIM_IMPL_BMX |       |       |       |            |          |
|  10 |         BITMAP CONVERSION TO ROWIDS|                              |  1799K|    42M|       |   230   (0)| 00:00:03 |
|  11 |          BITMAP INDEX FULL SCAN    | ECP_ITEM_MASTER_DIM_IPF_BMX  |       |       |       |            |          |
|  12 |        BITMAP CONVERSION TO ROWIDS |                              |  1799K|    42M|       |   229   (0)| 00:00:03 |
|  13 |         BITMAP INDEX FULL SCAN     | ECP_ITEM_MASTER_DIM_IS3_BMX  |       |       |       |            |          |
|  14 |       BITMAP CONVERSION TO ROWIDS  |                              |  1799K|    42M|       |   228   (0)| 00:00:03 |
|  15 |        BITMAP INDEX FULL SCAN      | ECP_ITEM_MASTER_DIM_IS4_BMX  |       |       |       |            |          |
|  16 |      BITMAP CONVERSION TO ROWIDS   |                              |  1799K|    42M|       |   201   (0)| 00:00:03 |
|  17 |       BITMAP INDEX FULL SCAN       | ECP_ITEM_MASTER_DIM_IS5_BMX  |       |       |       |            |          |
|  18 |     BITMAP CONVERSION TO ROWIDS    |                              |  1799K|    42M|       |   207   (0)| 00:00:03 |
|  19 |      BITMAP INDEX FULL SCAN        | ECP_ITEM_MASTER_DIM_OI_BMX   |       |       |       |            |          |
---------------------------------------------------------------------------------------------------------------------------

Isn’t it brilliant! The optimizer has seen that all the required columns can be found in indexes (six of them) – but they happen to be bitmap indexes so the optimizer has done a “bitmap conversion to rowid” on all six indexes one after the other with five consecutive hash joins – carrying the column values with each conversion and hash join.

Unfortunately the owner of this plan wasn’t happy with the resulting plan because a full tablescan turned out to be faster – nevertheless, it’s a very clever concept as the size of the table was measured in Gigabytes while the indexes were only a few megabytes each, allowing for a significant saving in I/O time.

I was a little curious, though, about the final join strategy. It’s annoying that Oracle didn’t report any costs on the hash join lines themselves because that could be very revealing. It’s remarkable that the value in the Bytes column for the final view (which is six columns of data) is the same as the bytes column for each index conversion (and remember that the projection from each conversion is just one data column with an accompanying rowid) – there’s clearly something wrong with the arithmetic.

This may explain why the optimizer has decided to run the 6-way join using only two running hash joins (rather than first setting up five hash tables in memory than passing the last table through them). If you think about this, when Oracle gets to the last hash join (lines 3, 4 and 18) it has to build a hash table from the result of the previous four joins and (in this case) that’s going to need a similar amount of memory as five in-memory hash tables. With that thought in mind I was puzzled that Oracle hadn’t just built five in-memory hash tables then walked through each in turn with the sixth.

Still – it’s not my (or my client’s) problem; maybe one day I’ll need to look more closely at a similar case.

[Further reading on Index Joins]

Jonathan Lewis's picture

ANSI – argh

I’m not keen on ANSI standard SQL – even though it is, technically, the strategic option and even though you have to use it for full outer joins and partitioned outer joins.

One reason for disliking it is that it “separates join predicates from filter predicates” – a reason often given in praise of the syntax which, to my mind, claims a spurious distinction and introduces a mechanism that makes it harder to keep mental track of what’s going to happen as you walk  through the join order.

The other reason for disliking ANSI SQL in Oracle databases is that sometimes it really is necessary to add hints to the SQL to make the optimizer do what needs to be done – and ANSI makes it so much harder and messier to add hints to code. Here’s a wonderful example that Tony Hasler presented in our recent debate “Does Oracle Ignore Hints” at the UKOUG annual conference:

WITH q1 as (
	SELECT /*+ qb_name(q1block) */
		*
	FROM	t1
	JOIN	t2
	ON	t1_i1 = t2_i1
	AND	t1_i1 < 10
),
q2 AS (
	SELECT
		/*+ qb_name(q2block) */
		*
	FROM
		t3
	JOIN	t4
	ON	t3_i1 = t4_i1
	AND	t3_i1 < 10
)
SELECT
	/*+
		no_merge(@q1block)
		no_merge(@q2block)
		leading (@q1block t2)
		use_nl  (@q1block t1)
	*/
	*
FROM
	q1
JOIN
	q2
ON	t1_i1 + t2_i1 = t3_i1 + t4_i1
;

Just to make life really hard, he’s included a couple of “factored subqueries” – and there are a few outstanding optimizer defects with handling subquery factoring – so when he claimed that this was an example of Oracle ignoring hints I had two different directions of investigation to worry about.

Here’s the execution plan (from my 10.2.0.3 system with the data generation, constraints and indexing that Tony supplied):

------------------------------------------------------------------------
| Id  | Operation                      | Name  | Rows  | Bytes | Cost  |
------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |       |   250K|    33M|    54 |
|*  1 |  HASH JOIN                     |       |   250K|    33M|    54 |
|   2 |   VIEW                         |       |  5000 |   327K|    11 |
|*  3 |    HASH JOIN                   |       |  5000 |   581K|    11 |
|   4 |     TABLE ACCESS BY INDEX ROWID| T4    |  5000 |   253K|     3 |
|*  5 |      INDEX RANGE SCAN          | T4_I1 |   900 |       |     2 |
|   6 |     TABLE ACCESS BY INDEX ROWID| T3    |  5000 |   327K|     3 |
|*  7 |      INDEX RANGE SCAN          | T3_I1 |   900 |       |     2 |
|   8 |   VIEW                         |       |  5000 |   361K|    12 |
|*  9 |    HASH JOIN                   |       |  5000 |   615K|    12 |
|  10 |     TABLE ACCESS BY INDEX ROWID| T1    |  5000 |   297K|     3 |
|* 11 |      INDEX RANGE SCAN          | T1_I1 |   900 |       |     2 |
|  12 |     TABLE ACCESS BY INDEX ROWID| T2    |  5000 |   317K|     3 |
|* 13 |      INDEX RANGE SCAN          | T2_I1 |   900 |       |     2 |
------------------------------------------------------------------------

Query Block Name / Object Alias (identified by operation id):
-------------------------------------------------------------
   1 - SEL$16C51A37
   2 - SEL$4C69CCA2 / Q2@SEL$1
   3 - SEL$4C69CCA2
   4 - SEL$4C69CCA2 / T4@SEL$2
   5 - SEL$4C69CCA2 / T4@SEL$2
   6 - SEL$4C69CCA2 / T3@SEL$2
   7 - SEL$4C69CCA2 / T3@SEL$2
   8 - SEL$7939585E / Q1@SEL$1
   9 - SEL$7939585E
  10 - SEL$7939585E / T1@SEL$3
  11 - SEL$7939585E / T1@SEL$3
  12 - SEL$7939585E / T2@SEL$3
  13 - SEL$7939585E / T2@SEL$3

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("T1_I1"+"T2_I1"="T3_I1"+"T4_I1")

As you can see, Oracle has copied the two factored subqueries inline (they appear just once each in the body of the query so this is – probably – inevitable). Then Oracle has obeyed the no_merge() hints – which I could check by deleting the hints and watching the plan change. So why, in lines 10 through 13, has Oracle not obeyed the leading() and use_nl() hints ?

By changing the ANSI syntax to traditional Oracle syntax, I got a different plan:

-------------------------------------------------------------------------
| Id  | Operation                       | Name  | Rows  | Bytes | Cost  |
-------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |       |   250K|    33M| 10045 |
|*  1 |  HASH JOIN                      |       |   250K|    33M| 10045 |
|   2 |   VIEW                          |       |  5000 |   327K|    11 |
|*  3 |    HASH JOIN                    |       |  5000 |   581K|    11 |
|   4 |     TABLE ACCESS BY INDEX ROWID | T4    |  5000 |   253K|     3 |
|*  5 |      INDEX RANGE SCAN           | T4_I1 |   900 |       |     2 |
|   6 |     TABLE ACCESS BY INDEX ROWID | T3    |  5000 |   327K|     3 |
|*  7 |      INDEX RANGE SCAN           | T3_I1 |   900 |       |     2 |
|   8 |   VIEW                          |       |  5000 |   361K| 10003 |
|   9 |    TABLE ACCESS BY INDEX ROWID  | T1    |     1 |    61 |     2 |
|  10 |     NESTED LOOPS                |       |  5000 |   615K| 10003 |
|  11 |      TABLE ACCESS BY INDEX ROWID| T2    |  5000 |   317K|     3 |
|* 12 |       INDEX RANGE SCAN          | T2_I1 |   900 |       |     2 |
|* 13 |      INDEX RANGE SCAN           | T1_I1 |     1 |       |     1 |
-------------------------------------------------------------------------

Query Block Name / Object Alias (identified by operation id):
-------------------------------------------------------------
   1 - SEL$1
   2 - Q2BLOCK / Q2@SEL$1
   3 - Q2BLOCK
   4 - Q2BLOCK / T4@Q2BLOCK
   5 - Q2BLOCK / T4@Q2BLOCK
   6 - Q2BLOCK / T3@Q2BLOCK
   7 - Q2BLOCK / T3@Q2BLOCK
   8 - Q1BLOCK / Q1@SEL$1
   9 - Q1BLOCK / T1@Q1BLOCK
  11 - Q1BLOCK / T2@Q1BLOCK
  12 - Q1BLOCK / T2@Q1BLOCK
  13 - Q1BLOCK / T1@Q1BLOCK

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("T1_I1"+"T2_I1"="T3_I1"+"T4_I1")
   3 - access("T3_I1"="T4_I1")
   5 - access("T4_I1"<10)
   7 - access("T3_I1"<10)
  12 - access("T2_I1"<10)
  13 - access("T1_I1"="T2_I1")
       filter("T1_I1"<10)

Notice how the optimizer is now obeying the leading() and use_nl() hints.

The problem is this: Oracle doesn’t optimise ANSI SQL, it transforms it then optimises it. Transformation can change query blocks, and Tony’s hints apply to specific query blocks. After a little testing and checking I worked out what the SQL looked like AFTER transformation and BEFORE optimisation; and it’s this:

select
	/*+ qb_name(sel$4) */
	*
from
	(
	SELECT
		/*+ qb_name(sel$1) */
		Q1.T1_I1 T1_I1, Q1.T1_I2 T1_I2, Q1.T1_D1 T1_D1, Q1.T2_I1 T2_I1, Q1.T2_I2 T2_I2, Q1.T2_TS T2_TS,
		Q2.T3_I1 T3_I1, Q2.T3_I2 T3_I2, Q2.T3_TSTZ T3_TSTZ, Q2.T4_I1 T4_I1, Q2.T4_I2 T4_I2
	FROM
		(
		SELECT
			/*+ NO_MERGE QB_NAME (Q1BLOCK) */
			from$_subquery$_003.T1_I1_0 T1_I1, from$_subquery$_003.T1_I2_1 T1_I2,
			from$_subquery$_003.T1_D1_2 T1_D1, from$_subquery$_003.T2_I1_3 T2_I1,
			from$_subquery$_003.T2_I2_4 T2_I2, from$_subquery$_003.T2_TS_5 T2_TS
		FROM	(
			SELECT
				/*+ qb_name(sel$3) */
				T1.T1_I1 T1_I1_0, T1.T1_I2 T1_I2_1, T1.T1_D1 T1_D1_2,
				T2.T2_I1 T2_I1_3, T2.T2_I2 T2_I2_4, T2.T2_TS T2_TS_5
			FROM
				TEST_USER.T1 T1,
				TEST_USER.T2 T2
			WHERE
				T1.T1_I1 = T2.T2_I1
			AND	T1.T1_I1 < 10
			)	from$_subquery$_003
		)	Q1,
		(
		SELECT
			/*+ NO_MERGE QB_NAME (Q2BLOCK) */
			from$_subquery$_006.T3_I1_0 T3_I1, from$_subquery$_006.T3_I2_1 T3_I2,
			from$_subquery$_006.T3_TSTZ_2 T3_TSTZ, from$_subquery$_006.T4_I1_3 T4_I1,
			from$_subquery$_006.T4_I2_4 T4_I2
		FROM
			(
			SELECT
				/*+ qb_name(sel$2) */
				T3.T3_I1 T3_I1_0, T3.T3_I2 T3_I2_1, T3.T3_TSTZ T3_TSTZ_2,
				T4.T4_I1 T4_I1_3, T4.T4_I2 T4_I2_4 FROM TEST_USER.T3 T3, TEST_USER.T4 T4
			WHERE
				T3.T3_I1 = T4.T4_I1
			AND	T3.T3_I1 < 10
			)	from$_subquery$_006
		)	Q2
	WHERE
		Q1.T1_I1 + Q1.T2_I1 = Q2.T3_I1 + Q2.T4_I1
	)
;

I got most of this from the “Query Block Name / Object Alias” section of the ANSI execution plan (there are some important clues there, like ‘T1@SEL$3′) and the “unparsed” SQL from the 10053 trace.

Notice how the query blocks q1block and q2block still exist – that’s why the no_merge() hints can survive the transformation. Notice, though, that the transformation engines has introduced a layer of inline views inside q1block and q2block - which is why the leading(@q1block t2) and use_nl(@q1block t1) hints are no longer valid: they reference objects which are not in q1block. To get his hints to work at the global level, Tony would have to change the last two hints to reference sel$3 rather than q1block.

So, next time you write a complicated piece of ANSI, make sure you think carefully about what you’re going to have to do if you subsequently have to add hints to force a particular execution plan.  (And bear in mind that one day the transformation engine might be modified to transform the query differently.)

[Further reading on "ignoring hints"]

Jonathan Lewis's picture

Collection Costs

Here’s an extract from an execution plan I found on a client site recently. I’ve collapsed lines 5 to 42 into a single line representing the rowsource produced by a fairly messy execution plan, leaving just the last three stages of execution on view. Each of three operations joins the same collection variable (using the table() operator) to the row source – once through a hash join, then twice more (joining to two other columns) through nested loop outer joins:

The resulting estimates of row counts and costs are quite entertaining and, fortunately, not very accurate:


-----------------------------------------------------------------------------------------------------
| Id  | Operation                                  | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                           |        |       |       |  5865M(100)|          |
|   1 |  NESTED LOOPS OUTER                        |        |   478G|   207T|  5865M  (1)|999:59:59 |
|   2 |   NESTED LOOPS OUTER                       |        |  5830M|  1895G|    18M  (1)| 50:38:00 |
|*  3 |    HASH JOIN                               |        |    71M|    14G|   266K  (2)| 00:44:49 |
|   4 |     COLLECTION ITERATOR PICKLER FETCH      |        |       |       |            |          |
|   5 |     {join-based row source}                |        | 87049 |    18M|   266K  (2)| 00:44:49 |
|  43 |   VIEW                                     |        |    82 | 10578 |            |          |
|* 44 |     COLLECTION ITERATOR PICKLER FETCH      |        |       |       |            |          |
|  45 |   VIEW                                     |        |    82 | 10578 |            |          |
|* 46 |    COLLECTION ITERATOR PICKLER FETCH       |        |       |       |            |          |
-----------------------------------------------------------------------------------------------------

The system was running 11.1.0.7, and the optimizer clearly has some problems (still) with the arithmetic of collection types.

Here’s a suggestion for use with the table() operator, by the way. The optimizer assumes that the number of rows produced by the table() operator will be roughly the same as the number of bytes in the default block size – and this can lead to some very poor execution plans (watch out, by the way, if someone tells you to rebuild your database with a new default block size – there may be some unexpected side effects). As a general principle I advise people that if they have a reasonable idea of the number of rows that they will be passing into a query of this type that they tell the optimizer what that number. The simplest way of doing this is to change your SQL from something like this:


from
        tableX                        ty,
        table(collection_variable)    tc,
        tableY                        ty,
...

to something like this – where you introduce an inline view with a /*+ cardinality */ hint:

from
        tableX                        tx,
        (
        select  /*+ cardinality(t 20) */
                *
        from    table(collection_variable)  t
        )                              tc,
        tableY                        ty,
...

It’s possible to use a “global” hint in the main query with a query block name referencing the inline view, of course – but it can be very hard to make this work correctly in more complex cases – especially if you are using ANSI SQL – so a simple inline approach with a hint in the view is probably a much safer bet.

Jonathan Lewis's picture

Index Join – 2

In an earlier article introducing the index join I raised a question that came up at the first ES2N virtual conference:

    “If you hint an index hash join, is there any way of telling Oracle the order in which it should use the indexes?”

Consider the following example:

create table indjoin
nologging
as
select
	rownum	id,
	rownum	val1,
	rownum	val2,
	rownum	val3,
	rpad('x',500) padding
from
	all_objects
where
	rownum <= 5000
;

/*

alter table indjoin
add constraint ij_pk primary key (id)

*/

create unique index ij_v1 on indjoin(id, val1);
create unique index ij_v2 on indjoin(id, val2);
create unique index ij_v3 on indjoin(id, val3);

-- gather statistics: without histograms

select
	/*+ index_join(ij) */
	count(*)
from
	indjoin	ij
where
	val1 between 100 and 200
and	val2 between 50 and 150
and	val3 between 250 and 550
;

The query plan for this query is (thanks to the hint) a three-way index hash join:

-----------------------------------------------------------------------------
| Id  | Operation                | Name             | Rows  | Bytes | Cost  |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT         |                  |     1 |    12 |    74 |
|   1 |  SORT AGGREGATE          |                  |     1 |    12 |       |
|*  2 |   VIEW                   | index$_join$_001 |     1 |    12 |    74 |
|*  3 |    HASH JOIN             |                  |       |       |       |
|*  4 |     HASH JOIN            |                  |       |       |       |
|*  5 |      INDEX FAST FULL SCAN| IJ_V1            |     1 |    12 |    18 |
|*  6 |      INDEX FAST FULL SCAN| IJ_V2            |     1 |    12 |    18 |
|*  7 |     INDEX FAST FULL SCAN | IJ_V3            |     1 |    12 |    18 |
-----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("VAL1">=100 AND "VAL1"<=200 AND "VAL2">=50 AND
              "VAL2"<=150 AND "VAL3">=250 AND "VAL3"<=550)
   3 - access(ROWID=ROWID)
   4 - access(ROWID=ROWID)
   5 - filter("VAL1"<=200 AND "VAL1">=100)
   6 - filter("VAL2"<=150 AND "VAL2">=50)
   7 - filter("VAL3"<=550 AND "VAL3">=250)

But what if you know the data better than Oracle, and know that the join order for the three indexes should be different – there are no extra direct hints you can add to the code to tell Oracle the best order for the hash join. (You might, of course, be able to make use of the cardinality() hint – or plan around with the undocumented, hence unsupported, opt_estimate() or column_stats() or index_stats() hints, but I wouldn’t be keen to use such an indirect approach.)

But you CAN rewrite the query to get the same mechanism working under your control. The code looks more complex – but we often have to make a trade between clarity (simplicity) and speed in critical cases, so you may find some examples where the complexity is acceptable:

select
	count(*)
from
	(
	select
		/*+ no_merge */
		rowid
	from
		indjoin		ij
	where
		val1 between 100 and 200
	)	v1,
	(
	select
		/*+ no_merge */
		rowid
	from
		indjoin		ij
	where
		val2 between 50 and 150
	)	v2,
	(
	select
		/*+ no_merge */
		rowid
	from
		indjoin		ij
	where
		val3 between 250 and 550
	)	v3
where
	v2.rowid = v1.rowid
and	v3.rowid = v1.rowid
;

It’s another example of referencing a table twice (or three times) in the query because multiple references allow you to define a better execution path than a single reference. The execution we get from this plan (running under 10.2.0.3) is as follows:


------------------------------------------------------------------
| Id  | Operation                | Name  | Rows  | Bytes | Cost  |
------------------------------------------------------------------
|   0 | SELECT STATEMENT         |       |     1 |    36 |    14 |
|   1 |  SORT AGGREGATE          |       |     1 |    36 |       |
|*  2 |   HASH JOIN              |       |   102 |  3672 |    14 |
|*  3 |    HASH JOIN             |       |   102 |  2448 |     9 |
|   4 |     VIEW                 |       |   102 |  1224 |     4 |
|*  5 |      INDEX FAST FULL SCAN| IJ_V1 |   102 |  1632 |     4 |
|   6 |     VIEW                 |       |   102 |  1224 |     4 |
|*  7 |      INDEX FAST FULL SCAN| IJ_V2 |   102 |  1632 |     4 |
|   8 |    VIEW                  |       |   302 |  3624 |     4 |
|*  9 |     INDEX FAST FULL SCAN | IJ_V3 |   302 |  4832 |     4 |
------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("V3".ROWID="V1".ROWID)
   3 - access("V2".ROWID="V1".ROWID)
   5 - filter("VAL1">=100 AND "VAL1"<=200)
   7 - filter("VAL2">=50 AND "VAL2"<=150)
   9 - filter("VAL3">=250 AND "VAL3"<=550)

By creating three explicit query blocks (which I’ve ring-fenced with no_merge hints), one for each index, I’ve made Oracle extract the same three sets of data that it was using in the index hash join. I’ve then left Oracle to join the three result sets – which it has done with hash joins. Interestingly this seems to have done a little less work than the original index join – the final complex filter action doesn’t appear in the manual rewrite.

Since I’ve now got a query that seems to be “just” a three table join, I can dictate the join order, guarantee the hash joins, and dictate which rowsources should be used as build rowsources, and which as probe. For example, let’s apply the following hints:

select
	/*+
		leading (v1 v3 v2)
		use_hash(v3) no_swap_join_inputs(v3)
		use_hash(v2) swap_join_inputs(v2)
	*/
	count(*)
from
        ....

The resulting plan is as follows:

------------------------------------------------------------------
| Id  | Operation                | Name  | Rows  | Bytes | Cost  |
------------------------------------------------------------------
|   0 | SELECT STATEMENT         |       |     1 |    36 |    14 |
|   1 |  SORT AGGREGATE          |       |     1 |    36 |       |
|*  2 |   HASH JOIN              |       |   102 |  3672 |    14 |
|   3 |    VIEW                  |       |   102 |  1224 |     4 |
|*  4 |     INDEX FAST FULL SCAN | IJ_V2 |   102 |  1632 |     4 |
|*  5 |    HASH JOIN             |       |   102 |  2448 |     9 |
|   6 |     VIEW                 |       |   102 |  1224 |     4 |
|*  7 |      INDEX FAST FULL SCAN| IJ_V1 |   102 |  1632 |     4 |
|   8 |     VIEW                 |       |   302 |  3624 |     4 |
|*  9 |      INDEX FAST FULL SCAN| IJ_V3 |   302 |  4832 |     4 |
------------------------------------------------------------------

The join order (you can check the trace file to confirm this) is: ij_v1, ij_v3, ij_v2 – but because of the swap_join_inputs(v2) hint the ij_v2 index appears first in the plan.
We build a hash table with ij_v2, then build a hash table with ij_v1 with we probe (join) ij_v3.
We then use the result of joining ij_v1/ij_v3 to probe (join) ij_v2 – which means v2 really is the last object in the join order.

It may look complex – but all we’ve done is describe an index-join in detail, and that has allowed us to specify which indexes are joined when. I’ve already pointed out that the manual version appears to be slightly more efficien than the original. It’s also more powerful, and addresses a defect in the current implementation of the index join. But that’s a topic for another blog.

[Further reading on Index Joins]

Jonathan Lewis's picture

Index Join

One of the less well known access paths available to the optimizer is the “index join” also known as the “index hash join” path. It’s an access path that can be used when the optimizer decides that it doesn’t need to visit a table to supply the select list because there are indexes on the table that, between them, hold all the required columns. A simple example might look something like the following:


create table indjoin
as
select
	rownum	id,
	rownum	val1,
	rownum	val2,
	rpad('x',500) padding
from
	all_objects
where
	rownum <= 3000
;

create unique index ij_v1 on indjoin(id, val1);
create unique index ij_v2 on indjoin(id, val2);

-- collect stats on the table and indexes

select
	ij.id
from
	indjoin		ij
where
	ij.val1 between 100 and 200
and	ij.val2 between 50 and 150
;

Note that the columns in the where clause appear in (some) indexes, and the column(s) in the select list exist in (at least) some indexes. Under these circumstances the optimizer can produce the following plan (the test script was one I wrote for 8i – but this plan comes from an 11.1 instance):


---------------------------------------------------------------------------
| Id  | Operation              | Name             | Rows  | Bytes | Cost  |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |                  |     3 |    36 |    24 |
|   1 |  VIEW                  | index$_join$_001 |     3 |    36 |    24 |
|*  2 |   HASH JOIN            |                  |       |       |       |
|*  3 |    INDEX FAST FULL SCAN| IJ_V1            |     3 |    36 |    11 |
|*  4 |    INDEX FAST FULL SCAN| IJ_V2            |     3 |    36 |    11 |
---------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access(ROWID=ROWID)
   3 - filter("VAL1"<=200 AND "VAL1">=100)
   4 - filter("VAL2"<=150 AND "VAL2">=50)

Column Projection Information (identified by operation id):
-----------------------------------------------------------
   1 - "ID"[NUMBER,22]
   2 - (#keys=1) "ID"[NUMBER,22]
   3 - ROWID[ROWID,10], "ID"[NUMBER,22]
   4 - ROWID[ROWID,10]

We do a fast full scan of the two indexes extracting the rowid and id from index ij_v1 and just the rowid from index ij_v2. We can then get the result we want by doing a hash join between these two result sets on the rowid values because any time the two rowsources have a rowid in common, it’s a rowid for a row where val1 is between 100 and 200, and val2 is between 50 and 150 and the first rowsource is carrying the id - which is the thing we need to report.

There are a couple of little observations that we can make about this example.

    First, although I’ve only used two indexes in this example Oracle is not limited to just two indexes. The number of indexes that could be used is effectively unlimited.
    Second, the index_join path is strictly limited to cases where the optimizer can see that every column in the query can be found in indexes on the table.
    Third, although my example uses index fast full scans that’s not a necessary feature of the plan. Just like any other hash join, Oracle could use an index range (or full) scan to get some of the data.
    Finally, there are clearly a couple of bugs in the code.

Bugs:

If you check the rows/bytes columns in the plan you’ll see that the predicted number of rows selected is the same for both indexes (lines 3 and 4) – but we extract the rowid and the id from the first index (projection detail for line 3), so the total data volume expected from line 3 is slightly larger than the total data volume from line 4 where we extract only the rowid; theoretically, therefore, the optimizer has used the tables (indexes) in the wrong order – the one supplying the smaller volume of data should have been used as the first (build) rowsource.

More significantly, though, a quick check of the code that generates the data tells you that each index will supply 101 rows to the hash join – and you can even show that for other query execution plans the optimizer will calculate this cardinality (nearly) correctly. In the case of the index join the optimizer seems to have lost the correct individual cardinalities and has decided to use the size of the final result set as the cardinality of the two driving index scans.

There’s more, of course – one of the strangest things about the index join is that if your select list includes the table’s rowid, the optimizer doesn’t consider that to be a column in the index. So even though the predicate section of the plan shows the rowids being projected in the hash join, Oracle won’t use an index join for a query returning the rowid !

Footnote: The reason I’ve written this brief introduction to the index join is because an interesting question came up at the first E2SN virtual conference.

“If you hint an index hash join, is there any way of telling Oracle the order in which it should use the indexes?”

The answer is no – but there are ways of creating code that will do what you want, and that will be the topic of my next blog.

[Further reading on Index Joins]

Jonathan Lewis's picture

Quiz Night

Apart from the fact that the “Rows” figure for the FILTER operation at line 6 is blank, what’s the obvious error in this extract from an execution plan:

-------------------------------------------------------------------------
| Id  | Operation                            | Name             | Rows  |
-------------------------------------------------------------------------
        ...
|   5 |      NESTED LOOPS                    |                  |  3864 |
|   6 |       FILTER                         |                  |       |
|   7 |        HASH JOIN OUTER               |                  |  3864 |
|   8 |         HASH JOIN OUTER              |                  |   282K|
|   9 |          TABLE ACCESS BY INDEX ROWID | PRODUCT          |   282K|
|  10 |           INDEX RANGE SCAN           | PRD_SUPP_I1      |   282K|
|  11 |          VIEW                        |                  |  2293K|
|  12 |           HASH GROUP BY              |                  |  2293K|
|  13 |            PARTITION LIST SINGLE     |                  |  5790K|
|  14 |             TABLE ACCESS FULL        | PRODUCT_PRICING  |  5790K|
|  15 |         VIEW                         |                  |  2307K|
|  16 |          HASH GROUP BY               |                  |  2307K|
|  17 |           PARTITION LIST SINGLE      |                  |  5703K|
|  18 |            TABLE ACCESS FULL         | PRODUCT_PRICING  |  5703K|
        ...
-------------------------------------------------------------------------

Update 21/Nov/2010:
Once again I am reminded of two things – it’s important to be precise in your use of language if you want people to understand the question; and you can see a lot if you look carefully.

If you start to think about the activity that the plan represents, and the SQL that might have produced it, there are some ideas you might get about re-writing the query to be more efficient – but the point I was trying to make is that there is clearly an error in the content that the optimizer is displaying. The error suggests either that the optimizer has done the wrong arithmetic, or that the output is not a correct copy of the results produced by the optimizer.

The answer I was expecting comes from line 7. Stripping the error back to the bare minimum we see this:

--------------------------------------------------------------------------
| Id  | Operation                             | Name             | Rows  |
--------------------------------------------------------------------------
        ...
|   7 |        HASH JOIN OUTER                |                  |  3864 |
|   8 |         rowsource 1 (HASH JOIN OUTER) |                  |   282K|
|  15 |         rowsource 2 (VIEW)            |                  |  2307K|
        ...
--------------------------------------------------------------------------

As Milo points out in comment 3, In an outer join the result set cannot have fewer rows than the “preserved” rowsource (which, in this case, is the result set from line 8). I mentioned the fact that the “Rows” figure for the FILTER operation at line 6 was blank – it’s just possible that the optimizer has overwritten the figure in line 7 with the figure that should have been in line 6; there are cases where a FILTER operation and the operation you would normally think of as its first child are combined, so it’s possible that a little storage glitch has appeared in some cases where the combination rule doesn’t apply.

Someone did mention the FILTER operation and pointed out that it wasn’t filtering any data. The commonest forms of FILTER operation essentially check that some predicate it true for each row in their first child rowsource – and it is possible for someone to write code that has a filter that doesn’t eliminate any rows. In fact, though, this plan is probably saying: “line 7 will produce 282K rows, and the filter at line 6 will reduce that to 3,684.” (There’s also a comment about a “group by” not reducing the size of the rowsource – the comment was caused by a parallax error, but it is possible, of course, for Oracle to decide that a “group by” is going to produce an output with just as many rows as the input.)

Sean Molloy’s opening comment asks how you can get two different estimates from the same tablescan — and follows up with one answer which is that since we are looking at PARTITION LIST SINGLE the two tablescans could be of different partitions. But it’s only a puzzle if there were no predicates on the tablescans and, as Pavol points out in comment 7, there are no “star flags” in the ID column to suggest the presence of any predicates – but there are no stars anywhere – and there have to be some predicates in the plan, since you can’t do a hash join, index range scan, or filter without a predicate. As Timur points out – you don’t get the predicate section in the report from dbms_xplan.display_awr(), so you don’t get the stars.

Speaking of missing information, Dave Costa in comment 4 suggests that the user made an error in choosing which bits of the plan to copy. I did the choosing – how could it possible by wrong ! Given the number of times I’ve said “you must include the predicate section”, why isn’t it there ? (answer: it’s display_awr). In fact lines 5 and 6 were redundant as far as the “obvious problem” was concerned – but I thought that the blank and reappearance of the same cardinality might be a helpful visual clue.

The SQL:

Several people have commented on the rationale for code that does two outer join aggregations on the same table. It does look a little unusual, but it’s not possible to come to any conclusion about whether it’s a good thing or a bad thing without knowing the data and the intent of the SQL. For example the intent could be something like:


select
        product_name, min(offer_price), max(offer_price) ...
from

(You can assume that in the actual code, the min() and max() would be hidden inside a couple of inline views)
In this case code which visits the product_pricing table twice might be a very good idea – because there is a special “index (min/max) range scan” optimisation that works very well if (a) have the right indexes in place (b) use a nested loop and (c) only ask for min, or max, but not both. Perhaps our problem is that the optimizer is doing a hash join when it should be doing a nested loop.

Another possibility is that we have something like:


select
        product_name, min(gbp_offer_price), min(usd_offer_price) ...
from

(Again you can assume the min() and max() would be hidden inside inline view, and the different column names would be derived names rather than being from two separate columns in a table).
Notice that the plan shows list partitioning – maybe we have one currency per partition, and we’ve written the query to maximise the benefits of partition elimination (as well as leaving the data nicely normalised, thus maximising efficiency of maintenance).

Bottom line on the SQL – in this case I wasn’t asking people to guess what was wrong with the code; but it’s very interesting to see how many different topics of thought can come out from a starting point of a few lines extracted from a plan.

Greg Rahn's picture

Reading Parallel Execution Plans With Bloom Pruning And Composite Partitioning

You’ve probably heard sayings like “sometimes things aren’t always what they seem” and “people lie”. Well, sometimes execution plans lie. It’s not really by intent, but it is sometimes difficult (or impossible) to represent everything in a query execution tree in nice tabular format like dbms_xplan gives. One of the optimizations that was introduced back in 10gR2 was the use of bloom filters. Bloom filters can be used in two ways: 1) for filtering or 2) for partition pruning (bloom pruning) starting with 11g. Frequently the data models used in data warehousing are dimensional models (star or snowflake) and most Oracle warehouses use simple range (or interval) partitioning on the fact table date key column as that is the filter that yields the largest I/O reduction from partition pruning (most queries in a time series star schema include a time window, right!). As a result, it is imperative that the join between the date dimension and the fact table results in partition pruning. Let’s consider a basic two table join between a date dimension and a fact table. For these examples I’m using STORE_SALES and DATE_DIM which are TPC-DS tables (I frequently use TPC-DS for experiments as it uses a [...]

Jonathan Lewis's picture

Manual Optimisation

Here’s an example of “creative SQL” that I wrote in response to a question on OTN about combining data from two indexes to optimise access to a table. It demonstrates the principle that you can treat an index as a special case of a table – allowing you to make a query go faster by referencing the same table more times.

Unfortunately you shouldn’t use this particular example in a production system because it relies on the data appearing in the right order without having an “order by” clause. This type of thing makes me really keen to have a hint that says something like: /*+ qb_name(my_driver) assume_ordered(@my_driver) */ so that you could tell the optimizer that it can assume that the rowset from a given query block will appear in the order of the final “order by” clause.

Jonathan Lewis's picture

CBO Surprise

Well, it surprised me!

I’ve said for a very long time that in principle, ignoring bugs and restrictions, the optimizer will always choose the lowest cost option during its search for an execution path. It turns out that this isn’t true. In a comment attached to a note I had written about a possible bug relating to function-based indexes I was told that there are cases where the optimizer follows a rule that allows it to ignore the lowest cost path if it is derived from a range-based predicate involving unpeekable bind variables.

The trouble is, any statement made about “bind variables” may also apply in any circumstances where the optimizer sees: “unknown value”. Here’s a simplified example that I find a little worrying (running on 11.1):

Jonathan Lewis's picture

Not NULL

Here’s a little detail that I’ve known for years – but keep forgetting until I embarrass myself by rediscovering it (usually in front of a client). I’ll start with a demonstration of a useful little feature of mandatory columns:


drop table t1 purge;

create table t1
as
select
	*
from
	all_objects
where
	rownum <= 10000
;

execute dbms_stats.gather_table_stats(user,'t1')

create index t1_i1 on t1(object_name);

set autotrace traceonly explain

select count(*) from t1;

/*

--------------------------------------------------------------------
| Id  | Operation             | Name  | Rows  | Cost (%CPU)| Time
--------------------------------------------------------------------
|   0 | SELECT STATEMENT      |       |     1 |    13   (0)| 00:00:0
|   1 |  SORT AGGREGATE       |       |     1 |            |
|   2 |   INDEX FAST FULL SCAN| T1_I1 | 10000 |    13   (0)| 00:00:0
--------------------------------------------------------------------

*/

Oracle can use the index on column object_name to count the number of rows in the table because the column has been declared NOT NULL, so every row in the table also has to appear in the index. Let’s just demonstrate that by changing the column definition:


alter table t1 modify object_name null;
select count(*) from t1;

/*

-------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Cost (%CPU)| Time     |
-------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |    40   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE    |      |     1 |            |          |
|   2 |   TABLE ACCESS FULL| T1   | 10000 |    40   (0)| 00:00:01 |
-------------------------------------------------------------------

*/

Now let’s make the column mandatory again – by adding a constraint:

To prevent automated spam submissions leave this field empty.
Syndicate content