Jun 16 2020 at 12:14

Погружаемся в индексы PostgreSQL

Invite pending

После прочтения этой статьи вы узнаете какие типы индексов есть в PostgreSQL. Какие есть способы построить индекс и в каких случаях использовать тот или иной тип индекса.

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

Индексы позволяют уменьшит количество последовательных просмотров табицы (seq scan). Поэтому понимать как их строить и в каком случае выбрать тот или иной тип индекса все же необходимо.

И так, подготовим таблицу для экспериментов:

create extension pgcrypto;
create table test (id serial, city text, salt text);

insert into test(name, salt) 
    select 'Moscow', gen_random_uuid() from generate_series(1, 3000000);

insert into test(name, salt) 
    select 'Vladivostok', gen_random_uuid() from generate_series(1, 3000000);

insert into test(name, salt) 
    select 'Perm', gen_random_uuid() from generate_series(1, 3000000);

Нашим тестовым запросом будет :

select * from test where id = 6539748;

На моей машине такой запрос без индексов выполнялся 598 миллисекунд, а при построенном индексе по полю id уже 94 миллисекунды. Теперь понятно, что индексы — мощная штука. Но как их построить и как они устроены внутри мы пока не знаем? Давайте заполнять пробелы.

Как построить индекс

Запрос на построение индекса к нашей тестовой таблице очень простой:

create index index_id on test (id);

Круто, теперь мы умеем строить индексы по таблице, вот только есть пару но. Create index захватывает блокировку (про типы блокировок я напишу отдельную статью) на всю таблицу. Эта блокировка препятствует любым изменениям. Если у нас небольшая таблица, то ничего страшного, индекс построится достаточно быстро и мы ничего не заметим.

К примеру на моей машине для нашей тестовой таблицы индекс строился целых 9 секунд. А что делать, если таблица большая, а индекс построить нужно?

На помощь нам приходит create index concurrently. Данная операция не блокирует таблицу, но при этом и работает дольше чем create index. Все на том же примере у меня это действие заняло почти 13 секунд. Однако, PostgreSQL не дает гарантий, что create index concurrently выполнится успешно. В случае возникновения конфликтов при построении, то такой индекс просто будет помечен как недействительный и не будет участвовать в выполнении запросов.

Замечу еще один момент: параллельное построение индекса доступно только с версии PostgreSQL 11.

Внутреннее устройство индекса

Чтобы посмотреть, какие типы индексов доступны на вашей инсталяции PostgreSQL нужно выполнить вот такой запрос select * from pg_am. У меня в PostgreSQL версии 11.8 доступны следующие типы:

B-Tree
Hash
GIST
GIN
SP-GIST
BRIN

В данной статье я разберу только два, самый популярных, индекса: b-tree и hash. Другие типы индексов, такие как GIN, нуждаются в отдельном, более глубоком разборе.

B-tree

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

В PostgreSQL используется b-tree Лемана-Яо. Что это за дерево такое? Дерево Лемана-Яо позволяет выполнять значительное количество операций чтения и записи над одним и тем же индексом. За более детальным описанием можете обратиться к научной статье Efficient Locking for Concurrent Operations on B-Trees.

B-tree хранит в себе данные в отсоритрованном виде, что дает нам возможность быстрого поиска нужного элемента (вспомните бинарный поиск). Еще одним немаловажным фактором является то, что b-tree в PostgreSQL можно читать как в прямом, так и в обратном порядке. Только вот что нам эта особенность дает?

К примеру такой запрос select min(id), max(id) from test есть ни что иное как простое чтение первого и последнего элемента в дереве. Это очень быстрая операция.

Hash

Мы знаем про индекс построенный на b-tree. Он выполняет свою задачу корректно и эффективно. Мы можем построить его параллельно, без блокировки таблицы. Лучше умы computer science трудились над оптимизацией b-tree. Тогда зачем нам другие типы индексов?

Помните, что я сказал про b-tree: эта структура данных хранит в себе элементы в отсортированном виде. А что делать, если какой то тип данных нельзя разумно отсоритровать? Или что делать, если нам ннужно отвеить на вопрос: содержит ли таблица такое значение или нет? Вот здесь нам помогут hash индексы.

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

Так же, как и у b-tree, хеш-индексы имеют ряд особенностей:

хеш-индексы не подходят для сортировки, потому как хеш (по факту это строка) нельзя разумно отсортировать;
поиск по частичному ключу не поддерживается
доступны только операторы =, <=>, IN()

оператор <=> работает также, как и оператор =, только в случае, если оба операнда равны NULL, возврашает 1, а не NULL и 0, а не NULL, если один из операндов равен NULL.

Темная сторона индексов

Если индексы такие крутые и так сильно помогают СУБД в работе, то почему бы нам не построить индексы на все поля для всех таблиц?

Вот сейчас мы и пришли к темной стороне индексов. Действительно это очень крутой инструмент, но он не бесплатен.

Индексы занимают место на диске и в памяти. К примеру на нашей тестовой таблице с 9 млн. записей хеш-индекс по полю salt занимает 256Мб, а b-tree индекс уже 507 Мб.

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

Hubs: