mardi 7 juin 2011

ANTI-JOINS : NOT IN vs NOT EXISTS

Une anti-jointure est une jointure entre 2 tables où les lignes de la première table sont retournées s’il n’existe pas de correspondance dans la 2ème table.

Les anti-jointures s’écrivent essentiellement en utilisant soit la clause NOT IN soit la clause NOT EXISTS.

Voici le script de création des 2 tables T1 et T2 que je vais utiliser pour illustrer les anti-jointures:

create table t1 (c1 number, c2 varchar2(50));

create table t2 (c1 number, c2 number);

-- t1
insert into t1 values (1,'TEST1');
insert into t1 values (2,'TEST2');
insert into t1 values (3,'TEST3');

-- t2
insert into t2 values (1,1);
insert into t2 values (2,2);
insert into t2 values (3,NULL);

commit;

create index idx_t1 on T1(c1);
create index idx_t2 on T2(c2);


Si on décide de joindre les tables T1 et T2 en utilisant T1.C1 et T2.C2 seules 2 lignes matchent :
SQL> select * from t1,t2 where t1.c1=t2.c2;

        C1 C2                 C1         C2
---------- ---------- ---------- ----------
         1 TEST1               1          1
         2 TEST2               2          2

2 rows selected. 

L’anti-jointure entre T1 et T2 doit retourner à priori la ligne TEST3 puisque cette ligne est la seule qui n’a pas de correspondance dans T2.
Voyons ce que donne l’anti-join en utilisant la clause NOT EXISTS:
SQL> select /* NOT_EXISTS */ * from t1 where not exists (select 1 from t2 where t1.c1=t2.c2);

        C1 C2
---------- ----------
         3 TEST3

1 row selected. 

On a bien la ligne TEST3 qui est retourné.

Voyons maintenant ce que donne l’anti-join avec la clause NOT IN :
SQL> select /* NOT_IN*/ * from t1 where t1.c1 not in (select t2.c2 from t2);

no rows selected

Cette fois ci le résultat est différent du NOT EXISTS.
Surpris ????

La première conclusion de ce test c’est que le NOT EXISTS et le NOT IN ne sont pas équivalent fonctionnellement. Dans un article précédent sur les semi-joins j’avais montré que les clauses IN et EXISTS étaient équivalent aussi bien fonctionnellement que d’un point de vue performances.
Pour les anti-joins ça peut être le cas mais pas toujours (comme le montre l’exemple ci-dessus).

Voyons pourquoi le NOT IN et le NOT EXISTS ne retournent pas le même résultat dans notre exemple.
L’explication réside dans la manière dont Oracle traite les valeurs NULL avec la clause NOT IN.
En effet, avec la clause NOT IN Oracle compare chaque valeur de T1.C1 avec T2.C2. Si T1.C1 a une correspondance dans T2 alors la ligne de T1 n’est pas retournée. Par contre si T1.C1 est comparé avec NULL, Oracle ne sait pas faire et retourne toujours FALSE pour ce test. Il faut rappeler que NULL dans le monde d’Oracle n’est pas une vraie valeur et veut juste dire : « je ne sais pas ».
Regardez le test PL/SQL ci-dessous.
SQL> set serveroutput on
SQL> declare
  2  v1 varchar2(10);
  3  v2 varchar2(10):='toto';
  4  begin
  5     IF v1<>v2 THEN
  6        dbms_output.put_line('DIFFERENT');
  7     ELSE
  8        dbms_output.put_line('EGAL');
  9     END IF;
 10  end;
 11  /
EGAL

PL/SQL procedure successfully completed.

On a une variable V1 qui est non settée donc NULL, et une variable V2 qui vaut ‘TOTO’. Quand on fait le test « IF V1<>V2 » on ne rentre pas dans le test alors que pour nous V1 est vraiment différent de V2. C’est pour ça qu’il faut toujours faire attention aux valeurs NULL dans Oracle. Que ce soit au niveau des colonnes ou bien au niveau des variables.

La clause NOT EXISTS, elle, ne tient pas compte des NULL et retourne donc un résultat plus logique pour nous.

