Oracle join elimination not working as expected when joining more than two tables

Question

Join elimination works fine when joining two tables:

SQL> set lines 200;
SQL> 
SQL> select * from v$version;

BANNER                                                                               CON_ID                                                                                                             
-------------------------------------------------------------------------------- ----------                                                                                                             
Oracle Database 12c Release 12.1.0.1.0 - 64bit Production                                 0                                                                                                             
PL/SQL Release 12.1.0.1.0 - Production                                                    0                                                                                                             
CORE    12.1.0.1.0  Production                                                                0                                                                                                             
TNS for Linux: Version 12.1.0.1.0 - Production                                            0                                                                                                             
NLSRTL Version 12.1.0.1.0 - Production                                                    0                                                                                                             

SQL> 
SQL> create table t01 (
  2    id integer,
  3    apk varchar2(255 char),
  4    constraint pk_01 primary key (id)
  5  );

Tabelle wurde erstellt.

SQL> create table t02 (
  2    id integer,
  3    apk varchar2(255 char),
  4    id_t01 integer,
  5    constraint pk_02 primary key (id),
  6    constraint fk_02 foreign key (id_t01) references t01(id)
  7  );

Tabelle wurde erstellt.

SQL> create table t03 (
  2    id integer,
  3    apk varchar2(255 char),
  4    id_t02 integer,
  5    constraint pk_03 primary key (id),
  6    constraint fk_03 foreign key (id_t02) references t02(id)
  7  );

Tabelle wurde erstellt.

SQL> create index ix_t03 on t03(id_t02);

Index wurde erstellt.

SQL> create index ix_t02 on t02(id_t01);

Index wurde erstellt.

SQL> insert into t01 (id, apk)
  2  select level, to_char(level)
  3  from dual
  4  connect by level <= 1000;

1000 Zeilen erstellt.

SQL> insert into t02(id, apk, id_t01)
  2  select id, apk, id from t01;

1000 Zeilen erstellt.

SQL> insert into t03(id, apk, id_t02)
  2  select id, apk, id from t01;

1000 Zeilen erstellt.

SQL> commit;

Transaktion mit COMMIT abgeschlossen.

SQL> 
SQL> exec dbms_stats.gather_table_stats(null, 'T01', method_opt=>'for all columns size skewonly', cascade=>true);

PL/SQL-Prozedur erfolgreich abgeschlossen.

SQL> exec dbms_stats.gather_table_stats(null, 'T02', method_opt=>'for all columns size skewonly', cascade=>true);

PL/SQL-Prozedur erfolgreich abgeschlossen.

SQL> exec dbms_stats.gather_table_stats(null, 'T03', method_opt=>'for all columns size skewonly', cascade=>true);

PL/SQL-Prozedur erfolgreich abgeschlossen.

SQL> commit;

Transaktion mit COMMIT abgeschlossen.

SQL> 
SQL> set autotrace traceonly explain;
SQL> 
SQL> select t02.id
  2  from t02
  3  left join t01 on t01.id = t02.id_t01;

Ausführungsplan
----------------------------------------------------------                                                                                                                                              

--------------------------------------------------------------                                                                                                                                          
| Id  | Operation            | Name  | Rows  | Bytes | Cost  |                                                                                                                                          
--------------------------------------------------------------                                                                                                                                          
|   0 | SELECT STATEMENT     |       |  1000 |  8000 |     2 |                                                                                                                                          
|   1 |  INDEX FAST FULL SCAN| PK_02 |  1000 |  8000 |     2 |                                                                                                                                          
--------------------------------------------------------------

--> A fast full scan on the primary key index of t02 takes place, t01 is not read. This is what I am expecting.

Joining t02 and t03 also works as expected:

SQL> 
SQL> select t03.id
  2  from t03
  3  left join t02 on t02.id = t03.id_t02;

Ausführungsplan
----------------------------------------------------------                                                                                                                                              

--------------------------------------------------------------                                                                                                                                          
| Id  | Operation            | Name  | Rows  | Bytes | Cost  |                                                                                                                                          
--------------------------------------------------------------                                                                                                                                          
|   0 | SELECT STATEMENT     |       |  1000 |  8000 |     2 |                                                                                                                                          
|   1 |  INDEX FAST FULL SCAN| PK_03 |  1000 |  8000 |     2 |                                                                                                                                          
--------------------------------------------------------------

--> A fast full scan on the primary key index of t03 takes place, t02 is not read. This is what I am expecting.

