Tagged: execution plan

Using Bitmap Indexes Effectively

Recently I was reading this thread, “Trying to make use of bitmap indexes” on the Oracle Forum. Before I had finished a working example, Jonathan Lewis had posted his response which was on par with my thoughts. Since this is a topic I see frequently, I thought I would finish my experiment and publish it here.

What We Are Given

The author of the original post had stated that the table in question contains about 16 million rows and states: “The table contains three IDEAL columns for bitmap indexes the first of which
may have only two, the second three and the third four distinct values. I was planning to change the index type on these columns to BITMAP [from B-tree]
.” To keep the focus of this post narrow, I’m only going to discuss whether or not one should consider bitmap indexes for queries, and not discuss potential update related issues.

The Data

For this experiment, I’m going to create a table that has three columns with the given NDV from above and add in a few extra filler columns to pad it out a bit. Since I do not know the exact table structure, I’ll just go with a simple example. In reality, the posters table may be wider, but for this example, it is what it is.

create table bm_test
nologging compress
as
select
  round(dbms_random.value(1, 2)) a  -- NDV 2
, round(dbms_random.value(1, 3)) b  -- NDV 3
, round(dbms_random.value(1, 4)) c  -- NDV 4
, to_char(800000+100000*dbms_random.normal,'fm000000000000') c3
, to_char(800000+100000*dbms_random.normal,'fm000000000000') c4
, to_char(15000+2000*dbms_random.normal,'fm000000') c5
, to_char(80000+10000*dbms_random.normal,'fm000000000000') c6
from dual
connect by level <= 16000000
/

desc bm_test
 Name		   Null?    Type
 ----------------- -------- ------------
 A			    NUMBER
 B			    NUMBER
 C			    NUMBER
 C3			    VARCHAR2(13)
 C4			    VARCHAR2(13)
 C5			    VARCHAR2(7)
 C6			    VARCHAR2(13)

exec dbms_stats.gather_table_stats(user,'BM_TEST');

create bitmap index bm1 on bm_test(a);
create bitmap index bm2 on bm_test(b);
create bitmap index bm3 on bm_test(c);

select a, b, c, count(*)
from bm_test
group by a,b,c
order by a,b,c;

         A          B          C   COUNT(*)
---------- ---------- ---------- ----------
         1          1          1     333292
         1          1          2     666130
         1          1          3     666092
         1          1          4     333585
         1          2          1     668594
         1          2          2    1332121
         1          2          3    1332610
         1          2          4     668608
         1          3          1     333935
         1          3          2     666055
         1          3          3     666619
         1          3          4     333106
         2          1          1     333352
         2          1          2     665038
         2          1          3     665000
         2          1          4     333995
         2          2          1     669120
         2          2          2    1332744
         2          2          3    1332766
         2          2          4     668411
         2          3          1     333891
         2          3          2     665924
         2          3          3     664799
         2          3          4     334213

24 rows selected.

select segment_name,
       segment_type,
       sum(blocks) blocks,
       sum(bytes)/1024/1024 mb
from user_segments
where segment_name like 'BM%'
group by segment_name, segment_type;

SEGMENT_NAME SEGMENT_TYPE     BLOCKS         MB
------------ ------------ ---------- ----------
BM_TEST      TABLE            102592      801.5
BM1          INDEX               768          6
BM2          INDEX              1152          9
BM3          INDEX              1408         11

select object_name, object_id
from user_objects
where object_name like 'BM%'

OBJECT_NAME   OBJECT_ID
------------ ----------
BM_TEST           54744
BM1               54745
BM2               54746
BM3               54747

The Queries And Execution Plans

The original post did not contain any queries or predicates, so for the purpose of this example I’m going to assume that there are exactly three predicates, one on each of column A, B and C, and that each predicate is a single equality (e.g. A=1 and B=1 and C=1). Looking at the data distribution from the query above, we observe there are approximately three different grouping counts: the lower around 333,000 the middle around 666,000 and the upper around 1,300,000. I will choose tuples from each of these groupings for the three test cases.

Query A

select *
from bm_test
where a=1 and b=1 and c=1;

333292 rows selected.
Plan hash value: 3643416817

