Overblog
Suivre ce blog
Editer l'article Administration Créer mon blog
10 décembre 2009 4 10 /12 /décembre /2009 15:13
Il y a une problématique assez connue et plutôt sérieuse : le comportement des sous-requêtes NOT IN face aux valeurs NULL.
Mais l'autre jour, je me suis aperçu qu'il y a un autre point rigolo : la nullabilité des colonnes a aussi un impact sur l'algorithme de jointure utilisé !

Et disons le : entre le HASH JOIN ANTI, et le FILTER, il y a vraiment un monde !

Allez, on va regarder ça d'un peu plus près :
1) NOT IN et NULL : pourquoi les résultats sont "faussés".
2) HASH JOIN ANTI, ça arrache
3) Pas de NULL ? Dites-le à Oracle !
4) Petits bonus

1) True, false, ou... on n'en sait rien !

On va prendre un exemple tout simple : une table contenant les valeurs 2 NULL, une autre table avec deux lignes prenant les valeurs 1 et NULL.

CREATE TABLE testnotin1
AS SELECT 2 nb FROM DUAL UNION ALL
SELECT null FROM DUAL;

CREATE TABLE testnotin2
AS SELECT 1 nb FROM DUAL UNION ALL
SELECT null FROM DUAL;


Quelles sont les lignes de la première table dont la valeur n'est pas dans la deuxième ?

SELECT *
FROM testnotin1
WHERE nb NOT IN (SELECT nb FROM testnotin2);

no rows selected


Explication :
Pour qu'une ligne de testnotin1 (a) soit retenue, il faut que pour chaque ligne de testnotin2 (b) :
le prédicat (affirmation) a.nb = b.nb soit fausse.
Or, a.nb = NULL (de même que NULL = b.nb) ne retourne ni vrai, ni faux, mais "indéterminé" !

Ici, il faut encore noter la différence de logique de l'approche "Il n'existe pas de ligne dans b, telle que a.nb = b.nb" :

SELECT *
FROM testnotin1 a
WHERE NOT EXISTS (SELECT 1
FROM testnotin2 b
WHERE a.nb = b.nb);

        NB
----------

         2


(on ne voit pas très bien le NULL, mais le résultat comporte bien deux lignes !)
A présent, on garde la ligne de A s'il n'y a aucune ligne de b pour laquelle le prédicat a.nb = b.nb retourne "vrai".
Or le cas indéterminé n'étant pas "vrai", il n'est pas une entrave pour la sélection de la ligne.

2) Le HASH, c'est bon !


Pour effectuer la requête NOT IN, Oracle a bien entendu plusieurs solutions.
Ici, je veux juste faire un peu de pub pour la méthode de jointure HASH JOIN ANTI.

Pour cela, on va créer deux tables "idéales" : l'une contenant beaucoup de lignes, l'autre peu :

CREATE TABLE test_hash_aj (id NOT NULL, val) AS
SELECT level id, lpad('x', 255, 'x') as val
FROM dual
CONNECT by level <= 1000000;

exec dbms_stats.gather_table_stats('PACMAN', 'TEST_HASH_AJ', cascade => true)

CREATE TABLE test_hash_aj2 (id primary key, val) AS
SELECT level * 1000 id, lpad('x', 255, 'x') as val
FROM dual
CONNECT by level <= 1000
/

exec dbms_stats.gather_table_stats('PACMAN', 'TEST_HASH_AJ2', cascade => true)


a. La méthode perdante :
Pour chaque ligne de A, on utilise l'index unique de B pour voir s'il y a ou non une correspondance (on force avec le hint nl_aj) :

SELECT *
FROM test_hash_aj a
WHERE id NOT IN (SELECT /*+nl_aj*/ id FROM test_hash_aj2 b)
/

999000 rows selected.

Elapsed: 00:00:03.42

-----------------------------------------------------------------
| Id  | Operation          | Name         | Rows  | Bytes | Cost
-----------------------------------------------------------------
|   0 | SELECT STATEMENT   |              |   997K|   251M| 10891
|   1 |  NESTED LOOPS ANTI |              |   997K|   251M| 10891
|   2 |   TABLE ACCESS FULL| TEST_HASH_AJ |   998K|   247M| 10478
|*  3 |   INDEX UNIQUE SCAN| SYS_C007206  |     1 |     4 |     0
-----------------------------------------------------------------

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
    1041999  consistent gets
         52  physical reads
          0  redo size
   10225277  bytes sent via SQL*Net to client
      22362  bytes received via SQL*Net from client
       1999  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
     999000  rows processed



