SQL Server: как избежать сортировки по убыванию

В данной статье речь пойдет о запросах, в которых необходимо обрабатывать данные в убывающем порядке. Первая статья по этой теме, «Сортировка без cоединения слиянием», опубликована в предыдущем номере журнала.

В ней было рассказано о том, как избежать явной сортировки в запросах, в ходе которых требуется обрабатывать данные по порядку. Мы рассмотрели оператор соединения слиянием Merge Join (Concatenation), который зависит от порядка, сохраняет порядок и объединяет два набора упорядоченных входных данных. В этой статье я расскажу о запросах, в которых данные необходимо обрабатывать в порядке убывания. Будут рассмотрены случаи, в которых оптимизатор SQL Server не распознает возможности использовать порядок индекса, и описаны приемы устранения проблемы. Как и в предыдущей статье, в примерах будет использоваться тестовая база данных TSQLV4 (http://tsql.solidq.com/SampleDatabases/TSQLV4.zip).

Порядок представления

Как известно, двоичные индексы на основе сбалансированного дерева для хранящихся на диске таблиц имеют двунаправленный список и поддерживают как просмотр ORDERED FORWARD (просмотры диапазона), так и просмотр ORDERED BACKWARD. Взглянув на операторы просмотра индекса Index Scan и поиска в индексе Index Seek, можно сказать, что требуется вернуть строки в порядке ключа индекса, проверив свойство Ordered. Оно будет иметь значение True для упорядоченного просмотра и False, если от оператора не требуется возвращать данные в порядке ключа индекса. Свойство Scan Direction указывает направление просмотра — FORWARD или BACKWARD. Я продемонстрирую это на простом примере упорядочения, прежде чем показать неверные запросы.

Приведенный в листинге 1 запрос (назовем его запросом 1) возвращает заказы, упорядоченные по orderid, по возрастанию.

Для таблицы существует кластеризованный индекс с orderid (по возрастанию) в качестве ключа; поэтому в плане используется просмотр ORDERED FORWARD индекса, как показано на плане запроса на рисунке 1.

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

Аналогично индекс можно просматривать в направлении ORDERED BACKWARD, чтобы извлекать данные по убыванию. Это показывает запрос, приведенный в листинге 2 (назовем его запросом 2). План для этого запроса вы видите на рисунке 2.

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

Одно из различий между просмотром ORDERED FORWARD и ORDERED BACKWARD заключается в том, что в первом случае может потенциально использоваться параллелизм, но для второго на сегодня нет реализации с параллелизмом в подсистеме хранилища. В остальном в обоих случаях необходимости в операции сортировки не возникает, так как данные извлекаются из индекса уже упорядоченными. Просмотр упорядоченного индекса масштабируется линейно. Собственно сортировка выполняет просмотр нелинейным образом, а именно, по закону n*log n. Поэтому, особенно при обработке очень большого числа строк, полезно избежать явной сортировки, извлекая заранее упорядоченные данные из индекса.

Функция упорядоченного набора STRING_AGG

Иногда оптимизатор не распознает, что может использовать порядок индекса, и это, к сожалению, приводит к явной сортировке. Особенно часто это случается, когда данные необходимо обрабатывать в порядке убывания в группах или секциях окна. Для начала рассмотрим пример, в котором используется порядок по возрастанию, а затем я покажу, что происходит, когда применяется порядок по убыванию. Предположим, что вы хотите задействовать функцию STRING_AGG, чтобы выдать для каждого клиента список значений orderid с разделительными запятыми, упорядоченный по orderdate по возрастанию и по orderid по возрастанию (для разрешения конфликтов). Требования к упорядочению представления отсутствуют, поэтому вы не планируете вводить в запрос предложение ORDER BY представления. В надежде задействовать оптимизацию статистического выражения потока на основе порядка без необходимости в явной сортировке, мы создаем следующий поддерживающий индекс:

CREATE INDEX idx_cid_od_oid ON
   Sales.Orders (custid, orderdate, orderid);

Затем используется запрос, показанный в листинге 3 (назовем его запросом 3), для выполнения задачи.

Этот запрос создает выходные данные, приведенные на экране 1 в сокращенной форме. План для этого запроса показан на рисунке 3.

Экран 1. Выходные данные запроса 3

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

Обратите внимание, что в плане показан просмотр ORDERED FORWARD индекса, за которым следует оператор Stream Aggregate на основе порядка, и отсутствует явная операция сортировки. Пока все хорошо. Но предположим, что нам необходимо объединить значения orderid на основе упорядочения orderdate по убыванию, orderid по убыванию. Чтобы это сделать, мы выдаем запрос, показанный в листинге 4 (назовем его запросом 4).

Этот запрос формирует выходные данные, приведенные на экране 2.

Экран 2. Выходные данные запроса 4

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

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

Напомню, что требование упорядочения представления в запросе отсутствует. Поэтому теоретически у оптимизатора не должно возникнуть проблем с использованием просмотра ORDERED BACKWARD, чтобы выдавать строки в порядке, необходимом оператору статистического выражения потока. Но, очевидно, оптимизатор не распознает этого, и в итоге применяет явную сортировку.

Возможное решение — задействовать индекс с упорядочением по убыванию. Создайте индекс по списку ключей (custid, orderdate DESC, orderid DESC), например:

CREATE INDEX idx_cid_odD_oidD ON
   Sales.Orders (custid, orderdate
   DESC, orderid DESC);

Повторно выполните запрос, приведенный в листинге 5 (назовем его запросом 5). Вы получите выходные данные, представленные на экране 3.

Экран 3. Результаты запроса 5

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

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

Обратите внимание, что индекс просматривается в направлении ORDERED FORWARD и явной сортировки не требуется. Это решение может быть приемлемым, если всегда требуется возвращать значения в порядке убывания. Но что делать, если иногда нужно возвращать значения по возрастанию, а иногда — по убыванию? Создание двух отдельных индексов для каждого варианта выглядит лишней жертвой. Но, оказывается, существует необычный, но простой обходной маневр. Достаточно добавить предложение ORDER BY представления, запросив представление результата в порядке custid по убыванию. Благодаря этому запросу оптимизатор распознает, что можно объединить оба требования упорядочения, в группе и представлении, и, самое главное, в обоих случаях полагается на порядок индекса. Чтобы это продемонстрировать, сначала выполним следующий код, дабы отбросить индекс по убыванию:

DROP INDEX idx_cid_odD_oidD ON
   Sales.Orders;

Затем повторно выполним запрос (назовем его запросом 6), показанный в листинге 6.

В результате формируются выходные данные, приведенные на экране 4 (обратите внимание, что идентификаторы клиентов выдаются в порядке убывания). План для этого запроса представлен на рисунке 6.

Экран 4. Результаты запроса 6

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

Индекс по возрастанию просматривается в направлении ORDERED FORWARD, и необходимости в явной сортировке нет!

Функции окна

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

Запрос, показанный в листинге 7 (назовем его запросом 7), вычисляет номера строк на основе упорядочения orderid по возрастанию.

Этот запрос формирует выходные данные, приведенные на экране 5.

Экран 5. Результаты запроса 7

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

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

Для таблицы имеется кластеризованный индекс, определенный по orderid, по возрастанию, в качестве ключа. В плане используется просмотр в направлении ORDERED FORWARD в индексе, чтобы предоставить функции окна строки в порядке, необходимом для вычислений, и поэтому нет необходимости в явной сортировке.

Затем выполните код, показанный в листинге 8 (назовем его запросом 8), запросив номера строк, вычисляемых на основе orderid в порядке убывания.

Этот запрос формирует выходные данные, представленные на экране 6.

Экран 6. Выходные данные запроса 8

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

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

Здесь план также просматривает кластеризованный индекс, чтобы избежать явной сортировки, только на этот раз используется просмотр в направлении ORDERED BACKWARD.

К сожалению, оптимизатор не рассматривает просмотр ORDERED BACKWARD, когда функция окна имеет предложение секционирования окна, и необходимо задействовать порядок по убыванию. Чтобы это продемонстрировать, предположим, что необходимо вычислить номера строк, секционированных по custid и упорядоченных по orderdate, orderid (начнем с примера с порядком по возрастанию). Следующий индекс идеален для этого вычисления (тот же индекс, что использовался в разделе, посвященном функциям сгруппированных упорядоченных наборов):

CREATE INDEX idx_cid_od_oid ON
   Sales.Orders (custid, orderdate, orderid);

Используем код, показанный в листинге 9 (назовем его запросом 9), чтобы получить желаемый результат.

Этот запрос выдает выходные данные, приведенные на экране 7.

Экран 7. Выходные данные запроса 9

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

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

Как мы видим, план выполняет просмотр в направлении ORDERED FORWARD в индексе, поэтому явной сортировки не требуется. Затем выполните код, показанный в листинге 10 (назовем его запросом 10), на этот раз запросив номера строк, вычисляемых в порядке убывания.

Этот запрос выдает выходные данные, представленные на экране 8.

Экран 8. Выходные данные запроса 10

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

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

Теоретически оптимизатор мог бы использовать просмотр ORDERED BACKWARD в индексе, поскольку запрос не содержит требований упорядочения представления. Однако этого не происходит. Используется неупорядоченный просмотр, за которым следует явная сортировка.

Как и в приведенном выше примере с функцией сгруппированного упорядоченного набора, здесь один из вариантов — создать индекс с упорядочением по убыванию. Но это означает, что если вычислять номера строк нужно иногда в порядке по возрастанию, а иногда по убыванию, то потребуется два индекса. Можно применить такой же прием, как в случае со сгруппированным запросом с функцией STRING_AGG, где к запросу добавлено предложение ORDER BY представления и строки представляются на основе custid с упорядочением по убыванию. Как по волшебству, оптимизатор сможет использовать порядок индекса для обеих целей. Попробуем применить этот прием к нашему запросу, приведенному в листинге 11 (назовем его запросом 11).

Этот запрос выдает выходные данные, показанные на экране 9. План для этого запроса представлен на рисунке 11.

Экран 9. Выходные данные запроса

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

План выполняет просмотр ORDERED BACKWARD в индексе и избегает явной сортировки.

Применение в табличных выражениях

Использование приема ORDER BY позволяет избежать сортировки при прямом запросе таблицы. Но что делать, если нужно определить табличное выражение, такое как представление, на основе функции сгруппированного упорядоченного набора или функции секционированного окна, с порядком по убыванию в группе или окне соответственно? Рассмотрим показанное в листинге 12 представление в качестве примера.

Пользователь, направляющий запрос к представлению, может ничего не знать о проблемах, связанных с явной сортировкой. Пользователь, который должен направить запрос к данным, но не заинтересован в определенном порядке представления, скорее всего, обойдется без предложения ORDER BY представления, например так (назовем это запросом 12):

SELECT * FROM Sales.CustOrders;

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

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

Обратите внимание на явную сортировку в плане. Естественно, можно создать индекс, упорядоченный по убыванию, чтобы избежать сортировки, но что если вы предпочитаете иметь всего один индекс, упорядоченный по возрастанию, и хотите использовать порядок индекса для вычислений, упорядоченных как по возрастанию, так и по убыванию? Если вы контролируете запросы к представлению, то можете просто добавить предложение ORDER BY представления с порядком по убыванию в запрос к представлению (назовем его запросом 13):

SELECT * FROM Sales.CustOrders
   ORDER BY custid DESC;

После того как SQL Server встраивает внутренний запрос, вы, в сущности, получаете эквивалент ранее рассмотренного запроса 6. План для этого запроса показан на рисунке 13.

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

Как мы видим, в плане используется просмотр ORDERED BACKWARD в индексе, что позволяет избежать явной сортировки.

Но что если не вы составляете запросы к представлению, и ничего не подозревающие пользователи регулярно делают запросы без предложения ORDER BY представления? Вам необходимо решение как часть определения представления. Первой попыткой может быть введение предложения ORDER BY во внутренний запрос представления, например, как в листинге 13.

Однако эта попытка завершается ошибкой с сообщением, что предложение ORDER BY не поддерживается во внутреннем запросе представления (экран 10).

Экран 10. Ошибка при выполнении запроса из листинга 13

Предложение ORDER BY недействительно в представлениях, встраиваемых функциях, производных таблицах, подчиненных запросах и обобщенных табличных выражениях, если также не указаны TOP, OFFSET или FOR XML.

ORDER BY не поддерживается, потому что представление, как считается, реализует отношение, а отношение является неупорядоченным. Как указывается в сообщении об ошибке, из этого правила существуют исключения, когда ORDER BY используется для целей, отличных от порядка представления, например для поддержки фильтра TOP или OFFSET-FETCH. Учитывая это, вы можете попробовать воспользоваться фильтром TOP (100) PERCENT, просто чтобы разрешить применение предложения ORDER BY, например, как в листинге 14.

На этот раз SQL Server позволяет создать представление. Затем вы запрашиваете представление без предложения ORDER BY представления:

SELECT * FROM Sales.CustOrders;

Однако вы получаете тот же план, что показан на рисунке 13, с явным оператором сортировки. Дело в том, что, поскольку внешний запрос не имеет предложения ORDER BY, а внутренний запрашивает 100% строк, SQL Server в ходе оптимизации удаляет комбинацию TOP и ORDER BY. Это объясняется тем, что, поскольку внешний запрос не имеет предложения ORDER BY представления, порядок представления обеспечивать не нужно. Возможный обходной прием — использовать TOP с очень большим количеством строк, например, как в листинге 15.

Повторно направьте запрос к представлению без предложения ORDER BY (назовем его запросом 14):

SELECT * FROM Sales.CustOrders;

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

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

На этот раз, как можно заметить, индекс просматривается в направлении ORDERED BACKWARD и удается избежать явной сортировки. Другой способ обойти затруднение — задействовать OFFSET 0 ROWS (листинг 16).

Использование OFFSET 0 ROWS в отсутствие предложения FETCH означает возвращение всего.

Повторно направим запрос к представлению без предложения ORDER BY:

SELECT * FROM Sales.CustOrders;

Вы получаете тот же план, что и на рисунке 14, с просмотром индекса ORDERED BACKWARD и без сортировки.

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

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

USE TSQLV4; -- http://tsql.solidq.com/SampleDatabases/TSQLV4.zip

SELECT orderid, orderdate, custid
FROM Sales.Orders
ORDER BY orderid;

SELECT orderid, orderdate, custid
FROM Sales.Orders
ORDER BY orderid DESC;

SELECT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate, orderid ) AS custorders
FROM Sales.Orders
GROUP BY custid;

