SQL: ナイーブツリーと再帰クエリ

今回は「SQLアンチパターン」の中で紹介されているナイーブツリーというアンチパターンについて見てみることにする。

www.oreilly.co.jp

使った環境は次の通り。

$ sw_vers 
ProductName:    Mac OS X
ProductVersion: 10.11.4
BuildVersion:   15E65
$ mysql --version
mysql  Ver 14.14 Distrib 5.7.12, for osx10.11 (x86_64) using  EditLine wrapper
$ sqlite3 --version
3.8.10.2 2015-05-20 18:17:19 2ef4f3a5b1d1d0c4338f8243d40a2452cc1f7fe4

ナイーブツリーとは

リレーショナル・データベースで再帰的な構造を表現したいときに発生しうるアンチパターン。例えば木構造などがその代表。このとき、その構造をそのままスキーマに落としこむと外部キーで自身を参照するテーブルを作ることになる。しかし、それをやってしまうとデータを入れるときは良いとしても取り出すときに困ったことになる。

このアンチパターンは RDBMS が再帰クエリをサポートしていると発生しない。しかし、再帰クエリをサポートしていない RDBMS もあるので、そのときは注意が必要になる。

今回は再帰クエリをサポートしていない MySQL でナイーブツリーがどう困ったことになるのかをまず見ておく。その上で再帰クエリをサポートしている SQLite ではアンチパターンが発生しないことも確認する。

題材としてはブログのコメントを表現するテーブルにする。コメントは親子関係を持っていて、あるコメントには複数の子のコメントがつく。

下準備

まずは MySQL をインストールする。今回は Mac OS X を使ったので Homebrew で入れる。

$ brew install mysql

MySQL を起動する。

$ mysql.server start
Starting MySQL
. SUCCESS!

MySQL に接続したら動作確認用のデータベースを用意する。

$ mysql -u root
mysql> CREATE DATABASE IF NOT EXISTS naivetree;
Query OK, 1 row affected, 1 warning (0.00 sec)

使用するデータベースを作ったものに切り替える。

mysql> use naivetree;
Database changed

題材とするテーブルは次の通り。 comments テーブルは parent_id カラムを外部キーとして自身を参照することになっている。

mysql> CREATE TABLE comments (
    -> id INTEGER NOT NULL, 
    -> parent_id INTEGER, 
    -> message TEXT NOT NULL, 
    -> PRIMARY KEY (id), 
    -> FOREIGN KEY(parent_id) REFERENCES comments (id)
    -> );
Query OK, 0 rows affected (0.01 sec)

こんなシンプルな構造になっている。

mysql> DESC comments;
+-----------+---------+------+-----+---------+-------+
| Field     | Type    | Null | Key | Default | Extra |
+-----------+---------+------+-----+---------+-------+
| id        | int(11) | NO   | PRI | NULL    |       |
| parent_id | int(11) | YES  | MUL | NULL    |       |
| message   | text    | NO   |     | NULL    |       |
+-----------+---------+------+-----+---------+-------+
3 rows in set (0.01 sec)

テスト用のデータを投入する。コメント id=1 はコメント id=2 と id=4 の子を持っている。そしてコメント id=2 はコメント id=3 を子に持っている。

mysql> INSERT INTO comments (id, parent_id, message) VALUES (1, null, 'ガルパンはいいぞ');
Query OK, 1 row affected (0.01 sec)

mysql> INSERT INTO comments (id, parent_id, message) VALUES (2, 1, 'それな');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO comments (id, parent_id, message) VALUES (3, 2, 'パンツァー・フォー！');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO comments (id, parent_id, message) VALUES (4, 1, 'さおりんは天使');
Query OK, 1 row affected (0.01 sec)

これで準備が整った。

アプリケーション側で再帰する

例えばコメント id=1 の子をすべて取得したいときを考えてみる。

この構造で考えられるひとつのやり方はアプリケーション側で構造を再帰的に辿るというもの。しかし、これはコメントの数が増えるごとに線形にクエリの発行数が増えるためスケールしない。あきらかにダメなアプローチ。

mysql> SELECT *
    -> FROM comments
    -> WHERE id = 1;
+----+-----------+--------------------------+
| id | parent_id | message                  |
+----+-----------+--------------------------+
|  1 |      NULL | ガルパンはいいぞ         |
+----+-----------+--------------------------+
1 row in set (0.00 sec)

mysql> SELECT *
    -> FROM comments
    -> WHERE parent_id = 1;
+----+-----------+-----------------------+
| id | parent_id | message               |
+----+-----------+-----------------------+
|  2 |         1 | それな                |
|  4 |         1 | さおりんは天使        |
+----+-----------+-----------------------+
2 rows in set (0.00 sec)

mysql> SELECT *
    -> FROM comments
    -> WHERE parent_id = 2;
+----+-----------+--------------------------------+
| id | parent_id | message                        |
+----+-----------+--------------------------------+
|  3 |         2 | パンツァー・フォー！           |
+----+-----------+--------------------------------+
1 row in set (0.00 sec)

外部結合を使う

