MySQL5.0.41 でストアド・プロシージャを試す（その４）

MySQL

ではどういう処理をしているのかストアド・プロシージャの中身を見てみよう。

CREATE PROCEDURE shortestPath()
BEGIN
  DECLARE maxLength INT DEFAULT 1;
  DECLARE newSize,oldSize INT DEFAULT 0;
  
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges; --（１）
  
  REPEAT
    INSERT IGNORE INTO paths --（２）
      SELECT DISTINCT p.startNode AS startNode,tail AS endNode,maxLength+1 AS length --（３）
      FROM paths p
      JOIN edges ON p.endNode=head --（４）
      WHERE p.length=maxLength
        AND p.startNode!=tail; --（５）
    
    SET maxLength=maxLength+1; --（６）
    SET oldSize=newSize;
    SELECT COUNT(*) INTO newSize FROM paths; --（７）
  UNTIL oldSize=newSize --（８）
  END REPEAT;
END

（１）まず edges テーブルからデータを引き写す。直に繋がっているので距離は 1 である。
（２）INSERT IGNORE については、マニュアルにこうある。

多くのレコードの INSERT でキーワード IGNORE が指定されていると、テーブルの既存の PRIMARY または UNIQUE キーと重複するレコードはすべて無視され、挿入されない。

もう少し具体的な説明。

例えば、あるテーブルについて、データが無い場合のみINSERTしたいような場合、INSERT前にテーブルをSELECTしてデータの有無を確かめなくても、キーワード”IGNORE”を指定すれば、INSERT文一発で理想の動きをします。

下記の場合で言うと、col1（col2でもいいけど）がPRIMARYかUNIQUEに指定される必要があります。


INSERT IGNORE INTO tbl_name (col1,col2) VALUES(1,'a');

paths テーブルを生成した際の SQL 文は以下の通りで、startNode と endNode のセットに対してプライマリ・キーを設定している。よって同じ経路についてのデータが重複することはないわけだ。

CREATE TABLE paths(
  startNode INT NOT NULL,
  endNode INT NOT NULL,
  length INT NOT NULL,
  CONSTRAINT paths_pri PRIMARY KEY (startNode,endNode)
);
CREATE INDEX s_idx ON paths (startNode);
CREATE INDEX e_idx ON paths (endNode);
CREATE INDEX l_idx ON paths (length);

（３）SELECT DISTINCT は重複したレコードがある場合にひとつだけ取り出すという意味。
（４）paths の endNode から1歩進む。初期状態では、paths テーブルは edges テーブルのデータがコピーされただけの状態になっているから、その１行目は (startNode, endNode, length) = (1, 2, 1) となっている。そこでテーブルの結合条件（４）に従って、ノード2 から伸びている経路を探すことになる。
（５）これにはさらに条件がついていて、現在の maxLength に等しいもので、かつ今見ている行とは異なる経路に限定して探している。１ラウンド目は maxLength=1 なので、距離が 1 のエッジが全て該当する。1行目に関して言えば、(startNode, endNode, length) = (2, 4, 1) と (2, 8, 1) が該当し、(1,4,2) と (1,8,2) の 2行が paths テーブルに追加されることになる。
（６）１ラウンド終了するごとに maxLength の値を１つ増やすことにより、次のラウンドではより長い経路を探索する。
（７）paths テーブルの行数をカウントして newSize に代入している。
（８）前のラウンドの終了時の行数 oldSize と比較して、行数が増えているかどうか調べる。行数が変わっていなければすべての経路の洗い出しが完了したことになるので、REPEAT を終了する。