Pourquoi NOT IN est sémantiquement différent de NOT EXISTS ?

Il y a quelques semaines, un peu agacé par une discussion où on m’expliquait, une fois encore, que pour obtenir de meilleures performances il fallait écrire une requête avec une syntaxe plutôt qu’une autre, j’ai écrit un article intitulé NOT EXISTS, NOT IN ou OUTER JOIN, on s’en fout ! Comme Sisyphe avant moi, je sais qu’il faudra que je remonte ma pierre bientôt ; la mienne est faîtes d’idées reçues. La prochaine fois, elle sera juste un peu moins lourde.

L’intérêt des technologies Oracle, c’est que vous ne pouvez pas vraiment vous laisser aller ! Alors que j’avais préparé sur ce blog ma parade, j’ai pris un raccourci. Et bien, c’est quand vous prêtez le flan qu’on vous rentre dedans gentillement.

Donc c’est vrai ! Je me laisse aller à prendre des raccourcis. Pire : je le fais exprès ! Il faut dire, à ma décharge, que le contexte du moment n’était pas exactement à discuter des subtilités de l’optimiseur avec des esprits brillants mais plutôt l’inverse (pourvu qu’ils ne se reconnaissent pas ;-D). Enfin, c’est un mal pour un bien puisque, j’imagine en écho à mon article et sur son blog, Ahmed AANGOUR a écrit SEMI-JOINS : IN vs EXISTS. Dans cet article, il explore avec intelligence un autre cas d’idée reçue et met le doigt sur l’époque de ces changements, c’est à dire la version 8i, grâce au paramètre optimizer_features_enable. Il a un esprit affuté, de la rigueur, des références saines et il ne se laisse pas encore aller comme moi à des concessions. Il doit être jeune ; je ne saurais trop vous conseiller de vous abonner à son blog, les bonnes ressources en français ne sont pas si répandues. Je lui souhaite de continuer à être exigeant.

Mais il m’appartient maintenant d’expliquer mon raccourci ; en quoi les clauses NOT IN et NOT EXISTS sont en réalité différentes et l’astuce que j’ai utilisée sans le dire dans mon article pour les rendre identiques…

Le cas des NULL

Mon raccourci concerne les valeurs NULL. Si vous modifiez l’exemple de l’article précédent en enlevant la contrainte sur la colonne id de la table t2, vous pourrez constater que les 2 plans sont en réalité différents :

alter table t2 modify (id null);

explain plan for
select id from t1 a
where id not in
(select id from t2 b);

select * from table(dbms_xplan.display(format=>'basic +predicate +cost'));

PLAN_TABLE_OUTPUT
-------------------------------------------------
Plan hash value: 1979235315

-------------------------------------------------
| Id | Operation | Name | Cost (%CPU)|
-------------------------------------------------
| 0 | SELECT STATEMENT | | 46 (5)|
|* 1 | HASH JOIN ANTI NA | | 46 (5)|
| 2 | INDEX FULL SCAN | T1_PK | 1 (0)|
| 3 | TABLE ACCESS FULL| T2 | 44 (3)|
-------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("ID"="ID")

explain plan for
select id from t1 a
where not exists
(select 1 from t2 b where b.id=a.id);

PLAN_TABLE_OUTPUT
---------------------------------------------------
Plan hash value: 1906534000

-------------------------------------------------
| Id | Operation | Name | Cost (%CPU)|
-------------------------------------------------
| 0 | SELECT STATEMENT | | 46 (5)|
|* 1 | HASH JOIN ANTI | | 46 (5)|
| 2 | INDEX FULL SCAN | T1_PK | 1 (0)|
| 3 | TABLE ACCESS FULL| T2 | 44 (3)|
-------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("B"."ID"="A"."ID")

Vous le découvrez en comparant les 2 commandes explain ci-dessus, la requête avec la clause NOT IN met en oeuvre une opération d’anti-jointure NA (aka Null-Aware)…

En quoi les 2 ordres sont-ils différents

Greg Rahn a écrit un article sur ces algorithmes « xxx JOIN NA » et ses petits frères dit « xxx JOIN SNA », tous les 2 introduits avec Oracle 11g. Il référence la patente associée en plus d’en illustrer simplement le principe.

Pour bien comprendre, il suffit de réfléchir le sens d’une clause NOT IN. Il s’agit en fait de dire que la valeur testée est différente de toutes les valeurs dans la liste. Autrement dit vous pouvez remplacer une clause NOT IN par un ensemble de conditions ajoutées par un et logique AND, chacune testant la différence (!= ou <>) entre la colonne de la condition et les valeurs de la liste. C’est d’ailleurs bêtement ce qu’Oracle fait lorsque vous exécutez une requête mettant en oeuvre une clause NOT IN avec une liste statique. Regardez le plan ci-dessous :

explain plan for select count(*)
from t1
where id not in (1, null);

select * from table(dbms_xplan.display(format=>'basic +predicate +cost'));

PLAN_TABLE_OUTPUT
-----------------------------------------------
Plan hash value: 1213398864

-----------------------------------------------
| Id | Operation | Name | Cost (%CPU)|
-----------------------------------------------
| 0 | SELECT STATEMENT | | 1 (0)|
| 1 | SORT AGGREGATE | | |
|* 2 | INDEX FULL SCAN| T1_PK | 1 (0)|
-----------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
2 - filter("ID"<>1 AND "ID"<>TO_NUMBER(NULL))

Autrement dit d’après le plan précédent not in (1, null) est équivalent à "ID"<>1 AND "ID"<>TO_NUMBER(NULL). Or comme la condition "ID"<>TO_NUMBER(NULL) n’est jamais vraie, si notre liste contient une valeur NULL, la requête ne retourne aucune ligne. On peut valider ce point avec une requête simple :

select dummy  
from dual
where dummy not in (select null from dual);

no rows selected

L’algorithme JOIN NA ignore donc toutes les valeurs testées à partir du moment où il rencontre une valeur NULL dans la seconde phase de son exécution, c’est à dire à gauche de la jointure.

Dans le cas d’une requête avec une clause NOT EXISTS, le comportement est différent. En effet, la condition utilisée est alors une égalité. Lorsque la valeur est NULL la condition d’égalité n’est pas vérifiée mais, magie de la double négation ou du NOT NOT EXISTS, la condition est finalement vraie et la ligne renvoyée. Pour s’en persuader, ré-écrivons la requête précédente avec un NOT EXISTS plutôt qu’un NOT IN :

select dummy  
from dual a
where not exists (select 1
from dual
where a.dummy=null);

D
-
X

Conclusion(s)

Le cas de l’écriture de l’ordre SQL directement sous la forme d’une jointure externe comme ci-dessous est quant à elle équivalente à la clause NOT EXISTS :

select a.id from t1 a, t2 b
where a.id=b.id(+)
and b.id is null;

On peut tirer plusieurs natures de conclusions à ces réflexions. En général d’abord ! la sémantique des ordres SQL est extrêmement importante pour permettre à Oracle de retrouver le « bon » ;-) plan. Il parait évident que si les valeurs ramenées sont différentes, même aux limites, les plans seront généralement différents. Une de ces subtiles différences peut en outre coûter très cher au final puisque, par exemple, les index ne stockent pas les valeurs NULL. Soyez donc vigilent sur ces comportements aux limites. Les contraintes et en particulier NOT NULL ou UNIQUE mais également les contraintes référentielles changent le sens de vos requêtes. Il y a bien d’autres cas ! Le paramétrage NLS de vos clients peuvent également changer les plans d’exécution ; on en a déjà discuté dans un article précédent intitulé « Oracle doit-il faire un tri après un INDEX FULL SCAN ? ».

De manière plus contextuelle ensuite :

  • D’abord, à défaut d’être un menteur puisque j’avais mis une contrainte NOT NULL sur la colonne de la table T2 à dessein pour rendre identiques les 3 requêtes, je suis effectivement un tricheur ! Je n’y ai fait qu’une subtile référence en écrivant la phrase « Vaste sujet que la sémantique surtout si vous considérez les valeurs NULL ou les valeurs distinctes ». Je dis donc « touché Ahmed ! »
  • D’autre part, c’est une réponse encore plus flagrante au prochain qui me propose de remplacer une clause NOT IN par une jointure externe puisque cela démontre que les 2 clauses ne sont même pas sémantiquement équivalentes.

