ヒストグラムの粗い配置を使用したSQLServerの結合推定

SQL Server 2014リリース以降に行われたカーディナリティ推定に加えられた主な変更は、Joe Sack、Yi Fang、およびVassilisPapadimosによるMicrosoftホワイトペーパー「SQLServer2014カーディナリティ推定を使用したクエリプランの最適化」で説明されています。

それらの変更の1つは、単純な結合の推定に関するものです。統計ヒストグラムを使用して、単一の等式または不等式の述語を使用します。「JoinEstimateAlgorithmChanges」という見出しのセクションで、このペーパーでは、最小および最大のヒストグラム境界を使用した「粗調整」の概念を紹介しました。

単一の等式または不等式述語を使用した結合の場合、レガシーCEは、線形補間を使用して2つのヒストグラムを段階的に整列させることにより、結合列のヒストグラムを結合します。この方法では、カーディナリティの推定に一貫性がなくなる可能性があります。したがって、新しいCEは、最小および最大のヒストグラム境界のみを使用してヒストグラムを整列させる、より単純な結合推定アルゴリズムを使用するようになりました。

一貫性は低い可能性がありますが、段階的なヒストグラムの位置合わせにより、レガシーCEはわずかに優れた単純結合条件の推定値を生成する可能性があります。新しいCEは、粗い配置を使用します。ただし、見積もりの差は十分に小さいため、プランの品質の問題が発生する可能性は低くなります。

この論文の技術レビュー担当者の1人として、この変更に関するもう少し詳細が役立つと思いましたが、それでは最終バージョンにはなりませんでした。この記事では、その詳細の一部を追加します。

粗いヒストグラムの位置合わせの例

粗い配置 ホワイトペーパーの例では、AdventureWorksサンプルデータベースのデータウェアハウスバージョンを使用しています。名前にもかかわらず、データベースはかなり小さいです。バックアップはわずか22.3MBで、約200MBに拡張されます。 AdventureWorksのインストールと構成のドキュメントページのリンクからダウンロードできます。

関心のあるクエリがFactResellerSalesに結合されますおよびFactCurrencyRate テーブル。

SELECT
    FRS.ProductKey,
    FRS.OrderDateKey,
    FRS.DueDateKey,
    FRS.ShipDateKey,
    FCR.DateKey,
    FCR.AverageRate,
    FCR.EndOfDayRate,
    FCR.[Date]
FROM dbo.FactResellerSales AS FRS
JOIN dbo.FactCurrencyRate AS FCR
    ON FCR.CurrencyKey = FRS.CurrencyKey;

これは単一の列での単純な等結合ですそのため、ヒストグラムの粗い配置を使用した結合カーディナリティと選択性の推定に適しています。

ヒストグラム

必要なヒストグラムは、CurrencyKeyに関連付けられています結合された各テーブルの列。 AdventureWorksDWデータベースの新しいコピーで、より大きなFactResellerSalesの既存の統計表はサンプルに基づいています。再現性を最大化し、詳細な計算を可能な限り簡単にする（スケーリングを回避する）ために、最初に行うことは、フルスキャンを使用して統計を更新することです。

UPDATE STATISTICS dbo.FactCurrencyRate WITH FULLSCAN;
UPDATE STATISTICS dbo.FactResellerSales WITH FULLSCAN;

これらのテーブルには、小さくてシンプルな maxdiff を作成するという、デモに適した利点があります。ヒストグラム：

DBCC SHOW_STATISTICS
    (FactResellerSales, CurrencyKey)
WITH HISTOGRAM;
 
DBCC SHOW_STATISTICS
    (FactCurrencyRate, [PK_FactCurrencyRate_CurrencyKey_DateKey])
WITH HISTOGRAM;

最小一致ヒストグラムステップの組み合わせ

粗調整の最初のステップ計算は、最も一致しないヒストグラムステップによって提供される結合カーディナリティへの寄与を見つけることです。ヒストグラムの例では、最小一致ステップ値はRANGE_HI_KEY = 6にあります。：

この強調表示されたステップの推定等結合カーディナリティは、1,713 * 1,158 =1,983,654行です。。

一致した残りのステップ

