7つのSQLServerソートの内部

7つのSQLServerソート実装クラスは次のとおりです。

CQScanSortNew
CQScanTopSortNew
CQScanIndexSortNew
CQScanPartitionSortNew（SQL Server 2014のみ）
CQScanInMemSortNew
インメモリOLTP（Hekaton）ネイティブにコンパイルされたプロシージャTop N Sort（SQL Server 2014のみ）
インメモリOLTP（Hekaton）ネイティブにコンパイルされたプロシージャGeneral Sort（SQL Server 2014のみ）

最初の4つのタイプは、この記事のパート1で取り上げました。

5。 CQScanInMemSortNew

このソートクラスにはいくつかの興味深い機能があり、そのうちのいくつかはユニークです：

名前が示すように、常に完全にメモリ内でソートされます。 tempdbに流出することはありません
並べ替えは、標準のCランタイムライブラリMSVCR100のクイックソートqsort_sを使用して常に実行されます。
一般、上位N、および個別ソートの3つの論理ソートタイプすべてを実行できます。
クラスター化された列ストアのパーティションごとのソフトソートに使用できます（パート1のセクション4を参照）
使用するメモリは、実行直前に予約されるのではなく、プランとともにキャッシュされる場合があります
実行計画ではメモリ内の並べ替えとして識別できます
最大500個の値を並べ替えることができます
インデックス作成の並べ替えには使用されません（パート1のセクション3を参照）

CQScanInMemSortNew 頻繁に遭遇することのないソートクラスです。標準ライブラリのクイックソートアルゴリズムを使用して常にメモリ内でソートするため、一般的なデータベースのソートタスクには適していません。実際、このソートクラスは、すべての入力が実行時定数（@variable参照を含む）である場合にのみ使用されます。実行プランの観点からは、Sort演算子への入力は Constant Scanでなければならないことを意味します以下の例が示すように、演算子：

-- Regular Sort on system scalar functions
SELECT X.i 
FROM 
(
    SELECT @@TIMETICKS UNION ALL
    SELECT @@TOTAL_ERRORS UNION ALL
    SELECT @@TOTAL_READ UNION ALL
    SELECT @@TOTAL_WRITE
) AS X (i)
ORDER BY X.i;
 
-- Distinct Sort on constant literals
WITH X (i) AS
(
    SELECT 3 UNION ALL
    SELECT 1 UNION ALL
    SELECT 1 UNION ALL
    SELECT 2
)
SELECT DISTINCT X.i
FROM X
ORDER BY X.i;
 
-- Top N Sort on variables, constants, and functions
DECLARE
    @x integer = 1,
    @y integer = 2;
 
SELECT TOP (1) 
    X.i
FROM 
(
    VALUES
        (@x), (@y), (123), 
        (@@CONNECTIONS)
) AS X (i)
ORDER BY X.i;

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

ソート中の一般的なコールスタックを以下に示します。 MSVCR100ライブラリのqsort_sの呼び出しに注意してください。

上記の3つの実行プランはすべて、 CQScanInMemSortNewを使用したメモリ内ソートです。ソートメモリをキャッシュするのに十分小さい入力を使用します。この情報は、実行計画ではデフォルトで公開されていませんが、文書化されていないトレースフラグ8666を使用して公開できます。このフラグがアクティブな場合、並べ替え演算子に追加のプロパティが表示されます。

この例では、以下に示すように、キャッシュバッファは62行に制限されています。

-- Cache buffer limited to 62 rows
SELECT X.i
FROM
(
    VALUES 
    (001),(002),(003),(004),(005),(006),(007),(008),(009),(010),
    (011),(012),(013),(014),(015),(016),(017),(018),(019),(020),
    (021),(022),(023),(024),(025),(026),(027),(028),(029),(030),
    (031),(032),(033),(034),(035),(036),(037),(038),(039),(040),
    (041),(042),(043),(044),(045),(046),(047),(048),(049),(050),
    (051),(052),(053),(054),(055),(056),(057),(058),(059),(060),
    (061),(062)--, (063)
) AS X (i)
ORDER BY X.i;

