Индексы в PostgreSQL и CREATE INDEX

Зачем нужны индексы

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

Как работают индексы

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

Индексы в базах данных работают аналогично каталогу в библиотеке. Они помогают быстро находить необходимую информацию без необходимости просматривать все данные.

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

Индексы в PostgreSQL

В PostgreSQL индекс создается на основе одного или нескольких значений полей и ссылок на соответствующие строки этой таблицы. Для наглядности рассмотрим тот же пример с библиотекой. Пусть существует база данных «Библиотека» с таблицей «Книга», содержащей следующие поля: ID книги (уникальный идентификатор), название, автор и год издания.
Рассмотрим следующий запрос для этой таблицы:

    SELECT * FROM book WHERE P(year) = 1

В данном случае выражение P(year) = 1 обозначает, что значение year соответствует условию (или предикату) P.

Если для year отсутствует индекс, то PostgreSQL вынужден полностью прочитать таблицу book для выполнения запроса, считая для каждой записи предикат, и при соблюдении условия добавлять запись к конечному результату.

Но если для колонки year определен индекс, то PostgreSQL сразу получает из индекса указатели на строки таблицы, удовлетворяющие нужному условию P, не просматривая при этом таблицу целиком. И уже после по полученным ссылкам считать данные и сформировать ответ.

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

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

CREATE INDEX (или как создать индекс PostgreSQL)

В PostgreSQL, чтобы оптимизировать запрос и создать индекс, нужно выполнить команду CREATE INDEX:

    CREATE INDEX book__author_year__index
ON book (author, year,....)

Эта команда поддерживает множество дополнительных параметров. Рассмотрим некоторые из них.

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

    CREATE UNIQUE INDEX book__author_year__index
ON book (author, year,....)

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

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

    SELECT * FROM book
WHERE lower(author) = 'charles bukowski'

Стандартный индекс для author не поможет, так как PostgreSQL создаст индекс из этого поля в исходном виде, а для искомой выборки нужны видоизмененные значения поля. Но можно сразу сделать индекс по результатам функции:

    CREATE INDEX book__lower_author__index ON book(lower(author))

С таким индексом запрос отработает быстрее.

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

Чтобы использовать новый тип, нужно перед списком полей в запросе нужно добавить директиву USING вместе с желаемым типом. Например, чтобы использовать индекс типа Hash, потребуется запрос:

    CREATE INDEX book__author__index ON book USING HASH (author)

Типы индексов в PostgreSQL

B-tree

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

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

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

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

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

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

B-tree индекс может также ускорить запросы, использующие не все поля индекса, а какую-то их часть. Например, он может ускорить выполнение LIKE при отборе, которые начинаются с определенной подстроки:

    SELECT * FROM book WHERE author LIKE 'Joanne%'

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

    SELECT * FROM book WHERE author = 'Stephen King'

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

Hash

Хэш-индексы стоит применять при условиях, проверяющих равенство или использующих сравнение, например, author = ’Mikhail Bulgakov’. Это обусловлено ограничениями алгоритма хэширования. При построении индекса используется хэш-функция, которая принимает в качестве аргументов значение ключа индекса и вычисляет значение. Это значение сохраняется вместе с указателем на запись в таблице.

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

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

    CREATE INDEX book__author__index ON book USING hash (author);

GiST

Аббревиатура GiST означает «generalized search tree». Эта структура данных является сбалансированным деревом поиска, аналогичным B-дереву. Но если B-дерево полезно только для данных, которые можно сравнить, то такое дерево нужно в тех случаях, когда операция сортировки нецелесообразна, например, для запроса с географическими данными или геометрическими объектами.

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

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

SP-GiST

Индекс SP-GiST, где префикс расшифровывается как «space partitioning», позволяет создавать несбалансированные деревья. Такое дерево может помочь для задачи разделения множества на непересекающиеся части. Например, SP-GiST можно применять для улучшения поиска геометрических данных. Свойство не пересечения помогает принятию решений при поиске и вставке. Однако такие деревья обычно имеют мало ветвей, что затрудняет их хранение в памяти.

GiST и SP-GiST облегчают расширение PostgreSQL и внедрение новых структур индексов для индексирования разнообразных данных.

GIN

Индекс GIN (Generalized Inverted Index) применяется для составных типов данных, доступ к которым осуществляется через ключи. Они используют реализацию одного из нескольких алгоритмов и их тоже можно расширять.
Его стоит использовать для определенных типов при следующих условиях:

• для массивов — операторы &&, <@, =, @>
• для jsonb (можно применить к определенным полям) — операторы ?, ?&, ?|, @>
• для tsvector — операторы @@ и @@@

BRIN

BRIN (Block Range Index) нужен для индексирования больших таблиц, где столбцы могут коррелировать с их физическим положением в таблице. Введем понятие зоны блоков — набора записей, которые расположены рядом в таблице, где для каждой зоны хранится сводная информация.

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

Такой индекс применим для всех операторов сравнения, кроме неравенства, или применять для условий, подходящих под следующие параметры:

