Оптимизация функций ранжирования в T-SQL

184

Работа с базами данных в .NET Framework --- Оконные функции T-SQL --- Оптимизация функций ранжирования

Эта статья посвящена оптимизации функций ранжирования: ROW_NUMBER, NTILE, RANK и DENSE_RANK. Итераторы, вычисляющие функции ранжирования, работают со строками, по одной секции за раз и в порядке, заданном в предложении упорядочения окна. Поэтому если нужно избежать сортировки, надо соблюдать описанные ранее рекомендации POC. В своих примерах я предполагаю, что созданный в предыдущей статье индекс idx_actid_val_i_tranid существует. Если у вас его нет, создайте этот индекс, чтобы получать результаты, максимально близкие к моим.

Два итератора, которые помогают вычислять функции ранжирования — Segment и SequenceProject. Segment служит для пересылки одного сегмента строк за раз в следующий итератор. В нем есть свойство Group By, которое определяет список выражений, по которым надо сегментировать. Результатом его работы в каждой строке является флаг, который называется SegmentN (где N представляет определенное число в выражении, например Segment1004) и указывает, является ли строка первой в сегменте.

Итератор Sequence Project отвечает собственно за вычисление функции ранжирования. Оценивая флаги, созданные предыдущими итераторами Segment, он сбрасывает, сохраняет или увеличивает значение ранга, полученного на основе предыдущей строки. Результатом работы итератора Sequence Project со значением ранжирования является значение по имени ExpressionN (и здесь N представляет определенное число выражения, например Expr1003).

Оптимизация функции ROW_NUMBER

Для описания оптимизации функции ROW_NUMBER я воспользуюсь следующим запросом:

SELECT actid, tranid, val,
  ROW_NUMBER() OVER(PARTITION BY actid ORDER BY val) AS rownum
FROM dbo.Transactions;

План этого запроса показан на рисунке:

Так как есть POC-индекс, просмотр осуществляется упорядоченно. Как вы помните, в отсутствие такого индекса в плане появляется дорогой итератор Sort. Далее итератор Segment формирует группы строк, основываясь на столбце секционирования actid, и создает флаг (SegmentN), указывающий начало новой секции. Там, где SegmentN указывает на начало новой секции, итератор Sequence Project генерирует номер строки (и называет это ExprN), в других местах он увеличивает предыдущее значение на единицу.

У функций ранжирования есть интересная особенность упорядочения окна, которая может в некоторых случаях становиться препятствием. Предложение упорядочения окна в функциях ранжирования является обязательным и не может быть основано на константе. Обычно это не проблема, потому что обычно ранжирование создается на основе определенных требований по упорядочению, которые соответствуют некоторым атрибутами и выражениям таблицы. Однако иногда просто нужно создавать уникальные значения без определенного порядка. Вы можете сказать, что если упорядочение не имеет значения, можно задать произвольный атрибут для упорядочения. Но тогда надо помнить, что если POC-индекса нет, план будет содержать итератор Sort, или будет вынужден просматривать упорядоченный индекс, если он существует. Нужно разрешить чтение данных, которое не обязательно должно выполняться в порядке, заданном в индексе, что, возможно, позволит повысить производительность, а также хочется избежать сортировки.

Как уже говорилось, предложение упорядочения обязательно и SQL Server не разрешит упорядочение по константе, например такое как ORDER BY NULL. Но удивительно то, что если передать выражение с вложенным запросом, возвращающим константу, например ORDER BY (SELECT NULL), SQL Server его примет. Но раскрыв выражение, оптимизатор понимает, что упорядочение одинаково для всех строк, и удаляет требование по упорядочению из входных данных. Вот запрос, демонстрирующий этот метод:

SELECT actid, tranid, val,
  ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM dbo.Transactions;

План этого запроса показан на рисунке:

План запроса с функцией ROW_NUMBER с произвольным упорядочением

Посмотрите свойства итератора Index Scan и убедитесь, что значение свойства Ordered равно False, то есть от итератора не требуется возвращать данные в порядке ключей индекса.

Функция NTILE

