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

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

Индекс помогает ускорить запрос. Если запросы в БД начинают тормозить, то первым делом думают о создании индекса. Но нужно учитывать, это не всегда правильно. Нельзя воспринимать создание индексов как панацею. Если вы создадите индекс, то БД сама решит использовать его или нет.

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

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

Содержание

Структура индекса

Параметры индекса

Уникальный индекс

Блокировка

Сортировка

Составной индекс

Функциональный индекс

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

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

Виды сканирования таблицы

Sequential Scan

Index Scan

Index-only Scan

Bitmap Index Scan

Индексы PostgreSQL

Структура индекса

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

Screen Shot 2017-05-30 at 17.00.16.png

Индекс можно создать для любого столбца или представления (view), за исключением столбцов с типами данных для хранения больших объектов: text, image или varchar(max).

Создается индекс следующей командой:

CREATE INDEX name ON table (column);

К примеру, у нас есть таблица пользователей и мы создали индекс по колонке age.

CREATE INDEX users_age_idx ON users (age);

Теперь мы хотим найти пользователя, которому 15 лет. Что происходит внутри базы данных? Она знает, что на колонку age создан индекс и начнет поиск сначала по индексу, начиная с корня и спускаясь вниз по узлам до тех пор, пока не найдет искомое значение. В итоге поиска мы получаем указатель на строку со всеми данными из таблицы. Вместо того, что-бы проверять каждое значение, которое могло бы занять 7 шагов, мы нашли за 3 шага.

Screen Shot 2017-05-30 at 17.00.46.png

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

Screen Shot 2017-05-30 at 17.01.30.png

Кластеризованный индекс уже хранит данные в своих листьях. Он находится в отсортированном виде и создается только один на всю таблицу. Обычно на колонку id, которая является первичным ключом (primary key), по умолчанию создается кластеризованный индекс.

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

Куча (heap) это просто неотсортированные данные таблицы.

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

Параметры индекса

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

CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ]name ] ON table_name [ USING method ] ({ column | ( expression ) } [ ASC | DESC ] [ NULLS { FIRST | LAST } ] [, ...]) [ WHERE predicate ]

Уникальный индекс

CREATE UNIQUE INDEX users_uid_idx ON users (uid);

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

CREATE UNIQUE INDEX users_full_name_idx

ON users (first_name, last_name);

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

Screen Shot 2017-05-30 at 17.02.40.png

Блокировка

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

CREATE INDEX users_age__idx CONCURRENTLY ON users (age);

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

Сортировка

Индекс бывает полезен при сортировке выборки. При создании индекса мы можем указать ему направление сортировки ASC или DESC.

CREATE INDEX users_age__idx ON users (age) ASC;

Screen Shot 2017-06-01 at 15.49.53.png

После выборки всех записей и указания сортировки по колонке age, то БД воспользуется отсортированным индексом по колонке age и после соберет все данные по связанным записям.

SELECT * FROM users WHERE gender = 'female' ORDER BY age;

Также при создании индекса мы можем указать куда вставлять записи со значением NULL, добавив параметры NULL FIRST или NULLS LAST.

CREATE INDEX users_age__idx ON users (age) ASC NULL FIRST;

Функциональный индекс

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

SELECT * FROM users

WHERE (first_name || ' ' || last_name) = 'Glenn Quagmire';

Здесь функциональный индекс может сильно помочь. Создается он следующим образом:

CREATE INDEX users_full_name_idx

ON users (first_name || ' ' || last_name);

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

Screen Shot 2017-05-30 at 17.04.45.png

Составной индекс

Составной индекс – означает индекс, созданный по одной или более колонок. Т.е. если та же таблица пользователей имеет колонки age и gender, то можно создать индекс на эти две колонки:

CREATE INDEX users_age_idx ON users (age, gender);

Тут важно понимать, что порядок важен. Т.е. если мы используем в индексе две колонки (age + gender) то ключи индекса будут выглядеть как: 16male, 20female, 21male и т.д. Это означает, что при поиске по параметрам возраст + пол подсистема склеит их и попытается найти запись по индексу с соответствующим ключом.

Screen Shot 2017-05-30 at 17.02.07.png

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

Бывают случаи, что не нужно строить индекс по всей таблице. Например, есть наша любимая таблица users и в ней есть колонка is_active. Т.к., обычно, все запросы работают только с активными пользователям, то тогда есть возможность создать индекс только по активным записям:

CREATE INDEX users_name_part_idx ON users (name)

WHERE is_active = true;

Составные и уникальные индексы тоже могут быть частичными.

CREATE UNIQUE INDEX users_full_name_part_idx

ON users (first_name, last_name)

WHERE is_active = true;

Screen Shot 2017-05-30 at 17.04.03.png

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

Допустим, нам надо найти достать фамилии у всех пользователей с именем Lisa.

SELECT first_name, last_name FROM users WHERE first_name = 'Lisa';

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

CREATE INDEX users_fullname__idx

ON users (first_name, last_name);

БД знает, что индекс хранит уже в себе поля first_name и last_name.

Screen Shot 2017-06-01 at 18.44.16.png

После того, как БД найдет записи в индексе с именем Lisa, он не будет обращаться к исходной таблице за фамилией, он возьмет ее у индекса.

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

SELECT u.*, b.place FROM users

LEFT JOIN busyness ON u.id = b.user_id;

Screen Shot 2017-06-01 at 18.31.02.png

В результате БД воспользуется данными из индекса (user_id, place), потому что нам кроме значений place ничего не нужно. Не будет никакого обращения в таблицу busyness.

