入れ子集合モデルで子供データを取得する際のパフォーマンス

RDBで階層構造（平たく言うと行同士の親子関係）を表現するために様々なデータモデルが存在します。最もよく使用されていると思われるのは「隣接リストモデル」（子となる行の中で、親となる行のprimary keyやunique idを持っておくことで親子関係を表現するデータモデル）です。
ただし、このモデルでは「N階層以内の親を取得する」「N階層以内の子を取得する」ことは容易ですが、階層数に依存せず再帰的に「全ての祖先を取得する」「全ての子孫を取得する」ことが苦手です。*1

このような欠点を持たないデータモデルとしてここ数年で注目を集めているモデルとして「入れ子集合モデル」があります。

SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル

従来のリレーショナル・データベースで階層データを扱うモデルには、「隣接リストモデル」や「経路列挙モデル」などが知られていますが、これらがデータ構造のイメージがつかみづらく、SQL も複雑で拡張性に乏しいという欠点を持っていたのに対し、直観的に理解しやすく、SQL も大変簡潔に書けるというメリットがあります。

一見いいコトずくめな「入れ子集合モデル」ですが、MySQL上で使用した場合にパフォーマンス上問題になったことが有ったので、メモとして残しておきます。

サンプルデータ

先ずはサンプルデータとして、こんな感じで都道府県を地域ごとに分けて、親子関係を入れ子集合モデルで表したデータを作ります。また、件数を稼ぐためにダミーデータを入れて総計1万行のデータとします。

テーブル

CREATE TABLE `region` (
	`id` INT NOT NULL AUTO_INCREMENT,
	`name` VARCHAR(50) NULL DEFAULT NULL,
	`lft` INT NULL DEFAULT NULL,
	`rgt` INT NULL DEFAULT NULL,
	PRIMARY KEY (`id`),
	INDEX `lft` (`lft`),
	INDEX `rgt` (`rgt`)
)

データ。

id	name	lft	rgt
1	日本	1	113
2	北海道地方	2	5
3	東北地方	6	19
4	関東地方	20	35
5	中部地方	36	55
6	近畿地方	56	71
7	中国地方	72	83
8	四国地方	84	92
9	九州地方	93	108
10	沖縄地方	109	112
11	北海道	3	4
12	青森県	7	8
13	岩手県	9	10
14	宮城県	11	12
15	秋田県	13	14
16	山形県	15	16
17	福島県	17	18
18	茨城県	21	22
19	栃木県	23	24
20	群馬県	25	26
21	埼玉県	27	28
22	千葉県	29	30
23	東京都	31	32
24	神奈川県	33	34
25	新潟県	37	38
26	富山県	39	40
27	石川県	41	42
28	福井県	43	44
29	山梨県	45	46
30	長野県	47	48
31	岐阜県	49	50
32	静岡県	51	52
33	愛知県	53	54
34	三重県	57	58
35	滋賀県	59	60
36	京都府	61	62
37	大阪府	63	64
38	兵庫県	65	66
39	奈良県	67	68
40	和歌山県	69	70
41	鳥取県	73	74
42	島根県	75	76
43	岡山県	77	78
44	広島県	79	80
45	山口県	81	82
46	徳島県	85	86
47	香川県	87	88
48	愛媛県	88	89
49	高知県	90	91
50	福岡県	94	95
51	佐賀県	96	97
52	長崎県	98	99
53	熊本県	100	101
54	大分県	102	103
55	宮崎県	104	105
56	鹿児島県	106	107
57	沖縄県	110	111
58	null	114	115
59	null	116	117
..	..	..	..
10000	null	19998	19999

（ルートとなるデータ「日本」+ 9地域 + 47都道府県が57件。+ダミーデータを含めて1万件となります。
地域区分についてはWikipedia「都道府県/地域順の一覧」を参考としました。また、データのinsert後に統計情報を更新するためanalyze tableを実行しています。）

子孫（子供・孫・ひ孫....）を取得するクエリ

例えば、nameカラムの値が「日本」（id=1, lft=1, rgt=113）の子孫となるデータは下記のように絞り込めます。

