Internals of the Seven SQL Server Sorts—Part 2

Introduction

The seven SQL Server sort implementation classes are:

1. CQScanSortNew
2. CQScanTopSortNew
3. CQScanIndexSortNew
4. CQScanPartitionSortNew (SQL Server 2014 only)
5. CQScanInMemSortNew
6. In-Memory OLTP (Hekaton) natively compiled procedure Top N Sort (SQL Server 2014 only)
7. In-Memory OLTP (Hekaton) natively compiled procedure General Sort (SQL Server 2014 only)

The first four types were covered in part one of this article.

5. CQScanInMemSortNew

This sort class has a number of interesting features, some of them unique:

• As the name suggests, it always sorts entirely in memory; it will never spill to tempdb
• Sorting is always performed using quicksort qsort_s in the standard C run-time library MSVCR100
• It can perform all three logical sort types: General, Top N, and Distinct Sort
• It can be used for clustered columnstore per-partition soft sorts (see section 4 in part 1)
• The memory it uses may be cached with the plan rather than being reserved just before execution
• It can be identified as an in-memory sort in execution plans
• A maximum of 500 values or 16KB can be sorted
• It is never used for index-building sorts (see section 3 in part 1)

CQScanInMemSortNew is a sort class you will not encounter often. Since it always sorts in memory using a standard library quicksort algorithm, it would not be a good choice for general database sorting tasks. In fact, this sort class is only used when all its inputs are runtime constants (including @variable references). From an execution plan perspective, that means the input to the Sort operator must be a Constant Scan or Compute Scalar operator, as the examples below demonstrate:

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

The execution plans are:

A typical call stack during sorting is shown below. Notice the call to qsort_s in the MSVCR100 library:

All three execution plans shown above are in-memory sorts using CQScanInMemSortNew with inputs small enough for the sort memory to be cached. This information is not exposed by default in execution plans, but it can be revealed using undocumented trace flag 8666. When that flag is active, additional properties appear for the Sort operator:

The cache buffer is limited to 62 rows in this example as demonstrated below:

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

Uncomment the final item in that script to see the Sort cache buffer property change from 1 to 0:

When the buffer is not cached, the in-memory sort must allocate memory as it initializes and as required as it reads rows from its input. When a cached buffer can be used, this memory allocation work is avoided.

The following script can be used to demonstrate that the maximum number of items for a 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;

Again, uncomment the last item to see the InMemory Sort property change from 1 to 0. When this happens, CQScanInMemSortNew is replaced by either CQScanSortNew (see section 1) or CQScanTopSortNew (section 2). A non-CQScanInMemSortNew sort may still be performed in memory, of course, it just uses a different algorithm, and is allowed to spill to tempdb if necessary.

6. In-Memory OLTP natively compiled stored procedure Top N Sort

The current implementation of In-Memory OLTP (previously code-named Hekaton) natively-compiled stored procedures uses a priority queue followed by qsort_s for Top N Sorts, when the following conditions are met:

• The query contains TOP (N) with an ORDER BY clause
• The value of N is a constant literal (not a variable)
• N has a maximum value of 8192; although
• The presence of joins or aggregations may reduce the 8192 value as documented here

The following code creates a Hekaton table containing 4000 rows:

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;

The next script creates a suitable Top N Sort in a natively-compiled stored 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;

The estimated execution plan is:

A call stack captured during execution shows the insert to the priority queue in progress:

After the priority queue build is complete, the next call stack shows a final pass through the standard library quicksort:

The xtp_p*_ library shown in those call stacks is the natively-compiled dll for the stored procedure, with source code saved on the local SQL Server instance. The source code is automatically-generated from the stored procedure definition. For example, the C file for this native stored procedure contains the following fragment:

This is as close as we can get to having access to SQL Server source code.

7. In-Memory OLTP natively compiled stored procedure Sort

Natively-compiled procedures do not currently support Distinct Sort, but non-distinct general sorting is supported without any restrictions on the size of the set. To demonstrate, we will first add 6,000 rows to the test table giving a total of 10,000 rows:

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;

Now we can drop the previous test procedure (natively-compiled procedures cannot currently be altered) and create a new one that performs an ordinary (not top-n) sort of the 10,000 rows:

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;

The estimated execution plan is:

Tracing the execution of this sort shows that it starts by generating multiple small sorted runs using standard library quicksort again:

Once that process is complete, the sorted runs are merged, using a priority queue scheme:

Again, the C source code for the procedure shows some of the details:

Summary

• CQScanInMemSortNew is always an in-memory quicksort. It is limited to 500 rows from a Constant Scan, and may cache its sort memory for small inputs. A sort can be identified as a CQScanInMemSortNew sort using execution plan properties exposed by trace flag 8666.
• Hekaton native compiled Top N Sort requires a constant literal value for N <= 8192 and sorts using a priority queue followed by a standard quicksort
• Hekaton native compiled General Sort can sort any number of rows, using standard library quicksort to generate sort runs, and a priority queue merge sort to combine runs. It does not support Distinct Sort.

Thanks for reading.