ビットマップインデックス

ビットマップ インデックスは、ビットマップを使用する特殊な種類のデータベース インデックスです。

ビットマップ インデックスは、従来、絶対数またはデータを含むレコード数に対する相対数で、個別値の数が中程度である、カーディナリティの低い列 に適していると考えられてきました。カーディナリティの低い極端な例は、True と False の 2 つの値を持つブール データ(例: ある都市の居住者はインターネットにアクセスできるかどうか) です。ビットマップ インデックスはビット配列(一般にビットマップと呼ばれる) を使用し、これらのビットマップに対してビット単位の論理演算を実行してクエリに応答します。このようなデータのクエリでは、ビットマップ インデックスは他の構造に比べてスペースとパフォーマンスの面で大きな利点があります。欠点は、データが頻繁に更新される列の場合、従来のB ツリーインデックスよりも効率が悪いことです。そのため、データ ウェアハウスなどの高速クエリに特化した読み取り専用システムで使用されることが多く、オンライン トランザクション処理アプリケーションには通常適していません。

一部の研究者は、ビットマップインデックスは、読み取り専用でアクセスされる中程度または高カーディナリティデータ（一意の値を持つデータなど）にも有用であり、クエリはAND、OR、またはXOR演算子を使用して複数のビットマップインデックス列に頻繁にアクセスすると主張しています。^[1]

ビットマップ インデックスは、データ ウェアハウスアプリケーションで、大きなファクト テーブルをスター スキーマで構成された小さなディメンション テーブルに結合する場合にも役立ちます。

インターネット アクセスの例を続けると、ビットマップ インデックスは論理的に次のように考えることができます。

左側のIdentifier は各居住者に割り当てられた一意の番号を指し、HasInternet はインデックス付けされるデータであり、ビットマップ インデックスの内容は、見出しbitmaps の下の 2 つの列として表示されます。Bitmaps ヘッダーの下の左側の図の各列は、ビットマップ インデックス内のビットマップです。この場合、そのようなビットマップが 2 つあり、1 つは「インターネットあり」Yes用で、もう 1 つは「インターネットあり」No用です。ビットマップYの各ビットが、特定の行がインターネットにアクセスできる人物を指しているかどうかを示していることは簡単にわかります。これは、ビットマップ インデックスの最も単純な形式です。ほとんどの列には、より多くの個別値が含まれます。たとえば、売上高には、はるかに多くの個別値が含まれる可能性があります。ビットマップ インデックスのバリエーションを使用して、このデータにも効果的にインデックス付けできます。そのような 3 つのバリエーションを簡単に確認します。

注: ここで引用した参考文献の多くは、(John Wu (2007)) でレビューされています。^[2]ここで言及したアイデアのいくつかを試してみたいという方のために、それらの多くは、FastBit、^[3] Lemur Bitmap Index C++ Library、^[4] Roaring Bitmap Java library ^[5]やApache Hive Data Warehouse システムなどのオープンソースソフトウェアで実装されています。

歴史的な理由から、ビットマップ圧縮と逆リスト圧縮は別々の研究分野として開発され、後になって本質的に同じ問題を解決するものとして認識されました。^[6]

ソフトウェアは、ビットマップ インデックス内の各ビットマップを圧縮して、スペースを節約できます。このテーマについては、かなりの研究が行われてきました。 ^{[7] [8]} Roaring ビットマップなどの例外はありますが、^[9]ビットマップ圧縮アルゴリズムでは通常、バイト整列ビットマップ コード、^[10]ワード整列ハイブリッド コード、^[11]パーティション ワード整列ハイブリッド (PWAH) 圧縮、^[12]位置リスト ワード整列ハイブリッド、^[13]圧縮適応インデックス (COMPAX)、^{[14]拡張ワード整列ハイブリッド (EWAH) [15]}および圧縮 'N' 構成可能整数 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で割ることができ、インデックスを数倍高速化できます。^[19]テーブルが大きくなるほど、行のソートが重要になります。ストリーミングデータのインデックス作成時にソートと同じ結果を達成するために、再シャッフル手法も提案されています。^[14]

基本的なビットマップインデックスは、各個別値に対して1つのビットマップを使用します。異なるエンコード方法を使用することで、使用するビットマップの数を減らすことができます。 ^{[20] [21]たとえば、}バイナリエンコードのlog(C)ビットマップを使用してCの個別値をエンコードすることができます。^[22]

これによりビットマップの数が減り、スペースがさらに節約されますが、クエリに応答するには、ほとんどのビットマップにアクセスする必要があります。このため、マテリアライズド ビューまたは投影インデックスとも呼ばれるベース データの垂直投影をスキャンするほど効果的ではない可能性があります。(任意の) クエリ パフォーマンス、インデックス サイズ、およびインデックスのメンテナンスのバランスをとる最適なエンコード方法を見つけることは、依然として課題です。

