Индексы в PostgreSQL на практике, как выбирать?

Введение

Если кратко, индексы в PostgreSQL нужны для одного - ускорять доступ к данным. Если индекса нет, базе приходится просматривать таблицу целиком при помощи последовательного сканирования (seq scan). На небольших таблицах такая операция может быть незаметной, но на миллионах строк она быстро становится узким местом.

Индекс нужен затем, чтобы база не перебирала все данные подряд, а быстрее выходила на нужные строки. Аналогия здесь простая - как указатель в книге помогает найти нужный раздел без лишнего листания, так и индекс сокращает объем поиска. За счет этого запросы могут выполняться в разы быстрее, а в отдельных случаях - на порядки.

Но индекс - не бесплатное ускорение. Он занимает место на диске, а при INSERT, UPDATE и DELETE его тоже приходится обновлять. Поэтому главный вопрос не в том, нужны ли индексы вообще, а в том, какие из них стоит создавать и в каких случаях они действительно окупаются.

Одна из сильных сторон PostgreSQL в том, что здесь нет одного универсального индекса на все случаи жизни. Существует несколько типов индексов, и каждый из них лучше работает в своей ситуации: один - на обычных сравнениях и диапазонах, другой - на массивах, JSONB и похожих структурах, третий - на геоданных и геометрии. Поэтому на практике важно не просто создать индекс, а выбрать тот, который действительно поможет конкретному запросу и не принесет лишних затрат на запись и обслуживание.

Какие типы индексов есть в PostgreSQL?

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

• B-tree, основной и самый универсальный тип индекса. Именно он используется по умолчанию и подходит для большинства типовых задач: поиска по равенству, диапазонам, сортировке и другим сценариям, где важен упорядоченный доступ к данным
• Хэш-индекс (hash), индекс только для точных совпадений. В отличие от B-tree, он не хранит значение в упорядоченном виде, а работает по его хешу, поэтому не подходит для диапазонов и сортировки. Зато на больших таблицах и длинных значениях он может быть компактнее, если запросы почти всегда сводятся к условию "столбец = значение"
• GiST (Generalized Search Tree), обобщенное поисковое дерево для более сложных типов данных и условий поиска. На практике его часто используют там, где важны не просто равенство или диапазон, а более сложные отношения между значениями: например, в геометрии, геоданных, диапазонах и задачах поиска ближайших объектов. В отличие от GIN, который лучше подходит для составных значений вроде JSONB, GiST обычно выбирают тогда, когда нужно индексировать именно отношения между объектами, а не отдельные элементы внутри значения
• SP-GiST (Space-Partitioned GiST), индекс для данных, которые удобно сразу делить на части. Если GiST - более общий и гибкий вариант для сложных условий поиска, то SP-GiST лучше подходит там, где данные изначально можно разложить по ветвям и сегментам. Проще говоря, GiST решает более общий класс задач, а SP-GiST имеет смысл там, где сама структура данных уже подсказывает способ разбиения
• GIN (Generalized Inverted Index), индекс для случаев, когда в одном поле хранится не одно простое значение, а составное значение. Он хорошо подходит для массивов, JSONB, tsvector и похожих структур, где нужно быстро находить не всю запись целиком, а вложенные значения внутри нее. Если GiST чаще используют для отношений между объектами, то GIN - для поиска по содержимому составного значения
• BRIN (Block Range Index), индекс для очень больших таблиц. В отличие от B-tree, он не хранит подробную информацию по каждой строке, а собирает краткую сводку по диапазонам блоков таблицы. Поэтому BRIN имеет смысл там, где значения в столбце идут более-менее по порядку, например по дате, времени или идентификатору. Сам индекс получается маленьким, а поиск по большим объемам данных - дешевле

Но, в PostgreSQL важно смотреть не только на тип индекса, но и на то, как именно он построен. Индекс может быть уникальным, многоколонным, частичным или построенным на выражении. Это не отдельные виды индексов, а способы точнее настроить индекс под конкретную задачу.

Как индекс меняет план запроса на практике?

Прежде чем переходить к разбору каждого типа индекса по отдельности, полезно один раз посмотреть на базовый эффект индекса на простом примере. Для этого достаточно выполнить один и тот же запрос сначала без индекса, а затем - с индексом. Разницу будем смотреть через EXPLAIN ANALYZE.