• для типов box — операторы &&, &>, &<, &<|, >>, <<, <<|, <@, @>, @, |&>, |>>, ~, ~=
• для типов range — операторы &&, &>, &<, >>, <<, <@, -|-, =, @>, @>

Механизмы индексирования

Типы индексов PostgreSQL также называют методами доступа. Вне зависимости от типа индекса, они все сводятся к тому, что устанавливают соответствие между ключом и записями таблицы, где этот ключ встречается. У каждой строки есть идентификатор TID (tuple identifier — идентификатор кортежа), который включает в себя номер блока файла и позицию строки внутри этого блока.

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

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

Механизм индексации участвует в запросах, активируясь в соответствии с планом, созданным в процессе оптимизации запроса. При этом оптимизатор, исследуя различные варианты выполнения, обязан оценивать потенциал всех доступных методов.

Методы также отвечают за следующие задачи:

• Реализация алгоритма формирования индекса и разделения данных на страницы;
• Поиск в индексе по запросу вида «индексированное поле — оператор — выражение» для извлечения требуемых данных;
• Оценка затрат на применение индекса с целью определения его эффективности;
• Управление блокировками для обеспечения правильного параллельного выполнения и предотвращения конфликтов;
• Создание журнала предварительной записи (WAL).

Механизм индексирования обеспечивает единообразную работу с различными методами доступа, принимая во внимание их особенности.

Индексное сканирование

Рассмотрим пример работы с TID, полученными от индекса. Пусть есть та же таблица «Книга» с полями «Книга» ID книги, название, автор и год издания. Необходимо получить выборку по условию «год издания = 1985». В данном случае условие имеет подходящий вид, где оператором будет равенством, а выражение значение конкретного года. Условие часто должно быть сформулировано именно так, чтобы индекс мог быть применен.

В такой ситуации оптимизатор предпочел бы применить индексное сканирование (Index Scan), при котором метод доступа извлекает TID до тех пор, пока не будут обработаны все соответствующие строки. Механизм индексации направляется к соответствующим страницам таблицы, куда указывают TID.

Последовательное сканирование

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

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

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

Покрывающие индексы

Основной целью методов доступа является нахождение идентификаторов подходящих записей в таблице, чтобы затем получить запрашиваемые данные. Если в индексе уже содержатся все данные, нужные для запроса, он считается покрывающим (covering). Тогда оптимизатор может использовать исключительно индексное сканирование (Index Only Scan).

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

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

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

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

С помощью команды explain analyze можно выяснить число требующихся обращений к таблице:

    explain (analyze, costs off) SELECT year FROM book WHERE year < 2000

Если чистка была выполнена недавно, то обращение к таблице не понадобится. Чем ближе к нулю показатель Heap Fetches, тем лучше.

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

Null

В реляционных БД часто используются неопределенные значения null, так как с их помощью просто указывать, что значение отсутствует.

Это вызывает определенные сложности, поскольку требуется особый подход к обработке таких значений. Для нулевых значений появляется третье значение, и неясно, должно ли значение null рассматриваться как большее или меньшее по сравнению с другими (поэтому применяются специальные конструкции для сортировки, такие как NULLS FIRST). Кроме того, возникают вопросы о правильном использовании в агрегатных функциях и другие сложности.

Индексация null значений является компромиссом: без них индекс компактнее, но их включение позволяет использовать запросы с требованиями «поле IS NULL» и делает индекс покрывающим, возвращая данные даже для записей с неопределенными значениями.

Каждый вид метода доступа решает, индексировать null или нет, но чаще такое значение все-таки индексируется.

Частичные индексы

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

Например, в таблице «Книги» есть поле is_translated, указывающее, является ли книга переводом с другого языка. И нам известно, что в таблице около 90% книг – переводы. В таком случае стоит создать частичный индекс:

    CREATE INDEX ON book(is_translated) where is_translated;

Иногда отличие в объеме и производительности обычного и частичного индексов может быть кардинальным.

Сортировка

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

Существует два варианта: либо извлечь данные и отсортировать их, либо сразу прочитать упорядоченные данные.

Среди всех методов доступа только B-tree способно возвращать отсортированные данные.

Параллельное построение

При создании индекса на таблицу устанавливается блокировка SHARE, разрешающая чтение данных, но запрещающая их изменение до завершения индексации.

Это можно проверить, выполняя запрос в другом сеансе во время добавления индекса в таблице book. Если таблица крупная и активно используется, сеансы могут долго ожидать освобождения блокировки, что делает этот процесс неприемлемым.

Тогда можно создать индекс параллельно:

    CREATE INDEX CONCURRENTLY ON book(author);

Тогда создастся блокировка другого типа – SHARE UPDATE EXCLUSIVE, позволяющая и читать, и изменять данные. Однако даже с таким типом есть определенные ограничения: не допускается изменять структуру таблицы, а также проводить одновременно чистку, анализ или создание другого индекса в этой же таблице.

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

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

    SELECT indexrelid::regclass index_name, indrelid::regclass table_name FROM pg_index WHERE NOT indisvalid;

Заключение

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