Sqlserver
 sql >> Datenbank >  >> RDS >> Sqlserver

Interna der sieben SQL Server-Arten – Teil 2

Die sieben Sortierimplementierungsklassen von SQL Server sind:

  1. CQScanSortNeu
  2. CQScanTopSortNew
  3. CQScanIndexSortNeu
  4. CQScanPartitionSortNew (nur SQL Server 2014)
  5. CQScanInMemSortNeu
  6. In-Memory OLTP (Hekaton) nativ kompilierte Prozedur Top N Sort (nur SQL Server 2014)
  7. In-Memory OLTP (Hekaton) nativ kompilierte Prozedur General Sort (nur SQL Server 2014)

Die ersten vier Typen wurden in Teil 1 dieses Artikels behandelt.

5. CQScanInMemSortNew

Diese Sortierklasse hat eine Reihe interessanter Eigenschaften, von denen einige einzigartig sind:

  • Wie der Name schon sagt, sortiert es immer vollständig im Speicher; es wird niemals zu tempdb überlaufen
  • Die Sortierung erfolgt immer mit Quicksort qsort_s in der Standard-C-Laufzeitbibliothek MSVCR100
  • Es kann alle drei logischen Sortiertypen ausführen:General, Top N und Distinct Sort
  • Es kann für geclusterte Columnstore-pro-Partition-Softsorts verwendet werden (siehe Abschnitt 4 in Teil 1).
  • Der verwendete Speicher kann mit dem Plan zwischengespeichert werden, anstatt erst kurz vor der Ausführung reserviert zu werden
  • Es kann in Ausführungsplänen als In-Memory-Sortierung identifiziert werden
  • Es können maximal 500 Werte sortiert werden
  • Es wird niemals für indexbildende Sortierungen verwendet (siehe Abschnitt 3 in Teil 1)

CQScanInMemSortNew ist eine Sort-Klasse, der Sie nicht oft begegnen werden. Da es im Speicher immer mit einem Quicksort-Algorithmus aus der Standardbibliothek sortiert, wäre es keine gute Wahl für allgemeine Sortieraufgaben in Datenbanken. Tatsächlich wird diese Sortierklasse nur verwendet, wenn alle ihre Eingaben Laufzeitkonstanten sind (einschließlich @variable-Referenzen). Aus Sicht des Ausführungsplans bedeutet dies, dass die Eingabe für den Sort-Operator ein Konstanter Scan sein muss Operator, wie die folgenden Beispiele zeigen:

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

Die Ausführungspläne sind:

Eine typische Aufrufliste während des Sortierens ist unten dargestellt. Beachten Sie den Aufruf von qsort_s in der MSVCR100-Bibliothek:

Alle drei oben gezeigten Ausführungspläne sind In-Memory-Sortierungen mit CQScanInMemSortNew mit Eingaben, die klein genug sind, damit der Sortierspeicher zwischengespeichert werden kann. Diese Informationen werden in Ausführungsplänen nicht standardmäßig offengelegt, können aber mithilfe des undokumentierten Ablaufverfolgungsflags 8666 offengelegt werden. Wenn dieses Flag aktiv ist, werden zusätzliche Eigenschaften für den Sort-Operator angezeigt:

Der Cache-Puffer ist in diesem Beispiel auf 62 Zeilen begrenzt, wie unten gezeigt:

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

Entkommentieren Sie das letzte Element in diesem Skript, um zu sehen, wie sich die Eigenschaft Cache-Puffer sortieren von 1 auf 0 ändert:

Wenn der Puffer nicht zwischengespeichert wird, muss die speicherinterne Sortierung beim Initialisieren und nach Bedarf beim Lesen von Zeilen aus ihrer Eingabe Speicher zuweisen. Wenn ein zwischengespeicherter Puffer verwendet werden kann, wird diese Speicherzuweisungsarbeit vermieden.

Das folgende Skript kann verwendet werden, um zu demonstrieren, dass die maximale Anzahl von Elementen für ein CQScanInMemSortNew Quicksort im Arbeitsspeicher ist 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;

Kommentieren Sie erneut das letzte Element aus, um InMemory anzuzeigen Änderung der Sort-Eigenschaft von 1 auf 0. Wenn dies geschieht, CQScanInMemSortNew wird entweder durch CQScanSortNew ersetzt (siehe Abschnitt 1) ​​oder CQScanTopSortNew (Sektion 2). Ein Nicht-CQScanInMemSortNew sort kann natürlich immer noch im Speicher durchgeführt werden, es verwendet nur einen anderen Algorithmus und darf zu tempdb übergehen falls nötig.

