Детальное рассмотрение поведения при использовании INCLUDE

Некоторые базы данных такие, как Microsoft SQL Server, IBM Db2, а также PostgreSQL начиная с 11 версии – предлагают прибегнуть к оператору include для генерации индекса. Представление данного функционала в PostgreSQL (исходная статья вышла 30.04.2019) послужило поводом для этого объёмного рассуждения о работе с оператором include.

Перед углублением в детали, давайте начнём с короткого напоминания о том, как btree-индексы работают и что из себя представляет всемогущее index-only сканирование.

Содержание:

1. Напоминание: btree-индексы

2. Напоминание: Index-only сканирование

3. Оператор include

4. Фильтрация по полям в include

5. Уникальные индексы при использовании include

6. Сравнение

7. PostgreSQL: Никакой фильтрации до проверки области видимости

Напоминание: btree-индексы

Зачем нужен include? Для начала, вы должны понимать, что использование индекса влияет на три уровня структуры данных:

• Би-дерево

• Двусвязный список в конечном узле би-дерева (leaf node level)

• Таблица

Первые два уровня вместе формируют индекс, так что они могут быть объединены в одну сущность, которую назовём btree-индекс. Я предпочитаю хранить их раздельно, так как они необходимы для различных целей и имеют различное влияние на производительность. Тем более, что для объяснения необходимости использования include требуется сохранить это различие.

В общем случае, СУБД (система управления базами данных) начинает искать пересечение в би-дереве до первой совпадающей записи на уровне конечных узлов (1). Далее она проходит по двухсвязному списку пока не найдёт все совпадающие значения (2), и в конце извлекает все совпадающие значения из таблицы (3). На самом деле, два последних шага могут чередоваться, но это не важно для понимая основной идеи.

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

•        Би-дерево: часто меньше 5

•        Двусвязный список:

•       Таблица: ¹

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

Общая идея оптимизации заключается в том, чтобы делать меньше работы для достижения той же цели. Когда речь заходит о доступе к индексу, это значит, что СУБД пропускает структуру данных, если ей ничего оттуда не нужно.³

Вы можете почитать подробнее про работу btree-индексов “под капотом” в Глава 1, “Анатомия SQL индексов” из “Объяснение SQL производительности”

Напоминание: Index-only сканирование

Index-only сканирование ведёт себя следующим образом: оно не обращается к таблице, если необходимые данные имеются в двусвязном списке индекса.

Рассмотрим следующий индекс и запрос, которые я взял из “Index-Only сканирование: избегайте доступа к таблице”

 CREATE INDEX idx

     ON sales

      ( subsidiary_id, eur_value)

   SELECT SUM(eur_value)

     FROM sales

   WHERE subsidiary_id = ?

На первый взгляд, вы можете удивиться почему поле eur_value присутствует в определении индекса, но не упоминается в части запроса после where.

Ключевой точкой в данном примере является то, что btree-индекс содержит все необходимые столбцы – у СУБД нет необходимости обращаться к самой таблице. Вот почему мы обращаемся к index-only сканированию.

Применяя формулы, описанные выше, выигрыш по производительности в этом случае очень маленький, так как только несколько строк удовлетворяют условию оператора where. С другой стороны, если количество строк, удовлетворяющих условию оператора where, велико, например миллион, то количество операций чтения существенно бы сократилось с учётом фактора 100.

Пример выше использует тот факт, что двусвязный список (конечные узлы би-дерева) содержат поле «eur_value». Хотя другие узлы би-дерева так же хранят данное поле, данный запрос не нуждается в информации из этих узлов.

Оператор include

Использование include позволяет нам сделать различие между столбцами, которые мы хотим хранить в целом индексе (ключевые столбцы) и столбцы, которые понадобятся нам только в конечных узлах (include столбцы). Это означает, что мы можем убрать столбцы из неконечных узлов, если они нам не нужны в них.

Используя include, мы можем усовершенствовать индекс для данного запроса:

 CREATE INDEX idx

     ON sales ( subsidiary_id )

      INCLUDE ( eur_value )

Запрос всё ещё может использовать этот индекс для index-only сканирования, таким образом, получая, по существу, такую же производительность.

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

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

•  Дерево может иметь меньше уровней (<~40%)

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

•  Индекс чуть меньше (<~3%)

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

• Он документирует своё собственное назначение

Это однозначно самое недооценённое преимущество в случае использования include. Причина почему столбец учитывается в индексе описывается в его собственном объявлении (индекса).

Позвольте мне подробнее остановится на последнем пункте.

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

Следующий запрос демонстрирует данное утверждение:

 SELECT *

     FROM sales

     WHERE subsidiary_id = ?

     ORDER BY ts DESC

     FETCH FIRST 1 ROW ONLY

Как и раньше, для данной сущности subsidiary, данный запрос извлекает последнюю sales запись (ts это timestap).

 Для оптимизации этого запроса, было бы неплохо иметь индекс, который начинается с ключевых столбцов (subsidiary_id, ts). С этим индексом, СУБД может точно выбрать последнюю запись для subsidiary и вернуть её. И нет необходимости для чтения и сортировки всех записей для данной subsidiary, потому что двусвязный список сортируется в соответствии с ключевым индексом, то есть последняя запись для любой subsidiary должна иметь наибольшее значение ts. С этим подходом, запрос выполняется так же быстро, как и поиск по первичному ключу. Посмотрите “Индексирование порядка” и “Запрос N верхних строк” для того, чтобы подробнее ознакомится с данным подходом.

Перед добавлением нового индекса в этот запрос, мы должны проверить нет ли уже существующего индекса, который мог бы быть изменён (расширен) для поддержки данной фишки. Это, в общем то, хорошая практика, потому что расширение уже существующего индекса оказывает меньшее влияние на накладные расходы по обслуживанию, чем добавление нового индекса. Однако, когда мы изменяем существующий индекс, мы должны убедиться, что мы не снижаем полезность данного индекса в остальных запросах.

Если мы посмотрим на исходное объявление индекса, то мы столкнёмся с проблемой:

 CREATE INDEX idx

     ON sales

      ( subsidiary_id, eur_value )

Для того чтобы данный индекс поддерживал использование оператора order by, в вышестоящем запросе, нам необходимо вставить столбец ts между двумя уже имеющимися полями:

CREATE INDEX idx

     ON sales

      ( subsidiary_id, ts, eur_value ) 

Однако, это может сделать этот индекс менее полезным для запросов, в которых «eur_value» должен стоять на втором месте, например, если он был использован в where или в order by. Изменение этого индекса влечёт за собой существенный риск поломать другие запросы, если только мы не знаем, что таких запросов нет.

Картина полностью изменится, если мы посмотрим на индекс с использованием оператора include.

 CREATE INDEX idx

      ON sales ( subsidiary_id )

       INCLUDE ( eur_value )

Так как, «eur_value» столбец прописан в операторе include, он не в конечных узлах и таким образом, ни один из них не полезен ни для навигации по дереву, ни для определения порядка. Добавление нового столбца в конец ключевой части достаточно безопасно.

 CREATE INDEX idx

     ON sales ( subsidiary_id, ts )

     INCLUDE ( eur_value )

Даже несмотря на это, всё равно остаётся маленький шанс на то, что это негативно скажется на других запросах, но данный риск обычно оправдан.⁶

С точки зрения развития индексов, таким образом очень удобно добавлять столбцы в оператор include, если они вам нужны. Столбцы, которые добавлены только для доступности в index-only сканировании, являются основными кандидатами для этого.

Фильтрация в include столбцах

Пока мы не сконцентрировались на том, как оператор include позволяет работать index-only сканированию, давайте взглянем на другой случай, когда использование дополнительного столбца в индексе, становится выгодным.

 SELECT *

     FROM sales

     WHERE subsidiary_id = ?

     AND notes LIKE '%search term%'

Я сделал правило поиска, согласно которому показывается константное количество начальных и конечных групповых символов. Конечно, в своём коде вы будете использовать определённое вами значение.

Теперь давайте подумаем о грамотном индексе для данного запроса. Очевидно, что «subsidiary_id» должен быть на первом месте. Если мы возьмём предыдущий индекс из примера выше, он уже будет удовлетворять данному условию:

 CREATE INDEX idx

     ON sales ( subsidiary_id, ts )

      INCLUDE ( eur_value )

СУБД может использовать этот индекс с трёх-этапной процедурой, которая была описана в начале: (1) она будет использовать би-дерево для поиска первой записи с индексом указанным для «subsidiary»; (2) она пройдётся по двусвязному списку для того, что бы найти все «sales» для данной «subsidiary»; (3) она извлечёт все связанные «sales» из таблицы, удалит те, которые не подходят под паттерн «like» в столбце «notes», и после вернёт все оставшиеся строки.

