入れ子集合モデルで子供データを取得する際のパフォーマンス
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を使用して、クエリを最適化する
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と比較すると桁違いに遅いことが分かります。
