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

Замечу также, что некоторые формулы, приведенные здесь, являются результатом моих попыток реконструирования соотношений, используемых для оценки числа элементов, поэтому существует вероятность ошибок. Кроме того, все тесты выполнялись на версии SQL Server 2014 RTM, так что не исключено, что, по мере выхода следующих сборок, формулы оценки числа элементов поменяются.

Проблема возрастающего ключа

Проблема возрастающего ключа — это очередная классическая ситуационная задача сопоставления сканирования и поиска. Она будет продемонстрирована на примере таблицы Orders2 с 900 000 строк, создаваемой в результате выполнения кода, приведенного в листинге 1.

Для применения ограничения первичного ключа SQL Server создает некластеризованный индекс PK_Orders2 со столбцом orderid в качестве ключа. В процессе создания индекса строится гистограмма по столбцу orderid. Для анализа гистограммы выполним код:

DBCC SHOW_STATISTICS (‘dbo.Orders2’, ‘PK_Orders2’) WITH HISTOGRAM;

Результат выполнения кода показан в таблице 1.

 

Гистограмма

 

В данный момент все значения orderid из таблицы моделируются гистограммой; минимальное значение — 1, максимальное — 900 000. Выполняя запросы с применением фильтра к диапазону значений orderid, мы должны получить точные оценки числа элементов и, следовательно, оптимальные планы. Рассмотрим, например, два запроса, приведенные в листинге 2.

Первый запрос отфильтровывает малое количество строк, а второй — большое. Планы запросов показаны на рисунках 1 и 2 соответственно.

 

План с высокой избирательностью
Рисунок 1. План с высокой избирательностью

 

 

План с низкой избирательностью
Рисунок 2. План с низкой избирательностью

 

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

  • предусматривает применение поиска и нескольких уточняющих запросов;
  • является последовательным;
  • применяет сортировку с последующим применением агрегата потока;
  • имеет достаточно выделенной памяти для операций сортировки (без предупреждений о сбросе данных).

План запроса с низкой избирательностью (большое число отфильтрованных строк):

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

Проблема возрастающего ключа обычно возникает при запрашивании последнего диапазона в столбце, где значения постоянно возрастают. Например, в нашей таблице Orders2 постоянно увеличиваются значения ID новых заказов. Гистограмма обычно обновляется через каждые (500 + 20% числа записей) изменений в столбце. В нашей таблице в очередной раз это произойдет после добавления 180 500 строк. Это означает, что обычно последний добавленный диапазон записей гистограммой не моделируется. Для примера выполним код, добавляющий 100 000 строк, запросим таблицу и вновь проанализируем гистограмму (см. листинг 3).

В результате получаем гистограмму, аналогичную приведенной в таблице 1, согласно которой максимальным зарегистрированным значением по-прежнему является 900 000, то есть 100 000 новых значений гистограммой не моделируются. То, что теперь будет происходить при запросе диапазона, выходящего за рамки максимального значения в гистограмме, очень интересно, а в некоторых случаях — неожиданно. Метод, используемый SQL Server для оценки числа элементов в подобном случае, зависит от ряда факторов: версии блока оценки числа элементов (CE) (более старая, то есть до SQL Server 2014, или более новая), типа столбца (целый или числовой начиная с 0 или другой), а также от уникальности столбца.

Если столбец уникален и относится к целому или числовому типу начиная с 0

В версиях, предшествующих SQL Server 2014, при запрашивании диапазона значений ID заказов блок оценки числа элементов выполняет эту оценку по значениям, моделируемым гистограммой. Соответственно, при выходе диапазона фильтра за максимум, регистрируемый гистограммой, как правило, получается сильно заниженная оценка числа строк. Это может привести к тому, что оптимизатор будет делать неоптимальный выбор. Данную проблему можно продемонстрировать на примере приведенного ниже запроса. Запрос выполняется в SQL Server 2014, поэтому приходится указать флаг трассировки 9481, чтобы использовать более старую версию CE:

SELECT empid, COUNT (*) AS numorders
FROM dbo.Orders2
WHERE orderid > 900000
GROUP BY empid
OPTION (QUERYTRACEON 9481);

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

 