コメントの数が増えてもスケールさせるには少なくともクエリ一発で取り出せないといけない。そこで、次に考えられるのが子の parent_id カラムと親の id カラムを外部結合するやり方。しかし、これも階層の数があらかじめ決め打ちになっているときにしか使えない。

例えば次のようにする。ただし、これでは階層が 2 までの構造にしか対応できない。

mysql> SELECT c1.*, c2.*
    -> FROM comments c1
    -> LEFT OUTER JOIN comments c2
    -> ON c2.parent_id = c1.id
    -> WHERE c1.id = 1;
+----+-----------+--------------------------+------+-----------+-----------------------+
| id | parent_id | message                  | id   | parent_id | message               |
+----+-----------+--------------------------+------+-----------+-----------------------+
|  1 |      NULL | ガルパンはいいぞ         |    2 |         1 | それな                |
|  1 |      NULL | ガルパンはいいぞ         |    3 |         1 | さおりんは天使        |
+----+-----------+--------------------------+------+-----------+-----------------------+
2 rows in set (0.00 sec)

さっきのクエリだとテストデータの階層には足りないから、次は 3 に増やして...ってこれは無理だね。

mysql> SELECT c1.*, c2.*, c3.*
    -> FROM comments c1
    -> LEFT OUTER JOIN comments c2
    -> ON c2.parent_id = c1.id
    -> LEFT OUTER JOIN comments c3
    -> ON c3.parent_id = c2.id
    -> WHERE c1.id = 1;
+----+-----------+--------------------------+------+-----------+-----------------------+------+-----------+--------------------------------+
| id | parent_id | message                  | id   | parent_id | message               | id   | parent_id | message                        |
+----+-----------+--------------------------+------+-----------+-----------------------+------+-----------+--------------------------------+
|  1 |      NULL | ガルパンはいいぞ         |    2 |         1 | それな                |    3 |         2 | パンツァー・フォー！           |
|  1 |      NULL | ガルパンはいいぞ         |    4 |         1 | さおりんは天使        | NULL |      NULL | NULL                           |
+----+-----------+--------------------------+------+-----------+-----------------------+------+-----------+--------------------------------+
2 rows in set (0.01 sec)

こんな感じでナイーブツリーを作ってしまうとデータを取り出すときに苦労する。

再帰クエリ (WITH RECURSIVE) を使う

ナイーブツリーを作っても問題ないのは使う RDBMS が再帰クエリをサポートしているとき。再帰クエリを使うと、その名の通り再帰的な構造を辿ることができる。

例えば再帰クエリをサポートしている SQLite を試してみよう。 SQLite は Mac OS X であれば最初から使えるはず？

$ sqlite3 naivetree.db

テーブルを作る。

sqlite> CREATE TABLE comments (
   ...> id INTEGER NOT NULL,
   ...> parent_id INTEGER,
   ...> message TEXT NOT NULL,
   ...> PRIMARY KEY (id),
   ...> FOREIGN KEY(parent_id) REFERENCES comments (id)
   ...> );

テストデータを投入する。

sqlite> INSERT INTO comments (id, parent_id, message) VALUES (1, null, 'ガルパンはいいぞ');
sqlite> INSERT INTO comments (id, parent_id, message) VALUES (2, 1, 'それな');
sqlite> INSERT INTO comments (id, parent_id, message) VALUES (3, 2, 'パンツァー・フォー！');
sqlite> INSERT INTO comments (id, parent_id, message) VALUES (4, 1, 'さおりんは天使');

見やすいようにラインモードにする。

sqlite> .mode line

再帰クエリ (WITH RECURSIVE) を使ってコメント id=1 に連なるコメントを取得してみる。

sqlite> WITH RECURSIVE r AS (
   ...> SELECT * FROM comments WHERE id = 1
   ...> UNION ALL
   ...> SELECT comments.* FROM comments, r WHERE comments.parent_id = r.id
   ...> )
   ...> SELECT * FROM r;
       id = 1
parent_id =
  message = ガルパンはいいぞ

       id = 4
parent_id = 1
  message = さおりんは天使

       id = 2
parent_id = 1
  message = それな

       id = 3
parent_id = 2
  message = パンツァー・フォー！

ばっちり。

例えば id=2 のときはこんなかんじ。

sqlite> WITH RECURSIVE r AS (
   ...> SELECT * FROM comments WHERE id = 2
   ...> UNION ALL
   ...> SELECT comments.* FROM comments, r WHERE comments.parent_id = r.id
   ...> )
   ...> SELECT * FROM r;
       id = 2
parent_id = 1
  message = それな

       id = 3
parent_id = 2
  message = パンツァー・フォー！

すばらしい。

まとめ

今回は再帰的な構造をリレーショナル・データベースで表現するときに作ってしまいがちなアンチパターンのナイーブツリーについて書いた。再帰クエリをサポートしていない RDBMS でナイーブツリーを作りこんでしまうと、なかなか難儀なことになる。そしてメジャーな RDBMS の中でも MySQL が再帰クエリをサポートしていないことがとても悩ましい。

再帰的な構造を表現するのに、再帰クエリをサポートしていない RDBMS では次のような解決策がある。