再帰SQL

NTT オープンソースソフトウェアセンタ板垣貴裕

共通表式 WITH 句と再帰SQL (WITH RECURSIVE) は PostgreSQL 8.4 の新機能です。WITH と WITH RECURSIVE それぞれの説明と、実際の利用例として再帰クエリを使ったロック競合解析の方法を解説します。

共通表式 WITH 句

あるクエリの中で他のクエリの結果を使う方法には、既にサブクエリがあります。WITH 句は、サブクエリの結果に名前をつけ、クエリの複数の箇所からその結果を参照するための構文です。そのクエリの中だけで使用できる一時表 (TEMP TABLE) を作るのに近い動作になります。

利用例としては、あるサブクエリの結果を複数の列と比較する場合が挙げられます。例えば以下のように、表 keyword_list から取得した結果を、表 document の keyword1, keyword2, keyword3 の3つの列と比較しています。(このテーブル設計の良し悪しは、ここでは問わないで下さい ^^;)

例：サブクエリの結果と複数の列の比較

=# CREATE TABLE keyword_list (
     keyword text PRIMARY KEY,
     category text
   );
=# CREATE TABLE document (
     id serial PRIMARY KEY,
     contents text,
     keyword1 text REFERENCES keyword_list (keyword),
     keyword2 text REFERENCES keyword_list (keyword),
     keyword3 text REFERENCES keyword_list (keyword)
   );

=# WITH r AS (
     SELECT keyword
       FROM keyword_list
      WHERE category = 'database'
   )
   SELECT * FROM document, r
    WHERE keyword1 = r.keyword
       OR keyword2 = r.keyword
       OR keyword3 = r.keyword;

再帰SQL (WITH RECURSIVE)

再帰SQLは上記のWITH句を更に拡張した構文で、「WITH (初期候補) UNION [ALL] (繰り返し処理)」の形式で使います。典型的な利用方法は、親子関係を持つ木構造のテーブルに対して繰り返し自己結合 (セルフジョイン; Self-Join) を行う場合です。これまではアプリケーション側で繰り返し結合を行う必要がありましたが、再帰SQLを使うと PostgreSQL 内で繰り返しが行われるため、通信のオーバーヘッドが無くなり高速化が期待できます。ただし、繰り返し処理の条件を間違えるとキャンセルするまで無限ループに陥ることもあるので注意しましょう。

例：親のIDを指定してその子孫を全て取得

=# SELECT * FROM tree;
 id | parent
----+--------
  1 |
  2 |      1
  3 |      1
  4 |      3
 ...

=# WITH RECURSIVE r AS (
       SELECT * FROM tree WHERE id = 1
     UNION ALL
       SELECT tree.* FROM tree, r WHERE tree.parent = r.id
     )
   SELECT * FROM r ORDER BY id;
 id | parent
----+--------
  1 |
  2 |      1
  3 |      1
  4 |      3
(4 rows)

使用例：ロック競合解析

WITH句や再帰クエリは、それ専用に作られたアプリケーションでないと使い道が無いように思いがちですが、実はこれまで運用していたシステムでも用途があります。

PostgreSQL のシステムカタログ pg_locks はデータベース内で行われているロックの状態を調べるためのカタログです。ロック競合の解析に役に立つのですが、「何」を待っているかはすぐに分かるものの、「誰」を待っているかは目視の確認が必要でした。「ブロックされたプロセス → ブロックするプロセス」を目で追うことになります。pg_locks は「プロセス間のブロック依存性」という木構造を持つデータですので、再帰SQLの出番です。ロック競合の解析に必要になる「行の連鎖関係を目で追う」という手順をSQLにやらせてしまおう、というのが趣旨になります。

下準備

下準備として、pg_lock の行の比較を行う関数 locktag() を定義します。この関数は再帰SQLとは直接の関係はありませんが、同じオブジェクトを対象にしたロックか否かの判定をシンプルに記述できるよう関数として切り出しています。

CREATE FUNCTION locktag(pg_catalog.pg_locks) RETURNS text AS
$$
SELECT $1.locktype || ' ' ||
  CASE $1.locktype
    WHEN 'relation'      THEN $1.database || ' ' || $1.relation
    WHEN 'extend'        THEN $1.database || ' ' || $1.relation
    WHEN 'page'          THEN $1.database || ' ' || $1.relation
                              || ' ' || $1.page
    WHEN 'tuple'         THEN $1.database || ' ' || $1.relation
                              || ' ' || $1.page || ' ' || $1.tuple
    WHEN 'transactionid' THEN $1.transactionid::text
    WHEN 'virtualxid'    THEN $1.virtualxid
    -- TODO: for object, userlock and advisory
  END
$$
LANGUAGE sql IMMUTABLE STRICT;

再帰クエリを使ったロック競合の解析