Виды сканирования таблицы

При поиске значения из таблицы БД сама решает каким образом лучше это сделать.

Sequential Scan

SELECT * FROM users WHERE age = 21;

Screen Shot 2017-05-30 at 16.37.49.png

Последовательное сканирование. В этом случае БД будет проверять каждую запись на соответствие поиска пока не найдет нужную запись.

Index Scan

SELECT * FROM users WHERE age = 25;

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

Screen Shot 2017-05-30 at 17.29.55.png

Index-only Scan

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

CREATE INDEX users_age_idx ON users (age, gender);

То после следующего запроса:

SELECT age, gender FROM users WHERE age = 24;

БД возьмет эти данные у листьев индекса.

Screen Shot 2017-05-30 at 17.40.47.png

Bitmap Index Scan

Допустим, у нас созданы два разных индекса на колонки age и gender:

CREATE INDEX users_age__idx ON users (age);

CREATE INDEX users_gender__idx ON users (gender);

И мы пытаемся сделать выборку по этим полям:

SELECT * FROM users WHERE age > 20 AND gender = 'male';

БД сначала воспользуется индексом по колонке age, потом по колонке gender. Далее создаст битовую карту по результатам и отфильтрует их битовым оператором and.

Screen Shot 2017-06-01 at 13.45.37.png

То же самое будет происходит и с оператором OR.

SELECT * FROM users WHERE age > 20 OR gender = 'male';

Screen Shot 2017-06-01 at 16.02.50.png

Индексы PostgreSQL

Если при создании индекса не указывать его тип…

CREATE INDEX name ON table (column);

… то по умолчанию будет создан индекс типа B-Tree.

Однако PostreSQL позволяет создавать индексы таких типов, как B-Tree, Hash, GiST, SP-GiST, GIN и BRIN.

CREATE INDEX name ON table USING index_type (column);

B-Tree

B-tree (Balanced Tree) строит индексы используя реализацию сбалансированного дерева. Он может быть использован в условиях сравнения или проверке в диапазоне.

Screen Shot 2017-05-30 at 17.05.22.png

Полезен в следующих случаях:

операторы сравнения >, <, =, >=, <=, BETWEEN и IN;

условия пустоты IS NULL и IS NOT NULL;

операторы поиска подстроки LIKE и ~, если искомая строка закреплена в начале шаблона (например name LIKE 'Lisa%');

регистронезависимые операторы поиска подстроки ILIKE и ~*. Но только в том случае, если искомая строка начинается с символа, который одинаков и в верхнем и в нижнем регистре (например числа)`.

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

Hash

Hash индексы используются только при условии равенства name = 'Bart' и все. При построении hash индекса участвует hash функция, которая принимает значение 'Bart' и на выходе, вычисляя hash – 200, распределяет их по секциям. При корреляции объекты внутри секции выстраиваются в цепочку.

Screen Shot 2017-06-12 at 19.13.19.png

Создается следующее командой:

CREATE INDEX name ON table USING hash (column);

Внимание

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

GiST

GiST (Generalized Search Tree) для построения индексов использует один из нескольких алгоритмов, наиболее подходящих под тип индексируемого поля. Поэтому набор операторов при работе с которыми может быть задействован этот индекс зависит от типа поля. По умолчанию PostgreSQL предоставляет индексы для некоторых типов данных, таких как геометрические типы, сетевые адреса, диапазоны и т.д. Так же этот список можно расширить, установив соответствующие модули.

На базе GiST могут быть реализованы B-деревья, R-деревья и многие другие схемы индексации.

Полезен в следующих случаях:

типы box, circle и polygon – операторы &&, &>, &<, &<|, >>, <<, <<|, <@, @>, @, |&>, |>>, ~, ~=;

типы inet и cidr – операторы &&, >>, >>=, >, >=, <>, <<, <<=, <, <=, =;

тип point – операторы >>, >^, <<, <@, <@, <@, <^, ~=;

тип tsquery – операторы <@, @>;

тип tsvector – оператор @@;

все типы range – операторы &&, &>, &<, >>, <<, <@, -|-, =, @>, @>.

SP-GiST

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

Полезен в следующих случаях:

тип point – операторы >>, >^, <<, <@, <@, <@, <^, ~=;

типы box – операторы &&, &>, &<, &<|, >>, <<, <<|, <@, @>, @, |&>, |>>, ~, ~=;

все типы range – операторы &&, &>, &<, >>, <<, <@, -|-, =, @>, @>;

все типы text – операторы <, <=, =, =>, ~<=~, ~<~, ~>=~, ~>~.

GIN

GIN (Generalized Inverted Index) индексы применимы к составным типам, работа с которыми осуществляется с помощью ключей. Это массивы, jsonb и tsvector. Как и GiST индексы, они могут реализовать один из нескольких алгоритмов. И стандартный набор можно так же расширить, установив модели.

Полезен в следующих случаях:

массивы – операторы &&, <@, =, @>;

тип jsonb – операторы ?, ?&, ?|, @>;

тип tsvector – операторы @@ и @@@.

Так же GIN индекс может быть создан только для определенных полей jsonb поля.

BRIN

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

Полезен в следующих случаях:

типы box – операторы &&, &>, &<, &<|, >>, <<, <<|, <@, @>, @, |&>, |>>, ~, ~=;

все типы range – операторы &&, &>, &<, >>, <<, <@, -|-, =, @>, @>;

операторы сравнения >, <, =, >=, <=.

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