Этот запрос можно преобразовать в O (N), переписав запрос в формат, который поддерживает соединения ha sh. Хотя анализ алгоритма становится хитрым очень быстро, и я не уверен, будет ли новая форма быстрее.
Пример схемы
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;
/
Исходный запрос - 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 |
------------------------------------------------------
Операция FILTER немного странная, но в этом случае я считаю, что она действует как al oop, поэтому мы можем объединить операции 3 и 4/5, чтобы найти общее время выполнения. TABLE ACCESS FULL - это O (N), а INDEX UNIQUE SCAN - это O (LOG (N)). Таким образом, вы должны видеть O (N * LOG (N)) вместо O (N ^ 2).
Если вы видите два полных сканирования таблицы, это будет O (N ^ 2), но тогда вы должны попытаться выяснить, почему Oracle не использует индекс.
Стремление к O (N)
Если вы хотите сравнить данные в O (N), я считаю, что ха sh объединение является единственным вариантом. Ха sh объединения работают только с условиями равенства, и в этом случае я думаю, что Oracle недостаточно умен, чтобы понять, как переписать ваш запрос в обычные условия равенства. Мы можем сделать это сами, разбив запрос на две части и объединив их вместе:
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 |
---------------------------------------------
Новый план более сложный, но он использует соединение ha sh в операции 5, что в теории может быть O (2N). Но есть еще один O (N) FULL TABLE SCAN в строке 4. И есть O (N * LOG (N)) SORT UNIQUE в строке 2, хотя мы надеемся, что N будет намного меньше на этом шаге.
Что лучше?
Вы правильно думаете об этом вопросе - все больше людей должны учитывать сложность алгоритмов своих программ. И, как правило, хорошая идея - преобразовать условие соединения в нечто, поддерживающее соединения ha sh. Но с этим странным соединением я не уверен, что ты увидишь улучшение. Это может быть одним из многих случаев, когда константы и детали реализации перевешивают сложность.
Если вы хотите узнать больше, вот глава , которую я написал об использовании анализа алгоритма для понимания SQL производительность.