----------------------------------------------------------------------------------------
| Id  | Operation                    | Name    | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |         |       |       | 23314 (100)|          |
|   1 |  TABLE ACCESS BY INDEX ROWID | BM_TEST |   326K|    17M| 23314   (1)| 00:04:40 |
|   2 |   BITMAP CONVERSION TO ROWIDS|         |       |       |            |          |
|   3 |    BITMAP AND                |         |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| BM3     |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| BM2     |       |       |            |          |
|*  6 |     BITMAP INDEX SINGLE VALUE| BM1     |       |       |            |          |
----------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("C"=1)
   5 - access("B"=1)
   6 - access("A"=1)

Query B

select *
from bm_test
where a=1 and b=1 and c=2;

666130 rows selected.
Plan hash value: 3202922749

----------------------------------------------------------------------------------------
| Id  | Operation                    | Name    | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |         |       |       | 27105 (100)|          |
|   1 |  TABLE ACCESS BY INDEX ROWID | BM_TEST |   653K|    34M| 27105   (1)| 00:05:26 |
|   2 |   BITMAP CONVERSION TO ROWIDS|         |       |       |            |          |
|   3 |    BITMAP AND                |         |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| BM2     |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| BM1     |       |       |            |          |
|*  6 |     BITMAP INDEX SINGLE VALUE| BM3     |       |       |            |          |
----------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("B"=1)
   5 - access("A"=1)
   6 - access("C"=2)

Query C

select *
from bm_test
where a=1 and b=2 and c=2;

1332121 rows selected.
Plan hash value: 1873942893

-----------------------------------------------------------------------------
| Id  | Operation         | Name    | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |         |       |       | 28243 (100)|          |
|*  1 |  TABLE ACCESS FULL| BM_TEST |  1377K|    72M| 28243   (2)| 00:05:39 |
-----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter(("C"=2 AND "B"=2 AND "A"=1))

As you can see from the execution plans, Query A and B use the bitmap indexes and Query C uses a Full Table Scan. Of the 16,000,000 rows, Query A returns 333,292 (2.08%), Query B returns 666,130 (4.16%) and Query C returns 1,332,121 rows (8.33%). I think it is important to note that the change in the execution plan from index access to table scan is due to the costing, not directly due to the percentage of data returned.

Execution Times

I’m going to gather two sets of execution times. The first will be with a cold buffer cache, and the second with a warm buffer cache. All elapsed times are in seconds.

Query Execution Plan Cold Cache Warm Cache
A Bitmap Index 38 3
B Bitmap Index 40 4
C FTS 16 16

As you can see from the execution times, there is a significant difference (approx. 11x) between the cold and warm cache executions of each Query A and Query B. The other observation is that Query C (FTS) is faster than Query A (Index Access) on a cold cache. We surely need to account for this. One observation I made (from iostat) is that the I/O throughput rate for Query A and Query B was around 23MB/s while the I/O rate for Query C was around the 55MB/s range during the cold cache execution. None of the queries used the Parallel Query Option.

Lets take a look at the tkprof output from both the cold and warm cache executions of Query A and see if we can find where the time is being spent. The traces were collected using event 10046, level 8.

Query A TKPROF – Warm Cache

select /* warm cache */ *
from bm_test
where a=1 and b=1 and c=1


call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        1      0.00       0.00          0          0          0           0
Execute      1      0.00       0.00          0          0          0           0
Fetch     3334      2.20       2.17          0     102184          0      333292
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total     3336      2.20       2.18          0     102184          0      333292

Misses in library cache during parse: 0
Optimizer mode: ALL_ROWS
Parsing user id: 31

Rows     Row Source Operation
-------  ---------------------------------------------------
 333292  TABLE ACCESS BY INDEX ROWID BM_TEST (cr=102184 pr=0 pw=0 time=19332 us cost=23314 size=17945290 card=326278)
 333292   BITMAP CONVERSION TO ROWIDS (cr=1162 pr=0 pw=0 time=2329 us)
     92    BITMAP AND  (cr=1162 pr=0 pw=0 time=1691 us)
    642     BITMAP INDEX SINGLE VALUE BM3 (cr=367 pr=0 pw=0 time=104 us)(object id 54747)
    697     BITMAP INDEX SINGLE VALUE BM2 (cr=396 pr=0 pw=0 time=92 us)(object id 54746)
    727     BITMAP INDEX SINGLE VALUE BM1 (cr=399 pr=0 pw=0 time=117 us)(object id 54745)


Elapsed times include waiting on following events:
  Event waited on                             Times   Max. Wait  Total Waited
  ----------------------------------------   Waited  ----------  ------------
  SQL*Net message to client                    3337        0.00          0.00
  SQL*Net message from client                  3337        0.00          1.04

