経路列挙モデルにておいて、各ノードと、その子孫となる末端ノードを紐付けたい

Question

今、経路列挙モデルでツリー構造を管理しているテーブルがあるのですが、この各ノードに対して、それに紐づく末端のノードを取得する方法を考えています。
一応、末端の子孫ノードは抽出できているものの、時間がかかりすぎるので効率化したいのですが、お知恵を貸していただけないでしょうか。

モデルのイメージは以下の様な感じです。

-- 経路列挙モデルを採用しているテーブル
select node_id, node_path from t_node

 node_id | node_path
---------+-----------
       1 | 1
       2 | 2
       3 | 1-3
       4 | 1-3-4
       5 | 2-5
       6 | 2-5-6
       7 | 2-5-6-7
       8 | 2-8
       9 | 1-3-9
      10 | 1-3-9-10

-- view_last_node は末端ノードを抽出するビューです
select node_id, node_path from view_last_node

 node_id | node_path
---------+-----------
       4 | 1-3-4
       7 | 2-5-6-7
       8 | 2-8
      10 | 1-3-9-10

ここで今、以下の様なSQLで紐づくノードを抽出しています。マテリアライズド・ビューとしているのですが、現状1万5千レコードほどでもリフレッシュに1分以上かかっています。
node_idはプライマリキーで、node_pathにもインデックスは貼っています。

select
    tn.node_id,
    tn.node_path,
    tlast.node_id as last_node,
    tlast.node_path as last_path
from t_node as tn
inner join t_node as tlast on(tlast.node_path like tn.node_path || '%')
where tlast.node_id in(
    select node_id from view_last_node
);

 node_id | node_path | last_node | last_path
---------+-----------+-----------+-------------
       1 | 1         |         4 | 1-3-4
       1 | 1         |        10 | 1-3-9-10
       2 | 2         |         7 | 2-5-6-7
       2 | 2         |         8 | 2-8
       3 | 1-3       |         4 | 1-3-4
       3 | 1-3       |        10 | 1-3-9-10
       4 | 1-3-4     |         4 | 1-3-4
       5 | 2-5       |         7 | 2-5-6-7
       6 | 2-5-6     |         7 | 2-5-6-7
       7 | 2-5-6-7   |         7 | 2-5-6-7
       8 | 2-8       |         8 | 2-8
       9 | 1-3-9     |        10 | 1-3-9-10
      10 | 1-3-9-10  |        10 | 1-3-9-10

ちょっとした事でも構いませんので、何かアドバイスいただければと思います。
よろしくお願い致します。m(_ _)m

Answer 1

select
  tn.node_id
  , tn.node_path
  , tlast.node_id as last_node
  , tlast.node_path as last_path 
from
  t_node as tn 
  inner join view_last_node as tlast 
    on (tlast.node_path like tn.node_path || '%'); 

これで少しは早くなるかもしれません。

後は実行計画を見て遅くなっている原因を探しましょう。
また、likeでインデックスを使うにはロケールが関係しているので確認してみてください。
テキスト検索の方法とインデックス — Let's Postgres

Comments

[gittib_gittib]

回答ありがとうございます。
わずかに速くなりましたが、やはり1%程です。
like検索ですが、explainで確認する限り、インデックスはちゃんと使われていると思います。

Answer 2

Fettile Forest モデルという、素晴らしいモデルを見つけたので、そちらを共有して自己解決とさせていただきます。
実際に検証はしていませんが、この方法ならば副問い合わせのSQLたった1文で末端ノードを検出できます。

Answer 3

view_last_node も、マテリアライズドビューでしょうか？？

Comments

[gittib_gittib]

view_last_node は通常のビューですが、SQL全体からすると1%にも満たない程度のコストしか掛かっていないため、マテリアライズド・ビューにしてもほとんど改善は見込めないと思っています。
回答ありがとうございます。