＆＃8220;偽物＆＃8221;ビットマップインデックス？

Question

OLAPアプリケーションを中心としたソフトウェアを計画しています（計測データの分析に役立ちます）。保存された値はさまざまな角度から（時間、ソース、タイプなど）、リクエストはこれらのディメンションに沿って集約されたデータを要求します。クエリは多くの行を配信する傾向があります（最大約100,000）。

このトピックに関する私の研究（ myも参照）ここの質問）は、ビットマップインデックスが、私が計画している方法でデータを検索するための良い方法であることを示しているようです。ただし、複数のdbエンジンをサポートしたいのですが、その一部はテーブルにビットマップインデックスを提供していません（特にMySQL）。

今、私は確かに独自のビットマップインデックスを構築および維持し、それを使用してファクトテーブルを指す行IDを探すことができます。ただし、データベースは引き続きBツリーの行IDを検索するため、これはインデックスの目的全体を無効にすると思われます。より深い理論的背景または経験を積んだ人が、ディメンションテーブルで低速のJOINを実行する必要がないなど、何かをまだ得ているかどうかを教えてもらえますか？

また、答えが簡単でない場合に評価しなければならないことに関するヒントをいただければ幸いです。

Answer 1

ビットマップインデックスを直接サポートしていないDBエンジンには、ファクトテーブルにヒットすることなくこのタイプのクエリを実行できるスター最適化機能がまだあります。たとえば、SQL Serverには、インデックスインターセクションと呼ばれる機能があります。これは、ビットマップをその場で作成して解決を行うことにより、同様のことを行います。 Microsoftは、このパフォーマンスがビットマップインデックスに匹敵することを主張しています。 この投稿このトピックのファンアウトについて少し説明します。

MySQLがこれを実行するかどうかはわかりませんが、Postgresqlは確かに実行します。 IIRCの一部のバリアント（Greenplum、私は思う）もビットマップインデックスを直接サポートしており、それをメインDBエンジンに組み込むという話がありました。これがまだ行われたかどうかは思い出せません。

最新のDBMSプラットフォームでは、スタークエリの最適化が何らかの方法で提供されているため、車輪を再発明する必要はないと思われると思います。これを実行できない1つまたは2つを見つけることができますが、それらをサポートしないという選択肢が常にあります。

Answer 2

カスタムデータ構造を使用してメモリ内の多くのデータを操作する場合、ビットマップインデックスは幸運でしたが、良い（postgresqlのようなものではない）サードパーティのデータベースに実装するのは少し厄介です）インデックス構造を拡張するためのAPI。

一般に、とにかくBツリーインデックスを検索するので、私の経験がガイドであれば何も得られません。

だから、いいえ。

アプリケーションが本質的にOLAPであり、自然に順序付けられた範囲にグループ化される少数のディメンションがあり、本当に問題の漸近性を変更する必要がある場合は、構造のような「合計テーブル」を構築することを検討できます2 ^ dの操作で階層的な答えをクエリできます。また、関連するクエリを多数実行している場合は、それを償却できます。

座標xとyを持つ2dの例で、（x1、y1）から（x2、y2）の範囲の合計に関心がある場合。

個別に保存すると、面積に比例したエントリ数を合計する必要があります。

sumtableを使用して、各位置（x、y）にその位置の値を保存せず、代わりに（0,0）から（x、y）の領域の合計を保存します。

その後、次のように尋ねることで、あらゆる範囲のクエリに答えることができます。

sum（x2、y2）-sum（x1、y2）-sum（x2、y1）+ sum（x1、y1）

一定量のオーバーヘッド（xとyにインデックスがあり、SQLに格納していると仮定すると、データセットサイズは対数です）

もちろん、範囲に分割されない複雑な属性がある場合、これは分割されますが、単純な辞書編集インデックス、日付などを処理できます