Lorsqu’on utilise la clause NOT IN il faut donc prendre en compte la possibilité que la sous-requête puisse retourner des valeurs NULL.
Pour ce faire vous pouvez :
- soit ajouter une clause « WHERE NOM_COLONNE IS NOT NULL » dans la sous-requête
- soit ajouter une contrainte NOT NULL au niveau de la colonne
- soit appliquer la fonction NVL à la colonne

Exemple :
SQL> select /* NOT_IN_NOT_NULL*/ * from t1 where t1.c1 not in (select t2.c2 from t2 where t2.c2 is not null);

        C1 C2
---------- ----------
         3 TEST3

1 row selected.

SQL> select /* NOT_IN_NVL*/ * from t1 where t1.c1 not in (select NVL(t2.c2,-1) from t2);

        C1 C2
---------- ----------
         3 TEST3

1 row selected.

Maintenant que nous avons vu la subtilité fonctionnelle entre NOT IN et NOT EXISTS, voyons ce que ça donne d’un point de vue performances en analysant de plus près les plans d’exécution.

Les plans ci-dessous sont les plans pour la version 11g :
SQL> explain plan for
  2  select /* NOT_EXISTS */ * from t1 where not exists (select 1 from t2 where t1.c1=t2.c2);

Explained.

SQL> select * from table(dbms_xplan.display);

Plan hash value: 1534930707

-----------------------------------------------------------------------------
| Id  | Operation          | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |        |     2 |    24 |     3   (0)| 00:00:01 |
|   1 |  NESTED LOOPS ANTI |        |     2 |    24 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1     |     3 |    27 |     3   (0)| 00:00:01 |
|*  3 |   INDEX RANGE SCAN | IDX_T2 |     1 |     3 |     0   (0)| 00:00:01 |
-----------------------------------------------------------------------------

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

   3 - access("T1"."C1"="T2"."C2")
       filter("T2"."C2" IS NOT NULL)

16 rows selected.

SQL> explain plan for
  2  select /* NOT_IN*/ * from t1 where t1.c1 not in (select t2.c2 from t2);

Explained.

SQL> select * from table(dbms_xplan.display);

Plan hash value: 1275484728

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     2 |    24 |     7  (15)| 00:00:01 |
|*  1 |  HASH JOIN ANTI NA |      |     2 |    24 |     7  (15)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1   |     3 |    27 |     3   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T2   |     3 |     9 |     3   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   1 - access("T1"."C1"="T2"."C2")

15 rows selected.

Comme nous l’avions vu pour les semi-jointures, l’anti-jointure est une forme d’optimisation appliquée aux méthodes de jointures classiques telles que NESTED LOOP ou HASH JOIN. L’avantage par exemple du NESTED LOOP ANTI par rapport au NESTED LOOP classique c’est que la recherche dans la sous-requête s’arrête aussitôt qu’une correspondance a été trouvée dans cette table. C’est comme si on avait une clause EXIT dans le code d'une boucle imbriquée.
La nouveauté en 11G est pour le plan du NOT IN avec l’opération « ANTI NA ». NA signifiant NULL AWARE. Cette nouveauté permet d’appliquer la méthode ANTI-JOIN même lorsque la sous-requête retourne des valeurs NULL. Comme on peut le voir ci-dessous, en 10g l’optimiseur ne pouvait pas utiliser d’anti-jointures pour les clauses NOT IN (à moins bien sûr qu’une contrainte NOT NULL soit spécifié pour la colonne récupérée) :

SQL> alter session set optimizer_features_enable='10.2.0.4';

Session altered.

SQL> explain plan for
  2  select /* NOT_IN*/ * from t1 where t1.c1 not in (select t2.c2 from t2);

Explained.

SQL> @plan