When the cache is warm, there are no physical reads that take place. This would explain the fast execution of the query.

Note: For Bitmap execution plans, the number that appears in the rows column is actually bitmap fragments (compressed rowids), not actual rows. This is why the number looks suspiciously small.

Query A TKPROF – Cold Cache

select /* cold cache */ *
from bm_test
where a=1 and b=1 and c=1

call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        1      0.00       0.00          0          0          0           0
Execute      1      0.00       0.00          0          0          0           0
Fetch     3334     11.44      36.22      99722     102184          0      333292
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total     3336     11.45      36.22      99722     102184          0      333292

Misses in library cache during parse: 1
Optimizer mode: ALL_ROWS
Parsing user id: 31

Rows     Row Source Operation
-------  ---------------------------------------------------
 333292  TABLE ACCESS BY INDEX ROWID BM_TEST (cr=102184 pr=99722 pw=99722 time=294694 us cost=23314 size=17945290 card=326278)
 333292   BITMAP CONVERSION TO ROWIDS (cr=1162 pr=1041 pw=1041 time=2490 us)
     92    BITMAP AND  (cr=1162 pr=1041 pw=1041 time=5104 us)
    642     BITMAP INDEX SINGLE VALUE BM3 (cr=367 pr=324 pw=324 time=1840 us)(object id 54747)
    697     BITMAP INDEX SINGLE VALUE BM2 (cr=396 pr=351 pw=351 time=1817 us)(object id 54746)
    727     BITMAP INDEX SINGLE VALUE BM1 (cr=399 pr=366 pw=366 time=1534 us)(object id 54745)

Elapsed times include waiting on following events:
  Event waited on                             Times   Max. Wait  Total Waited
  ----------------------------------------   Waited  ----------  ------------
  SQL*Net message to client                    3336        0.00          0.00
  SQL*Net message from client                  3336        0.00          1.12
  db file sequential read                     99722        0.04         30.60

As you can see the majority of the time was spent on db file sequential read doing the 99,722 physical reads. This explains the difference in elapsed time between the cold and warm cache executions of Query A: it comes down to physical I/O. But why does Query C run in half the time that Query A runs in when the cache is cold, given that Query C is doing a FTS and Query A is not? Shouldn’t the FTS plan be slower than the index plan?

Looking at the raw trace file for Query A, we observe the following:

WAIT #2: nam='db file sequential read' ela= 241 file#=1 block#=1770152 blocks=1 obj#=54744 tim=1212013191665924
WAIT #2: nam='db file sequential read' ela= 232 file#=1 block#=1770153 blocks=1 obj#=54744 tim=1212013191666240
WAIT #2: nam='db file sequential read' ela= 351 file#=1 block#=1770156 blocks=1 obj#=54744 tim=1212013191666650
WAIT #2: nam='db file sequential read' ela= 240 file#=1 block#=1770157 blocks=1 obj#=54744 tim=1212013191666948
WAIT #2: nam='db file sequential read' ela= 298 file#=1 block#=1770158 blocks=1 obj#=54744 tim=1212013191667306

As you can see, the table is being read sequentially 1 block at a time. Let’s examine the TKPROF from Query C.

Query C TKPROF

select *
from bm_test
where a=1 and b=2 and c=2

call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        1      0.00       0.00          0          0          0           0
Execute      1      0.00       0.00          0          0          0           0
Fetch    13323      5.99      11.17     102592     115831          0     1332121
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total    13325      5.99      11.17     102592     115831          0     1332121

Misses in library cache during parse: 1
Optimizer mode: ALL_ROWS
Parsing user id: 31

Rows     Row Source Operation
-------  ---------------------------------------------------
1332121  TABLE ACCESS FULL BM_TEST
(cr=115831 pr=102592 pw=102592 time=102744 us cost=28243 size=75768825 card=1377615)

Elapsed times include waiting on following events:
  Event waited on                             Times   Max. Wait  Total Waited
  ----------------------------------------   Waited  ----------  ------------
  SQL*Net message to client                   13325        0.00          0.01
  SQL*Net message from client                 13325        0.00          4.23
  db file sequential read                         2        0.02          0.03
  direct path read                              952        0.08          5.20

The majority of the time is spent on direct path read.

Let’s dig deeper and look at the raw trace file from Query C.

