メモ: Lucene の roaring bitmap とか

http://www.elasticsearch.org/blog/frame-of-reference-and-roaring-bitmaps/ 読んだ。

• 検索エンジンでは、ソートされた整数列を扱うデータ構造が重要
• データ構造にはそれぞれ得意・不得意がある
  • postings lists に使われているデータ構造が必ずしも filter cache にも最適だとは限らない
• Lucene 5 で導入された roaring bitmap は速さとメモリ使用量のバランスがよい
• Elasticsearch 2.0 あたりで取り込まれそう。filter cache 効率化に期待？
• 現時点で filter cache は bitmap を使っているので、ヒットする document の密度によらずデータサイズや速度は一定。must_not したり、ヒットする document 数の少ない filter をキャッシュするよう頑張ったりしても速度やデータサイズは変わらない
• terms fileter のような軽い filter では cache 使わないほうがよいと書いてある
  • キャッシュするなら重い filter や、bool filter のような複合 filter で、かつ再利用可能性の高いものということか
  • といっても segment が全てシステムキャッシュに載っかってる贅沢な環境の話のようなので、全てが乗っからない環境では速くなるとは限らなさそう