SQL 再帰CTE:カテゴリツリーとロール権限のための階層データのモデリングとクエリ

Database tutorial - IT technology blog
Database tutorial - IT technology blog

単純なJOINでは対応できないとき

ECプラットフォームを構築しているとします。商品カテゴリはこんな構造になっています:

Electronics
  └── Phones
        ├── Android
        └── iPhone
  └── Laptops
        └── Gaming Laptops

最初の直感は自己結合(self-join)を使うことです。1階層目にJOIN、2階層目にもうひとつJOIN——そしてデータが5階層にも及ぶことに気づきます。本来3行で書けるはずのクエリが、気づけば8つのJOINを並べることになっています。

これが階層データの典型的な問題です。商品カテゴリ、組織図、ファイルシステム、権限の継承、コメントスレッドなど、構造が入れ子になる場所には必ず現れます。標準的なリレーショナルSQLは再帰構造を想定して設計されていませんでしたが、モダンなデータベースは再帰CTEによってこの問題をエレガントに解決しました。

基本概念

隣接リストモデル

階層データを格納する最も一般的な方法が隣接リストモデルです:各行が親への参照を保持します。このパターンを使ったcategoriesテーブルの例を見てみましょう:

CREATE TABLE categories (
    id        INT PRIMARY KEY,
    name      VARCHAR(100) NOT NULL,
    parent_id INT REFERENCES categories(id)  -- NULLはルートノードを意味する
);

理解しやすく、新しいノードの挿入も簡単です。難しいのは、ツリーとして読み出すこと——そこで再帰の出番になります。

再帰CTEとは?

CTE(共通テーブル式)とは、WITHキーワードを使ってSQLの先頭に定義する名前付きサブクエリのことです。再帰CTEは自分自身を参照するCTEで、処理するものがなくなるまでクエリを階層ごとにループさせます。

構造は常にUNION ALLで結合された2つの部分から成ります:

  • アンカーメンバー:開始点——基底ケース(ルートノード、または任意の開始ノード)
  • 再帰メンバー:CTE自身に結合し、イテレーションごとに1階層深く進む

データベースは新しい行が返らなくなるまで再帰メンバーを実行し続けます。アプリケーション側のループは不要です。

実践:カテゴリツリー

ステップ1:データの準備

カテゴリツリーを作成してテストデータを挿入してみましょう。PostgreSQL構文を使用します——MySQL 8+も同じWITH RECURSIVEキーワードを使います。SQL Serverも再帰CTEをサポートしていますが、RECURSIVEキーワードは省略します:

INSERT INTO categories (id, name, parent_id) VALUES
    (1, 'Electronics',    NULL),
    (2, 'Phones',         1),
    (3, 'Laptops',        1),
    (4, 'Android',        2),
    (5, 'iPhone',         2),
    (6, 'Gaming Laptops', 3),
    (7, 'Samsung',        4),
    (8, 'Pixel',          4);

ステップ2:ノードの全子孫を取得する

「Electronics」(id = 1)配下のすべてのカテゴリを取得したいとします。再帰CTEはこうなります:

