GIN и GiST: полнотекстовый поиск и гео

Booking.com обрабатывает 1.5М запросов в секунду. Часть из них - поиск отелей по геолокации и фильтры по тегам ('wifi', 'pool', 'pet-friendly'). B-Tree здесь не подходит. GIN и GiST - специализированные индексы, которые делают такие запросы за миллисекунды.

• **Uber/Lyft**: поиск ближайших водителей - GiST (PostGIS ST_DWithin) на таблице с геопозициями. Обновление локации ~4 раза/сек на миллионах устройств
• **GitHub Search**: поиск по коду и issues - GIN на tsvector. Индексирование 200М+ репозиториев. Альтернатива Elasticsearch для транзакционных данных
• **StackOverflow**: теги вопросов - GIN на массиве тегов. Запросы вида 'найди вопросы с тегами [postgresql] И [indexing]' через @>-оператор

GIN: инвертированный индекс как в поисковиках

Elasticsearch внутри - инвертированный индекс. PostgreSQL GIN (Generalized Inverted Index) - та же идея, встроенная в СУБД. Структура: словарь ключей → posting list (список heap-блоков где ключ встречается). Для строки 'postgresql database' создаются два входа: 'postgresql' и 'database', каждый ссылается на строку.

GIN оптимизирован для типов с несколькими значениями внутри одной строки: массивы, JSONB, tsvector, hstore. B-Tree строит один индексный ключ на строку; GIN строит N ключей. При запросе `@>` или `&&` PostgreSQL находит пересечение posting list'ов - это быстро даже на миллионах строк.

ML-параллель: TF-IDF и BM25 - это поверх инвертированного индекса. GIN - структура данных, ранжирование - отдельный слой. pgvector для векторного поиска использует другой подход (HNSW/IVFFlat), но GIN остаётся лучшим для точных многозначных совпадений (tags, ACL, JSON-paths).

GIN для JSONB и массивов: операторы и индексируемость

Два класса операторов GIN. Для массивов: `@>` (содержит), `&&` (пересечение), `<@` (содержится). Для JSONB: те же плюс `?` (ключ exists), `?|` (любой из ключей), `?&` (все ключи). GIN автоматически индексирует все ключи и значения JSONB - поэтому запрос `data ? 'email'` попадает в индекс.

Два opclass для JSONB: `jsonb_ops` (default) индексирует ключи и значения отдельно, поддерживает все операторы. `jsonb_path_ops` индексирует только пути к значениям, не поддерживает `?`/`?|`/`?&`, но в 2-3 раза компактнее и быстрее для `@>`. Выбор зависит от паттерна запросов.

GIN для полнотекстового поиска: tsvector и tsquery

PostgreSQL fulltext search: документ преобразуется в `tsvector` (нормализованные лексемы с позициями), запрос - в `tsquery`. Оператор `@@` проверяет совпадение. GIN-индекс на tsvector-колонке превращает это в мгновенный поиск по posting lists.

Почему не Elasticsearch? Для объёмов до 10-50М документов PostgreSQL FTS конкурентоспособен: нет дополнительной инфраструктуры, транзакционная консистентность, JOIN с основными данными. Elasticsearch выигрывает при: шардировании на несколько машин, сложном scoring (BM25 с полями), real-time индексировании >100K doc/sec.

GiST для пространственных типов и PostGIS

GiST (Generalized Search Tree) - расширяемый фреймворк для индексов, где каждый узел дерева хранит не точный ключ, а предикат (bounding box, диапазон, круг). Поиск - рекурсивный обход: пропускаем поддеревья, чей предикат несовместим с запросом. Это R-Tree на стероидах.

GiST vs GIN: выбор определяется типом запроса. GiST - для пространственных предикатов (ST_Within, KNN, range overlap), всегда один ключ на строку. GIN - для многозначных containment-запросов (массивы, JSONB, FTS). Один тип данных может поддерживать оба: tsvector поддерживает GIN (быстрее для поиска) и GiST (меньше памяти при записи).

GiST для range-типов и exclusion constraints

PostgreSQL range-типы: `int4range`, `tsrange`, `daterange` и др. GiST-индекс на range-типе поддерживает операторы `&&` (overlap), `@>` (contains), `<@` (contained by). Это позволяет строить запросы типа 'найди все брони, пересекающиеся с интервалом [check_in, check_out]' за O(log N).

Exclusion constraint - мощнее UNIQUE: UNIQUE = 'нет двух равных значений', EXCLUDE = 'нет двух строк, удовлетворяющих произвольному оператору'. Классический кейс - calendar booking без double-booking. Constraint проверяется через GiST-индекс на вставке/обновлении. Производительность вставки: O(log N) против O(N) для триггерного решения.

Связанные темы

GIN и GiST - специализированные индексы для конкретных типов данных:

• JSONB в PostgreSQL — GIN-индексы - основной инструмент для запросов по JSONB-документам
• Полнотекстовый поиск — GIN индексирует tsvector - фундамент FTS в PostgreSQL
• Расширения: PostGIS — PostGIS использует GiST для пространственных индексов

Ключевые идеи

• **GIN - инвертированный индекс**: ключ → posting list строк. Оптимален для @>, &&, ?, когда в строке N значений (массивы, JSONB, tsvector).
• **jsonb_ops vs jsonb_path_ops**: jsonb_ops универсален (?, ?|, ?&, @>), jsonb_path_ops в 2-3 раза компактнее для чистых @>-запросов.
• **Fulltext: GIN + tsvector**: setweight для field-boosting, ts_rank для ранжирования, phraseto_tsquery для фразового поиска.
• **GiST - расширяемое дерево**: предикаты вместо точных ключей. KNN через <->, ST_DWithin для радиуса, range && для пересечений.
• **EXCLUDE USING gist**: exclusion constraint через GiST-индекс - атомарная защита от пересечений за O(log N) вместо триггерного O(N).

Вопросы для размышления

• GIN-индекс на JSONB с jsonb_ops индексирует все ключи и значения. Что происходит с размером индекса при высокой кардинальности значений (UUID как значение в JSON)?
• Exclusion constraint с GiST проверяется на вставке. Как это влияет на производительность массового импорта данных о бронированиях?
• GIN поддерживает 'fast update' mode - буферизацию изменений. Когда это полезно и когда вредит?

Связанные уроки

• pg-14-partial-expr — Частичные и expression-индексы - предшествующий уровень абстракции
• pg-16-brin — BRIN - следующий специализированный индекс в серии
• pg-32-jsonb — GIN-индексы - основной инструмент для JSONB-запросов
• pg-33-fulltext — GIN индексирует tsvector для полнотекстового поиска
• pg-36-extensions — PostGIS использует GiST для пространственных запросов
• alg-05 — GiST - обобщённое дерево поиска: тот же принцип, другие предикаты
• db-10-indexes-advanced