6. In-Memory OLTP nativ kompilierte gespeicherte Prozedur Top N Sort

Die aktuelle Implementierung von nativ kompilierten gespeicherten In-Memory-OLTP-Prozeduren (früher Codename Hekaton) verwendet eine Prioritätswarteschlange, gefolgt von qsort_s für Top-N-Sortierungen, wenn die folgenden Bedingungen erfüllt sind:

  • Die Abfrage enthält TOP (N) mit einer ORDER BY-Klausel
  • Der Wert von N ist ein konstantes Literal (keine Variable)
  • N hat einen maximalen Wert von 8192; obwohl
  • Das Vorhandensein von Joins oder Aggregationen kann den 8192-Wert reduzieren, wie hier dokumentiert

Der folgende Code erstellt eine Hekaton-Tabelle mit 4000 Zeilen:

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;

Das nächste Skript erstellt eine geeignete Top-N-Sortierung in einer nativ kompilierten gespeicherten Prozedur:

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

Der geschätzte Ausführungsplan lautet:

Ein während der Ausführung erfasster Aufrufstapel zeigt, dass das Einfügen in die Prioritätswarteschlange im Gange ist:

Nachdem die Erstellung der Prioritätswarteschlange abgeschlossen ist, zeigt die nächste Aufrufliste einen letzten Durchlauf durch die Quicksort-Standardbibliothek:

Der xtp_p_* Die in diesen Aufruflisten angezeigte Bibliothek ist die nativ kompilierte DLL für die gespeicherte Prozedur, wobei der Quellcode auf der lokalen SQL Server-Instanz gespeichert ist. Der Quellcode wird automatisch aus der Definition der gespeicherten Prozedur generiert. Beispielsweise enthält die C-Datei für diese native gespeicherte Prozedur das folgende Fragment:

Dies kommt dem Zugriff auf den SQL Server-Quellcode am nächsten.

7. In-Memory OLTP nativ kompilierte Stored Procedure Sort

Systemintern kompilierte Prozeduren unterstützen derzeit kein eindeutiges Sortieren, aber ein nicht eindeutiges allgemeines Sortieren wird unterstützt, ohne Einschränkungen hinsichtlich der Größe des Satzes. Zur Demonstration fügen wir der Testtabelle zunächst 6.000 Zeilen hinzu, was insgesamt 10.000 Zeilen ergibt:

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;

Jetzt können wir die vorherige Testprozedur fallen lassen (nativ kompilierte Prozeduren können derzeit nicht geändert werden) und eine neue erstellen, die eine gewöhnliche (nicht Top-n) Sortierung der 10.000 Zeilen durchführt:

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;

Der geschätzte Ausführungsplan lautet:

Die Verfolgung der Ausführung dieser Sortierung zeigt, dass sie mit der Generierung mehrerer kleiner sortierter Läufe beginnt, wobei wieder Quicksort der Standardbibliothek verwendet wird:

Sobald dieser Prozess abgeschlossen ist, werden die sortierten Läufe unter Verwendung eines Prioritätswarteschlangenschemas zusammengeführt:

Auch hier zeigt der C-Quellcode für die Prozedur einige Details:

Zusammenfassung von Teil 2

  • CQScanInMemSortNew ist immer ein In-Memory-Quicksort. Es ist auf 500 Zeilen aus einem konstanten Scan begrenzt und kann seinen Sortierspeicher für kleine Eingaben zwischenspeichern. Eine Sortierung kann als CQScanInMemSortNew identifiziert werden sortieren Sie mithilfe von Ausführungsplaneigenschaften, die durch Ablaufverfolgungsflag 8666 verfügbar gemacht werden.
  • Die von Hekaton nativ kompilierte Top-N-Sortierung erfordert einen konstanten Literalwert für N <=8192 und sortiert unter Verwendung einer Prioritätswarteschlange, gefolgt von einem Standard-Quicksort
  • Das von Hekaton nativ kompilierte General Sort kann eine beliebige Anzahl von Zeilen sortieren, wobei Quicksort der Standardbibliothek verwendet wird, um Sortierläufe zu generieren, und eine Priority-Queue-Merge-Sortierung, um Läufe zu kombinieren. Distinct Sort wird nicht unterstützt.