Plan hash value: 895956251

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |    20 |     5   (0)| 00:00:01 |
|*  1 |  FILTER            |      |       |       |            |          |
|   2 |   TABLE ACCESS FULL| T1   |     3 |    60 |     3   (0)| 00:00:01 |
|*  3 |   TABLE ACCESS FULL| T2   |     3 |    39 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   1 - filter( NOT EXISTS (SELECT 0 FROM "T2" "T2" WHERE
              LNNVL("T2"."C2"<>:B1)))
   3 - filter(LNNVL("T2"."C2"<>:B1))

Note
-----
   - dynamic sampling used for this statement (level=2)

Ici c’est la clause FILTER qui est utilisée. Ce plan est beaucoup moins performant que celui avec l’anti-join.

Voyons maintenant ce que donne les plans pour les 2 clauses NOT IN et NOT EXISTS lorsqu’on garantit via une contrainte NOT NULL que la sous-requête ne peut pas retourner de valeurs NULL :

SQL> update t2 set c2=5 where c1=3;

1 row updated.

SQL> commit;

Commit complete.

SQL> alter table t2 modify c2 not null;

Table altered.

SQL> alter table t1 modify c1 not null;

Table altered.

SQL> explain plan for
  2  select /* NOT_IN */ * from t1 where t1.c1 not in (select t2.c2 from t2);

Explained.

SQL> select * from table(dbms_xplan.display);

Plan hash value: 1534930707

-----------------------------------------------------------------------------
| Id  | Operation          | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |        |     2 |    24 |     3   (0)| 00:00:01 |
|   1 |  NESTED LOOPS ANTI |        |     2 |    24 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1     |     3 |    27 |     3   (0)| 00:00:01 |
|*  3 |   INDEX RANGE SCAN | IDX_T2 |     2 |     6 |     0   (0)| 00:00:01 |
-----------------------------------------------------------------------------

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

   3 - access("T1"."C1"="T2"."C2")

15 rows selected.

SQL> explain plan for
  2  select /* NOT_EXISTS */ * from t1 where not exists (select 1 from t2 where t1.c1=t2.c2);

Explained.

SQL> select * from table(dbms_xplan.display);

Plan hash value: 1534930707

-----------------------------------------------------------------------------
| Id  | Operation          | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |        |     2 |    24 |     3   (0)| 00:00:01 |
|   1 |  NESTED LOOPS ANTI |        |     2 |    24 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1     |     3 |    27 |     3   (0)| 00:00:01 |
|*  3 |   INDEX RANGE SCAN | IDX_T2 |     2 |     6 |     0   (0)| 00:00:01 |
-----------------------------------------------------------------------------

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

   3 - access("T1"."C1"="T2"."C2")


En plus du même résultat on obtient désormais le même plan pour les 2 requêtes.

Cas pratique :

J’ai récemment eu à traiter un pb de performance sur une requête impliquant une clause NOT IN.
Voici le corps de cette requête avec son plan non-optimal (il s’agissait d’une base 10g):
SELECT  ti.ticker_symbol FROM TICKER_OPTION tf, ticker ti WHERE tf.ticker_id =
ti.ticker_id AND ti.provider_id = 2 AND tf.expiration_dt > SYSDATE AND tf.underlying_ticker_id = 2140
AND tf.ticker_id NOT IN (SELECT inv.ticker_id FROM inventory inv, to_do2 td WHERE  inv.inventory_id =
td.inventory_id AND inv.frequency = 1 AND td.how = 'INTRADAY_BIDASK_NIGHTLY')

Plan hash value: 1691322504

