Поиск или сканирование. Часть 1

Поиск по индексу Index Seek и сканирование индекса (таблицы) Index (Table) Scan — два наиболее распространенных оператора, используемых в планах выполнения запроса. Бытует ошибочное мнение, что сканирование — это плохо, а поиск — хорошо. Однако на самом деле каждый из методов хорош в определенных обстоятельствах. Как правило, оптимизатор выбирает наилучший вариант, исходя из особенностей конкретной ситуации. В таких случаях нам остается лишь радоваться его способности находить идеальное решение. Однако специалисту по оптимизации запросов интересно выявить случаи, когда выбор оптимизатора не является удачным, чтобы внести исправления.

В этой статье будут продемонстрированы элементы языка, для которых оптимизатор способен выбрать наилучшую стратегию, учитывая характеристики данных и наличие индекса. В частности, здесь приводятся решения для полусоединений и антиполусоединений с использованием предиката EXISTS. Кроме того, будут показаны элементы языка с ограниченными возможностями оптимизации, так что приходится принимать меры для получения оптимального плана. В качестве демонстрации я приведу планы запросов вывода значения min или max для группы и n верхних позиций для группы.

Демонстрационные данные

Демонстрационные данные для статьи сформированы с помощью кода, приведенного в листинге 1.

Код создает таблицу Orders, содержащую 1 000 000 заказов, таблицу Employees, содержащую 200 сотрудников компании, из которых 100 занимались обработкой заказов, и таблицу Customers, содержащую 40 000 клиентов, из которых 20 000 размещали заказы. Для иллюстрации выбора оптимального решения код создает несколько индексов в таблице Orders.

Сканирование против поиска

Существует много задач, решаемых с применением отдельных групп логики, предусматривающей анализ одной или нескольких строк у каждой группы, например:

• Полусоединения (наличие) и антиполусоединения (отсутствие). Например, вывод работников компании, занимавшихся или не занимавшихся обработкой заказов, вывод клиентов, размещавших или не размещавших заказы.
• Значения min или max для группы. Например, вывод максимального ID заказа для каждого сотрудника компании/клиента.
• N верхних позиций для группы. Например, вывод заказа с максимальным ID для каждого сотрудника компании или клиента.

При решении таких задач полезно применять POC-индекс, построенный для большой таблицы (в нашем случае Orders). Аббревиатура POC происходит от названий элементов, участвующих в запросе и фигурирующих в описании индекса: секционирование (Partitioning), сортировка (Ordering) и покрытие (Coverage). Например, для задачи «вывести заказ (orderid, orderdate, empid, custid) с максимальным ID» P = empid, O = orderid DESC, а C = orderdate, custid. Элементы P и O составляют список ключа индекса, а элемент C — список INCLUDE. Действительно, один из индексов, создаваемых в листинге 1 для демонстрации оптимизации решения такой задачи с помощью POC-индекса, следующий:

CREATE INDEX idx_eid_oid_i_od_cid
  ON dbo.Orders(empid, orderid DESC)
    INCLUDE(orderdate, custid);

Что примечательно, в зависимости от плотности элемента «группа или секционирование», предпочтительными являются разные стратегии оптимизации.

Если элемент «секционирование» имеет большую плотность (малое число значений, каждое из которых встречается многократно), наилучшей стратегией будет поиск в индексе по каждому значению. Например, столбец empid в таблице Orders имеет большую плотность (100 различных ID сотрудников компании). Поэтому оптимальной стратегией вывода заказа с максимальным ID будет сканирование таблицы Employees и циклическое применение поиска в POC-индексе к таблице Orders для каждого сотрудника. Учитывая, что в таблицу Employees внесено 200 работников компании, это выльется в 200 операций поиска, что означает в сумме несколько сотен операций чтения. Для сравнения, полное сканирование POC-индекса выльется в несколько тысяч операций чтения.

С другой стороны, столбец custid имеет малую плотность в таблице Orders (20000 различных ID клиентов). Учитывая, что таблица Customers содержит 40 000 клиентов, стратегия поисковых проходов будет реализована ценой сотни тысяч операций чтения, тогда как сканирование обойдется всего в несколько тысяч таких операций.

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

