Interne onderdelen van de zeven SQL Server-soorten - deel 2

De zeven implementatieklassen voor het sorteren van SQL Server zijn:

1. CQScanSorterenNieuw
2. CQScanTopSorterenNieuw
3. CQScanIndexSorterenNieuw
4. CQScanPartitionSortNew (alleen SQL Server 2014)
5. CQScanInMemSortNieuw
6. In-Memory OLTP (Hekaton) native gecompileerde procedure Top N Sort (alleen SQL Server 2014)
7. In-Memory OLTP (Hekaton) native gecompileerde procedure General Sort (alleen SQL Server 2014)

De eerste vier soorten werden behandeld in deel één van dit artikel.

5. CQScanInMemSortNieuw

Deze soortklasse heeft een aantal interessante eigenschappen, waarvan sommige uniek:

• Zoals de naam al doet vermoeden, sorteert het altijd volledig in het geheugen; het zal nooit overlopen naar tempdb
• Sorteren wordt altijd uitgevoerd met quicksort qsort_s in de standaard C runtime-bibliotheek MSVCR100
• Het kan alle drie de logische sorteertypes uitvoeren:Algemeen, Top N en Distinct Sort
• Het kan worden gebruikt voor geclusterde columnstore per partitie zachte sorteringen (zie sectie 4 in deel 1)
• Het geheugen dat het gebruikt, kan in de cache worden opgeslagen met het plan in plaats van gereserveerd te worden vlak voor uitvoering
• Het kan worden geïdentificeerd als een in-memory sortering in uitvoeringsplannen
• Er kunnen maximaal 500 waarden worden gesorteerd
• Het wordt nooit gebruikt voor het maken van indexen (zie sectie 3 in deel 1)

CQScanInMemSortNew is een soort klasse die je niet vaak zult tegenkomen. Aangezien het altijd in het geheugen sorteert met behulp van een standaard bibliotheek-quicksort-algoritme, zou het geen goede keuze zijn voor algemene database-sorteertaken. In feite wordt deze sorteerklasse alleen gebruikt als alle invoer runtime-constanten zijn (inclusief @variable-referenties). Vanuit het perspectief van een uitvoeringsplan betekent dit dat de invoer voor de sorteeroperator een Constante scan moet zijn operator, zoals de onderstaande voorbeelden laten zien:

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

De uitvoeringsplannen zijn:

Een typische call-stack tijdens het sorteren wordt hieronder weergegeven. Let op de aanroep naar qsort_s in de MSVCR100-bibliotheek:

Alle drie de hierboven getoonde uitvoeringsplannen zijn in-memory sorteringen met behulp van CQScanInMemSortNew met ingangen die klein genoeg zijn om het sorteergeheugen in de cache te plaatsen. Deze informatie wordt niet standaard weergegeven in uitvoeringsplannen, maar kan worden onthuld met behulp van ongedocumenteerde traceringsvlag 8666. Als die vlag actief is, verschijnen er aanvullende eigenschappen voor de sorteeroperator:

De cachebuffer is in dit voorbeeld beperkt tot 62 rijen, zoals hieronder wordt aangetoond:

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

Maak een opmerking over het laatste item in dat script om de sorteercachebuffer-eigenschap te zien veranderen van 1 in 0:

Als de buffer niet in de cache is opgeslagen, moet de sortering in het geheugen geheugen toewijzen bij het initialiseren en bij het lezen van rijen van de invoer. Wanneer een cache-buffer kan worden gebruikt, wordt dit werk voor geheugentoewijzing vermeden.

Het volgende script kan worden gebruikt om aan te tonen dat het maximum aantal items voor een CQScanInMemSortNew in-memory quicksort is 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;

Maak nogmaals een opmerking over het laatste item om de InMemory . te zien Sorteer eigenschapswijziging van 1 naar 0. Wanneer dit gebeurt, CQScanInMemSortNew wordt vervangen door CQScanSortNew (zie sectie 1) of CQScanTopSortNew (sectie 2). Een niet-CQScanInMemSortNew sortering kan natuurlijk nog steeds in het geheugen worden uitgevoerd, het gebruikt alleen een ander algoritme en mag overlopen naar tempdb indien nodig.

