LoginSignup
18
13

More than 3 years have passed since last update.

@bubu_sukeinSumally Inc.

今更SQL 再帰クエリ！～ナイーブツリーはアンチパターンなのか～

Last updated at Posted at 2020-09-04

再帰関数ってコーディングするとなんかかっこよくないですか？
実はSQLでも再帰があります。
今日は再帰クエリをご紹介します。

※少なくとも以下のRDBMSの最新バージョンは再帰クエリに対応しています。
　PostgreSQL, Oracle, SQL Server, MySQL(8.0～), SQLite

※この記事で記載するSQLはすべてPostgreSQLで動くものです。

再帰クエリとは

百聞は一見に如かず。

まずはデータ準備

init.sql
--ファイルか、フォルダの情報を格納するテーブル
CREATE TABLE object_tree (
    id              numeric(10)
,   name            varchar(25)
,   is_directory    boolean
,   parent_id       numeric(10)
,   CONSTRAINT pk_object_tree PRIMARY KEY (id)
);
--データ投入
INSERT INTO object_tree (id, name, is_directory, parent_id)
VALUES
    (1,  'root',        true, null)
,   (2,  'sub1',        true,  1)
,   (3,  'file1.txt',   false, 1)
,   (4,  'sub2',        true,  1)
,   (5,  'sub3',        true,  1)
,   (6,  'sub1a',       true,  2)
,   (7,  'sub1b',       true,  2)
,   (8,  'sub2a',       true,  4)
,   (9,  'sub3a',       true,  5)
,   (10, 'file2.txt',   false, 8)
;

そして、再帰クエリでデータ取得

下のようにパスの構造がわからなかったデータ構造から、
「何階層目にあるか」と「絶対パス」が明らかになりました。
image.png

rec_select.sql
--PoestgreSQLの場合
WITH RECURSIVE rec AS (
    -- 再帰のスタート地点
    SELECT
        ot.id           AS id
    ,   ot.name         AS name
    ,   ot.is_directory AS is_directory
    ,   ot.parent_id    AS parent_id
    ,   1               AS layer
    ,   '/' || ot.name  AS full_path
    FROM
        object_tree AS ot
    WHERE
        ot.parent_id IS NULL --一番上の階層を取得する条件
    UNION ALL
    -- 再帰でグルグル増えていく箇所
    SELECT
        ot.id                           AS id
    ,   ot.name                         AS name
    ,   ot.is_directory                 AS is_directory
    ,   ot.parent_id                    AS parent_id
    ,   rec.layer+1                     AS layer
    ,   rec.full_path || '/' || ot.name AS full_path
    FROM
        rec -- 自分自身のWITH句にobject_treeをくっつける
    INNER JOIN
        object_tree AS ot
    ON
        ot.parent_id = rec.id
    )
SELECT
    *
FROM
    rec

できましたね。
RECURSIVEのキーワードがいらないなど、RDBMSにより書き方の差は若干ありますが、ほぼ上記のように書けばよいです。

このときにlayer(階層)や、絶対パス(full_path)などのデータを作るとその後の参照に役立ちます。
再帰クエリのイメージを図解してくれてる方 がいます。これでイメージできるかと。
めでたしめでたし。
…ではなく、ここから、この再帰クエリの使いどころをご説明します。

使いどころ

その前に（ナイーブツリーの話）

上記元データとして使用した object_tree のように、自分の親のレコードIDを持つタイプのデータ構造を「自己参照型テーブル構造」だとか「ナイーブツリー」と呼ばれます。この「ナイーブツリー」は SQLアンチパターン の一つとして有名です。

ナイーブツリーは更新は楽というメリットよりも、デメリットが大きいということでアンチパターンとされています。

  • ナイーブツリーのメリット
    • 【UPDATE, INSERTが楽】フォルダの追加や、フォルダ配下のものの移動が楽。
  • ナイーブツリーのデメリット
    • 【SELECTが大変】どこまでも深くできるため、すべての子階層を取得するために、どれだけ結合したらいいかわからない。
    • 【DELETEが大変】ノードを削除（フォルダを削除）する場合、その子階層の特定に数回クエリを投げなきゃダメ。

この、ナイーブツリーというSQLアンチパターンの解決方法として、経路列挙モデル、入れ子集合モデル、閉包テーブルモデルなどあります。
※各モデルの説明は こちらの説明 が非常にわかりやすいです。

ただこの解決方法は、データ構造が直感的でなかったり、UPDATE, INSERTが複雑だったりで、単純にメリットだけあるわけではありません。

そこで再帰クエリ！

今回紹介している再帰クエリ、これはナイーブツリーから経路列挙モデルに変換する手法として使えます。
「ナイーブツリーでデータ更新し、参照は再帰クエリの経路列挙モデルでやる」というのが私のおすすめです。

ただし！

  • 再帰クエリは、データ参照するためのハードルが上がります。クエリを書くのめんどくさいです。
  • 毎回参照のたびにDBに再帰処理させるのも気が引けます。DBに申し訳ない気がします。

なので！
再帰クエリの結果はテーブル（もしくはマテリアライズドビュー）に格納して、簡単に参照することを推奨します。

つまり私は、「ナイーブツリーと経路列挙モデルの2テーブルを持つ」ことがいいと思います。
更新はナイーブツリーモデル、参照は経路列挙モデルが担当します。
ナイーブツリーのテーブル更新後、続けて経路列挙モデルのテーブルを全DELETE/INSERTします。