b. Deuxième méthode : on crée une table de hashage, qui a chaque valeur de id dans la table B, associe une adresse mémoire (ou index de tableau).
Puis on lit la table A, et pour chaque ligne, on regarde si la fonction de hashage renvoie quelque chose pour l'id.

SELECT *
FROM test_hash_aj a
WHERE id NOT IN (SELECT  id FROM test_hash_aj2 b)
/

999000 rows selected.

Elapsed: 00:00:01.90


--------------------------------------------------------------------
| Id  | Operation             | Name         | Rows  | Bytes | Cost
--------------------------------------------------------------------
|   0 | SELECT STATEMENT      |              |   997K|   251M| 10502
|*  1 |  HASH JOIN RIGHT ANTI |              |   997K|   251M| 10502
|   2 |   INDEX FAST FULL SCAN| SYS_C00720   |  1000 |  4000 |     2
|   3 |   TABLE ACCESS FULL   | TEST_HASH_AJ |   998K|   247M| 10478
--------------------------------------------------------------------


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
      40005  consistent gets
          0  physical reads
          0  redo size
   10225277  bytes sent via SQL*Net to client
      22362  bytes received via SQL*Net from client
       1999  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
     999000  rows processed



Eh oui, la deuxième méthode fait moins de consistent gets, et s'exécute plus rapidement.
Il faut quand même préciser qu'ici, la différence est limitée par le fait que la distribution des données est parfaite pour le parcours par index !

3) NULL ou bon ? Le CBO ne peut pas le deviner !

Reprenons nos deux tables, mais nettoyons un peu les contraintes :

SQL> ALTER TABLE test_hash_aj MODIFY id NULL;

Table altered.

Elapsed: 00:00:00.04
SQL> ALTER TABLE test_hash_aj2 DROP CONSTRAINT SYS_C00720 KEEP INDEX;

Table altered.



Et retentons l'expérience :

SELECT *
FROM test_hash_aj a
WHERE id NOT IN (SELECT  id FROM test_hash_aj2 b)
/

999000 rows selected.

Elapsed: 00:01:40.93

Execution Plan
----------------------------------------------------------
Plan hash value: 4041281780

-------------------------------------------------------------------
| Id  | Operation          | Name          | Rows  | Bytes | Cost
-------------------------------------------------------------------
|   0 | SELECT STATEMENT   |               |   998K|   247M|    12M
|*  1 |  FILTER            |               |       |       |      
|   2 |   TABLE ACCESS FULL| TEST_HASH_AJ  |   998K|   247M| 10482
|*  3 |   TABLE ACCESS FULL| TEST_HASH_AJ2 |     1 |     4 |    13
-------------------------------------------------------------------

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

   1 - filter( NOT EXISTS (SELECT /*+ */ 0 FROM "TEST_HASH_AJ2" "B" WHERE
              LNNVL("ID"<>:B1)))
   3 - filter(LNNVL("ID"<>:B1))


Statistics
----------------------------------------------------------
        189  recursive calls
          0  db block gets
   41021041  consistent gets
          0  physical reads
          0  redo size
   10225277  bytes sent via SQL*Net to client
      22362  bytes received via SQL*Net from client
       1999  SQL*Net roundtrips to/from client
          4  sorts (memory)
          0  sorts (disk)
     999000  rows processed


Le HASH JOIN ANTI n'est plus choisi... et l'index ne peut être utilisé !
Du coup, on se retrouve avec un opération filter qui coute vraiment très cher : on réexécute la recherche brutale dans B pour chaque ligne de A.

=> Oracle ne sait pas que les colonnes ne contiennent pas de NULL. Or les indexes ne stockent pas les entrées dont toutes les colonnes sont nulles.
... et ils semble donc également que les NULL posent des problèmes à la table de hashage.

Par contre, la méthode NOT EXISTS ne souffre pas du même problème :

 SELECT *
 FROM test_hash_aj a
 WHERE NOT EXISTS (SELECT  1 FROM test_hash_aj2 b WHERE a.id = b.id)