План с заниженной оценкой числа элементов
Рисунок 3. План с заниженной оценкой числа элементов

 

По гистограмме получается число строк, равное 1. В действительности должен получиться 0, но для блока оценки числа элементов допустимым оцениваемым минимумом является 1. Фактическое число — 100 000. Следовательно, оптимизатор принимает ряд не самых удачных решений:

  • вместо сканирования применяется поиск и много уточняющих запросов;
  • вместо параллельного плана используется последовательный;
  • вместо локального агрегата хеша с последующим глобальным агрегатом потока применяется сортировка с последующим применением агрегата потока;
  • нет достаточного объема памяти, выделенной для операций сортировки, следствием чего являются два цикла сброса в tempdb.

Существует несколько способов исправления этой ситуации.

  1. Добавить задание, предусматривающее более частое, выполняемое вручную обновление статистики столбца.
  2. Включить флаг трассировки 2371, вынуждая SQL Server уменьшать выраженное в процентах значение, включенное в определение частоты обновления статистики, по мере увеличения числа строк. Подробнее об этом рассказано в статье http://blogs.msdn.com/b/saponsqlserver/archive/2011/09/07/changes-to-automatic-update-statistics-in-sql-server-traceflag-2371.aspx.
  3. Включить флаг трассировки 2389, вынуждая SQL Server определять столбцы, которые являются возрастающим ключом, и для этих столбцов создавать в памяти мини-гистограмму, моделирующую последние изменения при перекомпиляции плана. Подробнее об этом рассказано в статье http://blogs.msdn.com/b/ianjo/archive/2006/04/24/582227.aspx.
  4. Использовать SQL Server 2014. Новый блок оценки числа элементов определяет, когда фильтр запроса выходит за рамки максимального значения в гистограмме. Он имеет доступ к счетчику модификаций столбца (modctr), поэтому знает, сколько изменений было внесено с момента последнего обновления. Если столбец уникален и относится к целому или числовому типу, начиная с 0, SQL Server делает исходное предположение, что он является возрастающим. Поэтому оценка интерполируется на основе распределения значений в существующей гистограмме и числа изменений, имевших место с момента последнего обновления. В результате оценка получается более точной.

Выполним в SQL Server 2014 следующий запрос без флага трассировки (план приведен на рисунке 4), заставляющего использовать более старую версию блока оценки числа элементов:

SELECT empid, COUNT (*) AS numorders
FROM dbo.Orders2
WHERE orderid > 900000
GROUP BY empid;

 

План с точной оценкой
Рисунок 4. План с точной оценкой

 

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

Например, для предиката orderid >= 900000 оценка числа элементов находится следующим образом:

1 × (1 + 100000/900000) = 1,11111.

Для предиката orderid >= 899995 оценка вычисляется по-другому:

6 × (1 + 100000/900000) = 6,66666.

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

Например, для предиката orderid >= 900000 вычисляется точная оценка 100001, а для предиката orderid >= 899995 — точная оценка 100006.

Если столбец неуникальный и относится к целому или числовому типу, начиная с 0

Как говорилось выше, уникальность столбца и его тип могут влиять на метод оценки числа элементов, применяемый SQL Server. Ниже описаны методы, применяемые SQL Server, если уникальность столбца не обеспечивается и столбец относится к целому и числовому типу, начиная с 0. Выполним приведенный в листинге 4 код для повторного создания демонстрационных данных, но на этот раз с неуникальным индексом.

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

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

SELECT empid, COUNT (*) AS numorders
FROM dbo.Orders2
WHERE orderid > 900000
GROUP BY empid
OPTION (QUERYTRACEON 9481);

Как и в случае с уникальным индексом, получается сильно заниженная оценка числа элементов, равная 1.

Новая версия CE делает нечто удивительное и отличное от того, что бывает в случае с уникальным индексом. По всей вероятности, исходное предположение, что столбец является возрастающим, не делается. Поэтому к счетчику modctr применяется жестко заданное значение в процентах, зависящее от используемого оператора. Эти значения в процентах используются в оценках для предикатов с неизвестным входом. Например, для оператора > применяется 30%, а для оператора BETWEEN — 9%. В нашем случае значение modctr — 100000. Поэтому для запроса с предикатом orderid > 900000 оценка рассчитывается как 0,30 × 100000 = 30000. Запрос приведен ниже:

SELECT empid, COUNT (*) AS numorders
FROM dbo.Orders2
WHERE orderid > 900000
GROUP BY empid;

План запроса показан на рисунке 5 в подтверждение того, что использовался этот метод оценки числа элементов.

 

План запроса для неуникального целого столбца без пересечения (версия 2014)
Рисунок 5. План запроса для неуникального целого столбца без пересечения (версия 2014)

 

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

Удивительно, что если предикат фильтра пересекается с максимальным значением на гистограмме, то оба варианта CE (более старая и более новая версии) применяют оценку, основанную на существующей гистограмме, и пересчитывают ее с учетом значения счетчика modctr. Удивительно это потому, что при использовании CE новой версии, как мы только что видели, для фильтра предиката orderid > 900000 получается оценка, равная 30000, тогда как для orderid >= 900000 получается 1,11111! Оценка вычисляется как 1 + (100000/900000). В этом можно убедиться на примере следующего запроса:

SELECT empid, COUNT (*) AS numorders
FROM dbo.Orders2
WHERE orderid >= 900000
GROUP BY empid;

План запроса показан на рисунке 6.

 

План запроса для неуникального целого столбца с пересечением (версия 2014)
Рисунок 6. План запроса для неуникального целого столбца с пересечением (версия 2014)

 

В дополнение к тому, что разные версии CE используют разные методы, здесь мы также видим пример ситуации, когда одна и та же версия CE с одними и теми же входными данными дает для предиката с оператором >= в качестве оценки меньшее число, чем для предиката с оператором >.

Если столбец уникален и не относится к целому или числовому типу, начиная с 0

Далее мы рассмотрим случаи, когда столбец является уникальным и не относится к целому или числовому типу, начиная с 0. Например, типом столбца является NUMERIC (12, 2), FLOAT, DATETIME и т. д. Для тестирования этого случая в сценарии, генерирующем демонстрационные данные, просто сменим тип столбца orderid на NUMERIC (12, 2) и обеспечим создание уникального индекса. Начнем с предикатов фильтра, не пересекающихся с максимальным значением на гистограмме.

CE более старой версии последовательно выдает оценку 1. CE новой версии, видимо, использует следующую формулу (получена путем реконструирования):

(Процентное значение, предусмотренное для оператора с неизвестным входом × modctr)/(1 + modctr/новое входное значение числа элементов).

Например, для предиката orderid > 900000 получаем (0.30 × 100000)/ (1 + 100000/1000000) = 27272.7

Это несколько измененный в сторону уменьшения вариант формулы, используемой для целого или числового типа, начиная с 0. В данном случае для аналогичного предиката получаем оценку 30000.

Если предикат фильтра пересекается с максимальным значением на гистограмме, CE более старой версии пересчитывает оценочную гистограмму с учетом modctr, как и в случае целого или числового типа, начиная с 0.

CE новой версии действует похоже, но не совсем так. Если предикат фильтра включает верхнюю границу (например, orderid >= 900000), получается оценка 1. Если интервал предиката начинается перед максимальным значением (например, orderid >= 899995), то используется следующая формула (опять-таки, получена путем реконструирования):

(Оценка гистограммы — 1) × (1 + modctr/старое входное значение числа элементов) + 2

Таким образом, для предиката orderid >= 899995 получаем (6 — 1) × (1 + 100000/900000) + 2 = 7,55555.

Если столбец неуникален и не относится к целому или числовому типу, начиная с 0

В этом разделе рассматриваются случаи, когда столбец не является уникальным и не относится к целому или числовому типу, начиная с 0. Для исследования такого случая в сценарии, генерирующем демонстрационные данные, просто сменим тип столбца orderid на NUMERIC (12, 2) и обеспечим создание неуникального индекса. Как и раньше, начнем с предикатов фильтра, не пересекающихся с максимальным значением на гистограмме.

