転置インデックスを実装しよう

相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。

デモ

モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。

インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。

でも、今回はUIの話ではないのです。ものすごく地味に、全文検索システムの核となる転置インデックスの設計と実装について説明します。最初に設計から入り、インデックスを構築するアルゴリズムとそれに対する検索を行うアルゴリズムを擬似コードで解説します。

概要設計

以前の記事でも述べましたが、テーブルデータベースは、ハッシュデータベースとして主キーとレコード本体のデータを関連付けて管理します。各レコードのデータは、名前と値からなるコラムの集合として記録され、ハッシュ（連想配列）と同様のインターフェイスで操作されます。

コラムインデックスを張れるというのがテーブルデータベースの最大の特徴です。全てのレコードにおける特定の名前のコラムを対象としたインデックスを管理するのです。新規に追加したレコードが該当のコラムを持っている場合や、既存のレコードの該当のコラムが更新された場合には、コラムインデックスも自動的に更新されなければなりません。コラムインデックスはB+木の外部データベースとして実現されます。処理の流れに基づいて整理すると、レコードの追加と削除については以下のデータベース操作が必要となります。

レコードを挿入する（tctdbputkeep）
1. レコード本体をメインのデータベースに挿入する（tchdbput）
2. コラムの値をキー、レコード本体の主キーを値にしたデータをインデックスに挿入する（tcbdbput）

レコードを削除する（tctdbout）
1. レコード本体をメインのデータベースから取得する（tchdbget）
2. コラムの値をキーとして、インデックスからデータを削除する（tcbdbout）
3. レコード本体をメインのデータベースから削除する（tchdbout）

レコードを更新する（tctdbput）
1. レコード本体をメインのデータベースから取得する（tchdbget）
2. 既存のコラムと新しいコラムを比較して異なる場合、上記のインデックス削除操作（tcbdbout）とインデックス挿入操作（tcbdbput）を行う。
3. レコード本体をメインのデータベースに上書きで挿入する（tchdbput）

削除操作の際には既存のレコードを使ってインデックスを元に戻すということと、更新操作の際には削除を行ってから挿入を行うというところがポイントです。MySQLの各種ストレージエンジンでも、CouchDBのストレージエンジンでも、たいていのインデックス付きストレージは上記の枠組みを踏襲しているはずです。

インデックスの型による実装の分岐

文字列型や数値型といった、比較によって探索範囲を絞り込むような操作はツリー系のインデックスで高速化することができるので、実装としてB+木データベースをそのまま使えばよいでしょう。コラムの値をキーにして、該当レコードをメインデータベースから取り出すための主キーを値として関連付けてB+木に入れるのです。コラムの値は複数のレコードで重複する可能性があるので、B+木の実装は重複キーを許容するタイプのものでなければいけません。文字列型と数値型は比較方法の違いでしかないので、B+木の比較関数を文字列用と数値用で切り替える以外はほとんど同じ実装を使いまわせます。

一方で、今回のトピックである転置インデックスは、文字列型や数値型とは一線を画します。B+木を使うところは一緒なのですが、検索キーの作り方が全く違うのです。コラムの値をさらに分解して、転置インテックス用のトークンを抽出し、各トークンをキーにして、該当レコードをメインデータベースから取り出すための主キーを値として関連付けてB+木に入れるのです。

とはいえ、インデックスの型にかかわらず、各インデックスに対して「主キーとコラムの値をパラメータとして渡してインデックスを更新する」という部分は共通です。すなわち、以下のような共通インターフェイスを介して個々の実装に分岐すれば、その上層は綺麗に実装できそうです。

// インデックスにコラムの値を追加する
bool tctdb_index_insert_column(TCTDB *tdb, INDEX *idx,
  const char *pkey, const char *value);

// インデックスからコラムの値を削除する
bool tctdb_index_remove_column(TCTDB *tdb, INDEX *idx,
  const char *pkey, const char *value);

ここまでの設計を注意深く行っておけば、それより下の層はコーディングテクニックのみの世界になります。すなわち、決まった仕様をアルゴリズムに落とし込んで、そのバグのない実装をそこそこ最適化しながら書きまくるという職人芸の世界です。それでは、トークン転置インデックスおよびq-gram転置インデックスの2つの実装を見ていきましょう。

トークン転置インデックスの正直な実装

トークン転置インデックスは簡単です。コラムの値を空白とカンマで区切った文字列をトークン（検索キー）にしてB+木に入れまくるだけです。擬似コードで書くとこんな感じでしょうか。

-- トークンの区切り文字
separators = " ,"