そのスクリプトの最後の項目のコメントを解除して、ソートキャッシュバッファプロパティが1から0に変更されることを確認します。

バッファがキャッシュされていない場合、メモリ内ソートは、初期化時および入力から行を読み取るときに必要に応じてメモリを割り当てる必要があります。キャッシュされたバッファを使用できる場合、このメモリ割り当て作業は回避されます。

次のスクリプトを使用して、 CQScanInMemSortNewのアイテムの最大数を示すことができます。インメモリクイックソートは500です：

SELECT X.i
FROM
(
    VALUES 
    (001),(002),(003),(004),(005),(006),(007),(008),(009),(010),
    (011),(012),(013),(014),(015),(016),(017),(018),(019),(020),
    (021),(022),(023),(024),(025),(026),(027),(028),(029),(030),
    (031),(032),(033),(034),(035),(036),(037),(038),(039),(040),
    (041),(042),(043),(044),(045),(046),(047),(048),(049),(050),
    (051),(052),(053),(054),(055),(056),(057),(058),(059),(060),
    (061),(062),(063),(064),(065),(066),(067),(068),(069),(070),
    (071),(072),(073),(074),(075),(076),(077),(078),(079),(080),
    (081),(082),(083),(084),(085),(086),(087),(088),(089),(090),
    (091),(092),(093),(094),(095),(096),(097),(098),(099),(100),
    (101),(102),(103),(104),(105),(106),(107),(108),(109),(110),
    (111),(112),(113),(114),(115),(116),(117),(118),(119),(120),
    (121),(122),(123),(124),(125),(126),(127),(128),(129),(130),
    (131),(132),(133),(134),(135),(136),(137),(138),(139),(140),
    (141),(142),(143),(144),(145),(146),(147),(148),(149),(150),
    (151),(152),(153),(154),(155),(156),(157),(158),(159),(160),
    (161),(162),(163),(164),(165),(166),(167),(168),(169),(170),
    (171),(172),(173),(174),(175),(176),(177),(178),(179),(180),
    (181),(182),(183),(184),(185),(186),(187),(188),(189),(190),
    (191),(192),(193),(194),(195),(196),(197),(198),(199),(200),
    (201),(202),(203),(204),(205),(206),(207),(208),(209),(210),
    (211),(212),(213),(214),(215),(216),(217),(218),(219),(220),
    (221),(222),(223),(224),(225),(226),(227),(228),(229),(230),
    (231),(232),(233),(234),(235),(236),(237),(238),(239),(240),
    (241),(242),(243),(244),(245),(246),(247),(248),(249),(250),
    (251),(252),(253),(254),(255),(256),(257),(258),(259),(260),
    (261),(262),(263),(264),(265),(266),(267),(268),(269),(270),
    (271),(272),(273),(274),(275),(276),(277),(278),(279),(280),
    (281),(282),(283),(284),(285),(286),(287),(288),(289),(290),
    (291),(292),(293),(294),(295),(296),(297),(298),(299),(300),
    (301),(302),(303),(304),(305),(306),(307),(308),(309),(310),
    (311),(312),(313),(314),(315),(316),(317),(318),(319),(320),
    (321),(322),(323),(324),(325),(326),(327),(328),(329),(330),
    (331),(332),(333),(334),(335),(336),(337),(338),(339),(340),
    (341),(342),(343),(344),(345),(346),(347),(348),(349),(350),
    (351),(352),(353),(354),(355),(356),(357),(358),(359),(360),
    (361),(362),(363),(364),(365),(366),(367),(368),(369),(370),
    (371),(372),(373),(374),(375),(376),(377),(378),(379),(380),
    (381),(382),(383),(384),(385),(386),(387),(388),(389),(390),
    (391),(392),(393),(394),(395),(396),(397),(398),(399),(400),
    (401),(402),(403),(404),(405),(406),(407),(408),(409),(410),
    (411),(412),(413),(414),(415),(416),(417),(418),(419),(420),
    (421),(422),(423),(424),(425),(426),(427),(428),(429),(430),
    (431),(432),(433),(434),(435),(436),(437),(438),(439),(440),
    (441),(442),(443),(444),(445),(446),(447),(448),(449),(450),
    (451),(452),(453),(454),(455),(456),(457),(458),(459),(460),
    (461),(462),(463),(464),(465),(466),(467),(468),(469),(470),
    (471),(472),(473),(474),(475),(476),(477),(478),(479),(480),
    (481),(482),(483),(484),(485),(486),(487),(488),(489),(490),
    (491),(492),(493),(494),(495),(496),(497),(498),(499),(500)
--,    (501)
) AS X (i)
ORDER BY X.i;