J’espère que cette expérience servira à d’autre d’exemple pour épingler mon comportement pas toujours irréprochable. Je sors un peu moins c.. de cette discussions. A vos commentaires !

Gregory Guillou

About Gregory Guillou

Gregory Guillou has written 766 post in this blog.

Senior Technical Architect at Easyteam

6 thoughts on “Pourquoi NOT IN est sémantiquement différent de NOT EXISTS ?

  1. NicK

    Bonjour,
    pas mal du tout comme article.

    « Lorsque la valeur est NULL la condition d’égalité n’est pas vérifiée mais, magie de la double négation ou du NOT NOT EXISTS, la condition est finalement vraie et la ligne renvoyée. »
    Rien compris à la phrase, désolé.
    Par contre avec l’exemple c’est un peu plus clair. :)

    « Le cas de l’écriture de l’ordre SQL directement sous la forme d’une jointure externe comme ci-dessous est quant à elle équivalente à la clause NOT EXISTS »
    Equivalente oui en théorie, mais pas en performance. J’ai eu un cas où cette jointure externe en 10G plombait les performances du progiciel. J’ai donc demandé la reécriture du SQL généré. (là, j’ai pu argumenter avec les dév.)

    NicK.

  2. Ahmed AANGOUR

    Merci Gregory pour la pub.
    Tu me diras combien je te dois même si tes compliments sont excessifs ;-)

    Pour ceux que ça interesse sachez que la nouvelle optimisation 11g ANTI NA (permettant à Oracle d’appliquer une anti-jointure même lorsque une valeur NULL peut être retournée par la sous-requête) est contrôlable par le paramètre caché « _OPTIMIZER_NULL_AWARE_ANTIJOIN ».

    exemple:
    SQL> alter session set « _optimizer_null_aware_antijoin »=false;

    Session altered.

    SQL> explain plan for
    2 select id from t1 a
    3 where id not in
    4 (select id from t2 b);

    Explained.

    SQL>
    SQL> select * from table(dbms_xplan.display(format=>’basic +predicate +cost’));

    PLAN_TABLE_OUTPUT
    ——————————————————————————–
    Plan hash value: 1416968524

    ————————————————-
    | Id | Operation | Name | Cost (%CPU)|
    ————————————————-
    | 0 | SELECT STATEMENT | | 2 (0)|
    |* 1 | INDEX FULL SCAN | T1_PK | 0 (0)|
    |* 2 | TABLE ACCESS FULL| T2 | 2 (0)|
    ————————————————-

    Predicate Information (identified by operation id):

    PLAN_TABLE_OUTPUT
    ——————————————————————————–
    —————————————————

    1 – filter( NOT EXISTS (SELECT 0 FROM « T2″ « B » WHERE
    LNNVL(« ID »<>:B1)))
    2 – filter(LNNVL(« ID »<>:B1))

    On retrouve ici le plan version 10g.

  3. ArKZoYD

    Thierry,

    Si toutes les colonnes indexées dans un index multi-colonnes ont une valeur NULL, la ligne n’est pas indexée non plus. Les cas que tu décris ressemblent plus à des demis, des tiers ou des quarts de NULL ;-D.

    Evidemment on peut toujours faire l’indien avec des index fonction mais l’idée, c’est surtout de mettre le doigt sur le fait que les contraintes sont importantes pour le CBO et que si une colonne est non-null autant le dire… Le bénéfice est substantiel en général ! IMHO

    Gregory

  4. TGA

    Bonjour,

    Pour t’embêter , tu dis un index ne stocke pas les Nulls :). Tu veux écrire un index mono-colonne ne stocke pas les NULLS, car un index concaténé peut stocker les Nulls.

    A+ et bonne continuation..