-- インデックスにコラムの値を挿入する
index_insert_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = split(value, separators)
  -- 各トークンをDB上のposting listに追加
  foreach token in tokens do
    idx.db.add(token, pkey)
  end
end

-- インデックスからコラムの値を削除する
index_remove_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = split(value, separators)
  -- 各トークンのDB上のposting listを更新
  foreach token in tokens do
    -- 既存のposting listを取得
    old_pkeys = idx.db.get(token)
    -- 新しいposting listを生成
    new_pkeys = []
    -- 既存のposting listで、該当レコード以外の主キーを移行
    foreach old_pkey in old_pkeys do
      if old_pkey != pkey then
        new_pkeys.add(old_pkey)
      end
    end
    -- 新しいposting listでDBを上書き
    idx.db.replace(token, new_pkeys)
  end
end

削除処理で、既存のposting listを取得してから該当レコードの主キーのみを削って書き戻すというところがポイントです。アルゴリズム的にダサいことこの上ないこの削除処理ですが、現実的にはこのような実装が最善です。posting listを予め整列させておいて計算量が O(logN) である二分探索を摘要するという手も考えられますが、それでも削除分を詰める処理はO(N)ですし、そもそもDBに書き戻すデータ量は変わらないので全く意味がありません。上位層でデータベースやインデックスを分割するのが計算量削減には有効なのですが、それはこのモジュールの実装には関係ないことですので、このままのアルゴリズムを最適化して実装すればよいでしょう。

q-gram転置インデックスの正直な実装

q-gram転置インデックスはちょっと複雑になります。コラムの値における一定の文字数の連続した部分文字列を、1文字ずつずらしながら、全ての組み合わせを抽出したものをトークン（検索キー）とします。例えば、「abcdef」をtri-gramで処理すると「abc」「bcd」「cde」「def」「ef」「f」が抽出されます。「ef」と「f」は3文字に満たないのですが、抽出しておかないと後で検索できないので無理やり仲間に入れてあげます。トークンに対応づけて格納するposting listには、そのトークンが何番目に現れたかというオフセット情報も加える必要があります。3文字以上の検索語で検索された場合に、トークン同士が並んでいるかの隣接判定を行うためです。ということで、擬似コードはこんな感じになります。

-- q-gramの単位文字数
qgunit = 3

-- インデックスにコラムの値を挿入する
index_insert_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = qgram_split(value, qgunit)
  -- 各トークンをDB上のposting listに追加
  offset = 0
  foreach token in tokens do
    idx.db.add(token, [pkey, offset])
    offset += 1
  end
end

-- インデックスからコラムの値を削除する
index_remove_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = qgram_split(value, qgunit)
  -- 各トークンのDB上のposting listを更新
  foreach token in tokens do
    -- 既存のposting listを取得
    old_pairs = convert_to_pairs(idx.db.get(token))
    -- 新しいposting listを生成
    new_pairs = []
    -- 既存のposting listで、該当レコード以外の主キーのペアを移行
    foreach old_pair in old_pairs do
      if old_pair[0] != pkey then
        new_pairs.add(old_pair)
      end
    end
    -- 新しいのposting listでDBを上書き
    idx.db.replace(token, new_pairs)
  end
end

追加処理では主キーとオフセットのペアをDBに入れています。なので、削除処理では、DBから取得したposting listをペアのリストに変換した上で扱うことになります（実際にはポインタをゴニョゴニョすればいいのでわざわざ変換はしませんが）。qgram_splitをどう実装するかも結構深い課題なのですが、文字エンコーディングをUTF-8やUTF-16/32に正規化してゴニョゴニョすればよいでしょう。TCではUTF-8の入力を前提としつつUTF-16に変換してから各種の正規化を施しています。

キャッシュの活用

ここまでの説明は、「正直な実装」についてです。アルゴリズムとしては最善を尽くしていますが、これをそのまま実装すると、ディスクがガリガリ音立てまくってちょっと悲しい気持ちになるだけです。トークンを検出する度にDBの読み書きを行っているのではI/Oの負荷が高すぎるので、キャッシュを活用して性能を改善を図るのが普通です。そのためには、擬似コードにおける idx.db に対する操作を全てキャッシュに対して行うようにすればよいのです。そしてキャッシュがメモリ容量を圧迫した時にデータベースにフラッシュ（flush＝吐き出す）するようにします。TCではTCMAP（オンメモリマップ）を使ってキャッシュを実現しています。

