SQL Serverはいつ巻き戻しをソートしますか？

はじめに

巻き戻し ネストされたループの内側の演算子は、結合または適用されます。アイデアは、実行計画の一部から以前に計算された結果を安全に再利用することです。

巻き戻すことができるプラン演算子の標準的な例は、怠惰なテーブルスプールです。。その存在理由 プランサブツリーから結果行をキャッシュし、相関するループパラメータが変更されていない場合は、後続の反復でそれらの行を再生します。行の再生は、行を生成したサブツリーを再実行するよりも安価な場合があります。これらのパフォーマンススプールの背景については以前の記事を参照してください。

ドキュメントには、次のオペレーターのみが巻き戻すことができると記載されています：

テーブルスプール
行数スプール
非クラスター化インデックススプール
テーブル値関数
並べ替え
リモートクエリ
アサート およびフィルター スタートアップ式を持つ演算子

最初の3つのアイテムは、ほとんどの場合パフォーマンススプールですが、他の理由で導入される可能性があります（熱心で怠惰な場合）。

テーブル値関数 適切な状況で結果をキャッシュおよび再生するために使用できるテーブル変数を使用します。テーブル値関数の巻き戻しに興味がある場合は、データベース管理者のStackExchangeに関するQ＆Aをご覧ください。

これらが邪魔にならないように、この記事はソートについてのみ説明しています。そしていつ巻き戻すことができるか。

巻き戻しの並べ替え

ソートはストレージ（メモリと、こぼれた場合はディスク）を使用するため、対応機能があります。ループの反復の間に行を格納します。特に、ソートされた出力は、原則として再生（巻き戻し）できます。

それでも、タイトルの質問に対する簡単な答えは、「ソートは巻き戻しますか？」です。は：

はい。ただし、あまり頻繁には表示されません。

ソートタイプ

並べ替えには内部でさまざまな種類がありますが、現在の目的では2つしかありません。

インメモリソート （CQScanInMemSortNew ）。
- 常にメモリ内。 こぼれない ディスクに。
- 標準ライブラリのクイックソートを使用します。
- 最大500行 および2つの8KBページ 合計で。
- すべての入力は実行時定数である必要があります。通常、これは、並べ替えサブツリー全体がのみで構成されている必要があることを意味します コンスタントスキャン および/またはComputeScalar 演算子。
- 実行計画で明示的に区別できるのは、詳細なショープランの場合のみです。有効になっています（トレースフラグ8666）。これにより、並べ替えに追加のプロパティが追加されます演算子。そのうちの1つは「InMemory=[0|1]」です。
他のすべての種類。

（両方のタイプの並べ替え 演算子には、トップNソートを含めますおよび個別の並べ替え バリアント）。

巻き戻し動作

インメモリソート いつでも巻き戻すことができます 安全なとき。相関ループパラメータがない場合、またはパラメータ値が直前の反復から変更されていない場合、このタイプの並べ替えでは、実行プランでその下の演算子を再実行する代わりに、保存されているデータを再生できます。
非メモリソート 巻き戻すことができます 安全な場合、ただし並べ替えの場合のみ演算子には最大1行が含まれます。 並べ替えに注意してください入力は、一部の反復で1つの行を提供する場合がありますが、他の反復では提供しません。したがって、実行時の動作は、巻き戻しと再バインドの複雑な組み合わせになる可能性があります。 並べ替えに提供される行数に完全に依存します実行時の各反復で。一般に、並べ替えが何であるかを予測することはできません。実行計画を検査することにより、各反復で実行します。

上記の説明で「安全」という言葉は、パラメータの変更が発生しなかったか、並べ替えの下に演算子がないことを意味します。変更された値の依存関係があります。

実行計画に関する重要な注意事項

実行計画は、並べ替えの巻き戻し（および再バインド）を常に正しく報告するとは限りません。演算子。オペレーターは報告します相関するパラメータが変更されていない場合は巻き戻し、変更されていない場合は再バインドします。