Полусоединения и антиполусоединения

Оптимизируя запросы с помощью предиката EXISTS (или других методов) при обработке полусоединений и антиполусоединений, оптимизатор, безусловно, способен проанализировать потенциальные планы, один из которых включает сканирование, а другой — цикл операций поиска по индексу применительно к таблице большего размера. В действительности вопрос выходит далеко за рамки простого выбора между сканированием и циклом операций поиска, так как существует три алгоритма соединения (вложенные циклы, слияние и хеш-соединение). Однако я исхожу из того, что оптимизатор потенциально способен выбрать идеальную стратегию, помимо прочего, на основе характеристик данных. В качестве примера рассмотрим два запроса для случая полусоединения (см. листинг 2). Планы этих запросов показаны на рисунке 1.

Рисунок 1. Полусоединения

План первого запроса с высокой плотностью элемента «секционирование» предусматривает выполнение операций поиска по индексу применительно к таблице Orders. План второго запроса с низкой плотностью элемента «секционирование» предполагает сканирование индекса таблицы Orders.

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

Рисунок 2. Антиполусоединения

Опять-таки в случае низкой плотности план предусматривает использование сканирования, а в случае высокой плотности — операции поиска.

Значения min или max для группы

Задача min или max предполагает вывод минимального или максимального значения для каждой группы. Наиболее естественный путь решения такой задачи — простой групповой запрос. При наличии PO-индекса (элемент C здесь неактуален) оптимизатор теоретически может оценить плотность столбца группы и в соответствии с результатом оценки выбрать наилучшую стратегию — сканирование или цикл операций поиска. Однако на сегодня в оптимизаторе не реализована логика выполнения цикла операций поиска для группового запроса. Таким образом, независимо от плотности, план будет предусматривать сканирование индекса. Это хорошо при низкой плотности (например, для группы, собранной по атрибуту custid), но плохо при высокой (например, для группы, собранной по атрибуту empid).

Для демонстрации примера выбора неоптимальной стратегии рассмотрим следующий запрос:

-- Логических чтений 3474
SELECT empid, MAX(orderid) AS maxoid
FROM dbo.Orders
GROUP BY empid;

План этого запроса — первый на рисунке 3.

Рисунок 3. Значение max для группы

Если нужен план, в котором поиск применяется к каждому сотруднику компании, то решение необходимо переработать. Один из способов предполагает использование оператора CROSS APPLY:

-- Логических чтений 4 + 670
SELECT E.empid, O.orderid
FROM dbo.Employees AS E
  CROSS APPLY (SELECT TOP (1) O.orderid
               FROM dbo.Orders AS O
               WHERE O.empid = E.empid) AS O;

План этого запроса — второй на рисунке 3.

Как мы видим, это искомый план. Если вас удивляет, зачем нужно использовать оператор CROSS APPLY, а не просто скалярный коррелированный подзапрос, то напомню, что CROSS APPLY убирает строки левой таблицы, не имеющие соответствий, что в данном случае предпочтительно.

N верхних позиций для группы

Задача вывода N верхних позиций для каждой группы (например, последний заказ для каждого сотрудника компании или клиента) — еще один пример, когда типовые решения дают статическую конфигурацию плана; во всяком случае, это так в контексте противопоставления сканирования циклу операций поиска. Приведу два типовых решения:

1. Вычислить номера строк и отфильтровать строки с номером 1. Такое решение всегда предполагает сканирование.
2. Выполнить запрос к таблице, разбитой на группы или секции, и с помощью оператора CROSS APPLY применить запрос TOP (1) к таблице большего размера. Это решение предполагает цикл операций поиска.

Итак, чтобы вывести последний заказ для каждого клиента (низкая плотность), следует использовать решение с функцией ROW_NUMBER. Для вывода последнего заказа для каждого сотрудника компании (высокая плотность) следует использовать решение с оператором CROSS APPLY. В листинге 4 приведены оба примера. Планы запросов показаны на рисунке 4.

Рисунок 4. N верхних позиций для группы

Прокси CROSS APPLY

Любопытную задачу, относящуюся к последнему примеру, предложил Эрланд Соммарског, MVP по SQL Server. Вокруг этой задачи развернулась интересная дискуссия с участием Хьюго Корнелиса, Пола Уайта и других специалистов. Предположим, в последнем запросе требуется пополнить список SELECT столбцами из таблицы Orders, не покрываемыми индексом. Например, приведенный ниже запрос добавляет столбец filler в список SELECT:

-- Логических чтений 2445833
SELECT E.empid, O.orderdate,
O.orderid, O.custid, O.filler
FROM dbo.Employees AS E
  CROSS APPLY (SELECT TOP (1) *
               FROM dbo.Orders AS O
               WHERE O.empid = E.empid
               ORDER BY orderid DESC) AS O;

Это небольшое изменение заметно отражается на скорости выполнения запроса. В моей системе без этого дополнительного столбца запрос выполняется за 77 миллисекунд и производится всего несколько сотен операций чтения. С дополнительным столбцом число операций чтения вырастает до 2,5 млн, а время выполнения запроса — до 8 секунд. Казалось бы, оптимальным планом нового запроса стала бы следующая схема действий для каждого сотрудника компании:

1. Поиск в некластеризованном индексе idx_eid_oid_i_od_cid для сбора ключа кластеризации.
2. Применение уточняющего запроса ключа (поиск в кластеризованном индексе) для сбора столбца filler из базовой строки данных.

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

Рисунок 5. N верхних позиций для группы, непокрывающий индекс, неоптимальный вариант

Модель оптимизации использует исходное допущение, известное как включение (containment) и включение (inclusion). Включение (containment) предполагает, что если вы что-то ищете, то искомое существует. В случае эквивалентного соединения (equijoin) исходное положение таково, что различные значения в столбцах соединения, существующие на одной стороне, существуют и на другой. Исходное положение о включении (inclusion) аналогично, но для предиката фильтра равенства с константой, то есть допущение таково, что фильтруемое значение действительно существует. Посмотрим на остаточный предикат оператора Clustered Index Scan: O.empid = E.empid. Учитывая исходные допущения модели, если ID каждого сотрудника компании, являющийся объектом сканирования, действительно существует, то по законам статистики из каждой сотни строк одна строка будет искомым совпадением (плотность Orders.empid — 0.01). Таким образом, опять же по законам статистики, для выхода на искомую строку понадобится чтение всего пары страниц. Если исходные допущения модели корректны, то эта стратегия лучше, чем двойной поиск. Однако в нашем случае исходные допущения модели не выполняются, поскольку у нас в таблице Employees 200 сотрудников компании, из которых 100 не имеют искомых заказов. Поэтому в 100 случаях цикл сканирования будет выполняться от начала до конца. Следовательно, производительность такого решения очень низкая.

Исправить ситуацию можно несколькими способами. Если есть возможность расширить индекс включением отсутствующих столбцов (в нашем случае filler), то это лучше всего. В результате получаем план, аналогичный второму варианту на рисунке 4. Если такой возможности нет, то можно указать подсказку индекса к таблице Orders: WITH (INDEX (idx_eid_oid_i_od_cid)). В результате получаем стратегию двойного поиска. Если вы предпочитаете не пользоваться подсказками, то можно применить метод, который я называю промежуточным CROSS APPLY. Этот метод предполагает использование двух операторов CROSS APPLY. Промежуточный оператор вычисляет соответствующий ID заказа для данного сотрудника компании с помощью запроса TOP (1), но не возвращает никаких элементов внешнему запросу. Оператор активирует внутренний оператор CROSS APPLY и передает внутреннему запросу соответствующий ID заказа, после чего внутренний запрос возвращает соответствующую строку из таблицы Orders. Промежуточный запрос CROSS APPLY возвращает строку, возвращаемую внутренним запросом CROSS APPLY, внешнему запросу, который, в свою очередь, возвращает искомые элементы заказа. Если смысл не вполне ясен, взгляните на запрос, предлагаемый в качестве решения, и вновь прочтите объяснение (см. листинг 5). План запроса показан на рисунке 6.

Рисунок 6. N верхних позиций для группы, непокрывающий индекс, оптимальный вариант

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

В заключение для очистки выполните код листинга 6.

Поиск или сканирование — вопрос непростой. В этой статье показано, что в некоторых случаях оптимизатор самостоятельно делает выбор, например при использовании предиката EXISTS для обработки полусоединений или антиполусоединений. Однако в некоторых случаях, например если требуется вывести значение min или max или n верхних позиций для группы, приходится вручную разрабатывать решение, которое дает оптимальный план запроса. В следующей статье на примере случая с возрастающим ключом будет показано, как из-за неточной оценки количества элементов оптимизатор может выбрать неудачную стратегию и что можно в этом случае сделать, чтобы исправить положение.

SET NOCOUNT ON;
USE tempdb;
GO
IF OBJECT_ID(N'dbo.Orders'   , N'U' ) IS NOT NULL DROP TABLE dbo.Orders;
IF OBJECT_ID(N'dbo.Customers', N'U' ) IS NOT NULL DROP TABLE
   dbo.Customers;
IF OBJECT_ID(N'dbo.Employees', N'U' ) IS NOT NULL DROP TABLE
   dbo.Employees;
IF OBJECT_ID(N'dbo.GetNums'  , N'IF') IS NOT NULL DROP FUNCTION
   dbo.GetNums;
GO
-- Определение функции GetNums
CREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
  WITH
    L0   AS (SELECT c FROM (VALUES(1),(1)) AS D(c)),
    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 rownum
            FROM L5)
  SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n
  FROM Nums
  ORDER BY rownum;
GO
-- Настройки распределения данных для заказов
DECLARE
  @numorders   AS INT      =   1000000,
  @numcusts    AS INT      =     20000,
  @numemps     AS INT      =       100,
  @numshippers AS INT      =         5,
  @numyears    AS INT      =         4,
  @startdate   AS DATE     = '20110101';
-- Создание и заполнение таблицы Customers
CREATE TABLE dbo.Customers
(
  custid   CHAR(11)     NOT NULL,
  custname NVARCHAR(50) NOT NULL
);
INSERT INTO dbo.Customers(custid, custname)
  SELECT
    'C' + RIGHT('000000000' + CAST(T.n * @numcusts + N.n AS
   VARCHAR(10)), 10) AS custid,
    N'Cust_' + CAST(N.n AS VARCHAR(10)) AS custname
  FROM dbo.GetNums(1, @numcusts) AS N
    CROSS JOIN ( VALUES(0),(1) ) AS T(n);
ALTER TABLE dbo.Customers ADD
  CONSTRAINT PK_Customers PRIMARY KEY(custid);
-- Создание и заполнение таблицы Employees
CREATE TABLE dbo.Employees
(
  empid     INT          NOT NULL,
  firstname NVARCHAR(25) NOT NULL,
  lastname  NVARCHAR(25) NOT NULL
);

INSERT INTO dbo.Employees(empid, firstname, lastname)
  SELECT T.n * @numemps + N.n AS empid,
    N'Fname_' + CAST(N.n AS NVARCHAR(10)) AS firstname,
    N'Lname_' + CAST(N.n AS NVARCHAR(10)) AS lastname
  FROM dbo.GetNums(1, @numemps) AS N
    CROSS JOIN ( VALUES(0),(1) ) AS T(n);
ALTER TABLE dbo.Employees ADD
  CONSTRAINT PK_Employees PRIMARY KEY(empid);
-- Создание и заполнение таблицы Orders
CREATE TABLE dbo.Orders
(
  orderid   INT        NOT NULL,
  custid    CHAR(11)   NOT NULL,
  empid     INT        NOT NULL,
  shipperid VARCHAR(5) NOT NULL,
  orderdate DATE       NOT NULL,
  filler    CHAR(160)  NOT NULL DEFAULT('a')
);
INSERT INTO dbo.Orders(orderid, custid, empid, shipperid, orderdate)
  SELECT n AS orderid,
    'C' + RIGHT('000000000'
            + CAST(
                1 + ABS(CHECKSUM(NEWID())) % @numcusts
                AS VARCHAR(10)), 10) AS custid,
    1 + ABS(CHECKSUM(NEWID())) % @numemps AS empid,
    CHAR(ASCII('A') - 2
           + 2 * (1 + ABS(CHECKSUM(NEWID())) % @numshippers))
           AS shipperid,
      DATEADD(day, n / (@numorders / (@numyears * 365.25))
                   -- late arrival with earlier date
                         - CASE WHEN n % 10 = 0
                       THEN 1 + ABS(CHECKSUM(NEWID())) % 30
                       ELSE 0
                     END, @startdate)
         AS orderdate
  FROM dbo.GetNums(1, @numorders)
  ORDER BY CHECKSUM(NEWID())
OPTION(MAXDOP 1);
ALTER TABLE dbo.Orders ADD
  CONSTRAINT PK_Orders PRIMARY KEY(orderid);
CREATE INDEX idx_eid_oid_i_od_cid
  ON dbo.Orders(empid, orderid DESC)
    INCLUDE(orderdate, custid);
CREATE INDEX idx_cid_oid_i_od_eid
  ON dbo.Orders(custid, orderid DESC)
  INCLUDE(orderdate, empid);
GO

-- Высокая плотность - поиск, логических чтений 4 + 670
SELECT E.empid
FROM dbo.Employees AS E
WHERE EXISTS
  (SELECT *
   FROM dbo.Orders AS O
   WHERE O.empid = E.empid);

-- Низкая плотность - сканирование, логических чтений 110 + 3481
SELECT C.custid
FROM dbo.Customers AS C
WHERE EXISTS
  (SELECT *
   FROM dbo.Orders AS O
   WHERE O.custid = C.custid);

-- Высокая плотность - поиск, логических чтений 4 + 670
SELECT E.empid
FROM dbo.Employees AS E
WHERE NOT EXISTS
  (SELECT *
   FROM dbo.Orders AS O
   WHERE O.empid = E.empid);

-- Низкая плотность - сканирование логических чтений 218 + 3481
SELECT C.custid
FROM dbo.Customers AS C
WHERE NOT EXISTS
  (SELECT *
   FROM dbo.Orders AS O
   WHERE O.custid = C.custid);

-- Для сканирования используйте ROW_NUMBER (низкая плотность), логических чтений 3481
WITH C AS
(
  SELECT ROW_NUMBER() OVER(PARTITION BY custid ORDER BY orderid DESC) AS n,
    *
  FROM dbo.Orders
)
SELECT custid, orderdate, orderid, empid
FROM C
WHERE n <= 1;

-- Для поиска используйте APPLY (высокая плотность), логических чтений 4 + 670
SELECT E.empid, O.orderdate, O.orderid, O.custid
FROM dbo.Employees AS E
  CROSS APPLY (SELECT TOP (1) *
               FROM dbo.Orders AS O
               WHERE O.empid = E.empid
               ORDER BY orderid DESC) AS O;

-- Промежуточный CROSS APPLY, логических чтений 4 + 922
SELECT E.empid, P.orderdate, P.orderid, P.custid, P.filler
FROM dbo.Employees AS E
  CROSS APPLY (SELECT TOP (1) O.*
               FROM dbo.Orders AS P
                 CROSS APPLY
                   (SELECT O.*
                    FROM dbo.Orders AS O
                    WHERE O.orderid = P.orderid) AS O
               WHERE P.empid = E.empid
               ORDER BY orderid DESC) AS P;

USE tempdb;
IF OBJECT_ID(N'dbo.Orders'   , N'U' ) IS NOT NULL DROP TABLE dbo.Orders;
IF OBJECT_ID(N'dbo.Customers', N'U' ) IS NOT NULL DROP TABLE dbo.Customers;
IF OBJECT_ID(N'dbo.Employees', N'U' ) IS NOT NULL DROP TABLE dbo.Employees;
IF OBJECT_ID(N'dbo.GetNums'  , N'IF') IS NOT NULL DROP FUNCTION dbo.GetNums;