チャンとイオアニディスは、圧縮を考慮せずに、マルチコンポーネントエンコーディング方式のクラスを分析し、2コンポーネントエンコーディングがパフォーマンスとインデックスサイズの曲線の屈曲点に位置し、したがってインデックスサイズとクエリパフォーマンスの間の最良のトレードオフを表すという結論に達しました。^[20]

高カーディナリティ列の場合、値をビンに分割すると便利です。ビンごとに複数の値をカバーし、各ビンの値を表すビットマップを作成します。このアプローチにより、エンコード方法に関係なく、使用されるビットマップの数が削減されます。^[23]ただし、ビン化されたインデックスは、基本データを調べずに一部のクエリにのみ応答できます。たとえば、ビンが 0.1 から 0.2 の範囲をカバーする場合、ユーザーが 0.15 未満のすべての値を要求すると、ビンに含まれるすべての行がヒットの可能性があり、実際に 0.15 未満であるかどうかを確認する必要があります。基本データをチェックするプロセスは、候補チェックと呼ばれます。ほとんどの場合、候補チェックにかかる時間は、ビットマップ インデックスの操作に必要な時間よりも大幅に長くなります。そのため、ビン化されたインデックスのパフォーマンスは不規則です。一部のクエリでは非常に高速ですが、クエリがビンに正確に一致しない場合は大幅に遅くなります。

ビットマップ インデックスの概念は、1985 年に発表された Israel Spiegler 教授と Rafi Maayan による研究「バイナリ データベースの格納と検索に関する考慮事項」で初めて導入されました。^[24]ビットマップ インデックスを実装した最初の商用データベース製品は、Computer Corporation of America のModel 204でした。Patrick O'Neil は1987 年にこの実装に関する論文を発表しました。 ^[25]この実装は、基本的なビットマップ インデックス (圧縮なし) と行識別子のリスト (RID リスト) のハイブリッドです。全体として、インデックスはB+treeとして構成されます。列のカーディナリティが低い場合、B ツリーの各リーフ ノードには長い RID リストが含まれます。この場合、RID リストをビットマップとして表すために必要なスペースが少なくなります。各ビットマップは 1 つの個別の値を表すため、これが基本的なビットマップ インデックスです。列のカーディナリティが増加すると、各ビットマップはスパースになり、ビットマップを格納するために、RIDリストとして同じコンテンツを格納するよりも多くのディスクスペースが必要になる場合があります。この場合、RIDリストを使用するように切り替えられ、B +ツリーインデックスになります。^{[26] [27]}

ビットマップ インデックスを使用する最大の理由の 1 つは、ビットマップ インデックスから生成される中間結果もビットマップであり、より複雑なクエリに応答するための後続の操作で効率的に再利用できることです。多くのプログラミング言語は、これをビット配列データ構造としてサポートしています。たとえば、Java にはBitSetクラスがあります。

永続的なビットマップ インデックスを提供しない一部のデータベース システムでは、クエリ処理を高速化するためにビットマップを内部的に使用します。たとえば、PostgreSQLバージョン 8.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]!}}}$. ^{[28] [29]}

ビットマップ インデックス スキャンは、異なるインデックス上の式を組み合わせるため、テーブル上のすべての可能なクエリをサポートするには、列ごとに 1 つのインデックスのみが必要です。

このアクセス戦略を B ツリー インデックスに適用すると、複数の列の範囲クエリを組み合わせることもできます。このアプローチでは、テーブルの各行 に 1ビットの一時的なメモリ内ビットマップが作成されます (したがって、1 MB で800 万を超えるエントリを格納できます)。次に、各インデックスの結果がビット単位の演算を使用してビットマップに結合されます。すべての条件が評価された後、ビットマップには、式に一致する行に対して "1" が含まれます。最後に、ビットマップがトラバースされ、一致する行が取得されます。これにより、インデックスが効率的に結合されるだけでなく、すべての行がメイン テーブルから順番にフェッチされるため、テーブル アクセスの参照の局所性も向上します。 ^[30]内部ビットマップはクエリ後に破棄されます。テーブルに行が多すぎて 1 行あたり 1 ビットを使用できない場合は、代わりにディスク ページあたり 1 ビットの "損失のある" ビットマップが作成されます。この場合、ビットマップはフェッチするページを決定するためだけに使用され、一致するページのすべての行にフィルター基準が適用されます。

注記

文献

• O'Connell, S. (2005). 「Advanced Databases Course Notes」.サウサンプトン：サウサンプトン大学. {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• O'Neil, P.; O'Neil, E. (2001). 「データベースの原則、プログラミング、およびパフォーマンス」サンフランシスコ: Morgan Kaufmann Publishers。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• Zaker, M.; Phon-Amnuaisuk, S.; Haw, SC (2008). 「大規模データ ウェアハウス システムの適切な設計: ビットマップ インデックスと B ツリー インデックス」(PDF) . International Journal of Computers and Communications . 2 (2) . 2010-01-07に取得。