ここでも、最後のアイテムのコメントを解除して、 InMemoryを表示します。並べ替えプロパティが1から0に変更されます。これが発生した場合、 CQScanInMemSortNew CQScanSortNewのいずれかに置き換えられます（セクション1を参照）または CQScanTopSortNew （第2節）。 CQScanInMemSortNew以外 並べ替えは引き続きメモリ内で実行できますが、もちろん、別のアルゴリズムを使用するだけで、 tempdbにスピルすることができます。必要に応じて。

6。インメモリOLTPネイティブにコンパイルされたストアドプロシージャトップNソート

インメモリOLTP（以前のコード名はHekaton）の現在の実装では、ネイティブにコンパイルされたストアドプロシージャは、次の条件が満たされた場合に、優先キューとそれに続く上位Nソートのqsort_sを使用します。

クエリにORDERBY句を含むTOP（N）が含まれている
Nの値は定数リテラルです（変数ではありません）
Nの最大値は8192です。でも
結合または集計が存在すると、ここに記載されているように8192の値が減少する可能性があります

次のコードは、4000行を含むHekatonテーブルを作成します。

CREATE DATABASE InMemoryOLTP;
GO
-- Add memory optimized filegroup
ALTER DATABASE InMemoryOLTP
ADD FILEGROUP InMemoryOLTPFileGroup 
CONTAINS MEMORY_OPTIMIZED_DATA;
GO
-- Add file (adjust path if necessary)
ALTER DATABASE InMemoryOLTP
ADD FILE
(
	NAME = N'IMOLTP', 
	FILENAME = N'C:\Program Files\Microsoft SQL Server\MSSQL12.SQL2014\MSSQL\DATA\IMOLTP.hkf'
)
TO FILEGROUP InMemoryOLTPFileGroup;
GO
USE InMemoryOLTP;
GO
CREATE TABLE dbo.Test
(
    col1 integer NOT NULL,
    col2 integer NOT NULL,
    col3 integer NOT NULL,
 
    CONSTRAINT PK_dbo_Test
    PRIMARY KEY NONCLUSTERED HASH (col1)
    WITH (BUCKET_COUNT = 8192)
)
WITH
(
    MEMORY_OPTIMIZED = ON,
    DURABILITY = SCHEMA_ONLY
);
GO
-- Add numbers from 1-4000 using
-- Itzik Ben-Gan's number generator
WITH
  L0   AS (SELECT 1 AS c UNION ALL SELECT 1),
  L1   AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
  L2   AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
  L3   AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
  L4   AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
  L5   AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
  Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS n FROM L5)
INSERT dbo.Test
    (col1, col2, col3)
SELECT 
    N.n,
    ABS(CHECKSUM(NEWID())),
    ABS(CHECKSUM(NEWID()))
FROM Nums AS N
WHERE N.n BETWEEN 1 AND 4000;

次のスクリプトは、ネイティブにコンパイルされたストアドプロシージャで適切なトップNソートを作成します。