メモリ内以外のソート（最も一般的なもの）の場合、報告された巻き戻しは、ソート出力バッファーに最大で1つの行がある場合にのみ、保存されたソート結果を実際に再生します。それ以外の場合、並べ替えはレポート 巻き戻しますが、サブツリーは引き続き完全に再実行されます （再バインド）。

報告された巻き戻しが実際の巻き戻しであった回数を確認するには、実行回数を確認してください。 並べ替えの下の演算子のプロパティ。

歴史と私の説明

並べ替え オペレーターの巻き戻し動作は奇妙に思えるかもしれませんが、（少なくとも）SQLServer2000からSQLServer2019（およびAzure SQL Database）まではこのようになっています。公式の説明やドキュメントを見つけることができませんでした。

私の個人的な見解は、並べ替え 巻き戻しは、流出設備を含む基盤となる仕分け機構と、 tempdb でのシステムトランザクションの使用により、かなり費用がかかります。。

ほとんどの場合、オプティマイザーは明示的なパフォーマンススプールを導入する方が適切です。相関ループパラメータが重複している可能性を検出したとき。スプールは、部分的な結果をキャッシュするための最も費用のかからない方法です。

可能 並べ替えを再生する結果は、スプールよりも費用対効果が高いだけです。 並べ替え 最大で1行が含まれます。結局のところ、1つの行を並べ替える（または行を並べ替えない！）ことは、実際にはまったく並べ替えを伴わないため、オーバーヘッドの多くを回避できます。

純粋な憶測ですが、誰かが尋ねなければならなかったので、そこにあります。

デモ1：不正確な巻き戻し

この最初の例では、2つのテーブル変数を使用しています。最初の値には、列c1に3回複製された3つの値が含まれています。 2番目のテーブルには、c2 = c1の一致ごとに2つの行が含まれています。一致する2つの行は、列c3の値によって区別されます。。

タスクは、2番目のテーブルからc3が最も高い行を返すことです。 c1 = c2の各一致の値。コードはおそらく私の説明よりも明確です：

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
INSERT @T2 
    (c2, c3)
VALUES
    (1, 1),
    (1, 2),
    (2, 3),
    (2, 4),
    (3, 5),
    (3, 6);
 
SELECT
    T1.c1,
    CA.c2,
    CA.c3
