Loading article…
ビットマップインデックスは、ビットマップを使用する特殊なデータベースインデックスです。
ビットマップインデックスは、従来、絶対値またはデータを含むレコード数に対する相対値が少ない、カーディナリティの低い列に適していると考えられてきました。カーディナリティが低い極端な例は、ブールデータ（例：ある都市の住民がインターネットにアクセスできるかどうか）で、値はTrueとFalseの2つです。ビットマップインデックスはビット配列（一般にビットマップと呼ばれる）を使用し、これらのビットマップに対してビット単位の論理演算を実行することでクエリに応答します。ビットマップインデックスは、このようなデータのクエリにおいて、他の構造に比べてスペースとパフォーマンスの面で大きな利点があります。欠点は、データが頻繁に更新される列に対しては、従来のBツリーインデックスよりも効率が低いことです。そのため、高速クエリに特化した読み取り専用システム（例：データウェアハウス）でよく使用され、オンライントランザクション処理アプリケーションには一般的に適していません。
一部の研究者は、ビットマップインデックスは、読み取り専用でアクセスされ、AND、OR、またはXOR演算子を多用して複数のビットマップインデックス列にアクセスするクエリにおいて、中程度または高カーディナリティのデータ（一意の値のデータなど）にも有用であると主張している。[ 1 ]
ビットマップインデックスは、データウェアハウスアプリケーションにおいて、大きなファクトテーブルを、スター型スキーマに配置されたような小さなディメンションテーブルに結合する際にも役立ちます。
インターネットアクセスの例を続けると、ビットマップインデックスは論理的に次のように考えることができます。
On the left, Identifier refers to the unique number assigned to each resident, HasInternet is the data to be indexed, the content of the bitmap index is shown as two columns under the heading bitmaps. Each column in the left illustration under the Bitmaps header is a bitmap in the bitmap index. In this case, there are two such bitmaps, one for "has internet" Yes and one for "has internet" No. It is easy to see that each bit in bitmap Y shows whether a particular row refers to a person who has internet access. This is the simplest form of bitmap index. Most columns will have more distinct values. For example, the sales amount is likely to have a much larger number of distinct values. Variations on the bitmap index can effectively index this data as well. We briefly review three such variations.
Note: Many of the references cited here are reviewed at (John Wu (2007)).[2] For those who might be interested in experimenting with some of the ideas mentioned here, many of them are implemented in open source software such as FastBit,[3] the Lemur Bitmap Index C++ Library,[4] the Roaring Bitmap Java library[5] and the Apache Hive Data Warehouse system.
For historical reasons, bitmap compression and inverted list compression were developed as separate lines of research, and only later were recognized as solving essentially the same problem.[6]
ソフトウェアは、ビットマップ インデックス内の各ビットマップを圧縮してスペースを節約できます。このテーマについてはかなりの量の研究が行われてきました。 [ 7 ] [ 8 ] Roaring ビットマップなどの例外もありますが、[ 9 ]ビットマップ圧縮アルゴリズムは通常、Byte-aligned Bitmap Code、[ 10 ] Word-Aligned Hybrid コード、[ 11 ] Partitioned Word-Aligned Hybrid (PWAH) 圧縮、[ 12 ] Position List Word Aligned Hybrid、[ 13 ] Compressed Adaptive Index (COMPAX)、[ 14 ] Enhanced Word-Aligned Hybrid (EWAH) [15 ]および COmpressed 'N' Composable Integer SEt (CONCISE) [ 16 ] [ 17 ]などのランレングス エンコーディングを採用しています。これらの圧縮方法は、圧縮と解凍にほとんど労力を必要としません。さらに重要なことに、BBC、WAH、COMPAX、PLWAH、EWAH、CONCISEで圧縮されたビットマップは、解凍せずにビット単位の演算に直接参加できます。これにより、 LZ77などの一般的な圧縮技術よりもかなりの利点が得られます。BBC圧縮とその派生は、商用データベース管理システムで使用されています。BBCは、インデックスサイズの削減とクエリパフォーマンスの維持の両方に効果的です。BBCはビットマップをバイト単位でエンコードしますが、WAHはワード単位でエンコードするため、現在のCPUにより適しています。「合成データと実際のアプリケーションデータの両方で、新しいワードアライン方式は50%多くのスペースを使用するだけですが、圧縮データに対する論理演算はBBCよりも12倍高速です。」[ 18 ] PLWAHビットマップは、WAHビットマップが消費するストレージスペースの50%を占め、論理演算で最大20%高速なパフォーマンスを提供すると報告されています。[ 13 ] CONCISE [ 17 ]とEnhanced Word-Aligned Hybridについても同様の検討が可能です。 [ 15 ]
BBC、WAH、PLWAH、EWAH、COMPAX、CONCISEなどのスキームのパフォーマンスは、行の順序に依存します。単純な辞書式ソートでは、インデックスのサイズを9分の1に減らし、インデックスを数倍高速化できます。[ 19 ]テーブルが大きいほど、行をソートすることが重要になります。ストリーミングデータのインデックス作成時にソートと同じ結果を得るために、再シャッフル技術も提案されています。[ 14 ]
基本的なビットマップインデックスは、異なる値ごとに 1 つのビットマップを使用します。異なるエンコード方式を使用することで、使用するビットマップの数を減らすことができます。[ 20 ] [ 21 ]例えば、バイナリエンコードを使用した log(C) ビットマップを使用して C 個の異なる値をエンコードすることができます。[ 22 ]
これによりビットマップの数が減り、さらに容量を節約できますが、クエリに応答するにはほとんどのビットマップにアクセスする必要があります。そのため、基本データの垂直投影（マテリアライズドビューまたは投影インデックスとも呼ばれる）をスキャンするよりも効率的ではない可能性があります。クエリのパフォーマンス、インデックスサイズ、インデックスのメンテナンスのバランスが取れた最適なエンコード方法を見つけることは、依然として課題です。
圧縮を考慮しない場合、ChanとIoannidisはマルチコンポーネントエンコーディング方式のクラスを分析し、2コンポーネントエンコーディングがパフォーマンスとインデックスサイズの関係曲線の折れ点に位置し、インデックスサイズとクエリパフォーマンスの最適なトレードオフを表しているという結論に達した。[ 20 ]
カーディナリティの高い列の場合、値をビンに分割し、各ビンが複数の値をカバーし、各ビン内の値を表すビットマップを作成すると便利です。このアプローチでは、エンコード方法に関係なく、使用するビットマップの数を削減できます。[ 23 ]ただし、ビン化されたインデックスは、ベースデータを調べずに一部のクエリにしか応答できません。たとえば、ビンが 0.1 から 0.2 の範囲をカバーする場合、ユーザーが 0.15 未満のすべての値を要求したとき、ビンに含まれるすべての行がヒット候補となり、実際に 0.15 未満であるかどうかを確認するためにチェックする必要があります。ベースデータをチェックするプロセスは、候補チェックとして知られています。ほとんどの場合、候補チェックにかかる時間は、ビットマップ インデックスを操作するのに必要な時間よりもかなり長くなります。そのため、ビン化されたインデックスは、パフォーマンスが不安定になります。一部のクエリでは非常に高速ですが、クエリがビンに完全に一致しない場合は、はるかに低速になります。
ビットマップ インデックスの概念は、1985 年に発表されたイスラエル シュピーグラー教授とラフィ マヤンの研究「バイナリ データベースのストレージと検索に関する考察」で初めて紹介されました。[ 24 ]ビットマップ インデックスを実装した最初の商用データベース製品は、Computer Corporation of AmericaのModel 204でした。パトリック オニールは、 1987 年にこの実装に関する論文を発表しました。[ 25 ]この実装は、基本的なビットマップ インデックス (圧縮なし) と行識別子のリスト (RID リスト) のハイブリッドです。全体として、インデックスはB+ ツリーとして構成されています。列のカーディナリティが低い場合、B ツリーの各リーフ ノードには長い RID リストが含まれます。この場合、RID リストをビットマップとして表現する方がスペースが少なくて済みます。各ビットマップは 1 つの異なる値を表すため、これが基本的なビットマップ インデックスです。列のカーディナリティが増加すると、各ビットマップは疎になり、同じ内容を RID リストとして保存するよりも、ビットマップを保存する方がディスク容量が多く必要になる場合があります。この場合、RID リストを使用するように切り替わり、B+ ツリーインデックスになります。[ 26 ] [ 27 ]
ビットマップインデックスを使用する最も強力な理由の1つは、それらから生成される中間結果もビットマップであり、より複雑なクエリに答えるための後続の操作で効率的に再利用できることです。多くのプログラミング言語は、これをビット配列データ構造としてサポートしています。たとえば、JavaにはBitSetクラスがあり、.NETにはBitArrayクラスがあります。[ 28 ]
永続的なビットマップインデックスを提供しないデータベースシステムの中には、クエリ処理を高速化するために内部的にビットマップを使用するものがあります。例えば、PostgreSQLバージョン8.1以降では、「ビットマップインデックススキャン」という最適化機能が実装されており、単一テーブル上の利用可能なインデックス間の複雑な論理演算を高速化します。
列数の多いテーブルの場合、考えられるすべてのクエリ（いずれかのフィールドで等価フィルタリング条件を使用する場合）を満たすために必要な一意のインデックスの総数は非常に速く増加し、次の式で定義されます。
ビットマップインデックススキャンは、異なるインデックス上の式を組み合わせるため、テーブル上のあらゆるクエリをサポートするために、列ごとに1つのインデックスのみが必要となります。
このアクセス戦略を B ツリー インデックスに適用すると、複数の列に対する範囲クエリを組み合わせることもできます。このアプローチでは、テーブルの各行に対して1ビットを持つ一時的なイン メモリ ビットマップが作成されます (1 MB で800 万件を超えるエントリを格納できます)。次に、各インデックスの結果がビット演算を使用してビットマップに結合されます。すべての条件が評価された後、ビットマップには式に一致した行に対して「1」が含まれます。最後に、ビットマップを走査して一致する行を取得します。インデックスを効率的に組み合わせることに加えて、すべての行がメイン テーブルから順次フェッチされるため、テーブル アクセスの参照の局所性も向上します。[ 31 ]内部ビットマップはクエリ後に破棄されます。テーブルに行が多すぎて 1 行あたり 1 ビットを使用できない場合は、代わりにディスク ページごとに 1 ビットを持つ「損失あり」ビットマップが作成されます。この場合、ビットマップはフェッチするページを決定するためにのみ使用され、フィルタ条件は一致するページのすべての行に適用されます。
![{\displaystyle \mathbf {C} _{n}^{\left[{\frac {n}{2}}\right]}\equiv {\frac {n!}{\left(n-\left[{\frac {n}{2}}\right]\right)!\left[{\frac {n}{2}}\right]!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9160ac60d370e6a8b56c98a5ca0d30e8679b89d5)
{{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク){{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）