SELECT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid;

SELECT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid;

SELECT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid
ORDER BY custid DESC;

SELECT orderid, orderdate, custid,
  ROW_NUMBER() OVER(ORDER BY orderid) AS rownum
FROM Sales.Orders;

SELECT orderid, orderdate, custid,
  ROW_NUMBER() OVER(ORDER BY orderid DESC) AS rownum
FROM Sales.Orders;

SELECT custid, orderdate, orderid,
  ROW_NUMBER() OVER(PARTITION BY custid ORDER BY orderdate, orderid) AS rownum
FROM Sales.Orders;

SELECT custid, orderdate, orderid,
  ROW_NUMBER() OVER(PARTITION BY custid ORDER BY orderdate DESC, orderid DESC) AS rownum
FROM Sales.Orders;

SELECT custid, orderdate, orderid,
  ROW_NUMBER() OVER(PARTITION BY custid ORDER BY orderdate DESC, orderid DESC) AS rownum
FROM Sales.Orders
ORDER BY custid DESC;

CREATE OR ALTER VIEW Sales.CustOrders
AS

SELECT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid;
GO

CREATE OR ALTER VIEW Sales.CustOrders
AS

SELECT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid
ORDER BY custid DESC;
GO

CREATE OR ALTER VIEW Sales.CustOrders
AS

SELECT TOP (100) PERCENT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid
ORDER BY custid DESC;
GO

CREATE OR ALTER VIEW Sales.CustOrders
AS

SELECT TOP (1000000000000) custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid
ORDER BY custid DESC;
GO

CREATE OR ALTER VIEW Sales.CustOrders
AS

SELECT custid,
  STRING_AGG( CAST(orderid AS VARCHAR(20)), ‘,’ )
    WITHIN GROUP( ORDER BY orderdate DESC, orderid DESC ) AS custorders
FROM Sales.Orders
GROUP BY custid
ORDER BY custid DESC
OFFSET 0 ROWS;
GO