Groongaの結果セットにRoaring bitmapsを使えないか検討している須藤です。
以前、ClickHouseみたいにポスティングリストにRoaring bitmapsを使えないか検証しましたが、既存のPForDeltaの方がよかったのでやめました。しかし、結果セットには使えるかも？とは思っていました。ただ、Groongaの結果セットは「ヒットしたレコードはどれか」というビットで表現できる情報だけではなく、「ヒットしてレコードはどれで、それらのスコアはそれぞれいくつか」という「ヒットしたか」（ビットで表現できる）+「スコア」（64bit浮動小数点数で、ビットでは表現できない）というビットでは表現できない情報が必要です。そのため、使えるかも？とは思いつつ、じゃあどうやって？がわからずにそのままになっていました。
この間、なんとなくまたどうにかできないか調べてみたら、Roaring bitmapsのGo実装にはそれを実現する方法が含まれていることを見つけたので紹介します。まだGroongaでは検証していないので、Groongaで使いものになるかどうかはわかりません。
Roaring bitmaps
Roaring bitmapsは効率よくかつ高速にビットマップを表現する方法です。立っているビットの数に合わせて内部表現を変えることでそれを実現しています。たとえば、2 ** 15番目のビットだけが立っている場合、2 ** 15ビットのビットマップを用意して2 ** 15番目のビットを立てると2 ** 15 / 8バイト（4KiB）必要になりますが、2 ** 15番目という情報だけ持って表現すると2バイトで表現できます。こういう感じのことをいい感じにがんばって効率よくかつ高速にビットマップを表現しています。
それでは、ビットしか表現できないRoaring bitmaps（ビットマップなんだから当然）でどうやってビットより大きい情報を表現するとよいのでしょうか。
Bit Slice Indexing (BSI)
1つのビットマップでは表現できないなら複数のビットマップを組み合わせて表現すればよいのです。その実装がBit Slice Indexingという名前でGo実装に入っています。
たとえば、「ヒットしたか」と「64bit浮動小数点数のスコア」を表現するときは、「ヒットしたか」のために1つのビットマップ、「64bit浮動小数点数のスコア」のために64個のビットマップを持てばよいのです。
「64bit浮動小数点数のスコア」だと説明が面倒なので、「8bitの非負整数」で説明します。また、要素数が多いのも説明が面倒なので、10要素だけで説明します。
最初は、論理的には次のようになっています。
N番目の要素: 01234 56789
0bit目のビットマップ: 00000 00000
1bit目のビットマップ: 00000 00000
2bit目のビットマップ: 00000 00000
3bit目のビットマップ: 00000 00000
4bit目のビットマップ: 00000 00000
5bit目のビットマップ: 00000 00000
6bit目のビットマップ: 00000 00000
7bit目のビットマップ: 00000 00000
全ビットが0でサイズが10のビットマップが8個あります。8個のビットマップはそれぞれ各要素の0bit目から7bit目までを表現しています。0番目のビットの値をこの8個のビットマップから集めれば8bitの情報を表現できるというわけです。
たとえば、1番目の要素に7（00000111）を設定したい場合は次のようになります。
N番目の要素: 01234 56789
0bit目のビットマップ: 01000 00000 # <- 1番目の要素のビットが立った！
1bit目のビットマップ: 01000 00000 # <- 1番目の要素のビットが立った！
2bit目のビットマップ: 01000 00000 # <- 1番目の要素のビットが立った！
3bit目のビットマップ: 00000 00000
4bit目のビットマップ: 00000 00000
5bit目のビットマップ: 00000 00000
6bit目のビットマップ: 00000 00000
7bit目のビットマップ: 00000 00000
たくさんの要素のたくさんのビットが立つようならハッシュテーブルとか別のデータ構造のほうが効率がよいでしょうが、疎なら複数のRoaring bitmapsを組み合わせて表現したほうが効率がよいということもありそう、という気持ちにはなります。
まとめ
この間、たまたまRoaring bitmapsのGo実装にRoaring bitmapsベースでビットより大きい情報を表現する方法があることを知ったので紹介しました。Groongaの結果セットで使えるか検証したいですね。