これが処理の主体になる、ビュー pg_lock_chain の定義です。再帰クエリとWindow関数の row_number() を使用しています。 locktag() 関数の返値を比較して、同じオブジェクトに対するロックを列挙しています。

CREATE VIEW pg_lock_chain AS
  WITH RECURSIVE r AS (
      SELECT *, locktag(pg_locks),
             row_number() OVER () AS chain,
             1 AS level
       FROM pg_locks WHERE NOT granted
    UNION ALL
      SELECT s.*, locktag(s), r.chain, r.level + 1
        FROM r, pg_locks s
       WHERE (locktag(s) = r.locktag AND s.granted AND
              NOT r.granted AND s.pid <> r.pid)
          OR (s.pid = r.pid AND NOT s.granted AND r.granted)
     )
   SELECT * FROM r;

ロック競合の解析結果

ビュー pg_lock_chain の出力結果は以下のようになります。列 chain はロックの連鎖ごとの ID、level は連鎖の深さを表します。

=# SELECT chain, level, locktag, pid, mode, granted
     FROM pg_lock_chain
    ORDER BY chain, level;

 chain | level |        locktag        | pid  |     mode      | granted
-------+-------+-----------------------+------+---------------+---------
     1 |     1 | transactionid 9930    | 3976 | ShareLock     | f
     1 |     2 | transactionid 9930    | 3912 | ExclusiveLock | t
     2 |     1 | tuple 21509 22126 0 1 | 1992 | ExclusiveLock | f
     2 |     2 | tuple 21509 22126 0 1 | 3976 | ExclusiveLock | t
     2 |     3 | transactionid 9930    | 3976 | ShareLock     | f
     2 |     4 | transactionid 9930    | 3912 | ExclusiveLock | t
(6 rows)

この結果からは、pid (プロセスID) で示すと以下のロック競合があることが読み取れます。まず、chain = 1, 2 の2つがあることから2つのロック競合があることがわかります。ただし、途中から同一の連鎖になっている場合もあります。2つの連鎖は、どちらも pid=3912 のプロセスがロックの大元です。このプロセスが実行しているトランザクションを完了すれば、待機している他のトランザクションが再開できます。

(pid=3976) → (pid=3912)
(pid=1992) → (pid=3976) → (pid=3912)

実際に利用する際には、さらにシステムカタログ pg_stat_activity と結合して実行中の SQL を特定するなどの手順を取ることになるでしょう。

再帰SQLの互換性

PostgreSQL 8.4 の再帰SQLは標準SQLに従った構文ですが、8.3 以前のバージョンや他DBMSでは異なる構文を使う必要があります。同様の結果を得るためのSQLの書き方を以下に示します。既存のアプリケーションを移行する際などで参考にしてください。

PostgreSQL 8.4 : WITH RECURSIVE

標準SQLに規定された構文です。典型的な利用方法では、WITH RECURSIVE の直後に「ループの初期条件」を、UNION ALL の後に「ループでの繰り返し処理」を記述することになります。

WITH RECURSIVE r AS (
    SELECT 1 AS level, * FROM emp WHERE mgr IS NULL
  UNION ALL
    SELECT r.level + 1, emp.* FROM emp, r WHERE r.empno = emp.mgr
)
SELECT * FROM r;

PostgreSQL ～8.3 : connectby()

PostgreSQL 8.3 までは contrib/tablefunc モジュールで「connectby() 関数」として再帰処理が提供されていました。これは 8.4 でも継続して利用できます。関数に列名を渡したり、結果の型を明記する必要があるなど、記述が煩雑になるのが欠点でした。

SELECT t.level, e.empno, e.mgr, e.ename, e.job
  FROM emp e, (SELECT * FROM
     connectby('emp', 'empno', 'mgr', 'mgr', 7839, 0, '~') 
     AS cb(empno int, mgr int, level int, branch text, pos int)) t
WHERE e.empno = t.empno;

Oracle Database: CONNECT BY

Oracle では CONNECT BY 構文で再帰SQLを記述します。 "level" がシステム列であるなど、独特の構文です。

 SELECT level, empno, mgr, ename, job
   FROM emp
  START WITH mgr IS NULL
CONNECT BY PRIOR empno = mgr;

ただし、Oracle 11g Release 2 以降は標準SQLに則った構文も利用できるようになったため、新しいアプリケーションでは WITH 句を使うほうが移植性が高まるでしょう。

外部リンク

日本語ドキュメント: WITH問い合わせ (英語)
PostgreSQL Wiki: CTEReadme
新しい業界標準「SQL99」詳細解説 (@IT)
PostgreSQLの再帰SQL (CodeZine)
"Trees and More in SQL", David Fetter, FOSDEM 2009 (PDF)

(2009年3月2日公開)