SELECT children.*
FROM region AS parents LEFT OUTER JOIN region children
  ON children.lft > parents.lft AND children.lft < parents.rgt
WHERE 
   parents.id=1

これで、地域と都道府県のデータ56件を全て取得することが可能です。
しかし、この条件では都道府県のデータを除いて地域データのみを取得することができません。

直接の子供を取得するクエリが遅い

そこで、「日本」の直接の子供だけを取得するため、ここで挙げられている下記のようなクエリを使用します。

・クエリ1

SELECT children.*
  FROM region as parents
       LEFT OUTER JOIN region children
       ON parents.lft = (SELECT MAX(lft)
                     FROM region
                    WHERE children.lft > lft
                      AND children.lft < rgt)
  WHERE parents.id=1

このクエリを実行すると、「日本」の直接の子どもとなる地域区分のデータだけが取得できます。

実行結果

id	name	lft	rgt
2	北海道地方	2	5
3	東北地方	6	19
4	関東地方	20	35
5	中部地方	36	55
6	近畿地方	56	71
7	中国地方	72	83
8	四国地方	84	92
9	九州地方	93	108
10	沖縄地方	109	112

しかし、このクエリは非常に遅いです。
どんだけ遅いかというと、ローカル環境で測定したクエリ実行時間はこれぐらい*2。

	実行時間(sec.)
1回目	37.596
2回目	37.768
3回目	37.783

総件数1万件のテーブルにしては激しく遅いことが分かります。

EXPLAIN結果

このクエリのEXPLAINを取ってみましょう。
EXPLAIN結果は以下のとおりです。

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	parents	const	PRIMARY	PRIMARY	4	const	1	NULL
1	PRIMARY	children	ALL	NULL	NULL	NULL	NULL	10327	Using where
2	DEPENDENT SUBQUERY	region	ALL	lft,rgt	NULL	NULL	NULL	10327	Range checked for each record (index map: 0x6)