次に、ヒストグラムの範囲を特定する必要がありますRANGE_HI_KEY 可能な等結合一致の最大値までステップアップします。これには、ヒストグラム入力の1つが行を使い果たすまで、以前に見つかった最小値から前進することが含まれます。現在の例に一致する等結合範囲を以下に示します。

これらの2つの範囲は、等結合カーディナリティに寄与すると予想される残りの行を表します。

粗い周波数ベースの推定

問題は、粗いを実行する方法です。利用可能な情報を使用した、強調表示されたステップの等結合カーディナリティの推定。

元のカーディナリティ推定器は、線形補間を使用してきめ細かい段階的なヒストグラムの位置合わせを実行し、各ステップの結合の寄与を評価し（以前の最小ステップ値に対して行ったのと同じように）、各ステップの寄与を合計して、完全な参加の見積もり。この手順は多くの直感的な意味がありますが、実際の経験では、このきめ細かいアプローチにより計算のオーバーヘッドが追加され、さまざまな品質の結果が生成される可能性があります。

元の推定器には、ヒストグラム情報が利用できない場合、またはヒューリスティックに劣っていると評価された場合に、結合カーディナリティを推定する別の方法がありました。これは頻度ベースの推定と呼ばれ、次の定義を使用します。

C –カーディナリティ（行数）
D –個別の値の数
F –各個別の値の頻度（行数）
定義上、C =D*Fに注意してください

これらの各プロパティに対する関係R1とR2の等結合の効果は、次のとおりです。

F'=F1 * F2
D'=MIN（D1; D2）–封じ込めを想定
C'=D'* F'（これも定義上）

私たちは、等結合のカーディナリティであるC'の後にあります。式のD'とF'を代入し、展開します：

C'=D'* F '
C'=MIN（D1; D2）* F1 * F2
C'=MIN（D1 * F1 * F2; D2 * F1 * F2）
ここで、C1 =D1 * F1、およびC2 =D2 * F2なので、次のようになります。
C'=MIN（C1 * F2、C2 * F1）
最後に、F =C / D（これも定義による）なので：
C'=MIN（C1 * C2 / D2; C2 * C1 / D1）

C1 * C2は2つの入力カーディナリティ（デカルト結合）の積であることに注意してください。これらの式の最小値は、個別の値の数が多い式になることは明らかです。

C'=（C1 * C2）/ MAX（D1; D2）

これがすべて少し抽象的なように思われる場合、頻度ベースの等結合推定について考える直感的な方法は、一方の関係からの各個別の値が、もう一方の関係のいくつかの行（平均頻度）と結合することを考慮することです。片側に5つの異なる値があり、反対側のそれぞれの異なる値が平均して3回表示される場合、適切な（ただし粗い）等結合推定値は5 * 3=15です。

これは、見た目ほど幅広いブラシではありません。上記のカーディナリティと個別の値の数値は、関係全体からではなく、最小値を超える一致するステップからのみ得られることを覚えておいてください。したがって、最小値と最大値の間の大まかな見積もり。

周波数計算

強調表示されたヒストグラムのステップから、これらの各パラメーターを取得できます。

カーディナリティC EQ_ROWSの合計ですおよびRANGE_ROWS 。
個別の値の数D DISTINCT_RANGE_ROWSの合計ですプラス各ステップに1つ。

一致するFactResellerSalesのカーディナリティC1 ステップは、強調表示されたセルの合計です：

これにより、 C1 =59,142 行。

明確な範囲の行はないため、明確な値は4つのステップ境界自体から取得され、 D1 =4になります。。

2番目の表の場合：

これにより、 C2 =9,632 。ここでも、明確な範囲の行がないため、明確な値は10ステップの境界（ D2 =10 ）から取得されます。

EquijoinEstimateの完了

これで、等結合式に必要なすべての数値が得られました。

C'=（C1 * C2）/ MAX（D1; D2）
C'=（59142 * 9632）/ MAX（4; 10）
C'=569655744/10
C'= 56,965,574.4

これは、最小一致境界を超えるヒストグラムステップの寄与であることを忘れないでください。結合カーディナリティの推定を完了するには、最小一致ステップ値からの寄与を追加する必要があります。これは、1,713 * 1,158 =1,983,654行です。

