1

I'm planning software that's an OLAP application at its heart (it helps analyse metering data) and is going to have some kind of star schema for its database, because the stored values will be looked at from different angles (time, source, type etc.) and the requests will be asking for aggregated data along these dimensions. The queries tend to deliver a lot of rows (up to some 100 000).

My research on this topic (see also my question here) seems to indicate that bitmap indices are a good way to search for data the way I'm planning to. However, I want to support multiple db engines, some of which do not offer bitmap indices on their tables (in particular, MySQL).

Now, I can certainly build and maintain my own bitmap index and use it to look for row ids pointing to the fact table. However, I suspect that this is going to defeat the whole purpose of the index, because the database is still going to search for row ids in a B-Tree. Could somebody with more profound theoretical background or more experience tell me if I still gain anything, like not having to do slow JOINs on the dimension tables?

I would also appreciate hints on what I have to evaluate if the answer is not straightforward.

4

2 に答える 2

2

カスタムデータ構造を使用してメモリ内の大量のデータを操作するときにビットマップインデックスを使用することはできましたが、適切な（postgresqlのような）APIを備えていないサードパーティのデータベースに実装するのは少し厄介です。インデックス構造を拡張します。

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

だから、いや。

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

座標xとyを使用した2dの例。ここでは、（x1、y1）から（x2、y2）までの範囲の合計に関心があります。

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

合計テーブルを使用して、各位置（x、y）について、その位置の値を格納せず、代わりに（0,0）から（x、y）までの領域の合計を格納します。

次に、次の質問をすることで、任意の範囲クエリに答えることができます。

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

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

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

于 2008-11-07T14:44:14.963 に答える
1

ビットマップ インデックスを直接サポートしていない一部の DB エンジンには、ファクト テーブルにアクセスせずにこのタイプのクエリを実行できるスター最適化がまだあります。たとえば、SQL Server には Index Intersection と呼ばれる機能があり、その場でビットマップを構築して解決を行うことで同様のことを行います。Microsoftは、このパフォーマンスはビットマップ インデックスに匹敵すると主張しています。このトピックに関するちょっとしたファンアウトについては、この投稿を参照してください。

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

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

于 2008-11-07T14:40:01.553 に答える