-----------------------------------------------------------------------------------------------------------------
| Id  | Operation                     | Name                  | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------------------------
|*  1 |  FILTER                       |                       |      1 |        |   1272 |00:01:56.13 |    7469K|
|   2 |   NESTED LOOPS                |                       |      1 |    552 |   1810 |00:00:00.13 |    6360 |
|*  3 |    TABLE ACCESS BY INDEX ROWID| TICKER_OPTION         |      1 |    552 |   1810 |00:00:00.07 |     843 |
|*  4 |     INDEX RANGE SCAN          | TICKOPT_TICKER_ID_IDX |      1 |  17464 |  17832 |00:00:00.02 |     134 |
|*  5 |    TABLE ACCESS BY INDEX ROWID| TICKER                |   1810 |      1 |   1810 |00:00:00.06 |    5517 |
|*  6 |     INDEX UNIQUE SCAN         | TICKER_PK             |   1810 |      1 |   1810 |00:00:00.04 |    3707 |
|*  7 |   TABLE ACCESS BY INDEX ROWID | TO_DO2                |   1810 |      1 |    538 |00:01:55.96 |    7463K|
|   8 |    NESTED LOOPS               |                       |   1810 |      1 |   4984 |00:01:55.93 |    7462K|
|*  9 |     TABLE ACCESS FULL         | INVENTORY             |   1810 |      2 |   2761 |00:01:55.84 |    7458K|
|* 10 |     INDEX RANGE SCAN          | TO_DO2_INVID          |   2761 |      1 |    951 |00:00:00.06 |    4572 |
-----------------------------------------------------------------------------------------------------------------

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

   1 - filter( IS NULL)
   3 - filter("TF"."EXPIRATION_DT">SYSDATE@!)
   4 - access("TF"."UNDERLYING_TICKER_ID"=2140)
   5 - filter("TI"."PROVIDER_ID"=2)
   6 - access("TF"."TICKER_ID"="TI"."TICKER_ID")
   7 - filter("TD"."HOW"='INTRADAY_BIDASK_NIGHTLY')
   9 - filter(("INV"."FREQUENCY"=1 AND LNNVL("INV"."TICKER_ID"<>:B1)))
  10 - access("INV"."INVENTORY_ID"="TD"."INVENTORY_ID")

Cette requête générait plus de 7 millions de logical reads pour retourner 1272 lignes.
Le plan nous montre que la clause FILTER était utilisée et donc que l’optimisation ANTI-JOIN n’était pas effectuée. En jetant un œil sur la définition de la table INVENTORY je me suis aperçu que la colonne TICKER_ID était NULLABLE. On a vu précédemment qu’en 10g et lorsqu’on n’avait pas de preuve que la sous-requête ne pouvait pas retourner de valeur NULL, le CBO ne pouvait pas utiliser l’optimisation ANTI-JOIN via un la méthode NESTED LOOP ANTI ou HASH JOIN ANTI. En 11g il aurait pu utiliser la méthode ANTI NA.

Pour améliorer les perfs de cette requête j’ai ajouté la fonction NVL à la colonne TICKER_ID pour traiter explicitement les valeurs NULL. On peut voir ci-dessous que l’optimiseur s’en sort avec un meilleur plan utilisant notamment la méthode HASH JOIN ANTI. Le nombre de logical read passe alors de 7 millions à 9742 :
SELECT ti.ticker_symbol FROM TICKER_OPTION tf, ticker ti WHERE tf.ticker_id = ti.ticker_id AND ti.provider_id = 2
AND tf.expiration_dt > SYSDATE AND tf.underlying_ticker_id = 2140 AND tf.ticker_id NOT IN (SELECT nvl(inv.ticker_id,-10) FROM
inventory inv, to_do2 td WHERE  inv.inventory_id = td.inventory_id AND inv.frequency = 1 AND td.how = 'INTRADAY_BIDASK_NIGHTLY')

Plan hash value: 398754701