※経路列挙モデルのテーブルはVIEWで作り、DELETE/INSERT自体不要にするのもよいと思います。そこは各自柔軟に解釈ください。
image.png

これで、「更新が楽なナイーブツリー」と「参照が楽な経路列挙」の各モデルの長所を生かせました。

ここからは、CRUDのケース別のクエリサンプルをご紹介します。
※list_object_treeのDDLとDELETE/INSERTのクエリは末尾に記載します。

insert.sql
-- ノード（フォルダorファイル）を追加（sub1の下に追加）
INSERT INTO object_tree (id, name, is_directory, parent_id) VALUES
    (99, 'hoge.txt',    false, 2)
;
update.sql
-- sub2とその配下をsub3配下に移動
UPDATE object_tree
SET
    parent_id = 5
WHERE
    id = 4
;
-- sub2の名称をsub3xに変更
UPDATE object_tree
SET
    name = 'sub3x'
WHERE
    id = 4
;
delete.sql
--sub1とその配下をすべて削除
-- -- 1. まず配下を削除 
DELETE
FROM object_tree
WHERE
    id IN (
        SELECT childs.id
        FROM
            list_object_tree target
        INNER JOIN
            list_object_tree childs
        ON
            childs.full_path LIKE target.full_path||'/%'
        WHERE
            target.id = 2 --sub1のID
    )
;
-- -- 2. 次にsub1を削除 
DELETE
FROM object_tree
WHERE id = 2
;
select.sql
--sub3とその配下の取得（fullpath指定）
SELECT * FROM list_object_tree lot WHERE lot.full_path = '/root/sub3'
UNION ALL
SELECT * FROM list_object_tree lot WHERE lot.full_path LIKE '/root/sub3/%'
ORDER BY
    full_path
;

--sub3とその配下の取得（id指定）
SELECT * FROM list_object_tree WHERE id = 5 --sub3のID
UNION ALL
SELECT childs.*
FROM
    list_object_tree target
INNER JOIN
    list_object_tree childs
ON
    childs.full_path LIKE target.full_path||'/%'
WHERE
    target.id = 5 --sub3のID
ORDER BY
    full_path
;

-- 最下層のみ取得
SELECT
    *
FROM
    list_object_tree term
WHERE
    NOT EXISTS (
        -- 親IDとして登録されているレコードを除く
        SELECT 'X' FROM list_object_tree parent
        WHERE
            term.id = parent.parent_id
    )
ORDER BY
    term.full_path
;

適用しやすいデータモデル

今回推奨のナイーブと経路列挙の二重持ちですが、「1テーブルのときよりデータ量が2倍」、「DB更新で毎回DELETE/INSERTをする」というのが気になるかと思います。
そうです。若干利用に制限があります。
この二重持ちデータモデルは「データ量が限られており」、「更新頻度が低いエンティティ」に有効です。

具体的には、以下のようなマスタデータのエンティティとよくマッチします。

  • 組織（部署）マスタ
  • 組織（上司、部下）マスタ
  • ファイル、フォルダ階層マスタ
  • 商品分類マスタ

上記のようなエンティティモデルを設計する際はぜひご検討ください。

まとめ

  • 再帰クエリというものがある。再帰クエリ使用時に階層番号や絶対パスをSELECT項目で作ると便利。
  • 再帰クエリは組織やフォルダ階層などの「自己参照型のテーブル」に利用できる。
  • 再帰クエリは毎回書くのはややこしいからテーブルにデータを持っておくと便利（使いやすいデータ構造になる）。
  • ナイーブツリーの構造は再帰クエリがあるからそこまでアンチパターンとは（私は）思わない。

APPENDIX

参考資料

list_object_tree のDDLとDELETE/INSERTのクエリ

ddl.sql
CREATE TABLE list_object_tree (
    id              numeric(10)
,   name            varchar(25)
,   is_directory    boolean
,   parent_id       numeric(10)
,   layer           numeric(3)
,   full_path       text
,   CONSTRAINT pk_list_object_tree PRIMARY KEY (id)
,   CONSTRAINT uk_list_object_tree UNIQUE (full_path) --絶対パスが被ることがないよう設定。
);
delete_insert.sql
--DELETE
DELETE FROM list_object_tree;
--再帰クエリでINSERT
WITH RECURSIVE rec AS (
    -- 再帰のスタート地点
    SELECT
        ot.id           AS id
    ,   ot.name         AS name
    ,   ot.is_directory AS is_directory
    ,   ot.parent_id    AS parent_id
    ,   1               AS layer
    ,   '/' || ot.name ||   AS full_path
    FROM
        object_tree AS ot
    WHERE
        ot.parent_id IS NULL --一番上の改装
    UNION ALL
    -- 再帰でグルグル増えていく箇所
    SELECT
        ot.id                           AS id
    ,   ot.name                         AS name
    ,   ot.is_directory                 AS is_directory
    ,   ot.parent_id                    AS parent_id
    ,   rec.layer+1                     AS layer
    ,   rec.full_path || '/' || ot.name AS full_path
    FROM
        rec -- 自分自身のWITH句にobject_treeをくっつける
    INNER JOIN
        object_tree AS ot
    ON
        ot.parent_id = rec.id
    )
INSERT INTO list_object_tree
SELECT
    *
FROM
    rec
;
18
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
18
13