WAIT #2: nam='direct path read' ela= 6029 file number=1 first dba=1785609 block cnt=128 obj#=54744 tim=1212013229612857
WAIT #2: nam='direct path read' ela= 8638 file number=1 first dba=1787017 block cnt=128 obj#=54744 tim=1212013229628256
WAIT #2: nam='direct path read' ela= 7019 file number=1 first dba=1789193 block cnt=128 obj#=54744 tim=1212013229642410
WAIT #2: nam='direct path read' ela= 9276 file number=1 first dba=1791497 block cnt=128 obj#=54744 tim=1212013229658400
WAIT #2: nam='direct path read' ela= 6173 file number=1 first dba=1792777 block cnt=128 obj#=54744 tim=1212013229671314

As you can see with Query C, the read size is 128 blocks or 1MB (128 blocks * 8k block), the largest I/O that Oracle will issue. This explains the difference in the observed I/O throughput (23MB/s vs. 55MB/s): the bitmap index plan reads the table 1 block at a time, and the FTS reads (most of) it 128 blocks at a time. It makes good sense that if the read throughput rate is ~2x (23MB/s vs. 55MB/s) then the execution time would be ~0.5 as long (38 seconds vs. 16 seconds). The larger I/O size will have a higher throughput rate compared to a smaller I/O size. The exact breakdown of the multi-block reads are:

BLOCK_COUNT      COUNT TOTAL_BLOCKS
----------- ---------- ------------
          7          2           14
          8        106          848
          9         34          306
         16         10          160
         33          8          264
        119         42         4998
        128        750        96000
            ---------- ------------
sum                952       102590

Making Sense Of All The Observations

If we look at the tkprof output again from Query A, we see there are 99,722 waits on db file sequential read. Of those 99,722 waits, 98,681 are on the table (grep is our friend here using the raw trace file and the event and object number), the remaining are for the indexes. This tells us that 98,681 out of 102,592 total blocks of the table were retrieved, just 1 block at a time. Basically we have done a very inefficient full table scan. This explains our two observations: 1) why the FTS is faster than the index access plan with a cold cache and 2) why the FTS has a higher read throughput than the index access plan. It all comes down to efficient physical I/O.

The Big Picture

Just because a column has a low NDV does not necessarily mean it is an ideal candidate for a bitmap index. Just like B-tree indexes, bitmap indexes are best leveraged when the combination of them makes it very selective (returns only a small number of rows). The classic example of using a bitmap index on a gender column (male/female) is a horrible one in my opinion. If there are only two values, and there is an even distribution of data, 50% selectivity is too large and thus not a good candidate for a bitmap index. Would you use any index to access 50% of a table?

Bitmap indexes can be very useful in making queries run fast, but if the BITMAP CONVERSION TO ROWIDS returns a large list of rowids, you may find that a FTS (or partition scan) may yield better performance, but may use more I/O resources. It comes down to a trade off: If there is a high buffer cache hit rate for the objects in the bitmap plans, it will run reasonably fast and requite less physical I/O. If the objects are unlikely to be in the buffer cache, a FTS will yield better performance as long as it is not bottlenecked on I/O bandwidth.

Null-Aware Anti-Join

Recently someone showed me a query execution plan with an operation of HASH JOIN ANTI NA. At first, it was thought maybe it was a bug and the operation had a type-o in it, but after further research it was discovered it was a valid operation and a new cost-based query transformation for subquery unnesting in Oracle Database 11g. The NA stands for Null-Aware. There is also a second type of Null-Aware Anti-Join, which is the Single Null-Aware Anti-Join which is displayed in the execution plan as ANTI SNA. The null-aware anti-join may be computed using each of the three types of of join operations: the sort-merge join, hash join and nested loops join.

What is the advantage of a Null-Aware Anti-Join? If we look at the patent application for Null-Aware Anti-Joins we will see that paragraph 0006 gives a brief description:

[0006] A common type of query that is optimized is a query that contains a subquery whose join condition involves the NOT IN/ALL operator (NOT IN is equivalent to != ALL). In data-warehouses with reporting applications, such queries and subqueries are usually evaluated on very large sets of data. Thus, it is critical to make such queries scale in any SQL execution engine. When such queries are not optimized using anti-join, the subquery is executing an operation that is effectively a Cartesian product, which is quite inefficient.

Before we look at the performance side of things, lets just take a look at some simple examples with our favorite EMP table.

