Вътрешни елементи на седемте сорта SQL сървъри – част 2

Седемте класа за изпълнение на сортиране на SQL Server са:

1. CQScanSortNew
2. CQScanTopSortNew
3. CQScanIndexSortNew
4. CQScanPartitionSortNew (само за SQL Server 2014)
5. CQScanInMemSortNew
6. In-Memory OLTP (Hekaton) компилирана процедура Top N Sort (само за SQL Server 2014)
7. В паметта OLTP (Hekaton) компилирана процедура Общо сортиране (само за SQL Server 2014)

Първите четири типа бяха разгледани в част първа на тази статия.

5. CQScanInMemSortNew

Този клас за сортиране има редица интересни функции, някои от които уникални:

• Както подсказва името, винаги се сортира изцяло в паметта; никога няма да се разлее в tempdb
• Сортирането винаги се извършва с помощта на quicksort qsort_s в стандартната библиотека по време на изпълнение на C MSVCR100
• Може да изпълнява и трите логически типа сортиране:Общ, Най-висок N и Отличен сорт
• Може да се използва за меко сортиране на клъстерни хранилища на колони на дял (вижте раздел 4 в част 1)
• Паметта, която използва, може да бъде кеширана с плана, вместо да бъде запазена точно преди изпълнението
• Може да се идентифицира като сортиране в паметта в плановете за изпълнение
• Могат да бъдат сортирани максимум 500 стойности
• Никога не се използва за сортиране на индекси (вижте раздел 3 в част 1)

CQScanInMemSortNew е клас за сортиране, който няма да срещате често. Тъй като винаги сортира в паметта, използвайки алгоритъм за бързо сортиране на стандартна библиотека, не би бил добър избор за общи задачи за сортиране на база данни. Всъщност този клас за сортиране се използва само когато всички негови входове са константи по време на изпълнение (включително препратки @variable). От гледна точка на плана за изпълнение, това означава, че входът към оператора за сортиране трябва да бъде Постоянно сканиране оператор, както демонстрират примерите по-долу:

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

Плановете за изпълнение са:

Типичен стек от повиквания по време на сортиране е показан по-долу. Забележете извикването на qsort_s в библиотеката MSVCR100:

И трите плана за изпълнение, показани по-горе, са сортиране в паметта с помощта на 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 компилирана съхранена процедура Top N Sort

Текущата реализация на компилираните в паметта процедури OLTP (по-рано с кодово име Hekaton) използва приоритетна опашка, последвана от qsort_s за Топ N сортове, когато са изпълнени следните условия:

• Заявката съдържа TOP (N) с клауза ORDER BY
• Стойността на N е постоянен литерал (не променлива)
• N има максимална стойност от 8192; макар че
• Наличието на обединения или агрегирания може да намали стойността 8192, както е документирано тук

Следният код създава таблица Hekaton, съдържаща 4000 реда:

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 за съхранената процедура, с изходен код, запазен в локалния екземпляр на SQL Server. Изходният код се генерира автоматично от дефиницията на съхранената процедура. Например, C файлът за тази естествена съхранена процедура съдържа следния фрагмент:

Това е възможно най-близо до това да имаме достъп до изходния код на SQL Server.

7. В паметта OLTP компилирана съхранена процедура Сортиране

Компилираните процедури понастоящем не поддържат Distinct 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;

Сега можем да изхвърлим предишната тестова процедура (нативно компилираните процедури в момента не могат да бъдат променяни) и да създадем нова, която изпълнява обикновен (не top-n) вид на 10 000 реда:

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, компилиран от Hekaton, Top N Sort изисква постоянна литерална стойност за N <=8192 и сортира с помощта на опашка с приоритет, последвана от стандартно бързо сортиране
• Общото сортиране, компилирано от Hekaton, може да сортира произволен брой редове, като използва бързо сортиране на стандартната библиотека за генериране на цикли на сортиране и приоритетно сортиране с обединяване на опашката за комбиниране на изпълнения. Не поддържа отделно сортиране.