FROM @T1 AS T1
CROSS APPLY
(
    SELECT TOP (1)
        T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

NO_PERFORMANCE_SPOOL オプティマイザがパフォーマンススプールを導入するのを防ぐためのヒントがあります。これは、テーブル変数で発生する可能性があります。トレースフラグ2453が有効になっているか、テーブル変数の遅延コンパイルが使用可能であるため、オプティマイザはテーブル変数の真のカーディナリティを確認できます（値の分布は確認できません）。

クエリ結果には、c2が表示されますおよびc3 返される値は、個別のc1ごとに同じです。値：

クエリの実際の実行プランは次のとおりです。

c1 順番に表示された値は、前の反復と6回一致し、3回変化します。 並べ替え これを6回の巻き戻しと3回の再バインドとして報告します。

これが当てはまる場合、テーブルスキャン 3回しか実行されません。 並べ替え 他の6回は結果を再生（巻き戻し）します。

そのまま、テーブルスキャンを見ることができますテーブル@T1の各行に1回ずつ、合計9回実行されました。。 ここでは巻き戻しは発生しませんでした 。

デモ2：巻き戻しの並べ替え

前の例では、並べ替えは許可されていません（a）インメモリソートではないため、巻き戻します; （b）ループの各反復で、並べ替え 2つの行が含まれていました。プランエクスプローラーには、テーブルスキャンからの合計18行が表示されます。、9回の反復ごとに2行。

ここで例を微調整して、1つだけになるようにします。テーブル@T2の行 @T1からの一致する行ごとに：

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
-- Only one matching row per iteration now
INSERT @T2 
    (c2, c3)
VALUES
    --(1, 1),
    (1, 2),
    --(2, 3),
    (2, 4),
    --(3, 5),
    (3, 6);
 
SELECT
    T1.c1,
    CA.c2,
    CA.c3
FROM @T1 AS T1
CROSS APPLY
(
    SELECT TOP (1)
        T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

c3列で最も高くソートされた一致する行を保持したため、結果は前に示したものと同じです。。実行計画も表面的には似ていますが、重要な違いがあります：

並べ替えに1行あり相関パラメータc1の場合、いつでも巻き戻すことができます。変わりません。 テーブルスキャン 結果として3回しか実行されません。

並べ替えに注意してください より多くの行を生成します （9）受け取るより（3）。これは、並べ替えが結果セットを1回以上キャッシュし、巻き戻しに成功しました。

デモ3：何も巻き戻さない

先ほど、メモリ内にない並べ替えについて説明しました。最大が含まれている場合に巻き戻すことができます 1行。

ゼロ行で動作していることを確認するには、OUTER APPLYに変更しますテーブル@T2には行を入れないでください。間もなく明らかになる理由により、列c2の投影も停止します。：

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
-- No rows added to table @T2
 
-- No longer projecting c2
SELECT
    T1.c1,
    --CA.c2,
    CA.c3
FROM @T1 AS T1
OUTER APPLY
(
    SELECT TOP (1)
        --T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

結果にはNULLが含まれるようになりました列c3 予想通り：

実行計画は次のとおりです。

並べ替え バッファに行がない状態で巻き戻すことができたため、テーブルスキャン 列c1ごとに3回だけ実行されました値を変更しました。

デモ4：最大巻き戻し！

巻き戻しをサポートする他の演算子と同様に、並べ替え 再バインドのみ相関パラメータが変更された場合はそのサブツリーおよび サブツリーはその値に何らかの形で依存しています。

列c2を復元していますデモ3への投影では、これが実際に動作していることが示されます：

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
-- Still no rows in @T2
-- Column c2 is back!
SELECT
    T1.c1,
    CA.c2,
    CA.c3
FROM @T1 AS T1
OUTER APPLY
(
    SELECT TOP (1)
        T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

結果には、2つのNULLが表示されます。もちろん列：

実行計画はまったく異なります：

今回は、フィルター チェックT2.c2 = T1.c1が含まれています、テーブルスキャンを作成します独立相関パラメータc1の現在の値の。 並べ替え 安全に8回巻き戻すことができます。つまり、スキャンは1回だけ実行されます。。

デモ5：インメモリソート

次の例は、メモリ内の並べ替えを示しています。演算子：

DECLARE @T table (v integer NOT NULL);
 
INSERT @T 
    (v)
VALUES 
    (1), (2), (3), 
    (4), (5), (6);
 
SELECT 
    T.v,
    OA.i 
FROM @T AS T
OUTER APPLY
(
    SELECT TOP (1) 
        X.i 
    FROM 
    (
        VALUES
            (REPLICATE('Z', 1390)),
            ('0'), ('1'), ('2'), ('3'), ('4'), 
            ('5'), ('6'), ('7'), ('8'), ('9')
    ) AS X (i)
    ORDER BY NEWID()
) AS OA
OPTION (NO_PERFORMANCE_SPOOL);

得られる結果は実行ごとに異なりますが、例を次に示します。

興味深いのは、列iの値です。 ORDER BY NEWID()にもかかわらず、常に同じになります条項。

おそらく、これの理由は並べ替えであるとすでに推測しているでしょう。結果のキャッシュ（巻き戻し）。実行プランには、コンスタントスキャンが表示されます。 1回だけ実行し、合計11行を生成します：

この並べ替え Compute Scalarしかありませんおよびコンスタントスキャン 入力に演算子があるため、メモリ内ソート 。これらは最大で1行に限定されるものではなく、500行と16KBを収容できることを忘れないでください。

前述のように、並べ替えかどうかを明示的に確認することはできません。 インメモリですまたは、定期的な実行計画を検査することによってではありません。 詳細なshowplan出力が必要です、文書化されていないトレースフラグ8666で有効になります。これを有効にすると、追加のオペレータプロパティが表示されます：

文書化されていないトレースフラグを使用することが現実的でない場合は、並べ替え 入力メモリの割合による「InMemory」です。ゼロであり、メモリ使用量 実行後のshowplanで使用できない要素（その情報をサポートするSQL Serverバージョンの場合）

実行プランに戻る：相関パラメーターがないため、並べ替え は5回自由に巻き戻すことができます。つまり、コンスタントスキャン 一度だけ実行されます。 TOP (1)を自由に変更してください TOP (3)へまたはあなたが好きなものは何でも。巻き戻しとは、入力行ごとに結果が同じ（キャッシュ/巻き戻し）になることを意味します。

ORDER BY NEWID()に悩まされるかもしれません巻き戻しを妨げない条項。これは確かに物議を醸すポイントですが、種類に限定されるものではありません。より完全な議論（警告：うさぎの穴の可能性）については、このQ＆Aを参照してください。短いバージョンでは、これは意図的な製品設計の決定であり、パフォーマンスを最適化しますが、時間の経過とともに動作をより直感的にする計画があります。

デモ6：メモリ内ソートなし

これはデモ5と同じですが、複製された文字列が1文字長くなります。

DECLARE @T table (v integer NOT NULL);
 
INSERT @T 
    (v)
VALUES 
    (1), (2), (3), 
    (4), (5), (6);
 
SELECT 
    T.v,
    OA.i 
FROM @T AS T
OUTER APPLY
(
    SELECT TOP (1) 
        X.i 
    FROM 
    (
        VALUES
            -- 1391 instead of 1390
            (REPLICATE('Z', 1391)),
            ('0'), ('1'), ('2'), ('3'), ('4'), 
            ('5'), ('6'), ('7'), ('8'), ('9')
    ) AS X (i)
    ORDER BY NEWID()
) AS OA
OPTION (NO_PERFORMANCE_SPOOL);

繰り返しますが、結果は実行ごとに異なりますが、ここに例を示します。 iに注意してください値がすべて同じではなくなりました：

余分な文字は、ソートされたデータの推定サイズを16KB以上にプッシュするのに十分です。これは、インメモリソートを意味します使用できず、巻き戻しが消えます。

実行計画は次のとおりです。

並べ替え まだレポート 5巻き戻しますが、コンスタントスキャン は6回実行されます。つまり、巻き戻しは実際には発生しません。 6回の実行ごとに11行すべてが生成され、合計66行になります。

まとめと最終的な考え

並べ替えは表示されませんオペレーター本当に 非常に頻繁に巻き戻しますが、「行った」と表示されます かなりたくさん。

覚えておいてください、通常の並べ替え 安全な場合にのみ巻き戻すことができます一度にソートには最大1つの行があります。「安全」であるということは、ループ相関パラメータに変更がないか、並べ替えより下にないことを意味します。パラメータの変更の影響を受けます。

インメモリソート コンスタントスキャンから供給された最大500行と16KBのデータを操作できますおよびComputeScalar オペレーターのみ。また、安全な場合にのみ巻き戻します（製品のバグは別として！）が、最大1行に制限されません。

これらは秘教的な詳細のように見えるかもしれません、そして私はそれらがそうであると思います。つまり、実行計画を理解し、パフォーマンスの向上を何度も見つけることができました。おそらく、あなたもその情報がいつか役立つと思うでしょう。

ソートに注意してください入力よりも多くの行を生成します！

並べ替えのより現実的な例を見たい場合 最も近い試合のパート1で提供されたデモItzikBen-Ganに基づいて巻き戻しますシリーズは、並べ替えの巻き戻しとの最も近い一致を参照してください。