--------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                     | Name                  | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
--------------------------------------------------------------------------------------------------------------------------------------------
|   1 |  NESTED LOOPS                 |                       |      1 |      1 |   1272 |00:00:00.65 |    9742 |       |       |          |
|*  2 |   HASH JOIN ANTI              |                       |      1 |      1 |   1272 |00:00:00.64 |    5840 |  1452K|  1452K| 1288K (0)|
|*  3 |    TABLE ACCESS BY INDEX ROWID| TICKER_OPTION         |      1 |    552 |   1810 |00:00:00.08 |     676 |       |       |          |
|*  4 |     INDEX RANGE SCAN          | TICKOPT_TICKER_ID_IDX |      1 |  17464 |  17832 |00:00:00.03 |      49 |       |       |          |
|   5 |    VIEW                       | VW_NSO_1              |      1 |  17690 |  17799 |00:00:00.54 |    5164 |       |       |          |
|*  6 |     HASH JOIN                 |                       |      1 |  17690 |  17799 |00:00:00.52 |    5164 |  1573K|  1573K| 1713K (0)|
|*  7 |      TABLE ACCESS FULL        | TO_DO2                |      1 |  17690 |  17800 |00:00:00.02 |     983 |       |       |          |
|*  8 |      TABLE ACCESS FULL        | INVENTORY             |      1 |    501K|    502K|00:00:00.01 |    4181 |       |       |          |
|*  9 |   TABLE ACCESS BY INDEX ROWID | TICKER                |   1272 |      1 |   1272 |00:00:00.01 |    3902 |       |       |          |
|* 10 |    INDEX UNIQUE SCAN          | TICKER_PK             |   1272 |      1 |   1272 |00:00:00.01 |    2630 |       |       |          |
--------------------------------------------------------------------------------------------------------------------------------------------

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

   2 - access("TF"."TICKER_ID"="$nso_col_1")
   3 - filter("TF"."EXPIRATION_DT">SYSDATE@!)
   4 - access("TF"."UNDERLYING_TICKER_ID"=2140)
   6 - access("INV"."INVENTORY_ID"="TD"."INVENTORY_ID")
   7 - filter("TD"."HOW"='INTRADAY_BIDASK_NIGHTLY')
   8 - filter("INV"."FREQUENCY"=1)
   9 - filter("TI"."PROVIDER_ID"=2)
  10 - access("TF"."TICKER_ID"="TI"."TICKER_ID")


CONCLUSION :

Ce qu'il faut retenir de cet article c'est que lorsque les contraintes NOT NULL sont bien en place alors le choix entre NOT IN et NOT EXISTS n’a pas d’importance. L’optimiseur saura utiliser l’anti-jointure.
Par contre, si la sous-requête peut retourner des valeurs NULL alors il vaut mieux privilégier le NOT EXISTS pour éviter des erreurs fonctionnels (quel que soit la version d'Oracle) et des problèmes de performance (pour les versions antérieures à la 11g ne prenant pas en compte la méthode ANTI NA).

A lire aussi:
SEMI-JOINS: IN vs EXISTS
Sur le blog d'Arkzoyd: Pourquoi NOT IN est sémantiquement différent de NOT EXISTS ?

4 commentaires:

  1. Très intérressant, je pense que je vais jeter un oeil aux clauses NOT NULL de mon Datawarehouse

    RépondreSupprimer
  2. Bonjour,
    Une petite question STP :

    En utilisant : explain plan for select * from ADRESSE_VAD where ADRESSE_ID=1;
    Puis: select * from table(dbms_xplan.display);
    Ca me rend :

    ------------------------------------------------------
    | Id | Operation | Name |
    ------------------------------------------------------
    | 0 | SELECT STATEMENT | |
    | 1 | TABLE ACCESS BY INDEX ROWID| ADRESSE_VAD |
    |* 2 | INDEX UNIQUE SCAN | PK_ADRESSE_VAD |
    ------------------------------------------------------

    càd que je n'ai pas les colonnes :
    | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem |

    Comment puis-je les afficher ?

    Merci d'avance.

    RépondreSupprimer
    Réponses
    1. pour avoir les colonnes A-ROWS et A-TIME il faut executer la requête après avoir activé les stats d'execution (en ajoutant le hint GATHER_PLAN_STATISTICS ou bien settant le parametre STATISTICS_LEVEL à ALL).
      Ensuite on exécute la commande suivante:
      select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));

      Dans ton cas ta requête n'a pas été executée. T'as juste demandé à Oracle de te donner le plan qu'il chosirait si tu l'exécutais

      Supprimer
  3. Trying it as you suggest, I've got :

    --------------------------------------------------------------------------------------------------------------
    | Id | Operation | Name | Starts | A-Rows | A-Time | Buffers | Reads |
    --------------------------------------------------------------------------------------------------------------


    Ther is no E-Rows.


    Regards.

    RépondreSupprimer