Сортировка без cоединения слиянием

В некоторых случаях SQL Server не распознает, что может положиться на порядок индекса, но, применив ряд мер, вы сможете добиться от платформы нужного функционирования. Перед вами первая из двух статей, в которых будут описаны соответствующие задачи и решения. В данной статье речь пойдет о том, как избежать сортировки с оператором cоединения слиянием (сцепления) Merge Join. Во второй статье будет показано, как избежать сортировки, когда необходимо расположить данные по убыванию.

Одно из преимуществ индексов на основе двоичного дерева заключается в упорядочении данных по некоторому ключу индекса. Затем SQL Server может воспользоваться порядком индекса для представления или обработки данных (для таких операций, как ORDER BY, GROUP BY и JOIN) без потерь, связанных с операцией собственно сортировки. Извлечение заранее упорядоченных данных из индекса масштабируется линейно, поскольку стоимость упорядоченного сканирования пропорциональна числу обрабатываемых строк. Извлечение неупорядоченных данных с последующим применением операции сортировки масштабируется нелинейным образом, а именно по закону n*log n. Поэтому, если вам часто приходится использовать упорядоченные данные, полезно иметь под рукой поддерживающие индексы. Однако иногда SQL Server не распознает, что может положиться на порядок индекса, но, приложив определенные усилия, вы можете добиться от платформы должного поведения.

Упорядочение данных со значениями NULL в конце