キャッシュをフラッシュするにあたっては、キャッシュ内のレコードをインデックスのB+木の比較関数と同じ順序でソートしてから、その順番でインデックスに書き込みます。B+木はランダムアクセスよりシーケンシャルアクセスの方が圧倒的に高速だからです。それを踏まえると、キャッシュをフラッシュする戦略には2種類の解が導かれます。キャッシュ内の全レコードを一度にフラッシュする方法と、LRUなどで判定したヒット率の低いレコードのみをフラッシュする方法です。前者の戦略だとB+木のアクセスが完全にシーケンシャルになるので、スループットを最大化することができます。その反面、ソートや書き出しのために関連するリソースを長い時間ロックすることになり、レイテンシのばらつきが大きくなってしまいます。後者の戦略は全く逆の特性で、ロックの粒度が低いのでレイテンシは低く抑えられますが、B+木のアクセスパターンが悪化するので、スループットは低くなります。

冒頭のデモで用いたJava6 SDKの日本語文書約1万ファイルのインデックスを私の開発環境で作成した場合、全体を一気にフラッシュする戦略だと21秒で完了しましたが、フラッシュに最大1.78秒のロックがかかりました。ロック時間はそのままレイテンシに直結していまいます。一方でLRUの1%をちょびちょびフラッシュする戦略だと、最大0.05秒のロックで済んだ代償として、処理時間は49秒に伸びてしまいました。どちらの戦略が望ましいかはユースケースによるので、実装としてどちらを採用するかは悩ましいところです。ベンチマーク野郎達に気に入ってもらうには前者だし、SIのシーンの多くで要求されるのは後者でしょう。悩んだ末、とりあえずTCのテーブルデータベースはリアルタイム的な使い方を重視しているので、レイテンシ最低化のために後者をデフォルトにしました。ただし、インデックスを張らずにDBを作ってから後でインデックスを張る場合にのみ、一気にフラッシュする戦略で動作するようになっています。バルクでインデクシングしてリードオンリーで検索させるようなユースケースではこの方式が便利でしょう。

トークン転置インデックスを使った検索

テーブルデータベースに対してクエリが発行された際には、クエリオプティマイザによって、クエリに含まれる条件に合ったインデックスが探されて、適切なものがあればそれが使われます。トークン転置インデックスはSTRAND演算子（空白区切りトークンの完全一致AND検索）とSTROR演算子（空白区切りトークンの完全一致OR検索）の際に利用されます。いずれにせよ、クエリの式から抽出したトークンをもとにキャッシュとデータベースからposting listを取得し、それに含まれる主キーのリストを返します。STRANDの実装を擬似コードで示すと以下のようになります。

index_search_strand(tdb, idx, tokens)
  -- 最初のトークンだけ特別扱い
  res = {}
  token = tokens.shift()
  -- posting list内の主キーを結果のプールに入れる
  pkeys = idx.db.get(token)
  foreach pkey in pkeys do
    res.set(pkey)
  end
  -- 残りのトークンはAND条件で処理
  foreach token in tokens do
    nres = {}
    -- 既に取り出した集合にある主キーのみを選ぶ
    pkeys = idx.db.get(token)
    foreach pkey in pkeys do
      if res.exists(pkey) then
        nres.set(pkey)
      end
    end
    -- 結果の置き換え
    res = nres
  end
  res
end

とても簡単ですね。検索エンジンというと何だか凄い技術のように思っている人も多いかと思いますが、分かち書き方式（タグ検索方式）であれば上記のような短いコードで実装できてしまうものなのです。もちろん大規模なインデックスを扱うならばそれなりの工夫は必要になりますが、q-gram方式に比べるとインデックスも小さいし実装も単純だし、天国です。

q-gram転置インデックスを使った検索

一方で、q-gram転置インデックスは、地獄です。文字数と同じ数だけトークンが作られ、しかもposting listにオフセット情報も含めるので、インデックスのサイズが莫大になります。そして、主キーとオフセットを使ってトークンの隣接判定を行う必要があるため、実装もかなり複雑になってしまいます。q-gram転置インデックスはFTSPH演算子（フレーズ検索）とFTSAND演算子（空白区切りトークンの中間一致AND検索）とFTSOR演算子（空白区切りトークンの中間一致OR検索）とFTSEX演算子（Web検索エンジン風検索クエリ）の際に利用されます。ここではそれらに共通で呼び出される、トークンの隣接判定を伴う文字列中間一致について擬似コードを示します。

