Vnitřní části sedmi druhů SQL Server – část 2

Sedm tříd implementace řazení SQL Server je:

1. CQScanSortNew
2. CQScanTopSortNew
3. CQScanIndexSortNew
4. CQScanPartitionSortNew (pouze SQL Server 2014)
5. CQScanInMemSortNew
6. In-Memory OLTP (Hekaton) nativně kompilovaná procedura Top N Sort (pouze SQL Server 2014)
7. In-Memory OLTP (Hekaton) nativně kompilovaná procedura General Sort (pouze SQL Server 2014)

První čtyři typy byly popsány v první části tohoto článku.

5. CQScanInMemSortNew

Tato třída třída má řadu zajímavých funkcí, některé z nich jsou jedinečné:

• Jak název napovídá, vždy se třídí zcela v paměti; nikdy se nerozlije do tempdb
• Řazení se vždy provádí pomocí quicksort qsort_s ve standardní C runtime knihovně MSVCR100
• Může provádět všechny tři logické typy řazení:Obecné, Nejlepší N a Odlišné řazení
• Lze jej použít pro klastrovaná měkká řazení pro jednotlivé oddíly (viz část 4 v části 1)
• Paměť, kterou používá, může být uložena do mezipaměti s plánem, místo aby byla rezervována těsně před provedením
• V prováděcích plánech jej lze identifikovat jako řazení v paměti
• Lze seřadit maximálně 500 hodnot
• Nikdy se nepoužívá pro druhy vytváření indexů (viz část 3 v části 1)

CQScanInMemSortNew je třída, se kterou se často nesetkáte. Vzhledem k tomu, že vždy třídí v paměti pomocí standardního algoritmu rychlého třídění v knihovně, nebyla by to dobrá volba pro obecné úlohy třídění databází. Ve skutečnosti se tato třída třída používá pouze tehdy, když jsou všechny její vstupy běhové konstanty (včetně odkazů @proměnných). Z pohledu prováděcího plánu to znamená, že vstupem pro operátor Sort musí být Konstantní skenování operátor, jak ukazují příklady níže:

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

Prováděcí plány jsou:

Typický zásobník volání během třídění je uveden níže. Všimněte si volání qsort_s v knihovně MSVCR100:

Všechny tři výše uvedené prováděcí plány jsou tříděny v paměti pomocí CQScanInMemSortNew se vstupy dostatečně malými na to, aby třídicí paměť byla uložena do mezipaměti. Tyto informace nejsou ve výchozím nastavení v plánech provádění vystaveny, ale lze je odhalit pomocí nezdokumentovaného příznaku trasování 8666. Když je tento příznak aktivní, zobrazí se operátoru řazení další vlastnosti:

Mezipaměť je v tomto příkladu omezena na 62 řádků, jak je ukázáno níže:

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

Odkomentujte poslední položku v tomto skriptu, abyste viděli změnu vlastnosti vyrovnávací paměti pro řazení z 1 na 0:

Když není vyrovnávací paměť uložena do mezipaměti, musí řazení v paměti alokovat paměť při inicializaci a podle potřeby při čtení řádků ze svého vstupu. Když lze použít vyrovnávací paměť uloženou v mezipaměti, tato práce s alokací paměti se vyhne.

Následující skript lze použít k prokázání, že maximální počet položek pro CQScanInMemSortNew rychlé třídění v paměti je 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;

Znovu odkomentujte poslední položku, abyste viděli InMemory Seřadit změnu vlastnosti z 1 na 0. Když k tomu dojde, CQScanInMemSortNew je nahrazeno buď CQScanSortNew (viz část 1) nebo CQScanTopSortNew (sekce 2). NeCQScanInMemSortNew řazení lze samozřejmě stále provádět v paměti, jen používá jiný algoritmus a může se přelévat do tempdb v případě potřeby.

6. In-Memory OLTP nativně zkompilovaná uložená procedura Top N Sort

Současná implementace nativně kompilovaných uložených procedur In-Memory OLTP (dříve s kódovým označením Hekaton) používá frontu priority následovanou qsort_s pro Top N Sorts, pokud jsou splněny následující podmínky:

• Dotaz obsahuje TOP (N) s klauzulí ORDER BY
• Hodnota N je konstantní literál (nikoli proměnná)
• N má maximální hodnotu 8192; Ačkoli
• Přítomnost spojení nebo agregací může snížit hodnotu 8192, jak je zdokumentováno zde

Následující kód vytvoří tabulku Hekaton obsahující 4000 řádků:

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;

Další skript vytvoří vhodné řazení Top N v nativně zkompilované uložené proceduře:

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

Odhadovaný plán provádění je:

Zásobník volání zachycený během provádění ukazuje probíhající vkládání do prioritní fronty:

Po dokončení sestavení prioritní fronty zobrazí další zásobník volání poslední průchod standardním rychlým řazením knihovny:

xtp_p_* knihovna zobrazená v těchto hromadách volání je nativně zkompilovaná knihovna dll pro uloženou proceduru se zdrojovým kódem uloženým v místní instanci serveru SQL Server. Zdrojový kód je automaticky generován z definice uložené procedury. Například soubor C pro tuto nativní uloženou proceduru obsahuje následující fragment:

To je tak blízko, jak se můžeme dostat k přístupu ke zdrojovému kódu SQL Server.

7. In-Memory OLTP nativně zkompilovaná uložená procedura Sort

Nativně kompilované procedury v současné době nepodporují Distinct Sort, ale je podporováno nerozlišující obecné řazení bez jakýchkoli omezení velikosti sady. Abychom demonstrovali, nejprve do testovací tabulky přidáme 6 000 řádků, takže celkem 10 000 řádků:

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;

Nyní můžeme zrušit předchozí testovací proceduru (nativně kompilované procedury nelze aktuálně měnit) a vytvořit novou, která provede běžné (nikoli top-n) řazení 10 000 řádků:

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;

Odhadovaný plán provádění je:

Sledování provádění tohoto řazení ukazuje, že začíná generováním několika malých setříděných běhů opět pomocí standardního rychlého třídění:

Jakmile je tento proces dokončen, setříděné běhy jsou sloučeny pomocí schématu prioritní fronty:

Zdrojový kód procedury v C opět ukazuje některé podrobnosti:

Shrnutí části 2

• CQScanInMemSortNew je vždy rychlé třídění v paměti. Je omezena na 500 řádků z konstantního skenování a může ukládat do mezipaměti třídicí paměť pro malé vstupy. Řazení lze identifikovat jako CQScanInMemSortNew řazení pomocí vlastností prováděcího plánu vystavených příznakem trasování 8666.
• Nativní zkompilované řazení podle Hekaton Top N vyžaduje konstantní doslovnou hodnotu pro N <=8192 a řadí se pomocí prioritní fronty následované standardním rychlým řazením
• Nativní kompilované obecné třídění Hekaton může třídit libovolný počet řádků pomocí rychlého třídění standardní knihovny ke generování běhů řazení a třídění slučováním podle priority fronty ke kombinování běhů. Nepodporuje Distinct Sort.