一行目は、"parents.id=1"のとこですね。primary keyへの検索だし、これについてはまあ問題無し。
二行目については自己結合条件（"LEFT OUTER JOIN region children ON ～"）に関するクエリと思われますが、テーブルスキャンが行われてます。rgt, lftカラムへのインデックスは使用されていません。"analyze table"を実行したり、rgt,lftカラムに複合インデックスを追加したりしましたが、どうやってもテーブルスキャンが行われます。
三行目は相関サブクエリ（(SELECT MAX(lft) FROM region）～）以下の部分です。こちらもrgt,lftカラムへのインデックスを使ってくれず、テーブルスキャンです。また、実際には10327件ではなく、「外側部分の取得件数（二行目の検索結果） × 10327件」の評価が行われます。

つまり

• テーブルスキャンが1回実行される（Explain結果の二行目、三行目）
• 一回目のテーブルスキャン集計結果に対して、さらに集計結果 × 10327件分のテーブルスキャンが実行される（Explain結果の三行目）

というかなりヘビーな処理です。

この問題については、ここで挙げられているもう一つのタイプのクエリを使用することで解決します。

・クエリ2

SELECT children.*
FROM region AS parents LEFT OUTER JOIN region children
  ON children.lft > parents.lft AND children.lft < parents.rgt
WHERE 
   parents.id=1
   AND
   NOT EXISTS
  ( SELECT id FROM region AS mid_parents
      WHERE mid_parents.lft BETWEEN parents.lft AND parents.rgt
        AND children.lft BETWEEN mid_parents.lft AND mid_parents.rgt
        AND mid_parents.id NOT IN (children.id, parents.id))

ローカル環境で測定したクエリ実行時間はこれぐらい*3。

	実行時間(sec.)
1回目	0.000
2回目	0.000
3回目	0.000

ミリ秒以下です。

EXPLAIN結果

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	parents	const	PRIMARY	PRIMARY	4	const	1	NULL
1	PRIMARY	children	ALL	lft	NULL	NULL	NULL	55	Using where
2	DEPENDENT SUBQUERY	mid_parents	range	lft,rgt	lft	5	NULL	57	Range checked for each record (index map: 0x6)

二行目、三行目のステップでもインデックスが使用され、さらに集計対象件数が大幅に絞りこまれていることが確認できます。

参考情報

EXPLAIN結果の読み方については以下のページを参考にしました。

MySQL :: MySQL 5.1 リファレンスマニュアル :: 6.2.1 EXPLAINを使用して、クエリを最適化する

漢(オトコ)のコンピュータ道: MySQLのEXPLAINを徹底解説!!

PostgreSQLではどうなの？

クエリ1のEXPLAIN ANALYZE実行結果

Hash Left Join  (cost=280.28..498.72 rows=1 width=22) (actual time=11206.949..11207.157 rows=9 loops=1)
  Hash Cond: (parents.lft = (SubPlan 2))
  ->  Index Scan using id on region parents  (cost=0.29..8.30 rows=1 width=4) (actual time=0.016..0.018 rows=1 loops=1)
        Index Cond: (id = 1)
  ->  Hash  (cost=155.00..155.00 rows=10000 width=22) (actual time=11206.859..11206.859 rows=56 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 4kB
        ->  Seq Scan on region children  (cost=0.00..155.00 rows=10000 width=22) (actual time=0.005..10.161 rows=10000 loops=1)
  SubPlan 2
    ->  Result  (cost=0.41..0.42 rows=1 width=0) (actual time=1.112..1.113 rows=1 loops=10009)
          InitPlan 1 (returns $1)
            ->  Limit  (cost=0.29..0.41 rows=1 width=4) (actual time=1.108..1.108 rows=0 loops=10009)
                  ->  Index Scan Backward using lft on region  (cost=0.29..137.28 rows=1111 width=4) (actual time=1.104..1.104 rows=0 loops=10009)
                        Index Cond: ((lft IS NOT NULL) AND (children.lft > lft))
                        Filter: (children.lft < rgt)
                        Rows Removed by Filter: 4995

クエリ2のEXPLAIN ANALYZE実行結果

Nested Loop Anti Join  (cost=0.86..13103.49 rows=1111 width=22) (actual time=0.045..0.976 rows=9 loops=1)
  ->  Nested Loop Left Join  (cost=0.57..67.92 rows=1111 width=34) (actual time=0.030..0.204 rows=56 loops=1)
        ->  Index Scan using id on region parents  (cost=0.29..8.30 rows=1 width=12) (actual time=0.016..0.017 rows=1 loops=1)
              Index Cond: (id = 1)
        ->  Index Scan using lft on region children  (cost=0.29..48.51 rows=1111 width=22) (actual time=0.009..0.071 rows=56 loops=1)
              Index Cond: ((lft > parents.lft) AND (lft < parents.rgt))
  ->  Index Scan using lft on region mid_parents  (cost=0.29..10.49 rows=123 width=12) (actual time=0.009..0.009 rows=1 loops=56)
        Index Cond: ((lft >= parents.lft) AND (lft <= parents.rgt) AND (children.lft >= lft))
        Filter: ((children.lft <= rgt) AND (id <> ALL (ARRAY[children.id, parents.id])))
        Rows Removed by Filter: 26

・・・・PostgreSQLのEXPLAINはいまいちよく分からない。

	クエリ1実行時間（sec）	クエリ2実行時間（sec）
1回目	11.207	0.001
2回目	11.137	0.001
3回目	11.301	0.001

MySQLほどではないにせよ、やはりクエリ1はクエリ2と比較すると桁違いに遅いことが分かります。

*1:取得する階層に応じてN個のJOINを作る必要が有るため。再帰クエリ構文（http://ja.wikipedia.org/wiki/再帰クエリ）をサポートしているRDBMSであればこの問題は無くなるはず。

*2:HeidiSQL上で取得した値。また、各クエリ実行前にクエリキャッシュの削除を行っている。

*3:HeidiSQL上で取得した値。また、各クエリ実行前にクエリキャッシュの削除を行っている。