index_search_fts(tdb, idx, tokens)
  -- 隣接判定をするための全オカレンス情報の配列
  ocr = []
  -- 全トークンのposting listをオカレンス配列に入れる
  for i = 0, tokens.length do
    pairs = idx.db.get(token)
    foreach pair in pairs do
      -- そのオカレンスのトークン番号をペアに加える
      pair.push(i)
      ocr.push(pair)
    end
  end
  -- オカレンス配列をソート。主キーが第1キーでオフセットが第2キー
  sort_occrrence(ocr)
  -- 結果の主キーのセット
  res = {}
  -- オカレンス配列の全要素をスキャン
  i = 0
  while i < ocr.length do
    -- 要素を取り出す。主キーとオフセットとトークン番号のトリオ
    trio = ocr[i]
    i += 1
    -- トークン番号が0のものに着目
    if trio[2] == 0 then
      id = trio[0]
      off = trio[1]
      seq = 1
      -- 後続のオカレンスを調べる
      for j = i, ocr.length do
        ntrio = ocrs[j]
        -- 主キーが違っているかオフセットが進みすぎていたら抜ける
        if ntrio[0] != id or ntrio[1] > off + qgunit then
          break
        end
        -- 主キーが同じでトークン番号とオフセットが整合していた場合には
        if ntrio[2] == seq and ntrio[2] == off + qgunit then
          -- 現在のオフセットとトークン番号を進める
          off = ntrio[2]
          seq += 1
        end
      end
      -- 現在のオフセットがクエリの長さまで到達していたら結果セットに加える
      if off == trio[2] + tokens.length * qgunit then
        res.set(id)
        -- 次の主キーまで飛ばす
        while i < ocrs.length and ocrs[i][0] == id do
          i += 1
        end
      end
    end
  end
end

上記の処理に渡すトークンリストは、クエリの文字列からq-gramのq文字数毎にずらして切り出したものを用います。例えば、tri-gramで「abcdef」の場合は、「abc」と「def」になります。じゃあq文字の倍数でなかった場合はどうするかと言うと、最後のトークンだけ前に端数の文字数分を前にずらします。例えば「abcde」の場合、「abc」と「cde」を用います。その場合はposting listから取り出したオフセットもオカレンス配列に入れる際にずらしておくことで、隣接判定の処理で余計なことをせずに済ませます。

クエリの文字列がq文字以下だった場合には、クエリの文字列に前方一致する全てのトークンを調べる必要があります。その際には隣接判定は不要ですから、タグ検索の処理とほぼ同じようにposting listをそのまま結果セットに入れるような処理になります。

カウンティングソート

隣接判定の計算量を削減するためにオカレンス配列をソートしておくことが重要なわけですが、ソートするのってどうなのよと思いませんか。馬鹿正直過ぎます。ところで、オカレンス配列に求められる条件は次のものです。

主キーが同じオカレンス情報が連続している
主キーが同じ中ではオフセット毎にソートされている

もちろん全体をソートすればこの条件は達成されますが、冷静に考えてみると、全体を一気にソートしなくても達成できます。まず思いつくのは、オカレンス情報の各々を主キー毎に作った別々のリストに加えていく方法ですが、これには弱点があります。候補の数が多すぎる場合にリストの数が増えすぎて空間も時間も使いすぎてしまうのです。そこで、リストの数を一定にするために、主キーのハッシュ値を使うことを考えます。さらに、リストオブジェクトを新たに作るための空間と時間のオーバーヘッドがリストの数を制限することになるため、元の配列と同じ領域を使いたくなります。そこで気づくのが、主キーのハッシュ値を使ってカウンティングソート（分布数え上げソート）を行うことです。カウンティングソートの前提条件は比較する値の変域が予め分かっていることですが、ハッシュ値を使うとまさにそれを達成できます。

ということで、65536通りのハッシュ値を使ってカウンティングソートをした上で、同一ハッシュ値の要素群にはクイックソートをかけるようにしました。これによって、65536*(4=sizeof(int))で256KBの空間を使うかわりに、全体をクイックソートした場合よりもlog2(65536)=16で16倍高速化するかもしれない実装になったわけです。まあ実際には分布を数えるためのオーバーヘッドがかかるしオカレンスのハッシュ値が均等に分布するわけでもないため、速度は2倍程度にしかなりませんが。メモリに余裕があれば65536よりでかい変域を使ってもよいですが、細かく努力してもあまり成果がでないというのもまた現実です。

ビットマスク

あれ、さっきの説明だとインデックスから取得してきたposting listを全部オカレンス配列にぶち込んでいるけども、全部ソート処理に回されて効率悪いのはどうなのよと思いませんか。馬鹿正直過ぎます。ところで、隣接しているか確かめなくてもトークンがコラム内にあるかないかを調べるだけである程度は絞り込めます。つまりフィルタをかけて不要なオカレンス情報を予め振り落とすことによって、後で行うソート等の処理の計算量を減らすのです。例えば、「sakura」というクエリの場合、「sak」のposting listはオカレンス配列にそのまま入れるのですが、「ura」のposting listでは「sak」を処理した際に出てきた主キーのもののみをオカレンス配列に入れるのです。