WITH RECURSIVE category_tree AS (
    -- アンカー:ルートノードから開始
    SELECT id, name, parent_id, 0 AS depth
    FROM categories
    WHERE id = 1

    UNION ALL

    -- 再帰:現在の結果セットに子を結合
    SELECT c.id, c.name, c.parent_id, ct.depth + 1
    FROM categories c
    INNER JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT id, name, depth
FROM category_tree
ORDER BY depth, name;

結果:

 id | name             | depth
----+------------------+-------
  1 | Electronics      |   0
  2 | Phones           |   1
  3 | Laptops          |   1
  4 | Android          |   2
  5 | iPhone           |   2
  6 | Gaming Laptops   |   2
  7 | Pixel            |   3
  8 | Samsung          |   3

depthカラムは無償で追跡できます——コストなしで各ノードが何階層目にあるかを正確に把握できます。

ステップ3:完全なパンくずパスの構築

「Electronics > Phones > Android」のようなパンくず文字列はよくある要件です。走査しながらパスを文字列として蓄積するようCTEを修正します:

WITH RECURSIVE category_path AS (
    -- アンカー:ルートノード、パスはノード名から始まる
    SELECT id, name, parent_id, name::TEXT AS path
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    -- 再帰:既存パスに子ノード名を追加
    SELECT c.id, c.name, c.parent_id, cp.path || ' > ' || c.name
    FROM categories c
    INNER JOIN category_path cp ON c.parent_id = cp.id
)
SELECT id, name, path
FROM category_path
ORDER BY path;

ツリー内のすべてのノードに対してクリーンなパンくず文字列を生成します——アプリケーションレベルのループも余分なクエリも不要です。

実践的なユースケース:多階層ロール権限

権限の継承も、このパターンが威力を発揮するもうひとつの場面です。各ロールがシンプルな基底ロールを拡張する階層構造を考えてみましょう:

Viewer        (基本:閲覧可能)
  └── Editor  (追加:編集可能)
        └── Manager  (追加:公開可能)
              └── Admin  (追加:削除、ユーザー管理)

各ロールは固有の権限のみを持ちます。Managerがログインすると、EditorやViewerができることをすべて自動的に得られるべきです。蓄積されたすべてを収集するには、継承チェーンを上向きに辿る必要があります。

ロールと権限テーブルのセットアップ

CREATE TABLE roles (
    id        INT PRIMARY KEY,
    name      VARCHAR(50) NOT NULL,
    parent_id INT REFERENCES roles(id)  -- よりシンプルな基底ロールを指す
);

CREATE TABLE role_permissions (
    role_id    INT REFERENCES roles(id),
    permission VARCHAR(100) NOT NULL
);

INSERT INTO roles VALUES
    (4, 'Viewer',  NULL),  -- 基底ロール、何も継承しない
    (3, 'Editor',  4),     -- Viewerを拡張
    (2, 'Manager', 3),     -- Editorを拡張
    (1, 'Admin',   2);     -- Managerを拡張、すべてを継承

INSERT INTO role_permissions VALUES
    (1, 'delete_posts'),
    (1, 'manage_users'),
    (2, 'publish_posts'),
    (3, 'edit_posts'),
    (4, 'view_posts');

継承されたすべての権限をクエリする

Manager(id = 2)が持つすべての権限——EditorやViewerから継承したものも含めて——を取得するには、チェーンを上向きに辿ってすべての祖先ロールを見つけ、権限と結合します:

WITH RECURSIVE role_ancestors AS (
    -- アンカー:対象ロールから開始
    SELECT id, name, parent_id
    FROM roles
    WHERE id = 2  -- Manager

    UNION ALL

    -- 再帰:基底ロールへ上向きに辿る
    SELECT r.id, r.name, r.parent_id
    FROM roles r
    INNER JOIN role_ancestors ra ON r.id = ra.parent_id
)
SELECT DISTINCT rp.permission
FROM role_ancestors ra
JOIN role_permissions rp ON rp.role_id = ra.id
ORDER BY rp.permission;

結果:

permission
-----------
edit_posts
publish_posts
view_posts

クエリはManagerから始まり、Editor(parent_id = 3)、Viewer(parent_id = NULL)へと辿り、各ロールの権限を収集していきます。カテゴリツリークエリとの唯一の構造的な違いは結合の方向です:c.parent_id = ct.idの代わりにr.id = ra.parent_id。このたった1つの入れ替えが、子を探す走査から祖先を探す走査へと変えます。それ以外はすべて同じです。

実践的なヒントと注意点

parent_idには必ずインデックスを

parent_idにインデックスがない場合、再帰ステップのたびにフルテーブルスキャンが発生します。数千行程度であれば問題ありませんが、数十万行になると深刻なパフォーマンス問題になります:

CREATE INDEX idx_categories_parent ON categories(parent_id);
CREATE INDEX idx_roles_parent ON roles(parent_id);

無限ループへの対策

誤った循環参照——親チェーンが最終的に自分自身を指すノード——があると、再帰CTEはデータベースの再帰制限に達するまでループし続けます。安全策として深さの上限を追加しましょう:

WITH RECURSIVE category_tree AS (
    SELECT id, name, parent_id, 0 AS depth
    FROM categories WHERE id = 1

    UNION ALL

    SELECT c.id, c.name, c.parent_id, ct.depth + 1
    FROM categories c
    INNER JOIN category_tree ct ON c.parent_id = ct.id
    WHERE ct.depth < 20  -- 20階層で停止
)
SELECT * FROM category_tree;

PostgreSQL 14以降には、手動での深さトリックを使わずに適切なサイクル検出を行うための組み込みCYCLE句も備わっています。

スプレッドシートからのテストデータの投入

テスト用の階層データを準備するとき、私はCSVとしてエクスポートしたスプレッドシートからよく始めます。データインポート用にCSVをJSONに素早く変換する必要があるときは、toolcraft.app/ja/tools/data/csv-to-jsonを使っています——ブラウザ上で完全に動作するのでデータが外部に出ることはありません。一度しか使わない変換スクリプトをわざわざ書くより、はるかに速いです。

さらに発展させるために

再帰CTEは、データベースへの複数回のラウンドトリップやアプリケーションコードでのツリーロジックの展開が必要になる場面のために作られています。形は一貫しています:開始ノードを選ぶアンカーと、一度に1階層ずつ進む再帰メンバー——子孫を取得するために下向きに、祖先を収集するために上向きに。

ここで紹介した2つの例は両方向をカバーしています。カテゴリツリーの走査は下向き、権限の継承は上向きです。このコアパターンを身につければ、ほとんどの階層問題は「どちらの方向に走査するか?」に帰着します。

読み取りパフォーマンスをさらにスケールさせる必要がある場合は、クロージャーテーブルパターンを知っておく価値があります。これはすべての祖先・子孫ペアを別テーブルに事前にマテリアライズし、書き込みオーバーヘッドをO(1)の階層読み取りと引き換えにします——ツリーが数万ノードに達し、クエリ負荷が高くなったときに有効です。

Share: