Optimizing I/O Performance by Sorting – Part 1

Автор: Craig Freedman Seek Predicates

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

Давайте рассмотрим такое поведение оптимизатора на примере. Для того, чтобы влияние на производительность было заметным, нам понадобится достаточно большая таблица. Следующий сценарий создает таблицу из 25,6 миллионов строк, которая занимает около 3 ГБ памяти.

CREATE DATABASE IOTest
    ON ( NAME = IOTest_Data, FILENAME = '...\IOTest_Data.mdf', SIZE = 4 GB )
    LOG ON ( NAME = IOTest_Log, FILENAME = '...\IOTest_Log.ldf', SIZE = 200 MB )
GO
ALTER DATABASE IOTest SET RECOVERY SIMPLE
GO
USE IOTest
GO
CREATE TABLE T (
    PK INT IDENTITY PRIMARY KEY,
    RandKey INT,
    Flags TINYINT,
    Data INT,
    Pad CHAR(100))
GO
SET NOCOUNT ON
DECLARE @I INT
SET @I = 0
WHILE @I < 100000
  BEGIN
    WITH
      X2 (R) AS ( SELECT RAND() UNION ALL SELECT RAND() ),
      X4 (R) AS ( SELECT R FROM X2 UNION ALL SELECT R FROM X2 ),
      X8 (R) AS ( SELECT R FROM X4 UNION ALL SELECT R FROM X4 ),
      X16 (R) AS ( SELECT R FROM X8 UNION ALL SELECT R FROM X8 ),
      X32 (R) AS ( SELECT R FROM X16 UNION ALL SELECT R FROM X16 ),
      X64 (R) AS ( SELECT R FROM X32 UNION ALL SELECT R FROM X32 ),
      X128 (R) AS ( SELECT R FROM X64 UNION ALL SELECT R FROM X64 ),
      X256 (R) AS ( SELECT R FROM X128 UNION ALL SELECT R FROM X128 )
    INSERT T (RandKey, Flags, Data, Pad)
        SELECT R * 1000000000, 0xFF, 1, '' FROM X256
    SET @I = @I + 1
  END
GO
CREATE INDEX IRandKey on T (RandKey, Flags)
GO

Из-за фиксированной ширины столбца Pad каждая строка в таблице T занимает 113 байт (плюс накладные расходы). На одной 8 Кбайтной странице помещаются примерно 65 строк.

Столбец RandKey, как и следует из названия, содержит случайные значения. Обратите внимание, что по нему у нас есть некластерный индекс. При наличии предиката по столбцу RandKey SQL Server может использовать этот индекс для извлечения соответствующих строк из таблицы. Однако, поскольку значения в этом столбце случайны, строки выборки будут разбросаны по всему кластерному индексу.

Если мы выберем из таблицы не много строк с помощью фильтра по RandKey, SQL Server будет использовать некластерный индекс:

SELECT SUM(Data)
FROM T
WHERE RandKey < 1000

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1011]=(0) THEN NULL ELSE [Expr1012] END))
       |--Stream Aggregate(DEFINE:([Expr1011]=COUNT_BIG([T].[Data]), [Expr1012]=SUM([T].[Data])))
            |--Nested Loops(Inner Join, OUTER REFERENCES:([T].[PK], [Expr1010]) OPTIMIZED WITH UNORDERED PREFETCH)
                 |--Index Seek(OBJECT:([T].[IRandKey]), SEEK:([T].[RandKey] < (1000)) ORDERED FORWARD)
                 |--Clustered Index Seek(OBJECT:([T].[PK__T__...]), SEEK:([T].[PK]=[T].[PK]) LOOKUP ORDERED FORWARD)

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

Если мы выберем больше строк, SQL Server распознает, что случайные операции ввода-вывода слишком затратны, и переключится на сканирование кластерного индекса:

SELECT SUM(Data)
FROM T
WHERE RandKey < 10000000

 

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1009]=(0) THEN NULL ELSE [Expr1010] END))
       |--Stream Aggregate(DEFINE:([Expr1009]=COUNT_BIG([T].[Data]), [Expr1010]=SUM([T].[Data])))
            |--Clustered Index Scan(OBJECT:([T].[PK__T__...]), WHERE:([T].[RandKey]<(10000000)))

Этот запрос затрагивает только 1% данных. Тем не менее, запрос затронет более половины страниц в кластерном индексе, поэтому быстрее просканировать весь кластерный индекс, чем выполнять порядка 256 000 случайных операций ввода-вывода.

Где-то между этими двумя крайностями все становится немного интереснее:

SELECT SUM(Data)
FROM T
WHERE RandKey < 2500000

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN [Expr1010]=(0) THEN NULL ELSE [Expr1011] END))
       |--Stream Aggregate(DEFINE:([Expr1010]=COUNT_BIG([T].[Data]), [Expr1011]=SUM([T].[Data])))
            |--Nested Loops(Inner Join, OUTER REFERENCES:([T].[PK], [Expr1009]) WITH UNORDERED PREFETCH)
                 |--Sort(ORDER BY:([T].[PK] ASC))
                 |    |--Index Seek(OBJECT:([T].[IRandKey]), SEEK:([T].[RandKey] < (2500000)) ORDERED FORWARD)
                 |--Clustered Index Seek(OBJECT:([T].[PK__T__...]), SEEK:([T].[PK]=[T].[PK]) LOOKUP ORDERED FORWARD)

Этот запрос затрагивает всего 0,25% данных. План использует некластерный индекс, чтобы не перелопачивать большое количество строк. Тем не менее, выполнение 64000 случайных операций ввода-вывода довольно затратно, поэтому SQL Server добавляет сортировку. Сортируя строки по ключу кластерного индекса, SQL Server преобразует случайные операции ввода-вывода в последовательные операции ввода-вывода. Таким образом, мы получаем план с эффективность поиска закладок (он затрагивает только те строки, которые соответствуют условию) и заодно обеспечиваем производительность ввода-вывода как у последовательного просмотра.

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