したがって、最終的な等結合の推定値は、56,965,574.4 + 1,983,654=58,949,228.4行または58,949,200 有効数字6桁まで。

この結果は、ソースクエリの推定実行プランで確認されます：

ホワイトペーパーに記載されているように、これは大きな見積もりではありません。このクエリによって返される実際の行数は70,470,090です。。元の（「レガシー」）カーディナリティ推定器によって生成された推定値は、段階的なヒストグラムの配置を使用して、70,470,100行です。

多くの場合、より細かい方法でより良い結果が得られますが、それは統計が基礎となるデータ分布の非常に優れた表現である場合に限られます。これは、単に統計を最新の状態に保つことや、フルスキャンの母集団を使用することの問題ではありません。情報を最大201のヒストグラムステップにパックするために使用されるアルゴリズムは完全ではなく、いずれの場合でも、多くの実際のデータ分布は、そのようなヒストグラムの忠実度を実現できません。平均して、人々は、より粗い方法が完全に適切な推定を提供し、新しいCEでより高い安定性を提供することに気付くはずです。

2番目の例

これは前の例に少し基づいており、サンプルのデータベースをダウンロードする必要はありません。

DROP TABLE IF EXISTS
    dbo.R1,
    dbo.R2;
 
CREATE TABLE dbo.R1 (n integer NOT NULL);
CREATE TABLE dbo.R2 (n integer NOT NULL);
 
INSERT dbo.R1
    (n)
VALUES
    (1), (2), (3), (4), (5), (6), (7), (8), (9), (10),
    (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), 
    (6), (6), (6), (6), (6), (6), (6), (6), (6);
 
INSERT dbo.R2
    (n)
VALUES
    (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15),
    (10), (10);
 
CREATE STATISTICS stats_n ON dbo.R1 (n) WITH FULLSCAN;
CREATE STATISTICS stats_n ON dbo.R2 (n) WITH FULLSCAN;

一致した最小ステップを示すヒストグラムは次のとおりです。

最も低いRANGE_HI_KEY 一致するのは5です。EQ_ROWSの値は両方とも1であるため、推定される等結合カーディナリティは1 * 1 =1行です。。

最も一致するRANGE_HI_KEY は10です。粗い頻度ベースの推定のためにR1ヒストグラムの行を強調表示します：

EQ_ROWSの合計およびRANGE_ROWS C1 =24を与えます。個別の行の数は2DISTINCT_RANGE_ROWSです。（ステップ間の個別の値）プラス各ステップの境界に関連付けられた個別の値の3、 D1 =5 。

R2の場合、EQ_ROWSを合計します。およびRANGE_ROWS C2 =7を与えます。個別の行の数は2DISTINCT_RANGE_ROWSです。（ステップ間の個別の値）プラス各ステップの境界に関連付けられた個別の値の3、 D2 =5 。

等結合推定C'は次のとおりです。

C'=（C1 * C2）/ MAX（D1; D2）
C'=（24 * 7）/ 5
C'= 33.6

1行に追加最小ステップ一致から、合計で34.6行の推定値が得られます。等結合の場合：

SELECT
    R1.n,
    R2.n
FROM dbo.R1 AS R1
JOIN dbo.R2 AS R2
    ON R2.n = R1.n;

見積もり実行計画は、私たちの計算と一致する見積もりを示しています：

これは正確には正しくありませんが、「レガシー」カーディナリティ推定器は、実際の27行に対して15.25行を推定します。

完全な処理を行うには、ヒストグラムのヌルステップの一致による最終的な寄与も追加する必要がありますが、これは等結合（通常はヌルを拒否するように記述されている）では一般的ではなく、関心のある読者にとっては比較的簡単な拡張です。

最終的な考え

うまくいけば、記事の詳細が「粗い配置」について疑問に思ったことのある人のためにいくつかのギャップを埋めるでしょう。これは、カーディナリティ推定器の1つの小さなコンポーネントにすぎないことに注意してください。結合の推定に使用される他のいくつかの重要な概念とアルゴリズムがあります。特に、非結合述語を評価する方法、およびより複雑な結合を処理する方法があります。本当に重要な部分の多くは、ホワイトペーパーでかなりよくカバーされています。