2006-12-20

GiST

ぐだぐだと.

以前 RDB の勉強をしていた時に, GiST Generalized Search Tree というのがあることを知った. 名前のとおり RDB のために汎用的な索引付けの枠組みをつくろうという, 10 年近く前のプロジェクト. PostgreSQL にも含まれている ところをみると, そこそこ筋のいいアイデアらしい. (有名なのかも知れないけれどリテラシ不足につき不明.)

RDB の様々なデータ型毎に索引を実装するのは大変だから 一つの枠組みで扱いたいというのが動機にある. "様々な" 型というけれど, 具体的には多角形みたいな幾何データや, N 次元ベクトルみたいな高次のデータ(データマイニングで使うらしい)を想定している. たとえば幾何データの索引づけには R-Tree が よく知られている. R-Tree はストレージ効率のいい空間分割の仲間で, グラフィクス屋さんなら Octree とか Kd-Tree の亜種だと思えばわかりやすいかもしれない. GiST なら B-Tree 向けの型も R-Tree 向けの型も同じ枠組みで扱えるとことになっている.

そもそも索引付けの枠組みというのが想像しづらいかもしれない. そういう人は, Java の TreeSet に対する Comparatorstd::set の 比較ファンクタを思いうかべてほしい. TreeSet や std::set が枠組みで, Comparator やファンクタがその hotspot になる. 自分で定義したクラスのために Comparator#compare() を実装すれば TreeSet を使えるように, あるデータ型に Comparator 相当のものを実装するとその型を RDB で索引づけできるようになる. 実際には 7 種類のメソッド(というか関数)を実装する. (PostgreSQL のマニュアル参照. いくつかはオプションだった気もする.) 索引の木構造をどう辿るかだけ与えれば, あとはフレームワークがよろしくやってくれるというわけ.

索引と正規化

RDB に FTS を繋ぎたい と思っていた私は, GiST の枠組みにうまく乗れないものかと考えた. でも, どうやら無理だということがわかった. FTS は GiST の持っている色々な仮定に反している. たとえば FTS は一つのレコードが複数のインデクスを持っている. しかもそのインデクスはぜんぜん局所性がない. 厳しい.

それがわかった当初は GiST の限界に不満を感じていたのだが, 今はどちらかというと FTS の方こそが変なのだという気がしている. どのへんが変かというと, なんというか, テキストは正規化されていない. 正規化を前提とした RDB に正規化されていないテキストを放り込まれているので, 色々齟齬がおきる.

たぶん形態素解析みたいな字句解析の技術がテキストの正規化にあたるのだと思う. 実際 SQLite の FTS は字句解析後した個々の字句をレコードにした 隠しテーブルを持っている. ただそれはユーザからは見えない. これは全文検索のバックエンドに RDB を使う場合の定石でもある.

またグラフィクスの比喩で考えてみる. (RTR の輪読があったのでそんな気分.) たとえば空間的な問合せに対応した幾何データのデータベースがあるとして, FTS というのは一つのレコードにひとつの幾何データ, たとえば Teapot が入っているようなものだ. データベースは裏でパッチをテセレートし, できた三角形で R-Tree を作る. テセレートが字句解析, 三角形が字句に対応する.

テキスト(や三角形)の不便なところは, まず, 個々の要素だけでは何の役にも立たないこと. 元のデータ(テキスト/メッシュ)以外と relation をつくることはほとんどない. だから正規化をしても RDB の有難味が少い. あとは正規化といいつつその表現が一意に決まらないこと. 字句解析もテセレータもアルゴリズムは色々ある. こういうのは正規化を前提とした RDB には向かない.

逆にいうと, RDB は人間が前もって正規化した, すくなくとも ER みたいにモデル化したデータしか入らないところが不便だとも言る. もっと何も考えずに...というのは言い過ぎにしても, 正規化やモデル化の難しいデータを放りこむと 適当に解析してインデクスができるデータベースがほしい. さすがに任意のバイト列ではどうにもならないから, 画像, 音声のようにドメインをしぼって何とかする. たとえば画像のデータベースを考えるなら, 画像を解析してインデクス可能な要素を抽出する部分が pluggale になっていれば 画像データベースにおける GiST のようなものがつくれる. でも何を plug すればいいのかはわからない. メディア処理方面にはアイデアや研究があるのかもしれない. そういえば Riya はこの路線でうまくやった例なんだろうね.

画像は大変だからもっと素朴なものはないかなーと考えたが, そもそも計算機上で表現されているオブジェクトで構造を持っていないものは あまり多くないことの気付いた. 画像, 音声, 動画くらいしかない. もうちょっと研究よりだとセンサ系からの入力があるか.

結いつかは局画像処理とかデータマイニングを勉強しなきゃいけないのかなあ... などと考えを巡らせているうちに気が遠くなってきました... またそのうち.