Wewnętrzne siedem sortowań SQL Server – część 2

Siedem klas implementacji sortowania SQL Server to:

1. CQScanSortujNowość
2. CQScanTopSortujNowość
3. CQScanIndex SortujNowość
4. CQScanPartitionSortNew (tylko SQL Server 2014)
5. CQScanInPamięćSortujNowość
6. In-Memory OLTP (Hekaton) skompilowana natywnie procedura Top N Sort (tylko SQL Server 2014)
7. In-Memory OLTP (Hekaton) skompilowana natywnie procedura Ogólne sortowanie (tylko SQL Server 2014)

Pierwsze cztery typy zostały omówione w pierwszej części tego artykułu.

5. CQScanInMemSortNew

Ta klasa sortowania ma wiele interesujących funkcji, niektóre z nich są unikalne:

• Jak sama nazwa wskazuje, zawsze sortuje w całości w pamięci; nigdy nie rozleje się do tempdb
• Sortowanie jest zawsze wykonywane przy użyciu szybkiego sortowania qsort_s w standardowej bibliotece wykonawczej C MSVCR100
• Może wykonywać wszystkie trzy typy logicznego sortowania:Ogólne, Top N i Distinct Sort
• Może być używany do sortowania miękkiego magazynu kolumn w klastrze według partycji (patrz sekcja 4 w części 1)
• Pamięć, której używa, może być buforowana z planem, a nie rezerwowana tuż przed wykonaniem
• Może być zidentyfikowany jako sortowanie w pamięci w planach wykonania
• Można sortować maksymalnie 500 wartości
• Nigdy nie jest używany do sortowania budującego indeks (patrz sekcja 3 w części 1)

CQScanInMemSortNew jest klasą sortowania, z którą nie spotkasz się często. Ponieważ zawsze sortuje w pamięci przy użyciu standardowego algorytmu szybkiego sortowania biblioteki, nie byłby dobrym wyborem do ogólnych zadań sortowania bazy danych. W rzeczywistości ta klasa sortowania jest używana tylko wtedy, gdy wszystkie jej dane wejściowe są stałymi czasu wykonywania (w tym odwołania @variable). Z perspektywy planu wykonania oznacza to, że dane wejściowe do operatora sortowania muszą być Stałym skanowaniem operatora, jak pokazują poniższe przykłady:

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

Plany wykonania to:

Poniżej przedstawiono typowy stos wywołań podczas sortowania. Zwróć uwagę na wywołanie qsort_s w bibliotece MSVCR100:

Wszystkie trzy plany wykonania pokazane powyżej są sortowane w pamięci przy użyciu CQScanInMemSortNew z wejściami wystarczająco małymi, aby można było buforować pamięć sortowania. Te informacje nie są domyślnie ujawniane w planach wykonania, ale można je ujawnić za pomocą nieudokumentowanej flagi śledzenia 8666. Gdy ta flaga jest aktywna, wyświetlane są dodatkowe właściwości dla operatora sortowania:

W tym przykładzie bufor pamięci podręcznej jest ograniczony do 62 wierszy, jak pokazano poniżej:

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

Odkomentuj ostatni element w tym skrypcie, aby zobaczyć zmianę właściwości bufora sortowania pamięci podręcznej z 1 na 0:

Gdy bufor nie jest buforowany, sortowanie w pamięci musi alokować pamięć podczas inicjowania i zgodnie z wymaganiami, gdy odczytuje wiersze z danych wejściowych. Gdy można użyć buforowanego bufora, można uniknąć tej pracy związanej z alokacją pamięci.

Poniższy skrypt może służyć do wykazania, że ​​maksymalna liczba elementów dla CQScanInMemSortNew Szybkie sortowanie w pamięci to 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;

Ponownie odkomentuj ostatni element, aby zobaczyć InMemory Zmiana właściwości sortowania od 1 do 0. W takim przypadku CQScanInMemSortNew jest zastępowane przez CQScanSortNew (patrz sekcja 1) lub CQScanTopSortNew (sekcja 2). Nie CQScanInMemSortNew sortowanie może być nadal wykonywane w pamięci, oczywiście, używa tylko innego algorytmu i może rozlać się do tempdb jeśli to konieczne.

