插入查询需要优化 select 具有自连接

Question

A table EMPLOYEE 具有以下结构，其中包含 500 万行 (10^6)。

Name   
------  
EMPNAME
EMPID
MANAGERID (foreign key to same table)
STATUS

我们有一个不同的 table EmpAct，我们在其中执行插入，如下所示

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

这将成为一项成本高昂的操作，因为对于每个非在职员工（不是状态 1、2、3），它都会尝试将存在运行放入相同的 table 500 万条记录中 O( N^2) 操作。

有没有办法让它成为平面 O(N) 操作？

此外，插入到查询中是否可以使用，还是我们应该使用其他一些 PL/SQL 构造来进行插入？

Answer 1

您可以使用分层查询来获取经理状态以及当前 emp 的状态，例如：

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

（您显然不需要 emp 子查询；它只是用来为查询的其余部分生成数据。）

Answer 2

自加入：

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)
;

Answer 3

通过将查询重写为支持散列连接的格式，可以将此查询转换为 O(N)。虽然算法分析很快变得很棘手，我不确定新形式是否会更快。

示例架构

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 操作有点奇怪，但在这种情况下，我认为它就像一个循环，所以我们可以将操作 3 和 4/5 相乘以找到总的运行时间. TABLE ACCESS FULL 是 O(N)，INDEX UNIQUE SCAN 是 O(LOG(N))。所以你应该看到 O(N*LOG(N)) 而不是 O(N^2).

如果您看到两次完整的 table 扫描，那将是 O(N^2)，但是您应该尝试调查为什么 Oracle 没有使用索引。

争取 O(N)

如果你想在 O(N) 中比较数据，我相信散列连接是唯一的选择。散列连接仅适用于相等条件，在这种情况下，我认为 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 |
---------------------------------------------

新方案比较复杂，但是在操作5中使用了hash join，理论上可以O(2N)。但是第 4 行还有另一个 O(N) FULL TABLE SCAN。第 2 行有一个 O(N*LOG(N)) SORT UNIQUE，尽管希望 N 在这一步要小得多。

什么最好？

您正在以正确的方式思考这个问题 - 更多的人应该考虑他们程序的算法复杂性。通常将连接条件转换为支持散列连接的东西是个好主意。但是对于这种奇怪的连接条件，我不确定您是否会看到改进。这可能是常量和实现细节超过复杂性的众多情况之一。

如果你想了解更多，here's a chapter我写了一篇关于使用算法分析来理解SQL性能的文章。

插入查询需要优化 select 具有自连接

Optimization needed for insert into query with select having self join

sql

oracle

performance

query-optimization

insert-select

示例架构

原始查询 - O(N*LOG(N))

争取 O(N)

什么最好？