Напомню обсуждение NTILE из статьи "Функции ранжирования": принцип работы этой функции основан на двух элементах — номер строки и число строк в секции. Если они известны, можно применять формулу для вычисления номера подгруппы. Из предыдущего раздела вы уже знаете, как вычисляется и оптимизируется номер строки. Сложность здесь заключается в вычислении числа строк в соответствующей секции. Я сказал «сложность», потому что для этого недостаточно одного прохода данных. Причина в том, что число строк в секции нужно знать для каждой строки, а это число нельзя узнать, пока не просмотрены все строки секции. Чтобы посмотреть, как оптимизатор решает эту задачу, посмотрим на следующий запрос:

SELECT actid, tranid, val,
  NTILE(100) OVER(PARTITION BY actid ORDER BY val) AS rownum
FROM dbo.Transactions;

План этого запроса:

Оптимизатор решает задачу следующим образом:

Читает строки из POC-индекса, если он есть. (В нашем случае он существует.)
Сегментирует строки по элементу секционирования (в нашем случае actid).
Сохраняет строки секции по одной за раз в рабочей таблице (в плане представлено верхним итератором Table Spool).
Дважды читает временную таблицу (итераторы Table Spool в нижней части плана) — один раз для вычисления числа строк итератором Stream Aggregate и второй для получения подробной информации о строках.
Соединяет агрегат и строку с детальной информацией, чтобы получить число строк и подробные сведения в одной целевой строке.
Снова сегментирует строки по элементу секционирования (в нашем случае actid).
Использует итератор Sequence Project для вычисления номера подгруппы.

Заметьте, что итератор Table Spool представляет рабочую таблицу в tempdb. Хотя его доля в плане кажется небольшой, он довольно ресурсоемкий. Чтобы вы поняли насколько, скажу, что запрос с функцией ROW_NUMBER выполняется на моей машине две секунды, а с функцией NTILE — 45 секунд. Далее, при обсуждении функций агрегирования без упорядочения и кадрирования я расскажу, как избежать такого ресурсоемкого создания промежуточных таблиц.

Функции RANK и DENSE_RANK

Функции RANK и DENSE_RANK выполняют вычисления очень похоже на ROW_NUMBER за тем исключением, что они чувствительны к связям в значениях, используемых для упорядочения. Как вы помните, RANK возвращает число, на единицу большее, чем число строк с меньшим значением значения, по которому выполняется упорядочение, a DENSE_RANK вычисляется как единица плюс число уникальных строк со значением упорядочения меньшим, чем текущее значение. Поэтому помимо флага сегментирования, который обозначает начало новой секции, оператору Sequence Project также нужно знать, не изменилось ли значение упорядочения. В приведенном ранее плане для функции ROW_NUMBER был один итератор Segment, сгруппированный по элементу секционирования. Планы для RANK и DENSE_RANK похожи, но им нужен второй итератор Segment с группировкой по элементам и секционирования, и упорядочения. Вот пример, вызывающий функцию RANK:

SELECT actid, tranid, val,
  RANK() OVER(PARTITION BY actid ORDER BY val) AS rownum
FROM dbo.Transactions;

План этого запроса:

Первый итератор Segment группируется по actid, возвращая флаг Segment1004, второй тоже группируется по actid, val и возвращает флаг Segment1005. Если Segment1004 указывает, что строка является первой в секции, Sequence Project возвращает единицу. В противном случае Segment1005 указывает, что значение упорядочения изменилось, а Sequence Project возвращает соответствующий номер строки. Если значение упорядочения не изменилось, Sequence Project возвращает значение, равное предыдущему рангу.

Функция DENSE_RANK вычисляется похожим образом. Вот пример запроса:

SELECT actid, tranid, val,
  DENSE_RANK() OVER(PARTITION BY actid ORDER BY val) AS rownum
FROM dbo.Transactions;

План этого запроса:

Основное отличие состоит в том, что вычисляет итератор Sequence Project. Если Segment1005 указывает, что значение упорядочения изменилось, Sequence Project добавляет единицу к предыдущему «плотному» рангу.

Из-за того, что планы для RANK и DENSE_RANK так похожи на план для ROW_NUMBER, производительность ведет себя аналогичным образом. На моем компьютере каждый из трех запросов выполняется две секунды.