6. In-Memory OLTP native gecompileerde opgeslagen procedure Top N Sort

De huidige implementatie van In-Memory OLTP (voorheen met de codenaam Hekaton) native gecompileerde opgeslagen procedures maakt gebruik van een prioriteitswachtrij gevolgd door qsort_s voor Top N Sorts, wanneer aan de volgende voorwaarden is voldaan:

• De zoekopdracht bevat TOP (N) met een ORDER BY-clausule
• De waarde van N is een constante letterlijke (geen variabele)
• N heeft een maximale waarde van 8192; hoewel
• De aanwezigheid van samenvoegingen of aggregaties kan de 8192-waarde verminderen, zoals hier gedocumenteerd

De volgende code maakt een Hekaton-tabel met 4000 rijen:

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;

Het volgende script creëert een geschikte Top N Sort in een native gecompileerde opgeslagen 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;

Het geschatte uitvoeringsplan is:

Een call-stack die tijdens de uitvoering is vastgelegd, toont het invoegen in de prioriteitswachtrij die bezig is:

Nadat de opbouw van de prioriteitswachtrij is voltooid, toont de volgende oproepstack een laatste doorgang door de standaard bibliotheek quicksort:

De xtp_p_* bibliotheek die in die oproepstacks wordt weergegeven, is de native gecompileerde dll voor de opgeslagen procedure, waarbij de broncode is opgeslagen op de lokale SQL Server-instantie. De broncode wordt automatisch gegenereerd op basis van de opgeslagen proceduredefinitie. Het C-bestand voor deze native opgeslagen procedure bevat bijvoorbeeld het volgende fragment:

Dit komt zo dicht mogelijk bij toegang tot de broncode van SQL Server.

7. In-Memory OLTP native gecompileerde opgeslagen procedure Sorteren

Native gecompileerde procedures ondersteunen momenteel geen afzonderlijke sortering, maar niet-onderscheiden algemene sortering wordt wel ondersteund, zonder enige beperking op de grootte van de set. Om dit te demonstreren, zullen we eerst 6.000 rijen aan de testtabel toevoegen, wat een totaal van 10.000 rijen oplevert:

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 kunnen we de vorige testprocedure laten vallen (eigen gecompileerde procedures kunnen momenteel niet worden gewijzigd) en een nieuwe maken die een gewone (niet top-n) soort van de 10.000 rijen uitvoert:

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;

Het geschatte uitvoeringsplan is:

Het traceren van de uitvoering van deze sortering laat zien dat het begint met het opnieuw genereren van meerdere kleine gesorteerde runs met behulp van de standaard bibliotheek quicksort:

Zodra dat proces is voltooid, worden de gesorteerde runs samengevoegd met behulp van een prioriteitswachtrijschema:

Nogmaals, de C-broncode voor de procedure toont enkele details:

Samenvatting van deel 2

• CQScanInMemSortNew is altijd een in-memory quicksort. Het is beperkt tot 500 rijen van een constante scan en kan zijn sorteergeheugen cachen voor kleine invoer. Een sortering kan worden geïdentificeerd als een CQScanInMemSortNew sorteer met behulp van uitvoeringsplan-eigenschappen die worden weergegeven door traceringsvlag 8666.
• Native Hekaton gecompileerde Top N Sort vereist een constante letterlijke waarde voor N <=8192 en sorteert met behulp van een prioriteitswachtrij gevolgd door een standaard quicksort
• Inheemse gecompileerde Hekaton General Sort kan een willekeurig aantal rijen sorteren, met behulp van standaard bibliotheek quicksort om sorteerruns te genereren, en een prioriteitswachtrij merge sort om runs te combineren. Het ondersteunt geen onderscheidende sortering.