Для начала подготовим тестовую таблицу и наполним ее данными (полный скрипт: https://gist.github.com/gelovolro/f00ce519c346b6e4085b4839693c1062):

к сожалению, Дзен перестал поддерживать функционал вставки кода, на момент написания статьи, поэтому приходится вставлять картинку, а снизу ссылку на код в GitHub Gist

Если выполнить запрос с EXPLAIN ANALYZE из примера выше, в плане выполнения мы увидим последовательное сканирование таблицы (seq scan):

вывод плана запроса с последовательным сканированием

Теперь, применим вторую часть примера. Создадим индекс, обновим статистику таблицы и снова выведем план того же запроса, чтобы посмотреть на разницу (должно смениться на index scan):

к сожалению, Дзен перестал поддерживать функционал вставки кода, на момент написания статьи, поэтому приходится вставлять картинку, а снизу ссылку на код в GitHub Gist

вывод плана запроса с индексным сканированием

Этот пример наглядно показывает, зачем вообще нужны индексы. Без индекса PostgreSQL вынужден читать таблицу целиком через seq scan, а после создания индекса переходит к индексному плану и находит нужную строку - быстрее. В результате уменьшается не только объем обрабатываемых данных, но и общее время выполнения запроса. Именно ради такого эффекта индексы и создают на часто используемых условиях поиска.

Напоследок, давайте посмотрим сколько места на диске занимает btree-индекс по системному каталогу:

btree индекс занял 39 Мб

Давайте, теперь, перейдем к разбору каждого типа индекса по отдельности.

B-tree тип индекса

B-tree - это базовый и самый распространенный индекс в PostgreSQL. По умолчанию создается именно он, и этого уже хватает для большинства рабочих запросов. Если нужно искать по точному значению, диапазону или сразу получать данные в порядке сортировки, первым делом обычно смотрят именно в сторону b-tree.

B-tree - это не двоичное дерево вроде красно-черного. Это сбалансированное поисковое дерево, в котором значения хранятся в отсортированном виде, поэтому такой индекс хорошо работает не только для точного поиска, но и для диапазонов и сортировки. Именно из-за этой универсальности b-tree и стал индексом по умолчанию в PostgreSQL.

https://ru.wikipedia.org/wiki/B-tree

Почему это важно на практике?

На практике это означает, что b-tree хорошо подходит для самых частых условий в запросах: "=, >, <, >=, <=, BETWEEN", а также для ORDER BY.

Если данные нужно искать по обычным сравнениям или получать уже в отсортированном виде, то b-tree почти всегда будет первым кандидатом. Именно поэтому с него обычно начинают, а к более специализированным индексам переходят уже тогда, когда запросы выходят за рамки обычного упорядоченного поиска. Но b-tree не универсален во всех сценариях. Он хорош там, где значение можно сравнивать и упорядочивать как единое целое.

Исходники реализации b-tree в PostgreSQL можно изучить по следующей ссылке, где доступен внутренний readme-файл: https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README

Хэш-индекс (hash)

Хэш-индекс - это более узкоспециализированный индекс, чем b-tree. Его задача - не покрыть как можно больше сценариев, а максимально быстро отрабатывать проверки на точное совпадение.

Хэш-индекс не подходит для диапазонов и сортировки, он работает только с хэшем значения и не хранит значения в упорядоченном виде. При этом на длинных строках вроде UUID, URL и других больших значениях такой индекс может занимать меньше места, чем b-tree, поскольку внутри него хранится только 4-байтный хэш, а не само значение целиком: https://www.postgresql.org/docs/current/hash-index.html

Each hash index tuple stores just the 4-byte hash value, not the actual column value...

Сами исходники реализации хэш-индекса в PostgreSQL можно посмотреть в GitHub-репозитории PostgreSQL по следующей ссылке: https://github.com/postgres/postgres/blob/master/src/backend/access/hash/README

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

Но, если нужно использование:

• диапазонов
• ORDER BY
• многоколонного индекса

то здесь, уже почти всегда, логичнее смотреть в сторону b-tree индекса. Кроме того, авторы PostgreSQL сами отмечают, что хэш лучше всего подходит для поиска по равенству на больших таблицах, особенно когда значения уникальны. Чтобы увидеть использование хэш-индекса на практике, далее попробуем сделать пример с длинными значениями:

1. сначала выполним точечный поиск без индекса
2. затем создадим хэш-индекс и повторим тот же запрос
3. после этого выполним диапазонный запрос по тому же столбцу
4. а затем для сравнения создадим b-tree индекс, и снова посмотрим план
5. заодно сравним размер обоих индексов

Поскольку пример достаточно большой, то я сразу дам ссылку на github gist, который подготовил для примера с хэш-индексом, откуда вы можете скопировать SQL-код: https://gist.github.com/gelovolro/7d1bbaa2cbb0f818d4fffde4e5c5393a

А далее будем разбирать вывод плана, поэтапно, с исполненным запросом. Для начала подготовим каркас в виде тестовой таблицы и DML-кода, который ее заполнит:

Теперь, попробуем применить запрос без создания индексов, ожидаемо увидеть seq scan:

Далее создадим хэш индекс, обновим статистику и заново попробуем тот же запрос, должен появиться уже index scan, использующий хэш-индекс:

Теперь, попробуем применить диапазонный SQL-запрос, и здесь планировщик должен решить не использовать хэш-индекс, мы должны увидеть seq scan:

Посмотрим и за размером самого хэш-индекса:

хэш-индекс занял 32 Мб

Теперь, давайте создадим btree-индекс, как контр-пример и попробуем применить его с тем же запросом, который использовался для диапазонного запроса. И мы увидим, что планировщик предпочел использовать btree-индекс с использованием битовой карты. Почему?

при использовании btree-индекса использовалось и сканирование по битовой карте

Потому что в этом запросе диапазонное условие возвращает уже не одну-две строки, а заметную часть таблицы, и для такого случая планировщику выгоднее не идти по индексу - построчно, а сначала собрать через b-tree список подходящих ссылок на строки, а затем отсортировать их по физическому расположению и только после этого читать сами страницы таблицы. Подробнее про метод сканирования по битовой карте, прочитайте мою статью: https://dzen.ru/a/ZoAs76w0DksN7LQg

GiST-индекс

GiST (Generalized Search Tree) - это более общий механизм для сложных типов данных и нестандартных условий поиска. Если b-tree индекс хорошо работает там, где значения можно просто сравнить и упорядочить, то GiST-индекс нужен для случаев, где важны уже другие отношения между объектами:

• пересечение
• вхождение
• близость, расстояние и подобные вещи

Именно поэтому про GiST-индекс чаще вспоминают в задачах с геометрией, геоданными и поиском ближайших объектов.

Сам по себе термин "generalized search tree" можно перевести, как "обобщенное поисковое дерево". Это не одно конкретное дерево под обычное сравнение "меньше или больше", а общая каркасная структура, которую можно адаптировать под разные типы поиска и разные отношения между объектами.

То есть, смысл слова "generalized" тут в том, что структура:

• не жестко привязана только к числам
• не обязана работать только по линейному порядку

Проще всего смотреть на GiST-индекс, как на "каркас" для разных стратегий поиска. Поведение такого индекса определяется "операторным классом", то есть тем, для каких типов данных и каких операторов он построен. Поэтому GiST-индекс - это не один узкий сценарий, а целое семейство решений, которое можно адаптировать под разные типы данных.

На практике это означает, что GiST-индекс стоит рассматривать тогда, когда нужно индексировать не "значение как одно целое", а отношение между объектами. Например:

• пересекаются ли два диапазона
• попадает ли точка в область
• какой объект находится ближе всего к заданной координате

Важная особенность GiST в том, что он может возвращать не только точное совпадение, но и кандидатные строки, которые PostgreSQL потом перепроверяет уже по данным таблицы. То есть в некоторых сценариях GiST-индекс работает не как "абсолютно точный фильтр", а как быстрый способ резко сузить область поиска.

В чем тогда отличие GiST-индекса от SP-GiST индекса?

SP-GiST (Space-Partitioned GiST) выделяют в отдельный тип индекса потому, что он решает более узкий, но важный класс задач, чем обычный GiST-индекс.

Если GiST-индекс - это более общий и гибкий каркас для сложных условий поиска, то SP-GiST тип индекса нужен там, где данные естественно разбиваются на непересекающиеся части или ветви. Он подходит под структуры, связанные с таким понятием, как "partitioned search trees", например:

• quad-tree, дерево квадрантов, которое рекурсивно делит двумерное пространство на 4-е области, обычно используют для 2D-координат, карт и пространственного поиска: https://en.wikipedia.org/wiki/Quadtree
• k-d tree, k-мерное дерево, которое на каждом шаге делит пространство плоскостью по одной из координат, подходит для многомерных точек и поиска ближайших соседей: https://en.wikipedia.org/wiki/K-d_tree
• radix tree, префиксное дерево, где общие префиксы ключей сжимаются, применяют для строк, префиксного поиска и иерархических ключей: https://en.wikipedia.org/wiki/Radix_tree

Поэтому SP-GiST обычно рассматривают для префиксного поиска, иерархических структур и других случаев, где сам способ хранения данных уже подсказывает разбиение пространства. Проще говоря, GiST - про универсальность, а SP-GiST - про более точное попадание в хорошо структурированные данные.

GiST и SP-GiST индексы, оба поддерживают "k-NN поиск" (k-Nearest Neighbors, т.е. поиск k-ближайших соседей) для встроенных классов операторов для типа "POINT", поэтому такой пример подходит для практического сравнения двух индексов на одном и том же типе данных. Но, на практике разница между GiST и SP-GiST может оказаться не столь линейной, как может показаться по теоритическому описанию. Поэтому я проверил оба индекса на одном и том же большом наборе данных (20 млн. строк) в нескольких сценариях поиска. Тесты показали важную вещь: SP-GiST не дает автоматического выигрыша просто потому, что данные - "пространственные".

Ссылка на мой github-репозиторий с результатами тестов (на английском): https://github.com/gelovolro/postgres_indices_article

1). Я проводил проверку запросов на попадание точки в область. И это показало, что разница между GiST и SP-GiST проявляется не так ярко и не так стабильно, как можно было ожидать. Иначе говоря, само по себе удобное разбиение данных на области еще не гарантирует заметного выигрыша SP-GiST.

2). Более полезным для сравнения оказался другой кейс - "k-NN поиск", т.е. запросы на ближайших соседей. Но и здесь результат оказался не таким прямолинейным, как можно было ожидать... Устойчивого выигрыша SP-GiST по времени не получилось, а при более тяжелых сценариях преимущество оставалось за GiST.

Итого по проведенным тестам:

1. Вся практическая часть проверялась на одном масштабе: 20 млн. строк.
2. Основной тип данных для сравнения: POINT.
3. Данные строились, как неравномерное пространство с крупным перекосом по регионам, плотными локальными кластерами и пустыми зонами между ними.
4. Во всех сценариях сравнивались одни и те же варианты индекса: GiST, SP-GiST quad_point_ops, SP-GiST kd_point_ops.
5. Сначала я проверил ветку поиска точки по попаданию в область. Эта линия оказалась полезной, как промежуточная проверка, но не дала устойчивого и наглядного преимущества SP-GiST.
6. После этого основной фокус сместился на k-NN поиск, то есть на поиск ближайших соседей.
7. Одиночные k-NN запросы дали полезный промежуточный результат, но абсолютное время там слишком мало, чтобы делать по нему серьезные практические выводы.
8. Попытка усилить эффект через более тяжелый k-NN запрос увеличила время выполнения, но устойчивого преимущества SP-GiST это не дало.
9. Наиболее удачным оказался не одиночный, а batched k-NN workload, то есть пакет из нескольких благоприятных nearest-neighbor запросов.
10. Именно batched k-NN сценарий оказался самым полезным для практического сравнения.
11. При этом SP-GiST в этих тестах оказался компактнее по размеру индекса, чем GiST.
12. Среди вариантов SP-GiST самым компактным по итогам проверки оказался quad_point_ops.

Итоговый вывод по тестам такой: поиск по области не стал сильным практическим примером, а самым полезным сценарием для сравнения оказался кейс POINT + batched k-NN. При этом по времени выполнения лидировал GiST, а SP-GiST оказался компактнее по размеру индекса

GIN-индекс

GIN (Generalized Inverted Index) - это индекс для случаев, когда в одном поле хранится не одно простое значение, а составное значение, к примеру JSON-структура со значениями.

Если b-tree хорошо работает, когда нужно искать по самому значению целиком, а GiST и SP-GiST - когда важны отношения между объектами, то GIN нужен тогда, когда запрос ищет отдельные элементы внутри поля. Именно поэтому GIN-индекс чаще всего вспоминают рядом с массивами, JSONB и полнотекстовым поиском.

Само название GIN расшифровывается, как Generalized Inverted Index, то есть "обобщенный инвертированный индекс". Смысл здесь в том, что индекс хранит не саму запись целиком, а связь вида "ключ -> список строк, где этот ключ встречается". Если говорить проще, GIN особенно удобен там, где одно значение можно разложить на много частей: например, массив на элементы, JSONB на ключи и значения, а текстовый документ - на слова.

На практике это означает следующее, что GIN-индекс стоит рассматривать тогда, когда запросу важно не всё составное значение - целиком, а только часть его содержимого. Например:

• поиск массива, который содержит определенный элемент
• поиск JSONB, внутри которого есть нужный ключ или вложенный фрагмент
• полнотекстовый поиск по tsvector (типу из PostgreSQL, в котором текст хранится в виде подготовленного набора слов для полнотекстового поиска)

Подготовим тестовую таблицу для работы с GIN-индексом и наполним ее данными (https://gist.github.com/gelovolro/86f7925642ea8691fbd100338d9cf896):

к сожалению, Дзен перестал поддерживать функционал вставки кода, на момент написания статьи, поэтому приходится вставлять картинку, а снизу ссылку на код в GitHub Gist

Далее, чтобы не раздувать размер данной статьи, сфокусируемся только на запросе, когда GIN-индекс уже создан. В GitHub Gist, по ссылке выше, есть все запросы, включая проверку без индекса (seq scan) и запросы к системным каталогам. Создадим GIN-индекс и посмотрим вывод плана.

После создания GIN-индекса, PostgreSQL уже не идет в последовательное сканирование таблицы, а использует связку из двух шагов: bitmap index scan и bitmap heap scan.

Сначала по самому GIN-индексу находится набор строк, подходящих под условие "attrs @> ...". В моем примере таких строк оказалось довольно много - округлено 166 тыс. строк. Поэтому планировщик не стал использовать точечный index scan метод, а выбрал более подходящий вариант через битовую карту.

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

BRIN-индекс

BRIN (Block Range Index) - это индекс для очень больших таблиц, где значения в столбце более-менее связаны с физическим порядком строк в таблице. Проще говоря, BRIN имеет смысл тогда, когда данные лежат "похожими кусками". Например, старые даты - в начале таблицы, новые - в конце, или идентификаторы и время растут примерно в порядке вставки.

Само название BRIN расшифровывается, как "Block Range Index", то есть "индекс по диапазонам блоков". В отличие от b-tree, BRIN не хранит подробную информацию по каждой строке. Вместо этого он хранит краткую сводку по диапазонам страниц таблицы. Для каждого диапазона блоков индекс запоминает не сами строки, а обобщающую информацию о значениях в этом участке таблицы. Именно поэтому BRIN-индекс получается очень компактным по размеру.

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

Можно выразить кейс так, когда использовать BRIN-индекс:

• очень большая "append-only" таблица
• строки идут по порядку, допустим по timestamp полю

Но важно подчеркнуть детали, что:

• по точечному поиску b-tree индекс - обычно лучше
• BRIN-индекс "выстреливает" не как универсально самый быстрый, а как очень дешевый и очень уместный индекс для огромных упорядоченных таблиц
• на огромной таблице b-tree индекс может стать слишком тяжелым по занимаемому месту и общей цене поддержки, а BRIN-индекс дает приемлемый результат за очень маленькую цену, если данные расположены не совсем хаотично

Давайте посмотрим на практическом примере - разницу в размерах двух типов индексов, создадим один набор данных и создадим два индекса (b-tree & BRIN), и посмотрим информацию с системного каталога.

Подготовленный SQL DDL/DML с инструкциями по созданию индексов можно взять здесь: https://gist.github.com/gelovolro/3a182987be2590eb90aee0226a0b70ce

Посмотрим сразу на вывод размеров индексов - по одному и тому же набору данных:

BRIN-индекс намного меньше по размеру в сравнении с btree-индексом

Про еще один тип индекса, Bloom

Отдельно стоит упомянуть еще один индекс - Bloom, но в этой статье я сознательно оставил его "за скобками". Причина не в том, что он не заслуживает внимания, а в том, что это уже более специфический инструмент.

В PostgreSQL он существует не как один из базовых типов индексов, а доступен через расширение "bloom" (CREATE EXTENSION bloom), которое нужно подключать отдельно.

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

Именно поэтому я не стал разбирать его здесь отдельно. Для этого потребовалась бы уже своя отдельная статья, которая объяснила бы:

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

В рамках этой статьи такое отступление скорее увело бы в сторону, чем помогло бы яснее раскрыть основную тематику. В будущем, постараюсь создать отдельную статью на тему Bloom-индекса.

Постскриптум:

• при написании статьи использовалась следующая версия PostgreSQL v16
• к сожалению, Дзен перестал поддерживать функционал вставки исходного программного кода с syntax highlighting, на момент написания данной статьи. Про схожие проблемы рассказывают и другие Дзен-авторы: https://dzen.ru/a/XtUGaNtXXh9qY-gb поэтому вместо исходного кода, Вы видите комбинацию из картинки и ссылки на SQL-код в GitHub Gist. Прошу прощения за неудобства!