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は住所だ。住所は何も知らない。

  1. IDが意味を知らなければ、毎回データまでたどって読まなければならない。これがJOINだ。
  2. 10億件で4回のJOINは遅い。
  3. SIDXは、ID自体に意味を整列させて符号化しようとする研究だ。
  4. ビットマスクのAND一回で10億件を1万件に絞れる。JOINゼロ回。
  5. IDがすべてを知る必要はない。候補を絞ればよい。幅は使用統計を見て決める。
  6. 上位ビットに重要な情報があるので、ビットが切り詰められても核心は生き残る。
  7. 自然言語のクエリを一時SIDXに変えられれば、検索はビット演算になる。

IDが住所であることをやめ、知識になる瞬間、 データベースのルールが変わる。