Проблема только в последнем этапе данной процедуры: при обращении к таблице загружаются все строки независимо от того будут они в финальном результате или нет. Достаточно часто, обращение к таблице — это самая объёмная часть в суммарной сложности выполнения запроса. Загрузка ненужных данных, это огромная шляпа для производительности.

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

Другими словами, если notes столбец присутствовал в двусвязном списке, СУБД сможет применить like паттерн перед извлечением данного ряда из таблицы (за исключением PostgreSQL, смотрите ниже). Это предотвращает извлечение данных из таблицы, если указанный паттерн не подошёл. Если в таблице имеется больше столбцов, всё ещё остаётся возможность извлечь те столбцы для строк, которые удовлетворяют условию where – благодаря select *.

 CREATE INDEX idx

     ON sales ( subsidiary_id, ts )

      INCLUDE ( eur_value, notes )

Если в таблице имеется больше столбцов, тогда индекс не позволяет делать index-only сканирование. Тем не менее, это может быть примерно так же производительно, как index-only сканирование, если количество строк удовлетворяющих like паттерну будет крайне мало. В противном случае, если все строки удовлетворяют паттерну, производительность будет чуть хуже из-за увеличившегося размера индекса. Однако, можно достаточно просто достичь равновесия: для улучшения общей производительности, часто достаточно, чтобы like фильтр удалял хотя бы небольшой процент строк. Ваша выгода будет сильно зависеть от количества используемых столбцов.

Уникальные индексы при использовании include

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

Это позволяет нам создавать уникальные индексы, у которых имеются дополнительные столбцы в конечных узлах, например, для index-only сканирования.

 CREATE UNIQUE INDEX ...

     ON ... ( id )

   INCLUDE ( payload)

Данный индекс защищает от дублирования значений в id столбце,⁷ на данном этапе индекс позволяет сделать index-only сканирование при следующем запросе.

 SELECT payload

     FROM ...

   WHERE id = ?

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

Корректный синтаксис для базы данных Oracle выглядит следующим образом:

 CREATE INDEX ...

        ON ... ( id, payload)

 ALTER TABLE ... ADD UNIQUE ( id )

      USING INDEX ...

Совместимость

