Optimisation nécessaire pour l'insertion dans la requête avec select ayant une auto-jointure

Vous pouvez utiliser une requête hiérarchique pour obtenir le statut du manager ainsi que le statut actuel de l'emp, par exemple:

WITH emp AS (SELECT 'a' empname, 1 empid, 1 status, NULL mgr_id FROM dual UNION ALL
             SELECT 'b' empname, 2 empid, 2 status, 1 mgr_id FROM dual UNION ALL
             SELECT 'c' empname, 3 empid, 4 status, NULL mgr_id FROM dual UNION ALL
             SELECT 'd' empname, 4 empid, 1 status, 3 mgr_id FROM dual UNION ALL
             SELECT 'e' empname, 5 empid, 6 status, 3 mgr_id FROM dual UNION ALL
             SELECT 'f' empname, 6 empid, 3 status, NULL mgr_id FROM dual UNION ALL
             SELECT 'g' empname, 7 empid, 5 status, 6 mgr_id FROM dual),
 initres AS (SELECT empname, empid, status, mgr_id, PRIOR status mgr_status
             FROM   emp
             START WITH mgr_id IS NULL
             CONNECT BY PRIOR empid = mgr_id)
SELECT empname,
       empid,
       status
FROM   initres
WHERE  status IN (1, 2, 3)
OR     mgr_status IN (1, 2, 3);

EMPNAME      EMPID     STATUS
------- ---------- ----------
a                1          1
b                2          2
d                4          1
f                6          3
g                7          5

(Vous n'auriez évidemment pas besoin de la sous-requête emp; c'est seulement là pour générer des données pour le reste de la requête.)

Avec auto-inscription:

insert into empact
select e.empname, e.empid, e.status
from emp e left outer join emp m on e.mgr_id = m.empid
where e.status in (1,2,3) or m.status in (1,2,3)
;

Cette requête peut être convertie en O (N) en réécrivant la requête dans un format prenant en charge les jointures par hachage. Bien que l'analyse de l'algorithme devienne très rapidement délicate, et je ne suis pas sûr que le nouveau formulaire soit plus rapide.

Exemple de schéma

explain plan for
INSERT INTO empact
SELECT empName, empid, status
FROM  employee e
WHERE e.status in (1, 2, 3) 
UNION
SELECT empName, empid, status
FROM  employee e
WHERE EXISTS (SELECT 1 
              FROM employee  m 
              WHERE m.empid = e.managerid AND
                 m.status IN (1,2,3)
            );

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

Plan hash value: 3147379352

---------------------------------------------
| Id  | Operation                | Name     |
---------------------------------------------
|   0 | INSERT STATEMENT         |          |
|   1 |  LOAD TABLE CONVENTIONAL | EMPACT   |
|   2 |   SORT UNIQUE            |          |
|   3 |    UNION-ALL             |          |
|   4 |     TABLE ACCESS FULL    | EMPLOYEE |
|   5 |     HASH JOIN            |          |
|   6 |      TABLE ACCESS FULL   | EMPLOYEE |
|   7 |      TABLE ACCESS FULL   | EMPLOYEE |
---------------------------------------------

Requête d'origine - O (N * LOG (N))

explain plan for
INSERT INTO empact
SELECT empName, empid, status
FROM  employee e
WHERE e.status in (1, 2, 3) 
      OR
      EXISTS (SELECT 1 
              FROM employee  m 
              WHERE m.empid = e.managerid AND
                 m.status IN (1,2,3)
            );

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


Plan hash value: 961581243

------------------------------------------------------
| Id  | Operation                     | Name         |
------------------------------------------------------
|   0 | INSERT STATEMENT              |              |
|   1 |  LOAD TABLE CONVENTIONAL      | EMPACT       |
|   2 |   FILTER                      |              |
|   3 |    TABLE ACCESS FULL          | EMPLOYEE     |
|   4 |    TABLE ACCESS BY INDEX ROWID| EMPLOYEE     |
|   5 |     INDEX UNIQUE SCAN         | SYS_C0027564 |
------------------------------------------------------

L'opération FILTER est un peu bizarre, mais dans ce cas, je pense qu'elle agit comme une boucle, donc nous pouvons plusieurs opérations ensemble 3 et 4/5 pour trouver la durée totale de fonctionnement. Le TABLE ACCESS FULL est O (N) et le INDEX UNIQUE SCAN serait O (LOG (N)). Vous devriez donc voir O (N * LOG (N)) au lieu de O (N ^ 2).

Si vous voyez deux balayages de table complets, ce serait O (N ^ 2), mais alors vous devriez essayer de rechercher pourquoi Oracle n'utilise pas l'index.

Chercher O (N)

Si vous voulez comparer les données en O (N), je crois que la jointure par hachage est la seule option. Les jointures de hachage ne fonctionnent qu'avec des conditions d'égalité, et dans ce cas, je pense qu'Oracle n'est pas assez intelligent pour comprendre comment réécrire votre requête dans des conditions d'égalité régulières. Nous pouvons le faire nous-mêmes en divisant la requête en deux parties et en les UNIONING ensemble:

create table employee
(
    empname varchar2(100),
    empid number primary key,
    managerid number references employee(empid),
    status number
);
create table empact as select empName, empid, status from employee where 1=0;

insert into employee
select level, level, level, 1 from dual connect by level <= 100000;
begin
    dbms_stats.gather_table_stats(user, 'EMPLOYEE');
end;
/

Le nouveau plan est plus compliqué mais il utilise une jointure par hachage dans l'opération 5, qui en la théorie peut être O (2N). Mais il y a un autre O (N) FULL TABLE SCAN sur la ligne 4. Et il y a un O (N * LOG (N)) SORT UNIQUE sur la ligne 2, bien qu'avec un peu de chance le N est beaucoup plus petit à ce stade.

Qu'est-ce qui est le mieux?

Vous pensez à cette question de la bonne façon - plus de gens devraient considérer la complexité de l'algorithme de leurs programmes. Et généralement, la conversion d'une condition de jointure en quelque chose qui prend en charge les jointures par hachage est une bonne idée. Mais avec cette condition de jointure étrange, je ne suis pas sûr que vous constatiez une amélioration. C'est peut-être l'un des nombreux cas où les constantes et les détails d'implémentation l'emportent sur la complexité.

Si vous voulez en savoir plus, voici un chapitre que j'ai écrit sur l'utilisation de l'analyse d'algorithme pour comprendre les performances SQL.