そこで考えつくのが、トークン毎にハッシュを作って、オカレンス毎に主キーを登録していって最後に論理積をとるという方法です。でも、どっちみち後で完全なテストをするのだから、完全なハッシュを作らなくてもよいでしょう。主キーのハッシュ値を使ってビットマスクを作るだけでもよさそうです。そういえばカウンティングソートの時にハッシュ値を作っているのだから、それを流用してしまえばよさそうです。

ということで、クエリから切り出した第1のトークンのオカレンス情報はそのままオカレンス配列に格納しますが、第2トークン以降を処理する際には、第1トークンで作ったビットマスクでフラグが立っているものだけをオカレンス配列に格納することにします。ハッシュ値なので疑陽性になることがありますが、疑陽性のオカレンスも連接判定の際に削られるので問題ありません。いわずもがな、ビットマップによるハッシュ表はバケット1個あたり1ビットしか使いませんので、100万個のバケットのハッシュ表を作っても125KBしか空間を使わないで済むのです。

第2トークン以降のオカレンス情報がフィルタで削れるのはいいとして、じゃあ第1トークンのオカレンス情報はどうやって削りましょうか。オカレンス配列を作った後で、その配列全体をスキャンして、最終トークンの主キーとオフセットに着目してビットマスクを作った上で、もう一度配列全体をスキャンして、最終トークン以外のオカレンス情報をビットマスクを使ってフィルタすることにします。配列全体を2度もスキャンするのは効率悪い気もしますが、あくまで計算量はO(N)なのでソートのO(N log N)の前処理としては効率的とも言えます。

主キーの表現

単純化のために、主キー（文書ID）が数値であることを前提として今までの説明をしてきました。しかし、TCのテーブルデータベースは任意のバイト列を主キーに指定できるので、数値以外のデータもposting list内の文書IDとして指定できる必要があります。多くの検索エンジンでは文書IDが数値であることを利用して効率的な符号化を行っているのですが、任意のバイト列だとそのような効率化ができません。効率が悪いインデックスは存在価値がありませんから、ここはうまいこと方法を考えないといけません。悩んだ末、主キーが数値であることを前提にインデックスの構造を設計し、そうでない場合はエスケープ文字を使って表現することにしました。すなわち、主キーが数値である場合には効率的に処理ができ、数値でない場合にもそれなりに動くという特性になります。

主キーが自然数で10進数の正規形である場合は、つまり '0' から '9' までの文字のみから構成されて先頭が '0' ではなく全体が正の値である場合は、それを数値として扱い、デルタ符号を用いて直列化したデータを記録します。そうでない場合には、先頭にゼロコード（'\0') を接頭させてそのままのバイト列を記録します。インデックスからposting listを読み出す際には、先頭がゼロコードか否かで数値か任意バイト列かを判定します。数値である場合には10進数の正規形としてバイト列に復元します。

重複キーレコード方式と連結方式

インデックスはB+木のデータベースなのですが、B+木にposting listを格納するには大きく分けて2種類の方法があります。ひとつは、個々のオカレンス情報を別々のレコードとして扱い、キーが重複したレコードを格納できるというB+木の性質を利用して複数のレコードとして格納する方法です。もうひとつは、同一トークンの全てのオカレンス情報を単一のバイト列に直列化して、単一のレコードとして格納する方法です。前者はカーソルを使って特定の文書IDのオカレンス情報を取り出すといった効率化ができる半面、レコード数が多くなるので、個々のレコードのメタデータの分だけ空間効率が悪化します。後者はその逆の性質で、posting listの取得操作や更新操作にあたって全体を一括して処理しなければならない反面、空間効率は高まります。

結論としては、TCでは後者の一括方式を採用しています。検索の際には結局posting list全体をゴニョゴニョするので、個々のオカレンス情報をピンポイントで処理できるという性質はそれほど利点にならないからです。更新を高速化させるには前者の方が有利なのですが、更新操作の効率に関してはキャッシュに頑張らせて稼ぐと割り切って、現在の設計に落ち着いています。

まとめ

長々と説明しましたが、多分、実際のソースコードを読んでもらった方がわかりやすいです。tctdb.cをちょっと覗いてみてください。他のライブラリに全く依存せず、BoostもSTLも使っていないのに、6000行にも満たないコードで全文検索機能付きのテーブルデータベースを実現できています。よくぞここまで簡潔にまとめたものだなと我ながら感心している次第です。