6. Natywnie skompilowana procedura składowana w pamięci OLTP Top N Sort

Obecna implementacja In-Memory OLTP (wcześniej o nazwie kodowej Hekaton) natywnie skompilowanych procedur składowanych wykorzystuje kolejkę priorytetową, po której następuje qsort_s dla sortowań Top N, gdy spełnione są następujące warunki:

• Zapytanie zawiera TOP (N) z klauzulą ​​ORDER BY
• Wartość N jest stałym literałem (nie zmienną)
• N ma maksymalną wartość 8192; Chociaż
• Obecność łączeń lub agregacji może zmniejszyć wartość 8192, jak udokumentowano tutaj

Poniższy kod tworzy tabelę Hekaton zawierającą 4000 wierszy:

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;

Następny skrypt tworzy odpowiednie sortowanie Top N w natywnie skompilowanej procedurze składowanej:

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

Szacowany plan wykonania to:

Stos wywołań przechwycony podczas wykonywania pokazuje wstawianie do kolejki priorytetowej w toku:

Po zakończeniu budowania kolejki priorytetowej następny stos wywołań pokazuje ostatnie przejście przez standardową bibliotekę quicksort:

xtp_p_* Biblioteka pokazana w tych stosach wywołań to natywnie skompilowana biblioteka dll dla procedury składowanej, z kodem źródłowym zapisanym w lokalnym wystąpieniu programu SQL Server. Kod źródłowy jest generowany automatycznie na podstawie definicji procedury składowanej. Na przykład plik C dla tej natywnej procedury składowanej zawiera następujący fragment:

To jest tak blisko, jak tylko możemy uzyskać dostęp do kodu źródłowego SQL Server.

7. Natywnie skompilowana procedura składowana w pamięci OLTP Sort

Procedury skompilowane natywnie nie obsługują obecnie Distinct Sort, ale obsługiwane jest ogólne sortowanie nieodróżniające, bez żadnych ograniczeń dotyczących rozmiaru zestawu. Aby to zademonstrować, najpierw dodamy 6000 wierszy do tabeli testowej, dając w sumie 10 000 wierszy:

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;

Teraz możemy porzucić poprzednią procedurę testową (procedury skompilowane natywnie nie mogą być obecnie zmieniane) i utworzyć nową, która wykonuje zwykłe (nie górne) sortowanie 10 000 wierszy:

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;

Szacowany plan wykonania to:

Śledzenie wykonania tego sortowania pokazuje, że zaczyna się ono od wygenerowania wielu małych posortowanych przebiegów ponownie przy użyciu standardowej biblioteki quicksort:

Po zakończeniu tego procesu posortowane przebiegi są scalane przy użyciu schematu kolejki priorytetowej:

Ponownie, kod źródłowy C procedury pokazuje niektóre szczegóły:

Podsumowanie części 2

• CQScanInMemSortNew jest zawsze szybkim sortowaniem w pamięci. Jest ograniczony do 500 wierszy ze stałego skanowania i może buforować swoją pamięć sortowania dla małych danych wejściowych. Sortowanie można zidentyfikować jako CQScanInMemSortNew sortuj przy użyciu właściwości planu wykonania ujawnionych przez flagę śledzenia 8666.
• Natywna kompilacja Hekaton Top N Sort wymaga stałej wartości literału dla N <=8192 i sortuje przy użyciu kolejki priorytetowej, po której następuje standardowe szybkie sortowanie
• Natywnie skompilowane ogólne sortowanie Hekaton może sortować dowolną liczbę wierszy, używając standardowej biblioteki quicksort do generowania przebiegów sortowania oraz sortowania przez scalanie kolejek priorytetowych do łączenia przebiegów. Nie obsługuje odrębnego sortowania.