IDがアドレスではなく知識であるとき何が起こるか
アドレスは何も知らない
データベースで李舜臣を見つけるにはIDが必要だ。
Wikidataでは、李舜臣のIDは Q50184 である。
この数字は李舜臣を指す。
しかし文字列 Q50184 自体は何も知らない。
これが人なのか建物なのか知らない。 韓国人なのかフランス国民なのか知らない。 16世紀の人物なのか21世紀の人物なのか知らない。 生きているのか死んでいるのか知らない。
Q50184 はアドレスである。
郵便配達員は封筒の中に何が書かれているか全く知らない。
封筒のアドレスを見て配達するだけだ。
UUIDも同じである。550e8400-e29b-41d4-a716-446655440000。
128ビットの乱数。衝突を避けるためだけのユニーク性——
それが何を指すかについては何も教えてくれない。
過去50年間、データベースIDはこのように機能してきた。 IDはアドレスであり、何かを知るにはそのアドレスをたどってデータを読まなければならない。
たどらなければわからない
なぜこれが問題なのか。
「19世紀生まれのドイツ人男性哲学者」を見つけたいとしよう。
従来のデータベースでは、こうなる:
1. personsテーブルで gender = 'male' をフィルタ
2. nationalitiesテーブルとJOINし country = 'Germany' をフィルタ
3. birth_datesテーブルとJOINし year BETWEEN 1800 AND 1899 をフィルタ
4. occupationsテーブルとJOINし occupation = 'philosopher' をフィルタ
4回のJOIN操作。 各JOINは2つのテーブルの行を比較する。 テーブルが大きければインデックスを走査し、インデックスがなければフルスキャンを実行する。 10億レコードの場合、このプロセスは数秒から数十秒かかる。
なぜこんなに複雑なのか。
IDが何も知らないからだ。
Q50184 を見ても、これがドイツ人か韓国人か判断できないから、
別のテーブルに行ってその情報を取得しなければならない。
あらゆる質問に対して、IDが指す先をたどらなければならない。 これがデータベースが50年間払い続けてきたコストである。
もしID自体が知っていたら?
前提を逆転させよう。
もしID自体が本質的な情報を含んでいたら?
IDを見るだけで、 それが人間を指すのか、どの国の出身か、 どの時代に属するか、どう分類されるかがわかったら?
「19世紀ドイツ人男性哲学者」を見つけるのに、 JOINは不要になる。
10億のIDをスキャンして、 ビットを調べるだけで各IDがマッチするか即座に判断できる。
これが意味整列インデックスの核心的アイデアである。
意味をIDに整列させる
SIDX(Semantically-Aligned Index)は、こうしたIDを作るための研究だ。 GEULの文法には、SIDXで対象を指すReferenceの場所(GEUL-SIDX)がすでにある。 しかし幅と割り当て方はまだ決めていない。使用統計を積み上げて決める。 以下では説明のため64ビットを例にとる。
SIDXのビットはランダムな数ではない。 ビットの位置に意味が割り当てられる。
上位ビットには最も重要な情報が入る。 これはどんな種類の実体か。人間か、場所か、出来事か、概念か。
次のビットには分類情報が入る。 人間なら、どの時代の人間か、どの地域の人間か。
下位ビットへ行くほど具体的な情報が入る。
核心はこれだ:
ビットの順序が情報の重要度の順序である。
最も根本的な分類が最上位に、 最も細かな区別が最下位に。
これは単なる整列ではない。 設計哲学だ。
10億から1万へ、ワンパスで
SIDXの実用的な威力は数字に表れる。
10億個の実体があり、それぞれのSIDXが64ビットだとしよう。 総容量:10億 × 8バイト = 8GB。
この8GBはメモリに丸ごと載る。
「人間であり東アジア出身の実体」を探したい。 上位ビットに「人間」の印と「東アジア」のコードがあれば、 ビットマスク一つで絞り込める。
mask = 0xFF00_0000_0000_0000 (上位8ビット:タイプ+地域)
target = 0x8100_0000_0000_0000 (人間+東アジア)
for each sidx in 10億個:
if (sidx & mask) == target:
候補に追加
この演算はSIMDで並列化できる。 限界は演算ではなくメモリ帯域だ。 SILKの事前測定では、128ビットの署名1億個(1.6GB)をマスクでスキャンするのに、Go 8スレッドで約27ミリ秒かかった。 同じ割合なら、64ビットのSIDX 10億個(8GB)は0.1秒あまりだ。
10億件が1万件に絞られる。 1万件から詳細に絞り込むのは一瞬だ。
JOINゼロ回。 インデックスツリー探索ゼロ回。 ビットANDを一回するだけ。
幅はどれだけあるべきか
はじめは、もっと大きな空間が必要だと思っていた。
32バイト(256ビット)。32次元のFP16ベクトル。 実体の主要な属性をすべてIDに詰め込もうとした。 人間かどうか、性別、国籍、時代、職業、地域、生死、分類経路……
しかし気づいたことがある。
IDがすべてを知る必要はない。
10億件を1万件に絞れればよい。 残りは精密確認が受け持つ。
これは検問所のようなものだ。 高速道路の料金所でナンバープレートを見て 「この車は京畿道方面」と判断するのに、 車内に何が積まれているかを知る必要はない。
それなら64ビットで足りるかもしれない。 上位ビットでタイプと大分類を、 下位ビットで細分類を押さえれば、 10億件を1万件に絞るには余裕がありそうだ。 64ビット = 16ビットのワード4つ。ストリームの中でも軽い。
しかしこれはまだ仮説だ。 GEULは幅を机上で決めない。 4 WORD(64ビット)や16 WORDなどの候補を置き、実際の使用統計を見て決める。 決まるまでは順番に番号を振るIDで対象を指し、 SIDXを割り当てたあとで二つのIDを同じ対象として結ぶ。
グレースフルデグラデーション:ビットが切り詰められても意味は生き残る
意味整列のもう一つの強みはそのデグラデーション特性である。
SIDXのビットは重要度の高い順に並んでいるため、 下位ビットが損傷したり切り詰められたりしても、 上位ビットの核心情報は保存される。
完全な64ビット: "李舜臣、16世紀朝鮮の海軍将領"
48ビット: "16世紀朝鮮の軍人"
32ビット: "16世紀東アジアの人間"
16ビット: "人間"
8ビット: "物理的エンティティ"
情報が切り詰められるにつれ具体性は失われるが、 最も基本的な分類は最後まで残る。
これは「グレースフルデグラデーション」原則のビットレベルの実装である。
ネットワークの中断で部分的なデータしか届かなくても、 システムは「正確に誰かはわからないが、少なくとも人間についての話だ」とわかり、 推論を続けることができる。
ぼやけた輪郭は完全な沈黙よりましだ。 部分的な理解は完全な失敗よりましだ。
クエリがIDになる
意味整列インデックスが開く、最も興味深い可能性がある。
自然言語のクエリを一時的なSIDXに変えられるとしたら?
ユーザーが尋ねる:「壬辰倭乱で日本軍を破った将軍は誰?」
エンコーダがこの質問を分析する。 人間だ。東アジアだ。16世紀だ。軍事関連だ。 これらの属性をビットに組み立てると、一時的なSIDXが一つできる。
この一時SIDXで10億個のSIDXをスキャンする。 ビットパターンが最も似ている実体が候補に上がる。 李舜臣、元均、権慄、李億祺……
ここで詳細情報を照合すれば最終的な答えが出る。
検索と実体リンキング(entity linking)が一つの仕組みになりうる。 別途の検索エンジンも、 別途のNER(固有表現認識)パイプラインもなしに、 SIDXの比較一回で。
なぜBツリーではないのか?
伝統的なデータベースはBツリーインデックスを使う。
Bツリーは、整列されたデータから特定の値をO(log n)で見つけるのに優れている。 「Q50184を探せ」には最適だ。
しかし「人間であり東アジア出身のすべての実体を探せ」には弱い。 複合条件の検索には複数のインデックスを交差させる必要があり、 その交差コストはデータ規模に応じて急増する。
SIDX + SIMDの全件走査は別のアプローチだ。
Bツリーが「この住所に住んでいるのは誰か」をすばやく引く電話帳なら、 SIDXスキャンは「こんな特徴を持つのは誰か」をすばやく探すプロファイリングだ。
問いの種類が違い、だから最適なデータ構造も違う。
| 問いの種類 | Bツリー | SIDXスキャン |
|---|---|---|
| 特定IDの照会 | O(log n)、最適 | 不要(ハッシュで解決) |
| 複合条件の絞り込み | JOINが必要、遅い | ビットAND一回、速い |
| 類似実体の検索 | 不可能 | ビット類似度で可能 |
| 挿入 | O(log n)、リバランス | O(1)、追記 |
| 実装の複雑さ | 高い | 低い |
両者は競争ではなく分担だ。 いまSILKは、整列したランと二分探索で「述語がP106で目的語がQ169470の文書」のような正確な質問に答えている。 ビット署名のスキャンは、その手前で候補をふるう一次フィルタとして、次の段階に計画されている。
単純で、愚直で、速い。
ハフマンの知恵
SIDXのビット割り当てはハフマン符号の原理に従う。
ハフマン符号では、よく現れる記号に短い符号を、 まれな記号に長い符号を割り当てる。
SIDXでは、最もよく必要になる分類情報に上位ビットを、 まれにしか要らない詳細に下位ビットを割り当てる。
GEUL文法のCodec割り当ても同じ原理だ。 頻度が確認された形式はTAG WORD内の短い直接コードを受け取り、 まれな形式は拡張TAGが付くIssuer形式に回る。
ハフマンの知恵がこの設計全体を貫いている。 最もよく使うものに、最も少ないコストを。
まとめ
伝統的なIDは住所だ。住所は何も知らない。
- IDが意味を知らなければ、毎回データまでたどって読まなければならない。これがJOINだ。
- 10億件で4回のJOINは遅い。
- SIDXは、ID自体に意味を整列させて符号化しようとする研究だ。
- ビットマスクのAND一回で10億件を1万件に絞れる。JOINゼロ回。
- IDがすべてを知る必要はない。候補を絞ればよい。幅は使用統計を見て決める。
- 上位ビットに重要な情報があるので、ビットが切り詰められても核心は生き残る。
- 自然言語のクエリを一時SIDXに変えられれば、検索はビット演算になる。
IDが住所であることをやめ、知識になる瞬間、 データベースのルールが変わる。