全文検索エンジンGroongaを開発している須藤です。
爆速OLAPデータベースであるClickHouseが全文検索インデックスを実装したというブログ記事の中で「ポスティングリストの圧縮には最先端のRoaring bitmapsを使った」と書いていました。そんなによいものならGroongaのポスティングリストでも使おうかと思って検討してみたのですが、Groongaのユースケースではサイズ・速度ともに現在のPForDeltaの方が優れていたのでRoaring bitmapsは導入しませんでした。ただ、結果セットで使うにはよさそうな気がするので、おいおいそのユースケースでも検討したいです。
ClickHouseのブログ記事では各種圧縮手法を比較した論文「An Experimental Study of Bitmap Compression vs. Inverted List Compression」も紹介されていて、それを参考にしたと書かれています。Groongaで実験した結果もだいたい同じような傾向になりました。つまり、ポスティングリストの圧縮サイズ・展開速度はPForDeltaの方がRoaring bitmapsより性能がよいです。論文でも「Use SIMDBP128* and SIMDPforDelta* for inverted list compression for high query performance (e.g., intersection and union) and low space overhead.」と書かれています。ここで参照されている「SIMDBP128*」と「SIMDPforDelta*」はSIMDを使った高速なPForDeltaみたいなものです。
が、私は実験する前にこの論文を斜め読みしかしておらず、さらに、Roaring bitmapsのサイト内のページでこの論文の「Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods」を引用しているのでRoaring bitmapsの方がPForDeltaよりもよいのでは？と思ってしまっていました。
そのため、すでに知られていることを再確認する形になってしまいました。私と同じことを再確認しなくてもよいように、私が確認したことを紹介します。
Groongaのポスティングリストの圧縮方法
Groongaは情報の鮮度を重視しているため、データが更新されたらすぐに検索可能になるようにポスティングリストをインプレースで更新します。また、更新中に検索性能が落ちないように参照ロックフリー（更新中も参照をブロックしない）で更新します。
これをいい感じに実現するために、Groongaのポスティングリストはインプレースでの更新に向いているが圧縮率はそこそこのポスティングリストと、更新はできないがしっかり圧縮するポスティングリストを持っています。Groonga内部では前者を「バッファー」、後者を「チャンク」と呼んでいます。
バッファーはスキップリストとバイト単位の圧縮アルゴリズムを使っています。バイト単位の圧縮はVariable-Byteみたいに可変長でバイト単位で圧縮するんですが、各バイトの先頭ビットを見るのではなく、先頭バイトだけを見て長さを判断します。Groongaの作者の森さんが実装しました。森さんはBER圧縮と言っていたような気がしますが、BER圧縮ではないような。。。コメントにフォーマットを書いておいたので気になる人はコメントを見てください。
チャンクは次のどれかを使います。
- バッファーと同じバイト単位の圧縮アルゴリズム
- PFor
- PForDelta
対象の整数の数が少ないときはバイト単位の圧縮アルゴリズムで、そうではないときはPForかPForDeltaを使います。ソート済みの整数リストのときはPForDeltaでそうでないときはPForを使います。
Groongaのポスティングリストは次の最大5本のリストから構成されています。それぞれソート済みかどうかという情報もつけておきます。ソート済みのリストはPForDeltaを使えるということです。
- 文書ID（重複なしソート済みリストだがセクションIDがある場合は重複あり）
- セクションID（オプション、文書IDごとに重複なしソート済みリスト）
- トークンの出現数（重複あり）
- 重み（オプション、重複あり）
- 位置（オプション、文書ID・セクションIDのペアごとに重複なしソート済みリスト）
セクションIDというのは他の全文検索エンジンでは見ない概念だと思うので説明しておきます。
Groongaは1つのインデックスで複数のカラムのポスティングリストを扱うことができます。一般的にマルチカラムインデックスとよばれているインデックスのことです。これを実現するためにはトークンが出現した文書のIDを保持しているだけでは情報が足りません。どのカラムで出現したかがわからないからです。そのため、文書IDに加えてセクションIDも保持します。セクションIDによりどのカラムで出現したかを特定できます。
Groongaがどのようにポスティングリストを圧縮しているかがわかりましたね。それでは、各圧縮方法について具体的なデータフォーマットではなくどんなことをしているかのイメージを説明します。
バイト単位の圧縮アルゴリズム
なにか名前をつけた方がよさそうな気がしますが、いい名前が思いつかないので名無しのままで説明します。
対象の整数は32bit非負整数です。つまり4バイトのデータです。このアルゴリズムでは、小さな整数は1バイトで、少し大きな整数は2バイトで、といった具合に小さい整数ほど少ないバイト数で表現します。その代わり、大きな整数は5バイト使います。
ポスティングリストでは大きな整数がでることは少ないのでトータルでは小さくなることが多いです。なぜ大きな整数がでることが少ないかは次のPForDeltaの「Delta」の説明でわかります。
PForDelta
PForDeltaはPatched Frame of Reference Deltaの略です。ソート済みの整数値リストの圧縮に向いているアルゴリズムです。そして、ポスティングリストはソート済みの整数値リストです。なのでポスティングリストは向いているユースケースの1つです。
PForDeltaは3つのアルゴリズムを合わせたアルゴリズムです。「Patched」と「Frame of Reference」と「Delta」の3つのアルゴリズムです。
「Frame of Reference」は小さな整数のリストの圧縮に向いています。すべての整数を表現できる少ないビット数を求めてそのビット数で各整数を表現します。小さな整数ばかりだとより少ないビット数で表現できるので効果が高いです。
「Delta」は整数そのものではなく各整数の差分で整数リストを表現する方法です。たとえば、「1, 4, 4, 6」であれば「1, 3 (4-1), 0 (4-4), 2 (6-4)」と表現します。これ自体は圧縮方法ではありませんが、「Frame of Reference」と組み合わせることで「Frame of Reference」の効果を高めることができます。なぜなら、整数そのものよりも各整数の差分の方が小さな整数のリストになるからです。「Frame of Reference」は小さな整数ばかりの方が効果が高かったことを思い出してください。
ただし、ソート済みの整数リストでないと「Delta」は使えません。ソート済みでない場合、差分に負の整数が混ざる可能性があります。Groongaの圧縮の実装はすべて32bit非負整数を対象にしているので、負の整数が混ざるとうまく動きません。
トークンの出現数と重みはソート済みではないため「Delta」なしの「PFor」を使っています。
「Patched」も「Frame of Reference」の効果を高める方法です。「Frame of Reference」は大きな整数が混ざると効果が落ちます。各整数を表現するためにより多いビット数が必要になるためです。「Patched」は大きな整数を別扱いにして「Frame of Reference」で小さな整数だけを扱えるようにします。こうすることで「Frame of Reference」の効果を高めつつ大きな整数も扱えるようにしています。
Roaring bitmaps
Roaring bitmapsは32bit非負整数リスト（32bitビットマップ）を表現できる圧縮方法です。上位16bitでグループに分け、各グループごとに適切な表現を選択することで高速な操作と（PForDeltaに比べると）それなりの圧縮率を実現します。
特に高速な操作がビットマップ単位の和と積です。上位16ビットで固定幅でグループ分けされているのでビットマップ間で必要なサブ部分だけ操作することができるからです。
各グループは含まれる整数リストの性質に応じて次のように表現します。
- 密である：
2 ** 16bit（8192バイト）のビットマップで表現（下位16bitだけを表現すれば十分だから。） - 疎である：
- Run Length Encodingの方が効率がよい：Run Length Encodingで表現
- Run Length Encodingの方が効率が悪い：16bit（2バイト）整数の配列で表現（下位16bitだけを表現すれば十分だから。）
ビットマップで表現する場合は4バイトの整数が1ビットで表現できるのでサイズは1/32になります。配列の場合は2バイトなので1/2になります。Run Length Encodingの場合は同じ整数値がどれだけ連続していたか次第で圧縮率が変わります。
ビットマップになるとPForDeltaよりもサイズが小さそうですが、ポスティングリストが蜜になることはめったにありません。たとえば、隣接する65536文書がヒットする場合は蜜ですが、そのようなトークンはストップワード扱いされたりして検索で使われない可能性も高いでしょう。また、自然言語はジップの法則に従うので密になる可能性があるのはほんの一部のトークンだけになるでしょう。
GroongaでRoaring bitmapsを使えるようにして日本語版Wikipediaのデータで実験した感じではRoaring bitmapsの方がインデックス構築速度・インデックスサイズともに1.5倍くらいになっていた気がします。「あれ、思ったより速くないぞ？」と思って前述の論文やRoaring bitmapsの実装やフォーマットの仕様をマジメに確認し、「まぁ、だったらこんなもんか」と思って検討をやめてしまったので記録を残し忘れました。。。
GroongaのユースケースでRoaring bitmapsに不利だった点として以下の点があります。
- マルチカラムインデックスの場合（セクションIDをつかう場合）は文書IDが重複ありソート済み整数リストになり、そのままRoaring bitmapsを使えなかった。
- Roaring bitmapsは重複なし整数リストにしか使えない。
- 文書IDとセクションIDを1つの32bit非負整数値にパックすれば重複なしソート済み整数リストになるので、そのように前処理した。
- 位置も重複があるので文書IDとセクションIDのペアごとに別のRoaring bitmapsにしないといけない。
- 密になりにくい。
- 検索時はカーソルを使って整数を取り出し、集合の和・積を実現するのでRoaring bitmapsの集合操作の恩恵を得られない。
- ポスティングリストに文書IDが含まれているかどうかレベルで済む検索（たとえば、タグ検索）であれば、集合操作でよいが、フレーズ検索など文書ID以外の位置もチェックしないといけない検索では集合操作を使えない。
一方、検索時に各条件でヒットした文書の集合を保持する「結果セット」としてRoaring bitmapsを使うのはよいかもしれないという感触はあります。現在はハッシュテーブルで「結果セット」を実現していますが、「結果セット」で必要な特徴は以下の通りで、Roaring bitmapsが得意としていそうです。
- 高速な要素の追加
- 32bit整数の集合をできるだけコンパクトに表現（実行時の使用メモリー量をできるだけ抑えたい）
- 高速な集合操作（和・積・差）
- 各ヒットした文書のメタデータを保持（たとえばスコアー）
最後のメタデータがうまくできるかどうかが悩みどころです。
まとめ
Groongaのポスティングリストの圧縮方法としてPForDeltaの代わりにRoaring bitmapsを使うのはどうかと検討しましたが、実験した結果では既存のPForDelta実装の方が向いていたのでRoaring bitmapsは採用しませんでした。
しかし、「結果セット」に使うのはいいかも？という気はするので、おいおい検討したいです。
また、既存のPForDelta実装はSIMD対応にすることで高速化できそうなので、これもおいおい検討したいです。たとえば、 https://github.com/lemire/FastPFOR はSIMD対応により高速になることを示しています。
また、また、既存のバイト単位の圧縮アルゴリズムもSIMD化や別のアルゴリズムの採用などで高速化できる余地はありそうなので、これもおいおい検討したいです。アルゴリズムから見直す場合はどうやって互換性を維持するかも考慮しないといけないためなかなかむずかしそうな気はします。