`a Use unique (…) using index … с индексом, у которого имеется больше столбцов.

PostgreSQL: Никакой фильтрации до проверки области видимости

PostgreSQL имеет ограничение, когда она применяет фильтры на уровне индекса. Если упростить, то база данных не работает с этим, за исключением нескольких случаев. Хуже того, некоторые из этих случаев работают только когда соответствующие данные хранятся в ключевой части индекса, не в части с оператором «include». Это значит, что перемещение столбцов в «include» часть, может негативно сказаться на производительности, даже если применим вышеописанный подход.

Полная история начинается с того, что PostgreSQL хранит старые версии строк в таблице до того момента, как они станут невидимыми для всех транзакций и вакуум удалит их когда-нибудь позже. Для того что бы узнать считается версия строки видимой (для данной транзакции) или нет, каждая таблица имеет два дополнительных атрибута, которые показывают, когда версия строки была создана и удалена: xmin и xmax. Строка считается видимой, только если текущая транзакция попадает в интервал xmin – xmax.⁸

К сожалению, значения xmin/xmax не хранятся в индексах.⁹

Это значит, что всякий раз, когда PostgreSQL ищет требуемый индекс, ей нельзя сказать видима данная строка или нет для текущей транзакции. Данная запись может быть уже удалена или ещё не зафиксирована (закомиченна).  Стандартный путь для того, чтобы определить это посмотреть в таблицу и проверить значения xmin/xmax.

Следствием станет то, что в PostgreSQL отсутствует такая вещь, как index-only сканирование.  

Пока, поддерживается Index Only Scan операция в PostgreSQL - но она всё ещё требует проверки видимости каждой версии строки при помощи доступа к данным за рамками индекса. Вместо того, чтобы идти в таблицу Index Only Scan сначала сверяется с так называемой картой видимости (visibility map). Данная карта видимости очень плотная, поэтому количество операций чтения (слава богу) меньше, чем при извлечении xmin/xmax из таблицы. В любом случае, карта видимости не всегда даёт точный ответ: данная карта скорее говорит должна ли строка быть видимой или же её область видимости неизвестна. Последнее: Index Only сканирование всё равно требует извлечения xmin/xmax из таблицы (представлено как “Свойство кучи” в explain analyze).

После короткого отступления об области видимости, мы можем вернуться к фильтрации на уровне индексов.

SQL позволяет создавать сколь угодно сложные условия с оператором while. Данные выражения могут так же вызвать ошибки во время работы, такие как “деление на ноль”. Если PostgreSQL будет вычислять такие выражения перед тем, как убедиться в видимости соответствующей записи, даже невидимые записи могут вызвать подобные ошибки. Для предотвращения этого, PostgreSQL обычно проверяет область видимости перед выполнением таких выражений.

Имеется одно исключение из общего правила. Так как область видимости не может быть проверена во время поиска по индексу, операторы, которые могут использоваться для поиска, должны всегда быть безопасны для использования. Это операторы, которые определены в соответствующем оператору классе. Если фильтр “простого сравнения” использует оператор из такого класса, PostgreSQL может применить этот фильтр перед проверкой области видимости, потому что она знает, что эти операторы безопасны для использования. Затруднение в том, что у ключевых столбцов имеется оператор, связанный с ними. Столбцы в операторе include не имеют – фильтров основывающиеся на них не применяются перед тем, как их видимость не подтверждена. Это я так понял из документации PostgreSQL.

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

CREATE INDEX idx

    ON sales ( subsidiary_id, ts )

    INCLUDE ( eur_value, notes ) 

 SELECT *

     FROM sales

  WHERE subsidiary_id = ?

     AND notes LIKE '%search term%'

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

Like фильтр используется с полем «Filter», не в Index Cond. Это значит, что он был применён на уровне таблицы. Так же, количество обращений довольно велико для выборки в 16 строк.

В Bitmap Index/Heap Scan этот феномен становится более явным.

В Bitmap Index Scan вовсе не упоминается like фильтр. Вместо этого, он возвращает 256 строк, намного больше чем те 16, которые удовлетворяют условию в операторе where.

Заметим, что в данном случае, это не особенность include столбцов. Перенос include столбцов в индекс даёт такой же результат.

CREATE INDEX idx

      ON sales ( subsidiary_id, ts, eur_value, notes )

Это происходит потому, что like оператор не является частью оператора класса, так как это не безопасно.

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

 SELECT *

     FROM sales

  WHERE subsidiary_id = ?

     AND notes = 'search term'

Bitmap Index Scan сейчас применяет все условия из оператора where и допускает только оставшиеся 16 строк для Bitmap Heap Scan.

Заметим, этот план требует, чтобы столбец «respective» был ключевым столбцом. Если мы вернём столбец «notes» обратно в оператор include, у неё нет соответствующего классу оператора, так equals оператор более не считается безопасным.

Следовательно, PostgreSQL откладывает применение этого фильтра до момента доступа к таблице данных до проверки области видимости.

Сноски

0 – Мы рассчитываем, что на одну страницу/блок приходится 100 индексированных записей

1 – Худший случай, все необходимые строки в различных блоках, то есть самый худший из возможных группирующих факторов

2 - Тем не менее, двусвязный список может стать ограничивающим фактором, например, при index-only сканировании или в более широко выраженной процедуре, когда число извлекаемых из таблицы строк немногим меньше, чем количество строк, считываемых из двусвязного списка.

 3 – INDEX FAST FULL SCAN из Oracle Database это исключительный случай, в котором, используется только одна часть одной структуры: конечный узел би-дерева, то есть двусвязный список без своих ссылок. В качестве дополнительного примечания: Я до сих пор восхищаюсь, почему INDEX FAST FULL SCAN используется, как index-only сканирование только в Oracle Database

4 – Причина для этого достаточна проста: при добавлении новой строки в дерево, поддерживается только поиск по ключевым столбцам. Это значит, что даже если конечный узел был упорядочен на основании всех столбцов, нет никакого способа напрямую перейти к тому месту, куда будет помещена новая строка. СУБД будет вынуждена проверить все строки с таким же значением ключа.

5 – Пример в SQL Server: максимальная длина ключа 900/1700 байт, максимальная суммарная длина записи индекса 8060 байт

6 – Основной риск заключается, в том, что кластеризация станет хуже, в частности, в Oracle Database. Посмотрите “Автоматическая оптимизация кластеризации”. Другой риск в том, какой длины может быть двусвязный список.

7 – Кроме дублируемых null значений, которые приемлемы в роли уникальной связи.

8 – Конечно это упрощение. Почитайте “Как Postgres делает транзакции атомарными чтобы узнать, как моментальные снимки базы данных (снэпшот) работают в PostgreSQL.

9 – Просто добавить xmin/xmax через include выглядит заманчиво, но “создание индексов с использованием системных столбцов не поддерживается”. К тому же, xmax в индексе будет требовать каждое обновление/удаление для обновления всех индексов.