/
--------------------------------------------------------------------
| Id  | Operation             | Name         | Rows  | Bytes | Cost
--------------------------------------------------------------------
|   0 | SELECT STATEMENT      |              |   997K|   251M| 10502
|*  1 |  HASH JOIN RIGHT ANTI |              |   997K|   251M| 10502
|   2 |   INDEX FAST FULL SCAN| SYS_C00720   |  1000 |  4000 |     2
|   3 |   TABLE ACCESS FULL   | TEST_HASH_AJ |   998K|   247M| 10478
--------------------------------------------------------------------


Ce qui se comprend assez bien, puisque selon la logique décrite dans le premier paragraphe, la comparaison à une valeur NULL laisse le résultat global inchangé.

Mais tentons quand même d'expliquer clairement à Mr CBO que notre requête ne contient vraiment pas de NULL :

 SELECT *
 FROM test_hash_aj a
 WHERE id NOT IN (SELECT  id FROM test_hash_aj2 b WHERE id IS NOT NULL)
   AND id IS NOT NULL
/

--------------------------------------------------------------------
| Id  | Operation             | Name         | Rows  | Bytes | Cost
--------------------------------------------------------------------
|   0 | SELECT STATEMENT      |              |   997K|   251M| 10506
|*  1 |  HASH JOIN RIGHT ANTI |              |   997K|   251M| 10506
|*  2 |   INDEX FAST FULL SCAN| SYS_C00720   |  1000 |  4000 |     2
|*  3 |   TABLE ACCESS FULL   | TEST_HASH_AJ |   998K|   247M| 10482
--------------------------------------------------------------------



Ca marche !
A noter qu'ajouter COALESCE n'aide pas, et qu'il faut restreindre les NULL des deux côtés.

Cette histoire est assez traitre, parce que lorsqu'on a conscience du problème de "faux" résultats pour cause de NULL, on peut oublier que même lorsqu'il n'y a pas de NULL, les performances peuvent être lamentables en dépit d'une requête qui semble bien écrite...


4) Au passage...

a. A propos des indexes et des valeurs NULL
Ne pensez pas que les clefs ne sont pas stokées dans un index si une valeur est nulle. En fait, c'est uniquement lorsque toutes les colonnes composant l'index sont nulles que la clef n'est pas stockée.

Petit test :

CREATE INDEX test_hash_aj2_i ON test_hash_aj2(id, 1) COMPUTE STATISTICS
/

SELECT *
FROM test_hash_aj a
WHERE id NOT IN (SELECT  id FROM test_hash_aj2 b);

------------------------------------------------------------------------
| Id  | Operation             | Name            | Rows  | Bytes | Cost
------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |                 |   998K|   247M|  3013K
|*  1 |  FILTER               |                 |       |       |
|   2 |   TABLE ACCESS FULL   | TEST_HASH_AJ    |   998K|   247M| 10482
|*  3 |   INDEX FAST FULL SCAN| TEST_HASH_AJ2_I |     1 |     4 |     3
------------------------------------------------------------------------

b. NOT IN (NULL)... lnnvl !
Reprenons le plan d'exécution de la requête NOT IN, plus précisément aux informations sur les prédicats :

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

   1 - filter( NOT EXISTS (SELECT /*+ */ 0 FROM "TEST_HASH_AJ2" "B" WHERE
              LNNVL("ID"<>:B1)))
   3 - filter(LNNVL("ID"<>:B1))


La fonction LNNVL, renvoie la négation du résultat du prédicat en paramètre lorsque celui-ci vaut TRUE ou FALSE, et renvoie également TRUE lorsque le résutat est indéterminé :

WITH tt AS (SELECT 1 nb FROM dual
  UNION ALL SELECT null FROM dual
  UNION ALL SELECT 2 FROM DUAL)
SELECT nb, 'ouais !'
FROM tt
WHERE lnnvl(nb = 2)
/

 NB 'OUAIS!
--- -------
  1 ouais !
    ouais !


Et donc dans le filtre de l'EXPLAIN, on voit bien que le NULL est traité de la même manière que l'égalité, donc comme un critère de disqualification de la ligne.



Partager cet article

Published by Pacman - dans SGBD
commenter cet article

commentaires