The problem arises when I am trying to join t01, t02 and t03:

SQL> select t03.id
  2  from t03
  3  left join t02 on t02.id = t03.id_t02
  4  left join t01 on t01.id = t02.id_t01;

Ausführungsplan
----------------------------------------------------------                                                                                                                                              

------------------------------------------------------------                                                                                                                                            
| Id  | Operation          | Name  | Rows  | Bytes | Cost  |                                                                                                                                            
------------------------------------------------------------                                                                                                                                            
|   0 | SELECT STATEMENT   |       |  1000 | 16000 |    18 |                                                                                                                                            
|   1 |  NESTED LOOPS OUTER|       |  1000 | 16000 |    18 |                                                                                                                                            
|   2 |   TABLE ACCESS FULL| T03   |  1000 |  8000 |    18 |                                                                                                                                            
|   3 |   INDEX UNIQUE SCAN| PK_02 |     1 |     8 |     0 |                                                                                                                                            
------------------------------------------------------------

I would expect (only) a full index scan on pk_03 here, but the execution plan performs a nested loop between T03 and PK02.

What am I doing wrong? Do I have wrong expectations? I could not find anything in the Oracle documentation / stackoverflow / google that explains this behaviour.

The actual database I am working with does have more columns / tables etc., this is just a minimum example. The problem gets worse when joining twenty tables and the expected join elimination does not take place. This has quite a negative impact on our query execution times.

Thank you very much.

The optimizer must think that query plan will perform more efficiently than the alternatives. Are you certain this is a problem? If so, have you tried using query hints, e.g. no nested loops, etc.? — Jacob Barnes, Nov 06 '17 at 16:14
A fast full scan on pk_03 has a cost of 2 (see the join between t02 and t03), the execution plan of the join between t01, t02 and t03 has a cost of 18. This is exactly what I do not understand, why isn't the plan with the lower cost = 2 chosen? The actual query in my production database is represented as a view which is used by dozens of other queries; while I could try to tune this specific example, it is not possible for me to use query hints for all possible query combinations. — wulf6, Nov 06 '17 at 16:33
Your code works as you expect in version 12.1.0.2. I would suggest checking support.oracle.com. — Matthew McPeak, Nov 06 '17 at 19:43
@Matthew McPeak Looks like this problem is actually related to the oracle version: It works as expected in Oracle 12.2.0.1.0 and 11.2.0.4.0 - haven't checked 12.1.0.2 yet. Thank you! — wulf6, Nov 07 '17 at 08:55

kfinity · Answer 1 · 2017-11-06T18:04:39.250

select t03.id
    from t03
    left join t02 on t02.id = t03.id_t02
    left join t01 on t01.id = t02.id_t01;

The table t01 can be eliminated from this query because nothing from that table needs to be read to figure out which rows in t02 have valid FKs pointing to t01 - you can just check the PK index instead of the table.

And to check which rows from t03 have valid FKs pointing to t02, you also don't need to read t02.

But to join these two sets of rows together, you need to read all of t02, to see which rows from one set have ids which match rows from the other set. The indexes alone don't have enough information to make this join.

From this answer, "an index record contains only the indexed field and a pointer to the original record" - which means that fk_03 (on t03) looks kinda like this:

id_t02 t02_rowid
873    AAEiyFAAVAAA49bAAA
874    AAEiyFAAVAAA49bAAB
...

To join them together, you need to ask: Which of the t02 rowids (from the first index) are pointing to a record with an id_t01 value in the second index? And the indexes alone don't have that information - you have to read the table.

Actually, on reviewing, I think the issue is more of matching up t03.id with the pk_02 results. I'm not an expert at this, sorry.

Anyway, you can add that info to a composite index:

create index ix_t0302 on t03(id_t02, id);

Which changes the explain plan:

-------------------------------------------------------------------------------
| Id  | Operation          | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |          |    10 |   160 |     2   (0)| 00:00:01 |
|   1 |  NESTED LOOPS OUTER|          |    10 |   160 |     2   (0)| 00:00:01 |
|   2 |   INDEX FULL SCAN  | IX_T0302 |    10 |    80 |     1   (0)| 00:00:01 |
|*  3 |   INDEX UNIQUE SCAN| PK_02    |     1 |     8 |     1   (0)| 00:00:01 |
-------------------------------------------------------------------------------

*Edited to correct myself

Oracle join elimination not working as expected when joining more than two tables

1 Answers1