SQL> select * from emp;

     EMPNO ENAME      JOB	       MGR HIREDATE	     SAL       COMM	DEPTNO
---------- ---------- --------- ---------- ---------- ---------- ---------- ----------
      7369 SMITH      CLERK	      7902 1980-12-17	     800		    20
      7499 ALLEN      SALESMAN	      7698 1981-02-20	    1600	300	    30
      7521 WARD       SALESMAN	      7698 1981-02-22	    1250	500	    30
      7566 JONES      MANAGER	      7839 1981-04-02	    2975		    20
      7654 MARTIN     SALESMAN	      7698 1981-09-28	    1250       1400	    30
      7698 BLAKE      MANAGER	      7839 1981-05-01	    2850		    30
      7782 CLARK      MANAGER	      7839 1981-06-09	    2450		    10
      7788 SCOTT      ANALYST	      7566 1987-04-19	    3000		    20
      7839 KING       PRESIDENT 	   1981-11-17	    5000		    10
      7844 TURNER     SALESMAN	      7698 1981-09-08	    1500	  0	    30
      7876 ADAMS      CLERK	      7788 1987-05-23	    1100		    20
      7900 JAMES      CLERK	      7698 1981-12-03	     950		    30
      7902 FORD       ANALYST	      7566 1981-12-03	    3000		    20
      7934 MILLER     CLERK	      7782 1982-01-23	    1300		    10

14 rows selected.

As you can see, there is one row where MGR is null.

In the below examples, I’m going to refer to the outer query as the left side, and the subquery as the right side. Each test case has the query, the execution plan and a snippet of the 10053 trace.

11.1.0.6
Test Case 1: Either Side Can Be Null

select count(*)
from   emp
where  mgr not in (select mgr from emp);
Execution Plan
----------------------------------------------------------
Plan hash value: 54517352

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     8 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     8 |            |          |
|*  2 |   HASH JOIN ANTI NA |      |    13 |   104 |     5  (20)| 00:00:01 |
|   3 |    TABLE ACCESS FULL| EMP  |    14 |    56 |     2   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| EMP  |    14 |    56 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("MGR"="MGR")