-- Natively-compiled Top N Sort stored procedure
CREATE PROCEDURE dbo.TestP
WITH EXECUTE AS OWNER, SCHEMABINDING, NATIVE_COMPILATION
AS
BEGIN ATOMIC 
WITH 
(
    TRANSACTION ISOLATION LEVEL = SNAPSHOT, 
    LANGUAGE = N'us_english'
)
    SELECT TOP (2) T.col2 
    FROM dbo.Test AS T
    ORDER BY T.col2
END;
GO
EXECUTE dbo.TestP;

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

実行中にキャプチャされたコールスタックは、進行中の優先キューへの挿入を示しています。

優先キューの構築が完了すると、次の呼び出しスタックに標準ライブラリのクイックソートの最終パスが表示されます。

xtp_p _ * これらの呼び出しスタックに表示されるライブラリは、ストアドプロシージャ用にネイティブにコンパイルされたdllであり、ソースコードはローカルSQLServerインスタンスに保存されています。ソースコードは、ストアドプロシージャ定義から自動的に生成されます。たとえば、このネイティブストアドプロシージャのCファイルには、次のフラグメントが含まれています。

これは、SQLServerのソースコードにアクセスできる限り近いものです。

7。インメモリOLTPネイティブにコンパイルされたストアドプロシージャSort

ネイティブにコンパイルされたプロシージャは現在、個別の並べ替えをサポートしていませんが、セットのサイズに制限がなく、個別ではない一般的な並べ替えがサポートされています。実例を示すために、最初に6,000行をテストテーブルに追加して、合計10,000行にします。

WITH
  L0   AS (SELECT 1 AS c UNION ALL SELECT 1),
  L1   AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
  L2   AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
  L3   AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
  L4   AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
  L5   AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
  Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS n FROM L5)
INSERT dbo.Test
    (col1, col2, col3)
SELECT 
    N.n,
    ABS(CHECKSUM(NEWID())),
    ABS(CHECKSUM(NEWID()))
FROM Nums AS N
WHERE N.n BETWEEN 4001 AND 10000;

これで、以前のテスト手順を削除して（現在、ネイティブにコンパイルされた手順を変更することはできません）、10,000行の通常の（トップnではない）並べ替えを実行する新しい手順を作成できます。

DROP PROCEDURE dbo.TestP;
GO
CREATE PROCEDURE dbo.TestP
WITH EXECUTE AS OWNER, SCHEMABINDING, NATIVE_COMPILATION
AS
BEGIN ATOMIC 
WITH 
(
    TRANSACTION ISOLATION LEVEL = SNAPSHOT, 
    LANGUAGE = N'us_english'
)
    SELECT T.col2 
    FROM dbo.Test AS T
    ORDER BY T.col2
END;
GO
EXECUTE dbo.TestP;

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

このソートの実行をトレースすると、標準ライブラリのクイックソートを再度使用して、複数の小さなソートされた実行を生成することから始まることがわかります。

そのプロセスが完了すると、優先キュースキームを使用して、並べ替えられた実行がマージされます。

繰り返しになりますが、プロシージャのCソースコードには、いくつかの詳細が示されています。

パート2の概要

CQScanInMemSortNew 常にメモリ内のクイックソートです。コンスタントスキャンからの500行に制限されており、小さな入力用にソートメモリをキャッシュする場合があります。並べ替えは、 CQScanInMemSortNewとして識別できます。トレースフラグ8666によって公開された実行プランのプロパティを使用して並べ替えます。
Hekatonネイティブコンパイル済みトップNソートには、N <=8192の定数リテラル値が必要であり、優先キューとそれに続く標準クイックソートを使用してソートします
Hekatonネイティブコンパイル済み一般ソートは、標準ライブラリのクイックソートを使用してソート実行を生成し、優先キューマージソートを使用して実行を結合することにより、任意の数の行をソートできます。 DistinctSortはサポートしていません。

7つのSQLServerソートの内部–パート2

5。 CQScanInMemSortNew

6。インメモリOLTPネイティブにコンパイルされたストアドプロシージャトップNソート

7。インメモリOLTPネイティブにコンパイルされたストアドプロシージャSort

パート2の概要