はじめに

PostgreSQLでツリー状の階層をもつ検索をしたい案件があったので、ltreeを使ってみた。

ltreeとは

ltreeというのは(たぶん)Label-Treeの略なんだろうなあ。
名前のとおり、ラベルとピリオドを使って階層を模擬したデータ表現用のデータ型。
作者は全文検索やJSONBなどを開発したTeodor Sigaev = サンと (teodor@stack.net)とOleg Bartunov = サン (oleg@sai.msu.su)。
結構昔から存在するモジュールでPostgreSQL 8.3のころから存在している。
contribモジュールなので、PostgreSQLコミュニティがサポートしているというのも重要。

使ってみよう

contribモジュールなのでビルド手順とかは割愛。RPMインストールするなら、contribパッケージを入れればOK。

ltreeはデータ型とそれを操作するための関数/演算子のパッケージなので、使いたいデータベースに対してCREATE EXTENSIONで拡張をインストールしておく。

基本的には

ラベル.ラベル. ・・・ .ラベル

のような書式でltreeのデータを記述する。ピリオドが階層の区切りを示す。
残念ながらラベルに使用できるのは、アルファベット文字とアンダースコアのみ。日本語のラベルは使えないもよう。

なお、今回の検証はPostgreSQL 9.6を使用した。

サンプル：町田は神奈川

サンプルデータ

以下のように、ltree型のdataという列に、都道府県---市 or 郡 or 区---区 or 町 or 村のような階層をもつデータを登録しておく。

map=# \d map
     Table "public.map"
 Column | Type  | Modifiers 
--------+-------+-----------
 data   | ltree |

map=# SELECT data FROM map ORDER BY data;
               data               
----------------------------------
 Kanagawa
 Kanagawa.Kawasaki
 Kanagawa.Kawasaki.Kawasaki
 Kanagawa.Kawasaki.Sachi
 Kanagawa.Kawasaki.Tama
 Kanagawa.Machida
 Kanagawa.Minamiashigara
 Kanagawa.Minamiashigara.Hakone
 Kanagawa.Minamiashigara.Yugawara
 Kanagawa.Sagamihara
 Kanagawa.Sagamihara.Chuuou
 Kanagawa.Sagamihara.Machida
 Kanagawa.Sagamihara.Midori
 Kanagawa.Sagamihara.Minami
 Kanagawa.Yamato
 Kanagawa.Yokohama
 Kanagawa.Yokohama.Aoba
 Kanagawa.Yokohama.Kouhoku
 Kanagawa.Yokohama.Midori
 Kanagawa.Yokohama.Minami
 Kanagawa.Yokohama.Nishi
 Kanagawa.Yokohama.Tsurumi
 Kanagawa.Yokosuka
 Tokyo
 Tokyo.Machida
 Tokyo.Minato
 Tokyo.Ohta
 Tokyo.Shinagawa
 Tokyo.Tachikawa
(29 rows)

このdata列に対して、ltreeで提供している関数/演算子を使ってみる。

ある階層のラベルを指定する

ltreeでは、~という演算子と、正規表現っぽい記法で条件を記述できる。
まず、例としてYokohamaに包含される情報を検索してみる。

map=# SELECT data FROM map WHERE data ~ '*.Yokohama.*';
           data            
---------------------------
 Kanagawa.Yokohama
 Kanagawa.Yokohama.Nishi
 Kanagawa.Yokohama.Minami
 Kanagawa.Yokohama.Tsurumi
 Kanagawa.Yokohama.Kouhoku
 Kanagawa.Yokohama.Aoba
 Kanagawa.Yokohama.Midori
(7 rows)

Kanagawaにすれば他の市町村も対象に入る。

map=# SELECT data FROM map WHERE data ~ '*.Kanagawa.*';
               data               
----------------------------------
 Kanagawa
 Kanagawa.Yokohama
 Kanagawa.Yokohama.Nishi
 Kanagawa.Yokohama.Minami
 Kanagawa.Yokohama.Tsurumi
 Kanagawa.Yokohama.Kouhoku
 Kanagawa.Yokohama.Aoba
 Kanagawa.Yokohama.Midori
 Kanagawa.Kawasaki
 Kanagawa.Kawasaki.Sachi
 Kanagawa.Kawasaki.Kawasaki
 Kanagawa.Kawasaki.Tama
 Kanagawa.Sagamihara
 Kanagawa.Sagamihara.Chuuou
 Kanagawa.Sagamihara.Minami
 Kanagawa.Sagamihara.Midori
 Kanagawa.Sagamihara.Machida
 Kanagawa.Yokosuka
 Kanagawa.Yamato
 Kanagawa.Minamiashigara
 Kanagawa.Minamiashigara.Hakone
 Kanagawa.Minamiashigara.Yugawara
 Kanagawa.Machida
(23 rows)

末端の区名(Midori)を指定。