*****************************
Cost-Based Subquery Unnesting
*****************************
SU: Unnesting query blocks in query block SEL$1 (#1) that are valid to unnest.
Subquery Unnesting on query block SEL$1 (#1)
SU: Performing unnesting that does not require costing.
SU: Considering subquery unnest on query block SEL$1 (#1).
SU:   Checking validity of unnesting subquery SEL$2 (#2)
SU:   Passed validity checks.
SU:   Transform ALL subquery to a null-aware antijoin.
Registered qb: SEL$5DA710D3 0x77a2e6bc (SUBQUERY UNNEST SEL$1; SEL$2)

Test Case 2: Right Side Is Not Null

select count(*)
from   emp
where  mgr not in (select mgr from emp where mgr is not null);
Execution Plan
----------------------------------------------------------
Plan hash value: 2818854569

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     8 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     8 |            |          |
|*  2 |   HASH JOIN ANTI SNA|      |    13 |   104 |     5  (20)| 00:00:01 |
|   3 |    TABLE ACCESS FULL| EMP  |    14 |    56 |     2   (0)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| EMP  |    13 |    52 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("MGR"="MGR")
   4 - filter("MGR" IS NOT NULL)

*****************************
Cost-Based Subquery Unnesting
*****************************
SU: Unnesting query blocks in query block SEL$1 (#1) that are valid to unnest.
Subquery Unnesting on query block SEL$1 (#1)
SU: Performing unnesting that does not require costing.
SU: Considering subquery unnest on query block SEL$1 (#1).
SU:   Checking validity of unnesting subquery SEL$2 (#2)
SU:   Passed validity checks.
SU: Transform ALL subquery to a single null-aware antijoin.
Registered qb: SEL$5DA710D3 0x67e897e8 (SUBQUERY UNNEST SEL$1; SEL$2)

Test Case 3: Left Side Is Not Null

select count(*)
from   emp
where  mgr not in (select mgr from emp) and
       mgr is not null;
Execution Plan
----------------------------------------------------------
Plan hash value: 54517352

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     8 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     8 |            |          |
|*  2 |   HASH JOIN ANTI NA |      |    12 |    96 |     5  (20)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| EMP  |    13 |    52 |     2   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| EMP  |    14 |    56 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("MGR"="MGR")
   3 - filter("MGR" IS NOT NULL)

*****************************
Cost-Based Subquery Unnesting
*****************************
SU: Unnesting query blocks in query block SEL$1 (#1) that are valid to unnest.
Subquery Unnesting on query block SEL$1 (#1)
SU: Performing unnesting that does not require costing.
SU: Considering subquery unnest on query block SEL$1 (#1).
SU:   Checking validity of unnesting subquery SEL$2 (#2)
SU:   Passed validity checks.
SU:   Transform ALL subquery to a null-aware antijoin.
SU:   Checking validity of unnesting subquery SEL$2 (#3)
SU:   Validity checks failed.
Registered qb: SEL$5DA710D3 0x7a357c98 (SUBQUERY UNNEST SEL$1; SEL$2)

Test Case 4: Neither Side Is Null

select count(*)
from   emp
where  mgr not in (select mgr from emp where mgr is not null) and
       mgr is not null;
Execution Plan
----------------------------------------------------------
Plan hash value: 868928733

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     8 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     8 |            |          |
|*  2 |   HASH JOIN ANTI    |      |    12 |    96 |     5  (20)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| EMP  |    13 |    52 |     2   (0)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| EMP  |    13 |    52 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("MGR"="MGR")
   3 - filter("MGR" IS NOT NULL)
   4 - filter("MGR" IS NOT NULL)
*****************************
Cost-Based Subquery Unnesting
*****************************
SU: Unnesting query blocks in query block SEL$1 (#1) that are valid to unnest.
Subquery Unnesting on query block SEL$1 (#1)
SU: Performing unnesting that does not require costing.
SU: Considering subquery unnest on query block SEL$1 (#1).
SU:   Checking validity of unnesting subquery SEL$2 (#2)
SU:   Passed validity checks.
SU:   Transform ALL subquery to a regular antijoin.
Registered qb: SEL$5DA710D3 0x73a4d370 (SUBQUERY UNNEST SEL$1; SEL$2)

As you can see in Test Case 1 and Test Case 3, the optimizer chooses a Null-Aware Anti-Join. In Test Case 2, a Single Null-Aware Anti-Join is chosen, and in Test Case 4 a Regular Anti-Join is chosen.

Let’s compare the plans to 10.2.0.4. I used optimizer_features_enable='10.2.0.4' on my 11.1.0.6 database as well as tested it on 10.2.0.4; the plans are identical in both cases.

10.2.0.4
Test Case 1: Either Side Can Be Null

select count(*)
from   emp
where  mgr not in (select mgr from emp);
Execution Plan
----------------------------------------------------------
Plan hash value: 1842922539

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     4 |    14   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     4 |            |          |
|*  2 |   FILTER            |      |       |       |            |          |
|   3 |    TABLE ACCESS FULL| EMP  |    14 |    56 |     2   (0)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| EMP  |     2 |     8 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter( NOT EXISTS (SELECT 0 FROM "EMP" "EMP" WHERE
              LNNVL("MGR":B1)))
   4 - filter(LNNVL("MGR":B1))

Test Case 2: Right Side Is Not Null

select count(*)
from   emp
where  mgr not in (select mgr from emp where mgr is not null);
Execution Plan
----------------------------------------------------------
Plan hash value: 1842922539

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     4 |    14   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     4 |            |          |
|*  2 |   FILTER            |      |       |       |            |          |
|   3 |    TABLE ACCESS FULL| EMP  |    14 |    56 |     2   (0)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| EMP  |     2 |     8 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter( NOT EXISTS (SELECT 0 FROM "EMP" "EMP" WHERE "MGR" IS NOT
              NULL AND LNNVL("MGR":B1)))
   4 - filter("MGR" IS NOT NULL AND LNNVL("MGR":B1))

Test Case 3: Left Side Is Not Null

select count(*)
from   emp
where  mgr not in (select mgr from emp) and
       mgr is not null;
Execution Plan
----------------------------------------------------------
Plan hash value: 1842922539

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     4 |    14   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     4 |            |          |
|*  2 |   FILTER            |      |       |       |            |          |
|*  3 |    TABLE ACCESS FULL| EMP  |    13 |    52 |     2   (0)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| EMP  |     2 |     8 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter( NOT EXISTS (SELECT 0 FROM "EMP" "EMP" WHERE
              LNNVL("MGR":B1)))
   3 - filter("MGR" IS NOT NULL)
   4 - filter(LNNVL("MGR":B1))

Test Case 4: Neither Side Is Null

select count(*)
from   emp
where  mgr not in (select mgr from emp where mgr is not null) and
       mgr is not null;
Execution Plan
----------------------------------------------------------
Plan hash value: 868928733

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     8 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     8 |            |          |
|*  2 |   HASH JOIN ANTI    |      |     1 |     8 |     5  (20)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| EMP  |    13 |    52 |     2   (0)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| EMP  |    13 |    52 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("MGR"="MGR")
   3 - filter("MGR" IS NOT NULL)
   4 - filter("MGR" IS NOT NULL)

In 10.2.0.4 each of Test Case 1-3 have the same execution plan, but a different one than in 11.1.0.6 because of the new query transformation. Test Case 4 has the same plan in both 10.2.0.4 and 11.1.0.6, which is expected, because neither side can be null and the new query transformation does not kick in. Note the difference on line 2: The 11g plans use the null-aware anti-join, and the 10g plans use a filter.

Performance Test

For a performance test case, I’m going to create two tables of 100,000 rows using the below script and run the Test Cases against them setting OFE to 11.1.0.6 and 10.2.0.4:

drop table t1;

create table t1
as
select case when mod((rownum + 90000),1000) = 0
            then null
            else rownum
       end as a
from dual
connect by level <= 100000;

exec dbms_stats.gather_table_stats(user,'t1');

drop table t2;

create table t2
as
select case when mod((rownum + 90000),1000) = 0
            then null
            else rownum + 90000
       end as a
from dual
connect by level <= 100000;

exec dbms_stats.gather_table_stats(user,'t2');

Performance Test Results

Test Case 10.2.0.4 11.1.0.6
1 00:00:08.24 00:00:00.05
2 00:12:31.24 00:00:00.10
3 00:00:09.08 00:00:00.05
4 00:00:00.10 00:00:00.10

Test Case 1 and 3 have around 82x better time with the 11.1.0.6 plan compared to 10.2.0.4, but the significant difference is with Test Case 2. It’s time was reduced by 7500x or so; from over 12 minutes to less than 1 second. If we examine the 10.2.0.4 plans, we see the optimizer applies a filter push-down transformation using NOT EXISTS and LNNVL.

Let’s examine the statistics of each execution from autotrace.

10.2.0.4 Plan

Execution Plan
----------------------------------------------------------
Plan hash value: 59119136

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     4 |  4014K  (5)| 13:22:56 |
|   1 |  SORT AGGREGATE     |      |     1 |     4 |            |          |
|*  2 |   FILTER            |      |       |       |            |          |
|   3 |    TABLE ACCESS FULL| T1   |   100K|   390K|    45   (5)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| T2   |     1 |     4 |    45   (5)| 00:00:01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter( NOT EXISTS (SELECT 0 FROM "T2" "T2" WHERE "T2"."A" IS
              NOT NULL AND LNNVL("T2"."A":B1)))
   4 - filter("T2"."A" IS NOT NULL AND LNNVL("T2"."A":B1))


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
   14137436  consistent gets
          0  physical reads
          0  redo size
        420  bytes sent via SQL*Net to client
        415  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

11.1.0.6 Plan

Execution Plan
----------------------------------------------------------
Plan hash value: 1028670007

------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     8 |       |   245   (3)| 00:00:03 |
|   1 |  SORT AGGREGATE     |      |     1 |     8 |       |            |          |
|*  2 |   HASH JOIN ANTI SNA|      |  9998 | 79984 |  1568K|   245   (3)| 00:00:03 |
|   3 |    TABLE ACCESS FULL| T1   |   100K|   390K|       |    44   (3)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| T2   | 99900 |   390K|       |    45   (5)| 00:00:01 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("T1"."A"="T2"."A")
   4 - filter("T2"."A" IS NOT NULL)


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
        312  consistent gets
          0  physical reads
          0  redo size
        420  bytes sent via SQL*Net to client
        415  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

The big difference here is that the HASH JOIN ANTI SNA plan has significantly less consistent gets: 312 vs. 14,137,436 – over a 45,000x difference!!! Hence the 12 minutes to less than 1 second execution time. I think it is quite safe to say that the HASH JOIN ANTI SNA is much better than the FILTER plan.

As demonstrated, the Null-Aware Anti-Join query transformation can have a significant performance, even on two tables consisting of a modest 100,000 rows of data.