Internaler i de syv SQL Server-sorteringer

De syv SQL Server-sorteringsimplementeringsklasser er:

CQScanSortNew
CQScanTopSortNew
CQScanIndexSortNew
CQScanPartitionSortNew (kun SQL Server 2014)
CQScanInMemSortNew
In-Memory OLTP (Hekaton) indbygget kompileret procedure Top N Sort (kun SQL Server 2014)
In-Memory OLTP (Hekaton) indbygget kompileret procedure General Sort (kun SQL Server 2014)

De første fire typer blev dækket i del et af denne artikel.

5. CQScanInMemSortNew

Denne klasse har en række interessante funktioner, nogle af dem unikke:

Som navnet antyder, sorterer det altid helt i hukommelsen; det vil aldrig spilde til tempdb
Sortering udføres altid ved hjælp af quicksort qsort_s i standard C runtime-biblioteket MSVCR100
Den kan udføre alle tre logiske sorteringstyper:Generelt, Top N og Distinkt sortering
Den kan bruges til bløde sorteringer i grupperet kolonnelager pr. partition (se afsnit 4 i del 1)
Hukommelsen, den bruger, kan cachelagres med planen i stedet for at blive reserveret lige før udførelse
Det kan identificeres som en sortering i hukommelsen i udførelsesplaner
Maksimalt 500 værdier kan sorteres
Det bruges aldrig til indeksopbygningssorteringer (se afsnit 3 i del 1)

CQScanInMemSortNew er en slags klasse, du ikke vil støde på ofte. Da det altid sorterer i hukommelsen ved hjælp af en standard biblioteks quicksort-algoritme, ville det ikke være et godt valg til generelle databasesorteringsopgaver. Faktisk bruges denne sorteringsklasse kun, når alle dens input er runtime-konstanter (inklusive @variable referencer). Fra et udførelsesplansperspektiv betyder det, at input til sorteringsoperatøren skal være en Konstant scanning operator, som eksemplerne nedenfor viser:

-- 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;

Udførelsesplanerne er:

En typisk opkaldsstak under sortering er vist nedenfor. Læg mærke til opkaldet til qsort_s i MSVCR100-biblioteket:

Alle tre udførelsesplaner vist ovenfor er sorteringer i hukommelsen ved hjælp af CQScanInMemSortNew med input, der er små nok til, at sorteringshukommelsen kan cachelagres. Denne information er ikke afsløret som standard i eksekveringsplaner, men den kan afsløres ved hjælp af udokumenteret sporingsflag 8666. Når dette flag er aktivt, vises yderligere egenskaber for sorteringsoperatoren:

Cachebufferen er begrænset til 62 rækker i dette eksempel som vist nedenfor:

-- 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;

Fjern kommentaren til det sidste element i det script for at se egenskaben Sorter cachebuffer ændre sig fra 1 til 0:

Når bufferen ikke er cachelagret, skal sorteringen i hukommelsen allokere hukommelse, efterhånden som den initialiseres og efter behov, når den læser rækker fra dens input. Når en cachebuffer kan bruges, undgås dette hukommelsesallokeringsarbejde.

Følgende script kan bruges til at demonstrere, at det maksimale antal elementer for en CQScanInMemSortNew in-memory quicksort er 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;

Igen, fjern kommentarer til det sidste element for at se InMemory Sorter egenskabsændring fra 1 til 0. Når dette sker, CQScanInMemSortNew erstattes af enten CQScanSortNew (se afsnit 1) eller CQScanTopSortNew (afsnit 2). En ikke-CQScanInMemSortNew sortering kan selvfølgelig stadig udføres i hukommelsen, den bruger bare en anden algoritme og får lov til at spilde til tempdb hvis det er nødvendigt.

6. In-Memory OLTP indbygget kompileret lagret procedure Top N Sort

Den nuværende implementering af In-Memory OLTP (tidligere kodenavnet Hekaton) native-kompilerede lagrede procedurer bruger en prioritetskø efterfulgt af qsort_s for Top N Sorts, når følgende betingelser er opfyldt:

Forespørgslen indeholder TOP (N) med en ORDER BY-klausul
Værdien af N er en konstant literal (ikke en variabel)
N har en maksimal værdi på 8192; Selvom
Tilstedeværelsen af joinforbindelser eller aggregeringer kan reducere 8192-værdien som dokumenteret her

Følgende kode opretter en Hekaton-tabel, der indeholder 4000 rækker:

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;

Det næste script opretter en passende Top N Sort i en native-kompileret lagret procedure:

-- 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;

Den estimerede udførelsesplan er:

En opkaldsstak, der fanges under udførelse, viser indsættelsen til den igangværende prioritetskø:

Når opbygningen af prioritetskøen er fuldført, viser den næste opkaldsstak en sidste gennemgang gennem standardbibliotekets quicksort:

xtp_p_* bibliotek vist i disse opkaldsstakke er den oprindeligt kompilerede dll for den lagrede procedure med kildekode gemt på den lokale SQL Server-instans. Kildekoden genereres automatisk fra definitionen af den lagrede procedure. For eksempel indeholder C-filen for denne oprindelige lagrede procedure følgende fragment:

Dette er så tæt som vi kan komme på at have adgang til SQL Server-kildekoden.

7. In-Memory OLTP indbygget kompileret lagret procedure Sort

Native-kompilerede procedurer understøtter i øjeblikket ikke Distinct Sortering, men ikke-distinkt generel sortering understøttes uden nogen begrænsninger på størrelsen af sættet. For at demonstrere vil vi først tilføje 6.000 rækker til testtabellen, hvilket giver i alt 10.000 rækker:

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;

Nu kan vi droppe den tidligere testprocedure (native-kompilerede procedurer kan i øjeblikket ikke ændres) og oprette en ny, der udfører en almindelig (ikke top-n) sortering af de 10.000 rækker:

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;

Den estimerede udførelsesplan er:

Sporing af udførelsen af denne slags viser, at den starter med at generere flere små sorterede kørsler ved hjælp af standard biblioteks quicksort igen:

Når denne proces er fuldført, flettes de sorterede kørsler ved hjælp af et prioritetskøskema:

Igen viser C-kildekoden til proceduren nogle af detaljerne:

Sammendrag af del 2

CQScanInMemSortNew er altid en in-memory quicksort. Det er begrænset til 500 rækker fra en konstant scanning og kan cache dets sorteringshukommelse for små input. En sortering kan identificeres som en CQScanInMemSortNew sorter ved hjælp af eksekveringsplanegenskaber afsløret af sporingsflag 8666.
Hekaton native kompileret Top N Sort kræver en konstant bogstavelig værdi for N <=8192 og sorterer ved hjælp af en prioritetskø efterfulgt af en standard quicksort
Hekaton native kompileret General Sort kan sortere et vilkårligt antal rækker ved at bruge standard biblioteks quicksort til at generere sorteringskørsler, og en prioritetskøfletningssortering for at kombinere kørsler. Det understøtter ikke Distinct Sort.

Internaler i de syv SQL Server-sorteringer – Del 2

5. CQScanInMemSortNew

6. In-Memory OLTP indbygget kompileret lagret procedure Top N Sort

7. In-Memory OLTP indbygget kompileret lagret procedure Sort

Sammendrag af del 2