従来の行モード 実行プランでは、SQL Serverは、初期の半結合削減の実行の一部としてビットマップ演算子を導入する場合があります。 並列ハッシュまたはマージ結合の前。ビットマップはビルド入力から作成され、結合に到達する前にプローブ入力の行をフィルタリングするために使用されます。 行モードについて書きました 以前のビットマップとそれらもドキュメントでカバーされています。
この記事はバッチモードについてです 非常に異なる実装を持つビットマップ。 SQL Server 2012にバッチモード実行エンジンが最初に登場して以来、大幅な改善が行われています。ここに記載されている詳細は、執筆時点で最新のリリースバージョンであるSQLServer2017に適用されます。以前のバージョンに固有の機能については、今後インラインで説明します。
バッチモードで実行できる唯一の結合演算子は、ハッシュ結合です。クエリオプティマイザは、バッチモードのハッシュ結合（シリアルまたはパラレル）にビットマップを含めるかどうかを決定します。オプティマイザは、仮想の半結合の選択性を計算することにより、ビットマップの潜在的な有用性を評価します。 結合キーのハッシュ結合入力の数。
ビットマップフィルタリングの機能は、ビルド側に存在しない行をプローブ側から削除することであるため、セミ結合は理にかなっています。セミジョインの推定選択性が0.75の場合 以下の場合、オプティマイザはバッチモードのビットマップフィルタを使用する価値があると見なします。つまり、セミ結合の計算で、プローブ側の行の25％以上がビットマップによって削除されることが示された場合、ビットマップが指定されます。
正確な半結合の選択性は、ハッシュ結合にビットマップが必要かどうかを判断するためにのみ使用されます。プローブ側の選択性の推定値（カーディナリティの推定値への影響として表示）は、修飾されていない行を削除する際にビットマップが一般的に完全ではないという事実を反映するように変更されます。これは特に、ブルームフィルターを使用してビットマップが実装されている場合に当てはまります。これにより、誤検知が発生する可能性があります（プローブ側の行はフィルターを通過しますが、ビルド側とは結合しません）。
オプティマイザは、セミジョインの選択性を10の累乗に丸めることにより、この不確実性を考慮に入れます。これは、丸める前に10を底とする対数を取ることによって行われます。たとえば、半結合の選択性が0.316の場合、log 10が得られます。 値は-0.5をわずかに下回り、-1に切り捨てられます。結果として得られるプローブ側の選択性は10=0.1です。対照的に、0.317の半結合選択性はlog 10を与えます -0.5のすぐ上の値。これはゼロに丸められます。したがって、プローブ側の選択性は10 =1です（すべての行が合格）。この一連の計算から得られる可能性のあるプローブ側のビットマップ選択性は、1、0.1、0.01、0.001などです。推定された選択性が1に切り上げられた場合でも、ビットマップが使用される可能性があることに注意してください（すべての行が述語を通過します）。
個別のビットマップはありません バッチモードハッシュ結合の演算子。代わりに、ハッシュ結合演算子にはビットマップクリエーターがあります。 プロパティ（trueに設定）、またはプロパティがありません（falseに設定されていません）。行モードとバッチモードの実行のこの違いにより、ビットマップが作成されているかどうかを確認するのは簡単ではありませんが、基になるプロセスをより正確に反映します。行モードの実行では、ビットマップ 演算子は、ハッシュ結合ビルド入力に到達する前に、行が1つずつ流れるときにビットマップにデータを入力します。言い換えると、ビットマップとハッシュテーブルは、行モードの実行で同時に構築されます。バッチモードでは、ビットマップが作成される前にハッシュテーブルが完全に構築されます（これについては後ほど詳しく説明します）。
クエリオプティマイザは、ハッシュ結合のプローブ側でのバッチモードビットマップフィルタの位置について、コストベースの選択を行いません。ビットマップの選択性がプローブ側のすべての子演算子に適用されることを単に想定しています。実際には、オプティマイザによって単一の最終実行プランが選択されると、ビットマップはプローブ側にプッシュダウンされます。ビットマップをリーフ演算子まで完全にプッシュできない場合、カーディナリティの推定値は少し奇妙に見えます。これは、将来改善される可能性のあるトレードオフです。
オプティマイザがかどうかを決定している間 ハッシュ結合バッチモードビットマップを使用するかどうかに関係なく、バッチモード実行エンジンがタイプを決定します。 実行時に使用するビットマップの。この決定は、ハッシュテーブルのビルド中にビルド側の結合キーについて収集された統計情報によって通知されます。前述のように、行モードの実行とは対照的に、バッチモードのハッシュ結合は、ビットマップを構築するためにハッシュテーブルを個別にパスする前に、最初にハッシュテーブルを完全に構築します。
バッチモードのハッシュ結合ビットマップには、主に2つのタイプがあります。 シンプル ビットマップには、ビルド側の値の連続する範囲ごとに1ビットが含まれます。たとえば、1バイトの単純なビットマップは、8つの連続するビルド側の値が存在するかどうかを示すことができます。対応するビットを設定することにより、0から7までの値をビットマップにエンコードできます。値5は、位置値2のビット5を設定します。セット{1、5、7}を2 + 2 + 2 =2 + 32 + 128 =162 =10100010 2<としてエンコードできます。 / sub> 。ゼロから始まらない値の範囲は、セットに存在する最小値（ハッシュテーブルの統計からわかる）ですべての値をオフセットすることにより、同じ方法でエンコードできます。
単純なビットマップには、正確なを保存できるという利点があります。 範囲に比例したメモリを必要とする代わりに、実際に存在するビルド側の値に関する情報 存在する値の数。
2番目のタイプのビットマップはブルームフィルターです。これにより、各ビルド側の値に1つ以上のハッシュ関数を適用した結果に応じて、ビットマップ構造に1つ以上のビットが設定されます。各プローブ側の値に同じハッシュ関数を適用して、一致をテストします。ハッシュ関数のいずれかが設定されていないビットを識別する場合、現在のプローブ値がビルド側に表示されないことを確認できます。
ブルームフィルターは確率的構造であるため、ビルド側の一致がない一部のプローブ値（偽陽性）をフィルターで除外しない場合がありますが、存在する値（偽陰性）をフィルターで除外することはありません。言い換えると、ブルームフィルターは、「おそらく一致する」または「完全に一致しない」のいずれかを示します。誤検知の割合は、キーあたりのビット数を増やす（ビットマップを大きくする）か、ハッシュ関数を増やすことで減らすことができます。明確にするために、ブルームフィルターは 正確なフィルタリングを生成しますが、そうでない場合もあります。
ブルームフィルターは、単純なビットマップの場合、スペースと時間の効率に優れた代替手段を提供します。 スペース要件のために実行不可能です。ブルームフィルターのSQLServerバッチモード実装は、最新のCPUキャッシュアーキテクチャ用に最適化されており、内部的には複雑なビットマップとして知られています。 。複雑なビットマップは、SQL Server 2014以降、複数の結合列とすべてのバッチモードデータ型をサポートしています。
SQLServerがシンプルを選択するかどうか または複雑 （ブルームフィルター）ビットマップは範囲に依存します ビルド側の値の（ハッシュテーブル統計から）。ここで「範囲」という言葉には重要な注意事項があります。これについては、次のセクションで説明します。一方、これは実行エンジンがビットマップのタイプを選択する方法です：
- 小さなシンプルなビットマップ 値の範囲が2（8,388,608）以下の場合に使用されます。これは1MBのビット数です。
- 値の範囲が2より大きく2（8MB）以下の場合、実行エンジンは大きな単純なビットマップから選択します。 および複雑なビットマップ 各オプションに必要なメモリを計算し、小さい方を選択します。大きな単純なビットマップのサイズは最大8MBです。複雑なビットマップのサイズは、データを適切に表すために必要なキーあたりのビット数によって異なります。通常、より明確な値は、より大きな複雑なビットマップを意味します。
- 値の範囲が2ビットを超える場合、複雑なビットマップ 使用されます。
範囲 上記の値の内訳は、内部のバイナリに基づいています。 データの表現。たとえば、smallint 値128および255は、0x0080として表される場合があります。 および0x00FF 、0x7Fの範囲を指定します （127）バイナリ値。この範囲は、小さな単純なビットマップでうまく機能します。
一方、datetime 値「1900-01-01」および「1900-01-02」は、8バイトで0x0000000100000000として表される場合があります。 および0x0000000200000000 （日は4バイト、深夜以降のティックは4バイト）。このセグメント化された表現は、0x0100000000のバイナリ範囲を提供します （4,294,967,296）これらの2つの値の例では、大きすぎて単純なビットマップ（大きなものでも）に収まりません。複雑なバイナリ表現（バイトスワッピングなど）を持つデータ型は、通常、単純なビットマップではうまく機能しません。
さらに複雑なのは、バッチモードデータが正規化されることです。 —ベクトル化された命令で適切に機能するバイナリレイアウトに変換されます—サイズは常に64ビットです。 64ビットに収まらない値は、行内の64ビットポインタとともに「行外」に格納されます。このバイナリレイアウトは、T-SQLからバイナリタイプへの変換で報告されたものと同じではありません。
それでも、正規化されたレイアウトは整数型（integerなど）に対して十分に類似しています。 およびbigint ）単純なビットマップは、これらのデータ型の範囲に引き続き役立ちます。整数のようなバイナリ表現を持つ他のタイプ（例：money およびdate ）も適しています。
もう1つの例：integerのセット 1〜8,388,608の範囲の値はちょうど 範囲内の可能な整数値ごとに1ビットを使用して、1MBの小さな単純なビットマップに収まります。範囲には固定オフセットがある場合があるため、10,000,000〜18,388,607の整数範囲も適合します（オフセットは1,000万）。 番号に注意してください 存在する値の数は重要ではなく、範囲だけが重要です。 0と8,388,607の2つの値は、これら2つの極値の間のすべての可能な値のセットと同様に、小さな単純なビットマップ範囲を埋めます。
バッチモード実行エンジンがラージシンプルを構築することを決定したとき ビットマップまたは複合体 ハッシュ結合のビットマップであり、範囲テーブルも作成します。 ありません 小さいの範囲テーブルを作成する 単純なビットマップ。
範囲テーブルは、ハッシュテーブルに存在する値の（低、高）範囲を指定する8バイト値の8,192ペアで構成される固定サイズの128KB構造です。範囲テーブルは、バッチモードの実行と互換性のある任意のデータ型で作成できます。完成したハッシュテーブルのスキャン中に、データの各バッチを使用してビットマップにデータを入力します 範囲テーブル。
バッチ内の値ごとに、ハッシュ関数を使用して、範囲テーブル内のバケット（範囲値のペア）を検索します。バケットが現在使用されていない場合、値は8バイトの下限値と上限値の両方に格納されます。バケットがすでに使用されている場合は、代わりに次のバケットがいっぱいになります（空のバケットが見つかるまで、以下同様に続きます）。
範囲テーブルが3分の1いっぱいになると（8,192バケットのうち2,730が使用されます）、使用されたエントリがコピーされ、バケット範囲が2倍になり、保存された値が以前と同じ方法で再挿入されます（ただし、ハッシュ関数は考慮されます）新しいバケットサイズ）。重複するバケットはすべてマージされ、使用されるバケットの数が2,730を下回るまで、2倍のプロセスが続行されます。たとえば、最初に「範囲」（1-1）と（2-2）を含む2つのバケットは、最初の範囲が2倍になった後、（1-2）の単一の範囲バケットにマージできます。
ハッシュテーブルデータのすべてのバッチが範囲テーブルに処理されると、最後のバケットマージが実行され、インプレースクイックソートによってバケットが値順に並べられます。これにより、特定の対象値が指定された範囲バケットをバイナリ検索で見つけることができます。
このすべてのアクティビティの最終的な結果は、ハッシュテーブル内のデータを説明する最大2,730の異なる範囲のセットを生成することです（大きな単純または複雑なビットマップに加えて）。
範囲テーブルは、ハッシュ結合ビットマップフィルターがプローブ側の列ストアスキャンオペレーターにプッシュダウンされるときに使用されます。各列ストアセグメントには、セグメントに存在する最小および最大データ値に関するカタログメタデータがあります。実行エンジンは、この情報を使用して、ビットマップ範囲テーブルで一致するものをバイナリ検索できます。一致するものが見つからない場合、実行エンジンはセグメントを完全にスキップできます。
この実行時の最適化は先読みに対しても行われるため、エンジンは、範囲テーブルフィルターによって削除されることがわかっているセグメントをメモリに読み取ることを回避することもできます。範囲テーブルによって削除されないセグメントは、ビットマップを使用して引き続きフィルタリングされます。この組み合わせにより、最大数の行ができるだけ早く削除されます。
範囲テーブルは小さな単純なビットマップ用に作成されていませんが、値の範囲（オフセットを含む）がわかっているため、その構造を使用してセグメントを削除することもできます。射表を使用してサブレンジに分割する価値がないほど小さいです。
ビットマップが列ストアスキャンにプッシュダウンされていない場合でも、ハッシュ結合の前に半結合の削減を実現するために、通常のバッチモードフィルターとして評価できます。これは、列ストアスキャン中のセグメントの削除やフィルタリングよりもはるかに効率的ではありませんが、ハッシュ結合自体でフィルタリングするよりも優れています。
スキャンの一部として列ストアデータにハッシュ結合バッチモードビットマップを適用すると、非常に優れたパフォーマンスが得られますが、ビットマップを適用する前に、不純なセグメントデータを解凍する必要があります。この解凍はSIMD命令を使用して効率的に実行できますが、それでも余分な作業です。
SQL Server 2016では、辞書でエンコードされたセグメントデータの一般的な述語のビットマップを作成する機能が導入されました。述語は辞書エントリに対して評価され、新しいが生成されます。 各セットビットが述語を満たす辞書エントリを示す小さなビットマップ。このビットマップの適用は、特にビットマップが単一のSIMDレジスタに収まる場合、非常に高速になる可能性があります。ビットマップが収まらない場合でもSQLServerはSIMDを使用できますが、メモリ内のビットマップからビットを収集することは、レジスタ内の場合よりも少し効率が悪くなります。
この2016年の最適化は、すべてに適用できます。 上流のハッシュ結合によって作成されたビットマップ「述語」を含む、列ストアスキャンにプッシュされた述語。明確にするために、SQL Serverはハッシュ結合ビットマップを取得し、ディクショナリエントリを使用して新しい（はるかに小さい）ビットマップを作成します。この新しいビットマップは、解凍前にセグメントデータに適用されます。最適化は、拡張イベントcolumn_store_expression_filter_bitmap_setで監視できます。 。辞書ビットマップを使用する場合、イベントメンバーfilter_on_compressed_data_type メンバーが入力されます。通常、これには値RAWBITMAPが含まれます 。辞書ビットマップが単一の連続する値の範囲を表す場合、圧縮された辞書ビットマップを比較フィルターに変換するためのさらなる最適化が存在します。その場合、RAWBITMAP以外のものが表示されます。 （例：LTGT 比較よりも小さい/大きい場合）
列ストアスキャンでプッシュダウンフィルター（バッチモードハッシュ結合によって生成されたビットマップを含む）をビットマップにコンパイルする一般的な機能は、セッションレベルのトレースフラグ9361で無効にできます。特定の圧縮データビットマップの最適化は、セッションで無効にできます。レベルのトレースフラグ9362。単一の連続した範囲を持つ辞書ビットマップの比較フィルターへの変換は、トレースフラグ9363で無効にできます。残念ながら、バッチモードのビットマップまたはプッシュダウンフィルターに関する情報メッセージを報告するリテールビルドのトレースフラグはありません。コンパイル。
ハッシュ結合バッチモードビットマップに関する情報を生成する拡張イベントがいくつかあります。最も便利なものは次のとおりです。
-
query_execution_column_store_segment_scan_started -
query_execution_column_store_segment_scan_finished -
column_store_expression_filter_bitmap_set -
column_store_segment_eliminate
ハッシュ結合バッチモードのビットマップが列ストアスキャンにプッシュダウンされると、「開始された」イベントはBITMAP_SIMPLEを報告します またはBITMAP_COMPLEX filter_typeとして 。小さい単純なビットマップと大きい単純なビットマップを区別せず、範囲テーブルについて何も報告しません。拡張イベントメタデータには、column_store_filter_typeの他の値が含まれています BITMAP_SIMPLE_LARGEを含む 特に、大きな単純なビットマップが使用されている場合、拡張イベントは現在この出力を生成しません。おそらく、これは将来のリリースで修正されるでしょう。
グローバルトレースフラグ646を使用して、範囲テーブル（または小さな単純なビットマップ）によって有効にされたセグメント除去に関する情報をレポートできます。セグメントに同様の情報を報告し、拡張イベントを排除します。このセクションに記載されているすべてのトレースフラグは、文書化されておらず、サポートされていません。
バッチモードのビットマップは、正しいデータ型の場合に非常に効果的です。 （最大64ビットおよび整数のような）が使用され、特にセグメントデータがRLE圧縮（ピュアストレージ）を使用する場合、またはビットマップを辞書データ上の別のビットマップにコンパイルできる場合は、ビットマップを列ストアスキャンにプッシュダウンできます。
実行計画でハッシュ結合ビットマップに関するより詳細な情報が報告されていると便利な場合があります。少なくとも、作成されたビットマップのタイプは言うまでもありません。現状では、 Bitmap Creatorしかありません。 プロパティ、および操作するいくつかの拡張イベント。これにより、列ストアデータとバッチモードのハッシュ結合の実行エンジンに組み込まれているすべての巧妙な最適化を利用することでパフォーマンスが大幅に向上するため、詳細な計画分析が必要以上に難しくなります。
デモ、イラスト、およびこの記事で説明されている主なポイントの詳細については、私の個人サイトのバッチモードビットマップデモで入手できます。