【PostgreSQL】連結リストを先頭から順に表示する

DB に連結リストを実装する機会があったのですが、先頭から順に表示するのが予想に反して辛かったので実装例を作っておくことにしました。

PostgreSQL v9.4 で動作を確認しました。

計算量

レコード数 $n$ に対して $\mathcal{O}(n\log{n})$ 程度の時間計算量で動作する気がしていますが、再帰的問い合わせの評価を確認すると $\mathcal{O}(n^2)$ っぽい……？

今回紹介するコードは単純かつ連結な有向グラフとして連結リストを DB 上に実装しています。

？

順序付けはアプリケーションに丸投げすれば簡単に $\mathcal{O}(n)$ を達成できます。記事書くのやめていいですか？

テーブル定義とお試しデータ

CREATE TABLE items (
  id INT PRIMARY KEY,
  label TEXT,
  next_id INT
);
CREATE INDEX items_index ON items (id);

INSERT INTO items (id, label, next_id) VALUES (1, 'a', 3);
INSERT INTO items (id, label, next_id) VALUES (2, 'd', NULL);
INSERT INTO items (id, label, next_id) VALUES (3, 'b', 4);
INSERT INTO items (id, label, next_id) VALUES (4, 'c', 2);

片方向連結リストを表現している items テーブルを定義し、そこにいくつかのデータを流し込みます。
id を主キーとし、id が next_id であるようなレコードへ向かって辺を張っているような構造です。label は連結リストにおいて必須のカラムではありません。

INSERT まで実行するとテーブルは次のようになります。

id	label	next_id
1	'a'	3
2	'd'	NULL
3	'b'	4
4	'c'	2

クエリ

連結リストを先頭からの順序で表示するクエリです。

-- 先頭のノードは与えられていることにする
-- 双方向連結リストならただ前方向に探索すれば先頭を見つけることができる

WITH RECURSIVE dfs_linked_list(
  id,
  label,
  next_id,
  depth
) AS (
    SELECT id, label, next_id, 0 AS depth
    FROM items
    WHERE id = 1
  UNION ALL
    SELECT t1.id, t1.label, t1.next_id, t2.depth + 1
    FROM items t1, dfs_linked_list t2
    WHERE t2.next_id IS NOT NULL AND t1.id = t2.next_id
)
SELECT 
  id,
  label,
  next_id
FROM dfs_linked_list
ORDER BY depth;

WITH RECURSIVE を使った再帰問い合わせで depth というパラメータを管理します。これは連結リストに対する深さ優先探索において、そのノードの深さを表します。そしてそれはそのまま表示順に対応しますから、depth を使ってソートしてあげれば先頭からの順序で出力されます。

id	label	next_id
1	'a'	3
3	'b'	4
4	'c'	2
2	'd'	NULL

実行結果は上記の表のようになります。

おわり

単純に FUNCTION を使った再帰だとネストできる深さに制限があってこちらはこちらで扱い辛さがあります。
SQL、順序を扱うの厳しすぎませんか？