Наш первый пример особого упорядочения — классический. Я воспользуюсь таблицей Sales.Orders в базе данных TSQLV4 (http://tsql.solidq.com/SampleDatabases/TSQLV4.zip%20%20%20). Задача состоит в том, чтобы возвратить заказы (столбцы orderid и shippeddate), упорядоченные по shippeddate в порядке возрастания, orderid в порядке возрастания, но значениями NULL последними. Обычно SQL Server располагает значения NULL первыми. Как правило, эта задача решается с использованием выражения CASE в качестве первого упорядочивающего выражения, возвращающего флаг с более высоким значением порядка для значений NULL, а затем shippeddate и orderid, например:

USE TSQLV4;
SELECT orderid, shippeddate
FROM Sales.Orders
ORDER BY
CASE WHEN shippeddate
   IS NOT NULL THEN 0 ELSE 1 END,
shippeddate, orderid;

Это решение возвращает нужные выходные данные со значениями NULL в конце, как показывают результаты запроса, приведенные на экране 1.

Экран 1. Выходные данные со значениями NULL в конце

Существует индекс idx_nc_shippeddate, определенный по shippeddate и orderid (подразумевается благодаря наличию кластеризованного индекса по orderid). Проблема в том, что поскольку первое выражение упорядочения обрабатывает столбцы, то, аналогично нарушению способности искать значение в индексе (sargability) фильтров, SQL Server не может полагаться на порядок индекса в данном примере. Это приводит к явной сортировке в плане для запроса, как показано на рисунке 1, и, следовательно, к масштабированию n*log n.

Рисунок 1. Упорядочение данных с последними значениями NULL с сортировкой

Можно применить следующий обходной прием. Подготовьте два запроса, один из которых возвращает строки, где shippeddate отличается от NULL, со столбцом, сортируемым с использованием алгоритма flag sort (назовем его sortcol) на основе константы 0, а другой возвращает строки, где shippeddate равен NULL, со столбцом flag sort на основе константы 1. Примените оператор UNION ALL между ними и поместите все в обобщенное табличное выражение (CTE). Внешний запрос к CTE возвратит только желаемые столбцы, упорядочивая строки по sortcol, shippeddate и orderid. В листинге 1 приводится полный код решения. План для этого запроса показан на рисунке 2.

Рисунок 2. План для запроса из листинга 1

Обратите внимание, что в индексе в плане используются два поиска, чтобы получить данные: один для строк, где shippeddate отличается от NULL (выдаются с упорядочением по shippeddate и orderid), а другой, где shippeddate равен NULL (также выдаются с упорядочением по shippeddate и orderid). Два оператора Compute Scalar выдают флаг на основе константы — 0 для строк, где shippeddate не NULL, и 1 для строк, где shippeddate равен NULL. Затем оператор cоединения слиянием (сцепления) объединяет два упорядоченных входа на основе порядка: столбец флага, shippeddate и orderid. Этот оператор аналогичен оператору cоединения слиянием, только вместо присоединения объединяются два сортированных входа. На рисунке 3 показано, как этот оператор работает с упрощенным образцом двух сортированных целочисленных входных массивов.

Рисунок 3. Иллюстрация cоединения слиянием (сцепления)

Алгоритм довольно прост.

Получить первую строку в каждом из сортированных входных массивов.
Пока не достигнут конец любой входной последовательности, если левый ключ сортировки меньше или равен правому ключу сортировки, выдать левую строку и прочитать следующую строку из левого входного массива. В противном случае выдать правую строку и прочитать следующую строку из правого входного массива.
Если в любом из входных массивов остались любые строки, вывести их.

Красота алгоритма в том, что его можно применить к предварительно упорядоченным входным массивам на основе сканирования порядка индексов (или поисков и просмотров диапазона), как на плане, показанном на рисунке 2. Таким образом, в этом случае план масштабируется линейно.

Оконная функция с последними значениями NULL

Оператор cоединения слиянием (сцепления) можно использовать, чтобы получить упорядоченные объединенные строки для любых целей, а не только для упорядочения представления. Например, оконным функциям, таким как ROW_NUMBER, требуются данные, сортированные по секциям окна и столбцам упорядочения окна или просто столбцам упорядочения окна, если отсутствует предложение секционирования окна. Например, предположим, что нужно вычислить номера строк для заказов на основе shippeddate по возрастанию, orderid по возрастанию, но с последними значениями NULL. Как и в предыдущем примере, в предложении упорядочения окна можно начать с выражения CASE, которое выдает флаг с более высоким значением упорядочения для значений NULL, чем для значений, отличных от NULL, а затем продолжить с shippeddate и orderid (листинг 2).

Вы получаете следующие выходные данные, показывающие номера строк начиная с первого для дат отправки, отличных от NULL, и последним диапазоном номеров строк, назначенным строкам с датой отправки NULL (экран 2).

Экран 2. Результаты работы листинга 2

План для этого запроса показан на рисунке 4.

Рисунок 4. Оконная функция с последними значениями NULL с сортировкой

Как и на рисунке 1, вследствие того, что предложение упорядочения окна начинается с выражения, обрабатывающего столбцы, оптимизатор не полагается на порядок индекса и применяет явную сортировку. Как и в предыдущем примере, вы можете избежать явной сортировки, используя объединенные запросы с флагом сортировки (sortcol), только в данном случае предложение упорядочения окна, а не предложение порядка представления основывается на sortcol, shippeddate и orderid. Полный запрос решения приведен в листинге 3. План для этого запроса показан на рисунке 5.

Рисунок 5. Оконная функция с последними значениями NULL с cоединением слиянием (сцеплением)

Обратите внимание на использование cоединения слиянием (сцепления), применяемого к двум предопределенным входам, выдающим объединенные строки, сортированные, как требуется оконной функции; поэтому явная сортировка не используется.

В других моих статьях рассматривались решения для задач с интервалами, в которых я использую этот прием, чтобы избежать явной сортировки. Вы можете найти примеры в серии статей о расчете одновременных сеансов и в статье об упаковке интервалов. В этих решениях я объединяю время начала интервалов с временем завершения интервалов в одну хронологически упорядоченную последовательность и с помощью оператора cоединения слиянием (сцепления) избавляюсь от необходимости выполнять явную сортировку.

Отмена сведения

Другой пример, в котором можно применять оператор cоединения слиянием (сцепления), чтобы избежать явной сортировки, — упорядочение несведенных данных. Для демонстрации метода я использую таблицу с именем CustSales, для создания и заполнения 1 000 000 строк которой выполняется код листинга 4.

В таблице CustSales присутствуют строка для каждого клиента (custid) и столбец для каждого года заказа (valyyyy) со значениями общего заказа для текущего клиента и года. Обратите внимание на то, что программный код создает индекс по (valyyyy, custid) для каждого из трех лет заказов. Задача — отменить сведение данных, чтобы получить строку для клиента и года, с одним результирующим столбцом, содержащим год (назовем его orderyear), и другим, содержащим значение (назовем его val). Кроме того, результаты нужно сортировать по столбцу val по возрастанию.

Существует два основных метода решения задач отмены сведения. В одном используется оператор UNPIVOT, а в другом оператор APPLY. Я привожу классическое решение с использованием оператора UNPIVOT в листинге 5.

План для этого запроса показан на рисунке 6.

Рисунок 6. План для запроса UNPIVOT

Обратите внимание на явный оператор сортировки в плане. При наличии 1 000 000 строк в исходной таблице для выполнения запроса на моем компьютере потребовалось 4 секунды (результаты отброшены, чтобы сосредоточиться на времени обработки). Из-за необходимости явной сортировки этот план масштабируется по закону n*log n.

В листинге 6 приведено решение с использованием оператора APPLY.

План для этого запроса показан на рисунке 7. Как можно заметить, он очень похож на использовавшийся для решения с оператором UNPIVOT, и в нем также применяется явная сортировка. Для выполнения запроса на моем компьютере потребовалось 4 секунды, и масштабирование происходило по закону n*log n.

Рисунок 7. План для запроса APPLY

Если вам не нравятся планы, полученные для решений на основе UNPIVOT и APPLY, то мы поймем друг друга. Интуиция подсказывает, что должен существовать способ использования индексов для комбинаций (valyyyy, custid). Действительно, такое решение существует. Вы составляете отдельный запрос для каждого года, возвращающий custid, применимую константу yyyy как orderyear и соответствующий столбец valyyyy как val для строк, где valyyyy имеет значение, отличное от NULL. Затем применяете операторы UNION ALL между запросами и упорядочиваете результат по столбцу val (листинг 7).

План для данного запроса показан на рисунке 8.

Рисунок 8. План для запроса UNION ALL

В этом методе дважды используется сохраняющий порядок оператор cоединения слиянием (сцепления), который полагается на порядок индекса. Один раз между запросами, обрабатывающими годы 2016 и 2017, и второй раз между результатом и запросом, обрабатывающим 2018 год. Этот запрос был выполнен на моем компьютере за одну секунду и имеет линейное масштабирование.

Наконец, ради любопытства, предположим, что мы хотим отменить сведение данных, сортируя строки по возрастающему значению val, только на этот раз строки со значениями NULL сохраняются в столбце val. В результате значения NULL наконец-то оказываются сортированными. Этого можно достичь, сочетая два приема, описанные в статье, — упорядочение последних значений NULL без сортировки и отмена сведения данных без сортировки. Таким образом, необходимо объединить шесть запросов, по одному для каждого из трех лет и для каждого случая NULL | не-NULL, получая флаг сортировки (sortcol), как показано в листинге 8.

План для этого решения (с использованием обозревателя планов SentryOne) представлен на рисунке 9.

Рисунок 9. План для запроса UNION ALL с сохранением значений NULL

Любопытно, что пять операторов cоединения слиянием (сцепления) используются в этом плане без необходимости явной сортировки, поэтому данный план масштабируется линейно.

Итак, мы выяснили, как переписать запросы, чтобы эффективно использовать возможности оптимизации. Моей целью было избежать явной сортировки с применением методов на основе оператора cоединения слиянием (сцепления), использующего и сохраняющего порядок. В следующей статье я продолжу рассказ о том, как избежать явной сортировки. Мы рассмотрим запросы, которые предусматривают обработку данных в порядке убывания.

Листинг 1. Обходной прием сортировки

WITH C AS
(
  SELECT orderid, shippeddate, 0 AS sortcol
  FROM Sales.Orders
  WHERE shippeddate IS NOT NULL
  UNION ALL
  SELECT orderid, shippeddate, 1 AS sortcol
  FROM Sales.Orders
  WHERE shippeddate IS NULL
)
SELECT orderid, shippeddate
FROM C
ORDER BY sortcol, shippeddate, orderid;

Листинг 2. Упорядочивание окна

SELECT orderid, shippeddate,
  ROW_NUMBER() OVER(ORDER BY
CASE WHEN shippeddate IS NOT NULL
  THEN 0 ELSE 1 END,
shippeddate, orderid) AS rownum
FROM Sales.Orders;

Листинг 3. Полный запрос решения с оконной функцией с последними значениями NULL

WITH C AS
(
  SELECT orderid, shippeddate, 0 AS sortcol
  FROM Sales.Orders
  WHERE shippeddate IS NOT NULL
  UNION ALL
  SELECT orderid, shippeddate, 1 AS sortcol
  FROM Sales.Orders
  WHERE shippeddate IS NULL
)
SELECT orderid, shippeddate,
  ROW_NUMBER() OVER(ORDER BY sortcol, shippeddate, orderid) AS rownum
FROM C;

Листинг 4. Создание и заполнение таблицы с именем CustSales

USE tempdb;
DROP TABLE IF EXISTS dbo.CustSales;
GO
CREATE TABLE dbo.CustSales
(
  custid INT NOT NULL
    CONSTRAINT PK_CustSales PRIMARY KEY,
  val2016 NUMERIC(12, 2) NULL,
  val2017 NUMERIC(12, 2) NULL,
  val2018 NUMERIC(12, 2) NULL,
);
INSERT INTO dbo.CustSales WITH (TABLOCK) (custid, val2016, val2017, val2018)
  SELECT custid,
    NULLIF(val2016, 0) AS val2016,
    NULLIF(val2017, 0) AS val2017,
    NULLIF(val2018, 0) AS val2018
  FROM ( SELECT N.n AS custid,
           ABS(CHECKSUM(NEWID())) % 1000 AS val2016,
           ABS(CHECKSUM(NEWID())) % 1000 AS val2017,
           ABS(CHECKSUM(NEWID())) % 1000 AS val2018
         FROM TSQLV4.dbo.GetNums(1, 1000000) AS N ) AS D;
CREATE INDEX idx_val2016 ON dbo.CustSales(val2016, custid);
CREATE INDEX idx_val2017 ON dbo.CustSales(val2017, custid);
CREATE INDEX idx_val2018 ON dbo.CustSales(val2018, custid);

Листинг 5. Решение с использованием оператора UNPIVOT

SELECT custid, CAST(RIGHT(valyear, 4) AS INT) AS orderyear, val
FROM dbo.CustSales
  UNPIVOT(val FOR valyear IN (val2016, val2017, val2018)) AS U
ORDER BY val;

Листинг 6. Решение с использованием оператора APPLY

SELECT custid, orderyear, val
FROM dbo.CustSales
  CROSS APPLY ( VALUES(2016, val2016),
                      (2017, val2017),
                      (2018, val2018) ) AS A(orderyear, val)
WHERE val IS NOT NULL
ORDER BY val;

Листинг 7. Использование индексов для комбинаций (valyyyy, custid)

SELECT custid, 2016 AS orderyear, val2016 AS val
FROM dbo.CustSales
WHERE val2016 IS NOT NULL
UNION ALL
SELECT custid, 2017 AS orderyear, val2017 AS val
FROM dbo.CustSales
WHERE val2017 IS NOT NULL
UNION ALL
SELECT custid, 2018 AS orderyear, val2018 AS val
FROM dbo.CustSales
WHERE val2018 IS NOT NULL
ORDER BY val;

Листинг 8. Сочетание упорядочения последних значений NULL без сортировки и отмены сведения данных без сортировки

WITH C AS
(
  SELECT custid, 2016 AS orderyear, val2016 AS val, 0 AS sortcol
  FROM dbo.CustSales
  WHERE val2016 IS NOT NULL
  UNION ALL
  SELECT custid, 2016 AS orderyear, val2016 AS val, 1 AS sortcol
  FROM dbo.CustSales
  WHERE val2016 IS NULL
  UNION ALL
  SELECT custid, 2017 AS orderyear, val2017 AS val, 0 AS sortcol
  FROM dbo.CustSales
  WHERE val2017 IS NOT NULL
  UNION ALL
  SELECT custid, 2017 AS orderyear, val2017 AS val, 1 AS sortcol
  FROM dbo.CustSales
  WHERE val2017 IS NULL
  UNION ALL
  SELECT custid, 2018 AS orderyear, val2018 AS val, 0 AS sortcol
  FROM dbo.CustSales
  WHERE val2018 IS NOT NULL
  UNION ALL
  SELECT custid, 2018 AS orderyear, val2018 AS val, 1 AS sortcol
  FROM dbo.CustSales
  WHERE val2018 IS NULL
)
SELECT custid, orderyear, val
FROM C
ORDER BY sortcol, val;