Что такое GiST индекс и как он устроен

Что проверяют

Понимаете ли вы, что индекс в PostgreSQL это не одна структура, а семейство, и умеете ли выбирать под форму запроса. Для бэкендера на Node навык прикладной: условие, которое не ложится на B-дерево (пересечение диапазонов, геометрия, нечёткое совпадение), либо получает подходящий индекс, либо уезжает в полный перебор таблицы.

Как отвечать

GiST (Generalized Search Tree) это сбалансированное дерево, в котором движок не знает семантики ключей. Внутренний узел хранит предикат, истинный для всего поддерева, и поиск спускается только в те ветки, где предикат не противоречит условию. Вся конкретика вынесена в функции класса операторов: consistent (может ли поддерево содержать ответ), union (объединить ключи потомков), penalty и picksplit (куда класть ключ и как делить переполненную страницу), same. Реализовали их, получили индекс под свой тип данных.

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

create extension btree_gist;
alter table bookings
  add constraint no_overlap
  exclude using gist (room_id with =, period with &&);

Полезно сравнить с GIN: для tsvector по умолчанию берут GIN, он быстрее на чтение, а GiST компактнее, дешевле в обновлении и умеет запросы на близость.

Где спотыкаются

Считают GiST улучшенным B-деревом и вешают его на обычные равенства и сравнения, где btree и быстрее, и заметно компактнее.

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

Путают область применения с GIN. GIN живёт там, где значение раскладывается на множество элементов (массивы, jsonb, полнотекст), GiST там, где важны перекрытие, вложенность и близость.