mysql - 使用存储过程实现的 Warshall 算法

Question

我已经在 MySQL 存储过程中实现了 Warshall 的算法。不幸的是，该过程需要很长时间才能完成。我是编写存储过程的初学者，您知道我可以做些什么来让它更快吗？

简要说明:我正在尝试计算邻接表的传递闭包。我想知道哪些节点是连接的(直接在一条边上，或间接地在更多边上)。例如:

Input:  (1, 2), (2, 3), (3, 4)
Output: (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

下图说明了图表:

_{图片来自维基共享资源: https://en.wikipedia.org/wiki/File:Transitive-closure.svg}

您可以在SQL Fiddle上查看代码或在这里:

# "Warshall's algorithm" to calculate the transitive closure
# (1) For k = 1 to n
# (2)   For i = 1 to n
# (3)     If d[i,k] = 1
# (4)       For j = 1 to n
# (5)         If d[k,j] = 1 : d[i,j] = 1
create procedure closure()
begin
    drop table if exists adjMatrix;
    drop table if exists idArray;
    create temporary table adjMatrix (idFrom int not null, idTo int not null,
                                      primary key (idFrom, idTo));
    create temporary table idArray (id int);
    insert into adjMatrix select parent_id, id
                          from article where parent_id is not null;
    insert into idArray select id from article;
    blockk: begin
        declare k, fink int;
        declare ck cursor for select id from idArray;
        declare continue handler for not found set fink = 1;
        open ck;
        loopk: loop
            fetch ck into k;
            if fink = 1 then
                leave loopk;
            end if;
            blocki: begin
                declare i, fini int;
                declare ci cursor for select id from idArray;
                declare continue handler for not found set fini = 1;
                -- select k from dual;
                open ci;
                loopi: loop
                    fetch ci into i;
                    if fini = 1 then
                        leave loopi;
                    end if;
                    blockj: begin
                        if exists (select * from adjMatrix where idFrom=i and idTo=k)
                        then
                            blockx: begin
                                declare j, finj int;
                                declare cj cursor for select id from idArray;
                                declare continue handler for not found set finj = 1;
                                open cj;
                                loopj: loop
                                    fetch cj into j;
                                    if finj = 1 then
                                        leave loopj;
                                    end if;
                                    if exists (select * from adjMatrix
                                               where idFrom=k and idTo=j) then
                                        insert into adjMatrix values (i, j);
                                    end if;
                                end loop loopj;
                                close cj;
                            end blockx;
                        end if;
                    end blockj;
                end loop loopi;
                close ci;
                -- select idFrom, idTo from adjMatrix order by idFrom, idTo;
            end blocki;
        end loop loopk;
        close ck;
    end blockk;
    insert into adjMatrix select id, id from article where parent_id is null;
    select idFrom, idTo from adjMatrix order by idFrom, idTo;
    drop temporary table adjMatrix;
    drop temporary table idArray;
end//

在我的电脑上运行一个有 1466 条记录的表需要 45 秒:

mysql> call closure;
+--------+------+
| idFrom | idTo |
+--------+------+
|      1 |    1 |
|      1 |    2 |
|      1 |    3 |
|      1 |    4 |
|      1 |    5 |
|      2 |    3 |
|      2 |    4 |
|      2 |    5 |
|      3 |    4 |
|      3 |    5 |
|      4 |    5 |
~        ~      ~
|   1587 | 1587 |
|   1588 | 1588 |
|   1589 | 1589 |
+--------+------+
1472 rows in set (45.58 sec)

Answer 1

警告:由于我不熟悉 mysql，我已将问题“翻译”成 MSSQL，因此您需要做一些努力才能将其翻译回来 =)

我猜事情变慢的原因是因为 SQL 并不真正适合这种操作；它不“喜欢”分支和循环以及所有这些东西。它的作用类似于 A LOT，是将数据从一个表匹配到另一个表，最好是在大堆中。 (想想 RDBMS 中的 R)

因此，为了加快存储过程的速度，您可以切换到更适合这种编码风格的不同编程语言；或者您可以将问题转化为更适合 SQL 的问题。当然后者更有趣! =)

稍微考虑一下这个问题，我想到了这个:

CREATE TABLE #result (idFrom int not null, idTo int not null, primary key (idFrom, idTo));

INSERT INTO #result
SELECT parent_id, id
  FROM article 
 WHERE parent_id is not null;

 WHILE @@ROWCOUNT > 0
    BEGIN
        INSERT INTO #result 
        SELECT DISTINCT f.idFrom, t.idTo
          FROM #result f
          JOIN #result t
            ON t.idFrom = f.idTo
         WHERE NOT EXISTS ( SELECT *
                              FROM #result old
                             WHERE old.idFrom = f.idFrom
                               AND old.idTo = t.idTo )
    END

SELECT * FROM #result ORDER BY idFrom, idTo

同样，这是 TSQL(MSSQL 使用的 SQL 方言)，但我猜想将其转换为 mysql 应该非常简单 (??)。

它的作用是:

• 创建一个与您的 adjMatrix 表几乎相同的临时表 #result
• 从其中的源表加载“直接链接”
• 通过将一个记录 idTo 与另一个记录 idFrom 匹配来插入所有“辅助组合”；确保它在表中找不到所述组合，并确保所述列表只有唯一组合(不同)
• 如果添加了新记录(以及组合)，看看我们是否可以添加“下一个”层。

一旦没有发现新的东西，返回结果

例如:给定输入 (1, 2), (2, 3), (3, 4)

将首先用 (1, 2), (2, 3), (3, 4) 填充#result然后进入循环:

iteration1 将匹配以下记录:

• (1,2)-(2,3) => (1,3)
• (2,3)-(3,4) => (2,4)

并将它们添加到 #result 中，我们由此找到 (1, 2), (2, 3), (3, 4), (1, 3), (2, 4)

iteration2 将匹配以下记录:

• (1,2)-(2,3) => (1,3) 但由于 WHERE NOT EXISTS() 而将被淘汰
• (1,2)-(2,4) => (1,4)
• (2,3)-(3,4) => (2,4) 但由于 WHERE NOT EXISTS() 而将被淘汰
• (1,3)-(3,4) => (1,4)

然后它将 DISTINCT 所述列表并且仅保留 (1,4) 的一个实例并将添加因此找到 (1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1 ,4)

iteration4 将匹配以下记录:

• (1,2)-(2,3) => (1,3) 但由于 WHERE NOT EXISTS() 而将被淘汰
• (1,2)-(2,4) => (1,4) 但由于 WHERE NOT EXISTS() 而将被淘汰
• (2,3)-(3,4) => (2,4) 但由于 WHERE NOT EXISTS() 而将被淘汰
• (1,3)-(3,4) => (1,4) 但由于 WHERE NOT EXISTS() 而将被淘汰

由于所有新记录都被删除，我们最终得到一个零行数，因此跳出循环。

我也尝试过使用 SqlFiddle 输入的算法，结果几乎是即时的，但我最终输出了 15 条记录而不是 16 条记录。看来您的代码还包含一个 (1, 1) 记录，它有点让我吃惊？!

无论如何，希望这对您有所帮助。使用 SQL 一段时间后，您将自动学会对数据 block 进行操作，而不是“按值计算”，这会使任何 RDBMS 崩溃。它通常适用于一小部分数据，但一旦输入更多数据，性能就会下降。写得很好的基于集合的 SQL 几乎不会注意到处理 100 条记录或 100000 条记录之间的区别。 (可以这么说=)