Click here to view and discuss this page in DocCommentXchange. In the future, you will be sent there automatically.

SQL Anywhere 11.0.1 (日本語) » SQL Anywhere サーバ - SQL の使用法 » クエリ処理 » クエリの最適化と実行 » クエリ実行アルゴリズム » アルゴリズムの種類 » その他のアルゴリズム

 

ハッシュ・フィルタ・アルゴリズム (HF、HFP)

ハッシュ・フィルタは、ブルーム・フィルタとも呼ばれるデータ構造体で、単一カラムまたはカラム・セット内の値の分散を表します。ハッシュ・フィルタは、(長い) ビット文字列と考えることができます。1 ビットは特定のローが存在することを示し、0 ビットはそのビット位置にローがないことを示します。ローのセットからフィルタ内のビット位置に値をハッシュすることで、データベース・サーバは、(ハッシュの競合の有無に応じて) その値の一致するローがあるかどうかを判断できます。

次のプランを例にとります。

R<idx> *JH S<seq> JH* T<idx>

この例では、R を S と T にジョインします。データベース・サーバは、R のローをすべて読み込んでから、T のローを読み込みます。ハッシュ・フィルタがインデックス・スキャンによって返される R のローを使用して構築されている場合、データベース・サーバは、R とジョインできない T のローを直ちに拒否できます。このようにして、2 番目のハッシュ・ジョインで格納するローの数を減らすことができます。

ハッシュ・フィルタは、次の両方の条件を満たすクエリ内で使用できます。

  • クエリ内の操作が入力全体を読み込んでから、後の操作にローを返す場合。たとえば、1 つのカラムに基づいて 2 つのテーブルのハッシュ・ジョインを行うには、一方の入力のすべての関連するローを読み込み、ジョインのハッシュ・テーブルを作成する必要があります。

  • クエリのアクセス・プラン内の後続の操作が、その操作の結果内のローを参照する場合。たとえば、最初のジョインと同じカラムに基づく 2 つめのジョインは、最初のジョインを満たすローのみを使用します。

この場合、最初のジョインの結果として構築されたハッシュ・フィルタによって、2 つめのジョインのパフォーマンスが向上します。このとき、ハッシュ・フィルタのビット文字列内でルックアサイド操作が行われ、最初のジョインで正常に処理されたローがあるかどうかが確認されます。正常に処理されたローがない場合は、ハッシュ・フィルタ内に 1 ビットがなければ、2 つめのジョインでハッシュ・テーブルを調査しても一致するローは見つからないことがわかっているので、調査を完全に回避できます。