ノード検索の特徴
FFモデルのノード検索における最大の特徴は、次の2点です。
- JOIN テーブルを使わずに検索クエリが記述できる。
- 総ての検索クエリで、効果的な index を参照できる。
下図のツリー構造データを例にして説明します。
DEPTH|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
祖先ノード系の検索
この記事では、祖先ノード系の検索クエリについて紹介します。
1. 祖先ノードの検索
ノード[F] の祖先ノードを取得するクエリを考えてみます。以下の条件を満たすものが、[F]の祖先ノードになります。
- [F]の深度2 より上の深度である。 (ff_depth < 2)
- [F]の序列5 より左にあるノード。 (ff_queue < 5)
- 深度ごとに一番右にあるノード。
(MAX(ff_queue), GROUP BY ff_depth)
「[F]の深度2より上の深度」と「[F]の序列5 より左にあるノード」の条件は、以下の WHERE 句で指定できます。
WHERE ff_queue < 5 AND ff_depth < 2
「深度ごとに一番右にあるノード」は、以下の手順で取得します。
- ff_depth でグループ化を行い、各グループ内で最大の ff_queue を取得。
- 最大の ff_queue と一致する ff_queue を持つノードを取得する
まとめると、以下のクエリになります。
[F]の祖先ノード
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5 AND ff_depth < 2
GROUP BY ff_depth
)
;
2. 親ノードの検索
祖先ノードの検索クエリで WHERE 句の条件を少し修正すると、親ノードを検索するクエリが得られます。
[F]の親ノード
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5 AND ff_depth = (2 - 1)
GROUP BY ff_depth
)
;
サブクエリ内の ff_depth < 2が ff_depth = (2 - 1) に変わっただけです。(2 - 1) は、「基点となるノード[F]の深度2よりひとつ上の深度」を指定するための値です。
3. 根ノードの検索
親ノードの時と同じく、祖先ノードの検索クエリを少し修正するだけで得られます。
[F]の根ノード
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5 AND ff_depth = 0
GROUP BY ff_depth
)
;
4. 祖父母ノードの検索
親ノードと根ノードの例では、祖先ノードを取得するサブクエリの WHERE 句で ff_depth の条件を変えるだけで実現していました。祖父母ノードや曽祖父母ノードを取得するクエリも、同じ発想で記述できます。
[F]の祖父母ノード
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5 AND ff_depth = 2 - 2
GROUP BY ff_depth
)
;
[H]の曽祖父母ノード
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 7 AND ff_depth = 3 - 3
GROUP BY ff_depth
)
;
5. 祖先ノードを得るクエリの一般化
基点ノードの序列を QQ、深度を DD としたとき、n 代上の祖先ノードを得るクエリは次のように一般化されます。
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < QQ AND ff_depth = DD - n
GROUP BY ff_depth
)
;
6. 範囲指定による祖先ノードの検索
全祖先ノードを取得するクエリに WHERE 句に条件をひとつ追加すると、指定した範囲の祖先ノードが取得できます。
[H] の 2 代上までの祖先ノードを取得するクエリは、次のようになります。 AND ff_depth >= 3 - 2 が、追加された条件です。
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 7 AND ff_depth < 3
AND ff_depth >= 3 - 2
GROUP BY ff_depth
)
;