Striving for Optimal Performance
  • Blog
    • Archive
    • Categories
    • Search
  • Troubleshooting Oracle Performance
    • Description
    • Structure
    • Table of Contents
    • Forewords
    • Reviews
    • Downloadable Files
    • Addenda and Errata
    • First Edition
  • Public Appearances
    • Past Public Appearances
  • Contact
  • About

Join Elimination

11 January 2010 16 Comments Written by Christian Antognini

In some specific situations the query optimizer is able to completely avoid executing a join even if a SQL statement explicitly calls for it. Two are the cases currently covered by this optimization technique, which is called join elimination. The first one was introduced in Oracle Database 10g Release 2, the second one in Oracle Database 11g Release 2. Let’s take a look at two cases to illustrate how join elimination works.

Case #1

Up to Oracle Database 11g Release 1 join elimination is especially useful when views containing joins are used. Note, however, that join elimination does not work only with views. It can be applied to SQL statements without views as well. The following SQL statements define two tables and one view. Notice that between table T1 and table T2, there is a master-child relationship. In fact, table T2, with its column T1_ID, references the primary key of table T1.

SQL> CREATE TABLE t1 (
  2    id NUMBER NOT NULL,
  3    n NUMBER,
  4    pad VARCHAR2(4000),
  5    CONSTRAINT t1_pk PRIMARY KEY(id)
  6  );

SQL> CREATE TABLE t2 (
  2    id NUMBER NOT NULL,
  3    t1_id NUMBER NOT NULL,
  4    n NUMBER,
  5    pad VARCHAR2(4000),
  6    CONSTRAINT t2_pk PRIMARY KEY(id),
  7    CONSTRAINT t2_t1_fk FOREIGN KEY (t1_id) REFERENCES t1
  8  );

SQL> CREATE VIEW v AS
  2  SELECT t1.id AS t1_id, t1.n AS t1_n, t2.id AS t2_id, t2.n AS t2_n
  3  FROM t1, t2
  4  WHERE t1.id = t2.t1_id;

When all the columns are referenced, as shown in the following example, the join is regularly executed. No surprise here.

SQL> EXPLAIN PLAN FOR SELECT * FROM v;

SQL> SELECT * FROM table(dbms_xplan.display(NULL,NULL,'basic'));

PLAN_TABLE_OUTPUT
----------------------------------------------
Plan hash value: 3114288414

----------------------------------------------
| Id  | Operation                    | Name  |
----------------------------------------------
|   0 | SELECT STATEMENT             |       |
|   1 |  NESTED LOOPS                |       |
|   2 |   NESTED LOOPS               |       |
|   3 |    TABLE ACCESS FULL         | T2    |
|   4 |    INDEX UNIQUE SCAN         | T1_PK |
|   5 |   TABLE ACCESS BY INDEX ROWID| T1    |
----------------------------------------------

However, as illustrated in the next example, when only columns defined in the child table are referenced, the query optimizer is able to eliminate the join. It can do so because there is a validated foreign key constraint that guarantees that all rows in table T2 reference one row in table T1.

SQL> EXPLAIN PLAN FOR SELECT t2_id, t2_n FROM v;

PLAN_TABLE_OUTPUT
----------------------------------
Plan hash value: 1513984157

----------------------------------
| Id  | Operation         | Name |
----------------------------------
|   0 | SELECT STATEMENT  |      |
|   1 |  TABLE ACCESS FULL| T2   |
----------------------------------

The relevant part of the output of event 10053 is the following (notice that two queries are shown; the one before the transformation and the one after the transformation):