map=# SELECT data FROM map WHERE data ~ '*.Midori';
            data            
----------------------------
 Kanagawa.Yokohama.Midori
 Kanagawa.Sagamihara.Midori
(2 rows)

注：緑区は横浜市にも相模原市にもある。

なので、末端が'Machida'の情報を検索すると

map=# SELECT data FROM map WHERE data ~ '*.Machida';
            data             
-----------------------------
 Tokyo.Machida
 Kanagawa.Sagamihara.Machida
 Kanagawa.Machida
(3 rows)

こーなるｗ
（町田は神奈川派の人と、町田は相模原市町田区説を唱える相模原主義者がいるらしい）

subpathとnlevel

subpath関数はltreeから特定の階層を抜き出す関数である。
第2引数にはどのレベルから階層を抜き出すか(階層は0相対で指定)、また第3引数には抜き出す階層数を設定する。第3引数のデフォルト値は終端まで抜き出す。
上記のMachida検索の例にsubpathを追加する。

map=# SELECT subpath(data,1) FROM map WHERE data ~ '*.Machida';
      subpath       
--------------------
 Machida
 Sagamihara.Machida
 Machida
(3 rows)

map=# SELECT subpath(data,1,1) FROM map WHERE data ~ '*.Machida';
  subpath   
------------
 Sagamihara
 Machida
 Machida
(3 rows)

subpathの第2引数に負数を指定すると末端から探す。
例えば、Yokohamaに包含される末端のラベルを表示させたい場合は、こんな感じで記述する。

map=# SELECT subpath(data,-1) FROM map WHERE data ~ '*.Yokohama.*';
 subpath  
----------
 Yokohama
 Nishi
 Minami
 Tsurumi
 Kouhoku
 Aoba
 Midori
(7 rows)

nlevelというのはltree型データの階層数を返却する。

map=# SELECT data,nlevel(data) FROM map WHERE data ~ 'Kanagawa.*';
               data               | nlevel 
----------------------------------+--------
 Kanagawa                         |      1
 Kanagawa.Yokohama                |      2
 Kanagawa.Yokohama.Nishi          |      3
 Kanagawa.Yokohama.Minami         |      3
 Kanagawa.Yokohama.Tsurumi        |      3
 Kanagawa.Yokohama.Kouhoku        |      3
 Kanagawa.Yokohama.Aoba           |      3
 Kanagawa.Yokohama.Midori         |      3
 Kanagawa.Kawasaki                |      2
 Kanagawa.Kawasaki.Sachi          |      3
 Kanagawa.Kawasaki.Kawasaki       |      3
 Kanagawa.Kawasaki.Tama           |      3
 Kanagawa.Sagamihara              |      2
 Kanagawa.Sagamihara.Chuuou       |      3
 Kanagawa.Sagamihara.Minami       |      3
 Kanagawa.Sagamihara.Midori       |      3
 Kanagawa.Sagamihara.Machida      |      3
 Kanagawa.Yokosuka                |      2
 Kanagawa.Yamato                  |      2
 Kanagawa.Minamiashigara          |      2
 Kanagawa.Minamiashigara.Hakone   |      3
 Kanagawa.Minamiashigara.Yugawara |      3
 Kanagawa.Machida                 |      2
(23 rows)

これを組み合わせると、末端の階層情報のみを取り出して、インデントをつけてツリーっぽく表示することもできる。

map=# SELECT repeat('    ', nlevel(data) - 1) || subpath(data,-1,1)::text FROM map ORDER BY data ASC;
      ?column?      
--------------------
 Kanagawa
     Kawasaki
         Kawasaki
         Sachi
         Tama
     Machida
     Minamiashigara
         Hakone
         Yugawara
     Sagamihara
         Chuuou
         Machida
         Midori
         Minami
     Yamato
     Yokohama
         Aoba
         Kouhoku
         Midori
         Minami
         Nishi
         Tsurumi
     Yokosuka
 Tokyo
     Machida
     Minato
     Ohta
     Shinagawa
     Tachikawa
(29 rows)

全階層ラベルを取得

例えば、末端にMachidaを含むltree型データ内の全てのラベルの種類としては

Machida
Kanagawa
Sagamihara
Tokyo

が存在するわけだが、これをltrreが提供している機能だけで取り出すのは意外にもできない(ように思える)。
このために、ltree型のラベルをTEXT型に変換にして、TEXT型の関数を使って展開する必要がある。

map=# SELECT DISTINCT regexp_split_to_table(data::text, '\.') FROM map WHERE data ~ '*.Machida';
 regexp_split_to_table 
-----------------------
 Kanagawa
 Machida
 Sagamihara
 Tokyo
(4 rows)

うーん、これ相当の機能をltreeの関数として追加してもらえないか、提案してみようかなー。

おわりに

ということで、まずはltreeを使った検索をちょいと試してみました。
次回は、大量のltreeデータを登録したときの性能について検証したいと思います。