CE более старой версии, как и во всех других случаях, генерирует оценку 1. CE новой версии использует тот же метод, что и в случае с неуникальным столбцом, относящимся к целому или числовому типу, начиная с 0, а именно применяет к modctr процентное значение, предусмотренное для используемого оператора с неизвестным входом. Таким образом, для modctr, равного 100000, при использовании оператора > получаем оценку 30000.

Если предикат фильтра пересекается с максимальным значением на гистограмме, CE более старой версии последовательно пересчитывает гистограмму с учетом значения modctr.

При использовании CE новой версии, когда предикат фильтра включает верхнюю границу, оценка, видимо, получается из оценки гистограммы, пересчитанной с учетом modctr. Если интервал предиката начинается до максимального значения на гистограмме, то оценка, по-видимому, вычисляется как (оценка по гистограмме + 1), пересчитанная с учетом modctr.

Например, для предиката orderid >= 900000 получаем оценку 1,11111. Для предиката orderid >= 899995 оценка вычисляется как (6 + 1) × (1 + 100000/900000) = 7,77777.

Сводная таблица методов оценки числа элементов

В таблице 2 приведены разные методы, используемые блоком оценки числа элементов (CE) в различных обстоятельствах (опять-таки на основе результатов моих попыток реконструирования формул).

 

Методы оценки числа элементов

 

Разнообразие методов, используемых в новой версии СЕ в различных обстоятельствах, может привести в замешательство. Однако надеюсь, что эта статья даст вам некоторое представление о том, что происходит за гранью видимого, даже если иногда действия кажутся не совсем логичными.

Листинг 1. Тестовая таблица Orders2
SET NOCOUNT ON;
USE PerformanceV3; -- http://tsql.solidq.com/books/source_code/PerformanceV3.zip
IF OBJECT_ID(N’dbo.Orders2’, N’U’) IS NOT NULL DROP TABLE dbo.Orders2;
SELECT * INTO dbo.Orders2 FROM dbo.Orders WHERE orderid <= 900000;
ALTER TABLE dbo.Orders2 ADD CONSTRAINT PK_Orders2 PRIMARY KEY NONCLUSTERED(orderid);
Листинг 2. Пример двух запросов
-- Запрос с высокой избирательностью
SELECT empid, COUNT(*) AS numorders
FROM dbo.Orders2
WHERE orderid > 899900
GROUP BY empid;

-- Запрос с низкой избирательностью
SELECT empid, COUNT(*) AS numorders
FROM dbo.Orders2
WHERE orderid > 700000
GROUP BY empid;
Листинг 3. Добавление большого числа строк
-- Добавление еще 100000 строк
INSERT INTO dbo.Orders2
  SELECT *
  FROM dbo.Orders
  WHERE orderid > 900000 AND orderid <= 1000000;

-- Запрос
SELECT empid, COUNT(*) AS numorders
FROM dbo.Orders2
WHERE orderid > 900000
GROUP BY empid;

-- Повторный вывод статистики (тот же результат, что и в таблице 1)
DBCC SHOW_STATISTICS('dbo.Orders2', 'PK_Orders2') WITH HISTOGRAM;
Листинг 4. Создание данных с неуникальным индексом
-- Заполнение таблицы 900000 строк с созданием неуникального индекса
IF OBJECT_ID(N'dbo.Orders2', N'U') IS NOT NULL DROP TABLE dbo.Orders2;
SELECT * INTO dbo.Orders2 FROM dbo.Orders WHERE orderid <= 900000;
CREATE INDEX idx_orderid ON dbo.Orders2(orderid);
GO
-- Повторный вывод статистики (результат тот же, что в таблице 1)
DBCC SHOW_STATISTICS('dbo.Orders2', 'idx_orderid') WITH HISTOGRAM;
GO
-- Добавление еще 100000 строк
INSERT INTO dbo.Orders2
  SELECT *
  FROM dbo.Orders
  WHERE orderid > 900000 AND orderid <= 1000000;
-- Запрос
SELECT empid, COUNT(*) AS numorders
FROM dbo.Orders2
WHERE orderid > 900000
GROUP BY empid;
GO
-- Повторный вывод статистики (результат тот же, что в таблице 1)
DBCC SHOW_STATISTICS('dbo.Orders2', 'idx_orderid') WITH HISTOGRAM;