JE:   Considering Join Elimination on query block SEL$2 (#0)
*************************
Join Elimination (JE)
*************************
SQL:******* UNPARSED QUERY IS *******
SELECT "T2"."ID" "T2_ID","T2"."N" "T2_N" FROM CHA."T1" "T1",CHA."T2" "T2" WHERE "T1"."ID"="T2"."T1_ID"
JE:   cfro: T2 objn:86871 col#:2 dfro:T1 dcol#:2
JE:   cfro: T2 objn:86871 col#:2 dfro:T1 dcol#:2
Query block (0x2b732c78) before join elimination:
SQL:******* UNPARSED QUERY IS *******
SELECT "T2"."ID" "T2_ID","T2"."N" "T2_N" FROM CHA."T1" "T1",CHA."T2" "T2" WHERE "T2"."T1_ID"="T1"."ID"
JE:   eliminate table: T1 (T1)
Registered qb: SEL$FFBD8603 0x2b732c78 (JOIN REMOVED FROM QUERY BLOCK SEL$2; SEL$2; "T1"@"SEL$2")
---------------------
QUERY BLOCK SIGNATURE
---------------------
  signature (): qb_name=SEL$FFBD8603 nbfros=1 flg=0
    fro(0): flg=0 objn=86873 hint_alias="T2"@"SEL$2"

SQL:******* UNPARSED QUERY IS *******
SELECT "T2"."ID" "T2_ID","T2"."N" "T2_N" FROM CHA."T2" "T2"
Query block SEL$FFBD8603 (#0) simplified

Case #2

As of Oracle Database 11g Release 2 join elimination covers another case. Its aim is to avoid the execution of “unnecessary” self-joins. The following SQL statements show an example. Notice that since the join is performed on the primary key (column ID) there is no need to access the table twice. In fact, it is possible to replace the references to the eliminated table (T2 in this example) in the SELECT clause with columns of the table that is not eliminated (T1).

SQL> EXPLAIN PLAN FOR SELECT t11.*, t12.* FROM t1 t11, t1 t12 WHERE t11.id = t12.id;

SQL> SELECT * FROM table(dbms_xplan.display(NULL,NULL,'basic'));

PLAN_TABLE_OUTPUT
----------------------------------
Plan hash value: 3617692013

----------------------------------
| Id  | Operation         | Name |
----------------------------------
|   0 | SELECT STATEMENT  |      |
|   1 |  TABLE ACCESS FULL| T1   |
----------------------------------

The relevant part of the output of event 10053 is the following (also in this case notice that there are two queries):

JE:   Considering Join Elimination on query block SEL$1 (#0)
*************************
Join Elimination (JE)
*************************
SQL:******* UNPARSED QUERY IS *******
SELECT "T11"."ID" "ID","T11"."N" "N","T11"."PAD" "PAD","T12"."ID" "ID","T12"."N" "N","T12"."PAD" "PAD" FROM "CHA"."T1" "T11","CHA"."T1" "T12" WHERE "T11"."ID"="T12"."ID"
JE:   cfro: T1 objn:86871 col#:1 dfro:T1 dcol#:1
JE:   cfro: T1 objn:86871 col#:1 dfro:T1 dcol#:1
JE:   cfro: T1 objn:86871 col#:1 dfro:T1 dcol#:1
JE:   cfro: T1 objn:86871 col#:1 dfro:T1 dcol#:1
Query block (0x2c14f098) before join elimination:
SQL:******* UNPARSED QUERY IS *******
SELECT "T11"."ID" "ID","T11"."N" "N","T11"."PAD" "PAD","T12"."ID" "ID","T12"."N" "N","T12"."PAD" "PAD" FROM "CHA"."T1" "T11","CHA"."T1" "T12" WHERE "T11"."ID"="T12"."ID"
JE:   eliminate table: T1 (T12)
JE:   Replaced column: T12.PAD with column: T11.PAD
JE:   Replaced column: T12.N with column: T11.N
JE:   Replaced column: T12.ID with column: T11.ID
Registered qb: SEL$DF69B110 0x2c14f098 (JOIN REMOVED FROM QUERY BLOCK SEL$1; SEL$1; "T12"@"SEL$1")
---------------------
QUERY BLOCK SIGNATURE
---------------------
  signature (): qb_name=SEL$DF69B110 nbfros=1 flg=0
    fro(0): flg=0 objn=86871 hint_alias="T11"@"SEL$1"

SQL:******* UNPARSED QUERY IS *******
SELECT "T11"."ID" "ID","T11"."N" "N","T11"."PAD" "PAD","T11"."ID" "ID","T11"."N" "N","T11"."PAD" "PAD" FROM "CHA"."T1" "T11"
Query block SEL$DF69B110 (#0) simplified

Note that running the previous example in Oracle Database 11g Release 1 or earlier leads, as expected, to a join like the following one.

SQL> EXPLAIN PLAN FOR SELECT t11.*, t12.* FROM t1 t11, t1 t12 WHERE t11.id = t12.id;

SQL> SELECT * FROM table(dbms_xplan.display(NULL,NULL,'basic'));

PLAN_TABLE_OUTPUT
----------------------------------------------
Plan hash value: 774821007

----------------------------------------------
| Id  | Operation                    | Name  |
----------------------------------------------
|   0 | SELECT STATEMENT             |       |
|   1 |  NESTED LOOPS                |       |
|   2 |   NESTED LOOPS               |       |
|   3 |    TABLE ACCESS FULL         | T1    |
|   4 |    INDEX UNIQUE SCAN         | T1_PK |
|   5 |   TABLE ACCESS BY INDEX ROWID| T1    |
----------------------------------------------
10gR2, 11gR1, 11gR2, Query Optimizer
Chinese Edition of TOP Available!
Edition-Based Redefinition

16 Comments

7 Pings/Trackbacks

  1. Gary Gary
    11 January 2010    

    In Case 1, you can get odd effects with deferred constraints.

    alter table t2 drop constraint t2_t1_fk;
    alter table t2 add constraint t2_t1_fk foreign key (t1_id) references t1 deferrable;
    alter session set constraints=deferred;
    insert into t2 (id, t1_id) values (1,2);
    select t2_id, t2_n from v;
    select t1_id from v;
    select t1_id, t1_n from v;
    commit;

    The optimized selects assume the constraint is in force and give a one row result based solely on t2. The final select is forced to use t1 and returns no rows because the constraint isn’t currently in force for this session.
    PS. I hate deferred constraints.

    Reply
  2. sake sake
    12 January 2010    

    Very useful tip. Thanks.

    However, I’m curious, in what kind of real world situation when the “unnecessary” self-joins will occur ?
    (Besides coder mistake, of course)

    Reply
  3. extremedb extremedb
    12 January 2010    

    hi Christian

    I found 7 Rules for Join Elimination in last year

    1.Primary Key-Foreign Key – normal join, Starting in 10gR2
    2.Primary Key-Foreign Key – ANSI join, Starting in 11gR1
    3.Primary Key-Foreign Key – (semi/anti) join, Starting in 11gR1
    4.Unique Index – outer join, Starting in 11gR1

    Every guru knows above 4 things

    5.Primary Key-Primary Key – simple self join, Starting in 11gR2
    –> you ‘ve aleady mentioned

    There are two more things and one simular thing
    6.Primary Key-Primary Key – self join filter subsumption, Starting in 11gR2
    7.Join Back Elimination – Using Bit Map Join Index, Starting in 9iR1

    let me show you two things

    6.Primary Key-Primary Key – self join filter subsumption
    ex)
    SELECT e1.employee_id, e1.salary, e1.manager_id
    FROM employee e1
    WHERE e1.salary > 10000
    AND e1.manager_id > 100
    AND e1.employee_id IN (SELECT e2.employee_id
    FROM employee e2
    WHERE e2.salary > 9000);

    Outline Data:
    /*+
    …omission
    ELIMINATE_JOIN(@”SEL$5DA710D3″ “E1″@”SEL$1”)
    …omission
    */

    *************************
    Join Elimination (JE)
    *************************
    …omission
    JE: eliminate table: EMPLOYEE (E1)
    JE: Replaced column: E1.MANAGER_ID with column: E2.MANAGER_ID
    JE: Replaced column: E1.SALARY with column: E2.SALARY
    JE: Replaced column: E1.EMPLOYEE_ID with column: E2.EMPLOYEE_ID
    JE: Replaced column: E1.SALARY with column: E2.SALARY
    JE: Replaced column: E1.MANAGER_ID with column: E2.MANAGER_ID
    Registered qb: SEL$CAE83587 0x88a90ea8 (JOIN REMOVED FROM QUERY BLOCK SEL$5DA710D3; SEL$5DA710D3; “E1″@”SEL$1″)

    7.Join Back Elimination – Using Bit Map Join Index
    ex)

    CREATE BITMAP INDEX emp_join_idx_01 ON employee(d.location_id)
    FROM employee e, department d
    WHERE e.department_id = d.department_id;

    SELECT /*+ INDEX(e emp_join_idx_01) */
    COUNT (*)
    FROM employee e, department d
    WHERE e.department_id = d.department_id
    AND d.location_id = 1700;

    ——————————————————+
    | Id | Operation | Name |
    ——————————————————+
    | 0 | SELECT STATEMENT | |
    | 1 | SORT AGGREGATE | |
    | 2 | BITMAP CONVERSION COUNT | |
    | 3 | BITMAP INDEX SINGLE VALUE | EMP_JOIN_IDX_01|
    ——————————————————+

    Outline Data:
    /*+
    …omission
    ELIMINATE_JOIN(@”SEL$1” “D”@”SEL$1″)
    Outline(@”SEL$1″)
    BITMAP_TREE(@”SEL$1” “E”@”SEL$1” AND((“DEPARTMENT”.”LOCATION_ID”)))
    …omission
    */

    ***************************************
    STAR TRANSFORMATION PLANS
    ***************************************
    Best join order so far: 2
    Marked for join-back elimination: “D”@”SEL$1”
    Join order[1]: EMPLOYEE[E]#0
    ***********************
    Best so far: Table#: 0 cost: 1.0003 card: 15.2857 bytes: 45
    ***********************
    Registered qb: SEL$DBFB62D6 0xe414820 (BITMAP JOIN INDEX JOINBACK ELIMINATION SEL$1; SEL$1; “D”@”SEL$1″)

    Last, One simulat thing
    be careful, It is not join-elimination
    It is called Subquery Coalescing, Starting in 11gR2
    ex)
    SELECT /*+ QB_NAME(MAIN) */ e.employee_id, e.first_name, e.last_name
    FROM employee e
    WHERE e.salary > 2000
    AND ( EXISTS (SELECT /*+ QB_NAME(SUB1) */ 1
    FROM department d1
    WHERE d1.department_id = e.department_id
    AND d1.location_id = 1700)
    OR EXISTS (SELECT /*+ QB_NAME(SUB2) */ 1
    FROM department d2
    WHERE d2.department_id = e.department_id
    AND d2.department_name > ‘Accounting’)
    ) ;

    —————————————————+
    | Id | Operation | Name |
    —————————————————+
    | 0 | SELECT STATEMENT | |
    | 1 | MERGE JOIN | |
    | 2 | SORT UNIQUE | |
    | 3 | TABLE ACCESS BY INDEX ROWID | DEPARTMENT|
    | 4 | INDEX FULL SCAN | DEPT_ID_PK|
    | 5 | SORT JOIN | |
    | 6 | TABLE ACCESS FULL | EMPLOYEE |
    —————————————————+

    Outline Data:
    /*+
    …omission
    COALESCE_SQ(@”SUB2″)
    Outline(@”SEL$4B4BED4E”)
    COALESCE_SQ(@”SUB1″)
    …omission
    */

    Subquery Coalescing rewite SQL LIKE below.

    SELECT /*+ QB_NAME(MAIN) */ e.employee_id, e.first_name, e.last_name
    FROM employee e
    WHERE e.salary > 2000
    AND EXISTS (SELECT /*+ QB_NAME(SUB1) */ 1
    FROM department d1
    WHERE d1.department_id = e.department_id
    AND (d1.location_id = 1700 OR d2.department_name > ‘Accounting’)) ;

    from 10053 trace

    Registered qb: SEL$4B4BED4E 0x2428950 (SUBQUERY COALESCE SUB1; SUB1)
    ———————
    QUERY BLOCK SIGNATURE
    ———————
    signature (): QB_NAME=SEL$4B4BED4E nbfros=1 flg=0
    fro(0): flg=0 objn=73948 hint_alias=”D1″@”SUB1″

    Registered qb: SEL$5DD85A06 0x2428950 (SUBQUERY COALESCE SEL$4B4BED4E; SUB2)
    ———————
    QUERY BLOCK SIGNATURE
    ———————
    signature (): QB_NAME=SEL$5DD85A06 nbfros=1 flg=0
    fro(0): flg=0 objn=73948 hint_alias=”D1″@”SUB1″

    good stuff. right?

    Reply
  4. Timur Akhmadeev Timur Akhmadeev
    12 January 2010    

    Hi Christian,

    the second case is an enhancement introduced in a one-off patch #7679164 for most *nix, and is included in Win patch bundle #19

    Reply
  5. Gary Gary
    15 January 2010    

    @sake. One real-world example for case 1 is where you use a view to join a parent and child and the view has columns from both tables. If, when the view is used, only columns from the child table are used the join to the parent can be omitted.

    Reply
  6. Log Buffer #175: a Carnival of the Vanities for DBAs | The Pythian Blog Log Buffer #175: a Carnival of the Vanities for DBAs | The Pythian Blog
    15 January 2010    

    […] are still Striving for Optimal Performance, like Christian Antognini is. Here’s his item on join elimination, which he introduces thus: “In some specific situations the query optimizer is able to […]

  7. Christian Antognini Christian Antognini
    25 January 2010    

    Hi

    @Sake

    > However, I’m curious, in what kind of real world situation when the “unnecessary” self-joins will occur ?

    I do not have a real case to share with you. But, let’s face it, lot of databases run “strange” SQL statements ;-)

    @Gary

    > The optimized selects assume the constraint is in force and give a one row result based solely on t2.

    That should not happen. IMO this is a bug.

    @Dongkyu

    First of all, thank you for the detailed feedback! BTW, I do not consider case 7 a “join elimination” technique. And that even though a join is avoided. Otherwise we should consider also query rewrite techinques being part of “join elimination”. Anyway, it’s not really important ;-)

    @Timur

    > the second case is an enhancement introduced in a one-off patch #7679164 for most *nix

    Thanks for the information. I didn’t know it…

    Cheers,
    Chris

    Reply
  8. Blogroll Report 08/01/2009 – 15/01/2010 « Coskan’s Approach to Oracle Blogroll Report 08/01/2009 – 15/01/2010 « Coskan’s Approach to Oracle
    2 February 2010    

    […] 12-How does Join Elimination works in 11G for unnecessary self joins? Christian Antognini-Join Elimination […]

  9. Donatello Settembrino Donatello Settembrino
    5 February 2010    

    Ciao Christian,
    but if the tables are without PK and FK
    why do not you want to apply the constraints, I believe the following
    solution (PK and FK mode RELY), is the only viable, right?

    SQL> CREATE TABLE t1 (
      2      id NUMBER NOT NULL,
      3      n NUMBER,
      4      pad VARCHAR2(4000)
      5  );
    
    SQL> insert into t1
      2      select rownum as id, rownum+1 as n, dbms_random.string('Z', 1000) as pad
      3      from dual
      4      connect by level <= 100000;
    
    SQL> CREATE TABLE t2 (
      2        id NUMBER NOT NULL,
      3        t1_id NUMBER NOT NULL,
      4        n NUMBER,
      5        pad VARCHAR2(4000)
      6  );
    
    SQL> insert into t2
      2      select rownum as id, rownum as t1_id, rownum+1 as n, dbms_random.string('Z', 1000) as pad
      3      from dual
      4      connect by level <= 100000;
    
    SQL> CREATE VIEW v AS
      2       SELECT t1.id AS t1_id, t1.n AS t1_n, t2.id AS t2_id, t2.n AS t2_n
      3       FROM t1, t2
      4       WHERE t1.id = t2.t1_id;
    
    
    SQL> ALTER TABLE t1 ADD CONSTRAINT t1_pk
      2      PRIMARY KEY (id)
      3      RELY DISABLE NOVALIDATE;
    
    
    SQL> ALTER TABLE t2 ADD CONSTRAINT t2_t1_fk
      2      FOREIGN KEY (t1_id) REFERENCES t1
      3      RELY DISABLE NOVALIDATE;
    
    SQL> EXPLAIN PLAN FOR SELECT t2_id, t2_n FROM v;
    
    
    SQL> SELECT * FROM table(dbms_xplan.display(NULL,NULL,'all'));
    
    
    ---------------------------------------------------------------
    | Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)|
    ---------------------------------------------------------------
    |   0 | SELECT STATEMENT  |      |   100K|  1464K|  2522   (1)|
    |   1 |  TABLE ACCESS FULL| T2   |   100K|  1464K|  2522   (1)|
    ---------------------------------------------------------------
    
    

    thanks
    Donatello

    Reply
  10. Christian Antognini Christian Antognini
    28 February 2010    

    Ciao Donatello

    > why do not you want to apply the constraints, I believe the following
    > solution (PK and FK mode RELY), is the only viable, right?

    Sorry, but I’m not sure to understand what do you mean. Hence, if I missed you question, let me know!

    In the case do you want to know how to take advantage of join elimination in case of missing (enforced) constraints, yes, AFAIK the trick with the disabled constraints marked with RELY is the only viable option.

    HTH
    Chris

    Reply
  11. Donatello Settembrino Donatello Settembrino
    1 March 2010    

    Yes, it was just what I asked and confirm that I wanted

    Thanks

    Donatello

    Reply
  12. Oracle 11.2.0.1: баг типа PERFORMANCE – filtering join elimination « Oracle mechanics Oracle 11.2.0.1: баг типа PERFORMANCE – filtering join elimination « Oracle mechanics
    29 October 2010    

    […] операции исключения «избыточного» соединения (join elimination), а точнее в нашем случае FJE (Filtering Join Elimination – […]

  13. Common errors seen when using OUTER JOIN: Join Against a Constant « So Many Oracle Manuals, So Little Time Common errors seen when using OUTER JOIN: Join Against a Constant « So Many Oracle Manuals, So Little Time
    6 March 2011    

    […] first converted the outer join into a join (and then eliminated two tables from the query using the join elimination technique.) Tom explains: Whenever you see a construct such […]

  14. Log Buffer #175: a Carnival of the Vanities for DBAs Log Buffer #175: a Carnival of the Vanities for DBAs
    13 February 2013    

    […] are still Striving for Optimal Performance as Christian Antognini is. Here’s his item on join elimination, which he introduces thus: “In some specific situations the query optimizer is able to […]

  15. RELY trumps DISABLE | OraStory RELY trumps DISABLE | OraStory
    5 December 2014    

    […] Anyway, first, we can show a clear demonstration of JOIN ELIMINATION. […]

  16. Join Elimination-no_eliminate_join and constraint novalidate | LEO Notes Join Elimination-no_eliminate_join and constraint novalidate | LEO Notes
    13 October 2016    

    […] Oracle从10gR2优化器引入了一个table elimination,也叫join elimination,关于这一转换的说明请参考optimizer团队的why_are_some_of_the_tables_in_my_query_missing_from_the_plan这篇文章,而且在11g中又有了新的增强,Antognini的join-elimination对2个版本进行了测试和描述。 本文中主要关注no_eliminate_join和约束的状态对join elimination的影响,测试环境为11.2.0.4 测试脚本 […]

  1. Log Buffer #175: a Carnival of the Vanities for DBAs | The Pythian Blog on 15 January 2010 at 19:34
  2. Blogroll Report 08/01/2009 – 15/01/2010 « Coskan’s Approach to Oracle on 2 February 2010 at 19:58
  3. Oracle 11.2.0.1: баг типа PERFORMANCE – filtering join elimination « Oracle mechanics on 29 October 2010 at 17:06
  4. Common errors seen when using OUTER JOIN: Join Against a Constant « So Many Oracle Manuals, So Little Time on 6 March 2011 at 02:19
  5. Log Buffer #175: a Carnival of the Vanities for DBAs on 13 February 2013 at 16:35
  6. RELY trumps DISABLE | OraStory on 5 December 2014 at 13:57
  7. Join Elimination-no_eliminate_join and constraint novalidate | LEO Notes on 13 October 2016 at 10:01

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.