Глава 35. GIN: инвертированный индекс · PostgreSQL

35.1 Когда у строки много ключей

Возьми колонку с массивом тегов {sale, new, ru} или документ body из сотни слов. Запросы к ним - не про равенство строки целиком, а про вхождение элемента: «у каких строк в тегах есть sale?», «в каких документах встречается слово рейс?».

B-tree индексирует значение колонки целиком и для таких вопросов бесполезен: он не знает про «элемент внутри значения». GIN переворачивает связь. Он строит соответствие «элемент → список строк, где он встречается». Один документ из ста слов даёт сто записей в индексе - по одной на слово, и каждая указывает на этот документ.

35.2 Инвертированный индекс и posting lists

Структура GIN из двух уровней. Сверху - entry tree: B-tree по всем уникальным ключам (словам, элементам, фрагментам JSONB). Снизу - к каждому ключу прикреплён posting list: отсортированный список ctid строк, где этот ключ встречается.

entry tree:        рейс        задержка      багаж

                    │            │            │

posting lists:   [r1,r7,r9]   [r3,r7]      [r2,r7,r9]

Запрос «рейс И багаж» сводится к пересечению posting lists для рейс и багаж - быстрая операция над отсортированными списками. Если posting list большой, он сам превращается в дерево (posting tree), чтобы не разрастаться на одной странице. Подробно - в gin-index.

35.3 Почему B-tree проваливается на LIKE '%x%'

B-tree ускоряет LIKE 'abc%' (префикс) с правильным operator class, но LIKE '%abc%' (подстрока в середине) - никогда. Причина в устройстве: B-tree находит диапазон по началу значения, а подстрока может быть где угодно внутри, начало неизвестно. Значит, остаётся только прочитать все строки - Seq Scan.

sql

EXPLAIN SELECT * FROM docs WHERE body LIKE '%рейс%';   -- Seq Scan

Здесь и выходит на сцену GIN. Для полнотекста строят GIN по tsvector (разобранный на слова текст) и ищут оператором @@:

sql

CREATE INDEX ON docs USING gin (to_tsvector('simple', body));

EXPLAIN SELECT * FROM docs

WHERE to_tsvector('simple', body) @@ to_tsquery('simple', 'рейс');

-- Bitmap Index Scan через GIN, быстро

Разница на больших объёмах - между долгими секундами Seq Scan и миллисекундами поиска по словам.

35.4 GIN на JSONB

Второе главное применение - JSONB. GIN индексирует ключи и значения документа, и оператор содержания @> начинает работать через индекс:

sql

CREATE INDEX ON doc USING gin (body);

EXPLAIN SELECT * FROM doc WHERE body @> '{"tag":"sale"}';   -- через GIN

У JSONB есть два operator class. По умолчанию GIN индексирует и ключи, и пути, и значения - это поддерживает много операторов, но индекс крупный. jsonb_path_ops индексирует только пути целиком - индекс меньше и быстрее, но поддерживает в основном @>:

sql

CREATE INDEX ON doc USING gin (body jsonb_path_ops);

Выбор - между универсальностью и компактностью, и это снова вопрос operator class (см. operator-classes).

35.5 fastupdate и pending list

У GIN дорогая запись: одна строка с сотней слов порождает сотню записей в индексе, и каждая вставка трогает много мест. Чтобы не платить это на каждый INSERT, GIN по умолчанию использует fastupdate: новые записи сначала складываются в неупорядоченный pending list, а в основную структуру переносятся пачкой - при вакууме или когда pending list дорастёт до gin_pending_list_limit.

Выгода - быстрые вставки. Плата - поиск должен просмотреть и основную структуру, и pending list, поэтому при большом pending list поиск замедляется. Перенос делает VACUUM (или функция gin_clean_pending_list).

35.5.1 Подводный камень: GIN дорог на запись

GIN блестит на чтение и тяжёл на запись - об этом надо помнить при проектировании. Таблица с интенсивными INSERT/UPDATE и GIN-индексом по большому полю будет ощутимо медленнее на записи, а pending list будет расти между вакуумами.

Практические следствия:

GIN уместен там, где читают намного чаще, чем пишут (каталоги, логи для поиска, документы);
на горячей по записи таблице взвесь стоимость: возможно, полнотекст лучше держать в отдельной таблице или обновлять реже;
следи, чтобы autovacuum успевал переносить pending list, иначе поиск деградирует незаметно.

Это типичный размен индексов: GIN покупает быстрый поиск по вхождению ценой записи.

35.6 Что индексирует GIN

Сводка применений, чтобы не путать с соседними AM:

полнотекст - GIN по tsvector, оператор @@;
JSONB - GIN по документу, операторы @>, ?, и т.д.;
массивы - GIN по массиву, операторы @>, <@, && (содержит, содержится, пересекается);
LIKE/regex по подстроке - GIN по триграммам (расширение pg_trgm), оператор LIKE '%x%' через триграммы.

Общий признак, по которому выбирают GIN: у одной строки много индексируемых элементов, и поиск идёт по вхождению одного из них. Если же у строки один скалярный ключ и нужен порядок - это B-tree, не GIN.

Уроки в sandbox

lab-35.1. btree проваливается на LIKE, GIN спасает полнотекст

Сначала убедимся, что btree не помогает LIKE '%x%', потом построим GIN по tsvector и сравним. Перед каждым EXPLAIN предскажи тип узла.

Создай таблицу текстов: CREATE TABLE docs AS SELECT g id, 'рейс ' || g || ' статус ' || (CASE WHEN g%3=0 THEN 'задержка' ELSE 'вовремя' END) AS body FROM generate_series(1, 200000) g;.
Построй btree и попробуй подстроку: CREATE INDEX ON docs (body); EXPLAIN SELECT * FROM docs WHERE body LIKE '%задержка%'; - предскажи (Seq Scan: btree не умеет подстроку).
Построй GIN по tsvector: CREATE INDEX docs_fts ON docs USING gin (to_tsvector('simple', body)); ANALYZE docs;.
Полнотекстовый запрос: EXPLAIN SELECT * FROM docs WHERE to_tsvector('simple', body) @@ to_tsquery('simple','задержка'); - предскажи (Bitmap Index Scan через GIN).
Сравни время через EXPLAIN ANALYZE обоих вариантов и размеры индексов через \di+.

sandbox с автопроверкой - открыть в песочнице

Резюме

GIN - инвертированный индекс для данных, где у строки много элементов: массивы, JSONB, полнотекст. Он строит соответствие «элемент → список строк».
Структура двухуровневая: entry tree (B-tree уникальных ключей) и posting lists (отсортированные ctid); большой posting list становится posting tree.
B-tree бессилен против LIKE '%x%' (подстрока без известного начала) и полнотекста; GIN по tsvector с оператором @@ решает это быстро.
Для JSONB GIN включает оператор @>; есть два opclass: полный (универсальный, крупный) и jsonb_path_ops (компактный, в основном @>).
fastupdate складывает новые записи в pending list и переносит их пачкой при вакууме - быстрые вставки ценой просмотра pending list при поиске.
GIN дорог на запись: одна строка со многими элементами даёт много записей индекса; он уместен там, где читают намного чаще, чем пишут.
Выбирай GIN, когда у строки много индексируемых элементов и поиск идёт по вхождению; для одного скалярного ключа с порядком - B-tree.

Контрольные вопросы

Почему B-tree ускоряет `LIKE 'abc%'`, но не `LIKE '%abc%'`?
Показать ответ
B-tree находит диапазон по началу значения. У LIKE 'abc%' начало известно (abc), поэтому с подходящим operator class индекс находит диапазон значений, начинающихся на abc. У LIKE '%abc%' подстрока может стоять где угодно внутри, начало неизвестно - диапазон по началу не построить, и приходится читать все строки (Seq Scan). Для поиска подстроки или по словам нужен GIN: по триграммам (pg_trgm) для LIKE или по tsvector для полнотекста.
Как устроен GIN внутри?
Показать ответ
Двумя уровнями. Сверху entry tree - B-tree по всем уникальным ключам (словам, элементам массива, фрагментам JSONB). Снизу к каждому ключу прикреплён posting list - отсортированный список ctid строк, где этот ключ встречается. Запрос по нескольким ключам сводится к пересечению/объединению их posting lists - быстрой операции над отсортированными списками. Если posting list большой, он сам становится деревом (posting tree), чтобы не разрастаться на одной странице.
Что такое fastupdate и какой у него компромисс?
Показать ответ
fastupdate - режим (по умолчанию включён), при котором новые записи GIN сначала складываются в неупорядоченный pending list, а в основную структуру переносятся пачкой - при вакууме или по достижении gin_pending_list_limit. Выгода - быстрые вставки, ведь одна строка со многими элементами не трогает много мест индекса сразу. Плата - поиск должен просматривать и основную структуру, и pending list, поэтому при разросшемся pending list поиск замедляется. Перенос делает VACUUM.
В чём разница между обычным GIN на JSONB и `jsonb_path_ops`?
Показать ответ
Обычный operator class индексирует ключи, пути и значения документа - поддерживает много операторов (@>, ?, ?|, ?&), но индекс крупный. jsonb_path_ops индексирует пути целиком (хеши путь+значение)
- индекс меньше и быстрее, но поддерживает в основном оператор содержания @>. Выбор - между универсальностью (обычный) и компактностью под один сценарий (jsonb_path_ops). Это пример того, что operator class меняет и набор операторов, и размер индекса.
На какой таблице GIN - плохая идея?
Показать ответ
На таблице с интенсивной записью, где по индексируемому полю часто идут INSERT/UPDATE. GIN дорог на запись: строка со многими элементами порождает много записей индекса, а pending list растёт между вакуумами. На горячей по записи таблице это заметно замедлит вставки и может незаметно деградировать поиск, если autovacuum не успевает переносить pending list. GIN уместен там, где читают намного чаще, чем пишут - каталоги, документы, логи для поиска.

35.1 Когда у строки много ключей

35.2 Инвертированный индекс и posting lists

entry tree:        рейс        задержка      багаж

                    │            │            │

posting lists:   [r1,r7,r9]   [r3,r7]      [r2,r7,r9]

35.3 Почему B-tree проваливается на LIKE '%x%'

sql

EXPLAIN SELECT * FROM docs WHERE body LIKE '%рейс%';   -- Seq Scan

sql

CREATE INDEX ON docs USING gin (to_tsvector('simple', body));

EXPLAIN SELECT * FROM docs

WHERE to_tsvector('simple', body) @@ to_tsquery('simple', 'рейс');

-- Bitmap Index Scan через GIN, быстро

Разница на больших объёмах - между долгими секундами Seq Scan и миллисекундами поиска по словам.

35.4 GIN на JSONB

sql

CREATE INDEX ON doc USING gin (body);

EXPLAIN SELECT * FROM doc WHERE body @> '{"tag":"sale"}';   -- через GIN

sql

CREATE INDEX ON doc USING gin (body jsonb_path_ops);

Выбор - между универсальностью и компактностью, и это снова вопрос operator class (см. operator-classes).

35.5 fastupdate и pending list

35.5.1 Подводный камень: GIN дорог на запись

Практические следствия:

GIN уместен там, где читают намного чаще, чем пишут (каталоги, логи для поиска, документы);
на горячей по записи таблице взвесь стоимость: возможно, полнотекст лучше держать в отдельной таблице или обновлять реже;
следи, чтобы autovacuum успевал переносить pending list, иначе поиск деградирует незаметно.

Это типичный размен индексов: GIN покупает быстрый поиск по вхождению ценой записи.

35.6 Что индексирует GIN

Сводка применений, чтобы не путать с соседними AM:

полнотекст - GIN по tsvector, оператор @@;
JSONB - GIN по документу, операторы @>, ?, и т.д.;
массивы - GIN по массиву, операторы @>, <@, && (содержит, содержится, пересекается);
LIKE/regex по подстроке - GIN по триграммам (расширение pg_trgm), оператор LIKE '%x%' через триграммы.

Уроки в sandbox

lab-35.1. btree проваливается на LIKE, GIN спасает полнотекст

Создай таблицу текстов: CREATE TABLE docs AS SELECT g id, 'рейс ' || g || ' статус ' || (CASE WHEN g%3=0 THEN 'задержка' ELSE 'вовремя' END) AS body FROM generate_series(1, 200000) g;.
Построй btree и попробуй подстроку: CREATE INDEX ON docs (body); EXPLAIN SELECT * FROM docs WHERE body LIKE '%задержка%'; - предскажи (Seq Scan: btree не умеет подстроку).
Построй GIN по tsvector: CREATE INDEX docs_fts ON docs USING gin (to_tsvector('simple', body)); ANALYZE docs;.
Полнотекстовый запрос: EXPLAIN SELECT * FROM docs WHERE to_tsvector('simple', body) @@ to_tsquery('simple','задержка'); - предскажи (Bitmap Index Scan через GIN).
Сравни время через EXPLAIN ANALYZE обоих вариантов и размеры индексов через \di+.

sandbox с автопроверкой - открыть в песочнице

Резюме

GIN - инвертированный индекс для данных, где у строки много элементов: массивы, JSONB, полнотекст. Он строит соответствие «элемент → список строк».
Структура двухуровневая: entry tree (B-tree уникальных ключей) и posting lists (отсортированные ctid); большой posting list становится posting tree.
B-tree бессилен против LIKE '%x%' (подстрока без известного начала) и полнотекста; GIN по tsvector с оператором @@ решает это быстро.
Для JSONB GIN включает оператор @>; есть два opclass: полный (универсальный, крупный) и jsonb_path_ops (компактный, в основном @>).
fastupdate складывает новые записи в pending list и переносит их пачкой при вакууме - быстрые вставки ценой просмотра pending list при поиске.
GIN дорог на запись: одна строка со многими элементами даёт много записей индекса; он уместен там, где читают намного чаще, чем пишут.
Выбирай GIN, когда у строки много индексируемых элементов и поиск идёт по вхождению; для одного скалярного ключа с порядком - B-tree.

Контрольные вопросы

Почему B-tree ускоряет `LIKE 'abc%'`, но не `LIKE '%abc%'`?
Показать ответ
B-tree находит диапазон по началу значения. У LIKE 'abc%' начало известно (abc), поэтому с подходящим operator class индекс находит диапазон значений, начинающихся на abc. У LIKE '%abc%' подстрока может стоять где угодно внутри, начало неизвестно - диапазон по началу не построить, и приходится читать все строки (Seq Scan). Для поиска подстроки или по словам нужен GIN: по триграммам (pg_trgm) для LIKE или по tsvector для полнотекста.
Как устроен GIN внутри?
Показать ответ
Двумя уровнями. Сверху entry tree - B-tree по всем уникальным ключам (словам, элементам массива, фрагментам JSONB). Снизу к каждому ключу прикреплён posting list - отсортированный список ctid строк, где этот ключ встречается. Запрос по нескольким ключам сводится к пересечению/объединению их posting lists - быстрой операции над отсортированными списками. Если posting list большой, он сам становится деревом (posting tree), чтобы не разрастаться на одной странице.
Что такое fastupdate и какой у него компромисс?
Показать ответ
fastupdate - режим (по умолчанию включён), при котором новые записи GIN сначала складываются в неупорядоченный pending list, а в основную структуру переносятся пачкой - при вакууме или по достижении gin_pending_list_limit. Выгода - быстрые вставки, ведь одна строка со многими элементами не трогает много мест индекса сразу. Плата - поиск должен просматривать и основную структуру, и pending list, поэтому при разросшемся pending list поиск замедляется. Перенос делает VACUUM.
В чём разница между обычным GIN на JSONB и `jsonb_path_ops`?
Показать ответ
Обычный operator class индексирует ключи, пути и значения документа - поддерживает много операторов (@>, ?, ?|, ?&), но индекс крупный. jsonb_path_ops индексирует пути целиком (хеши путь+значение)
- индекс меньше и быстрее, но поддерживает в основном оператор содержания @>. Выбор - между универсальностью (обычный) и компактностью под один сценарий (jsonb_path_ops). Это пример того, что operator class меняет и набор операторов, и размер индекса.
На какой таблице GIN - плохая идея?
Показать ответ
На таблице с интенсивной записью, где по индексируемому полю часто идут INSERT/UPDATE. GIN дорог на запись: строка со многими элементами порождает много записей индекса, а pending list растёт между вакуумами. На горячей по записи таблице это заметно замедлит вставки и может незаметно деградировать поиск, если autovacuum не успевает переносить pending list. GIN уместен там, где читают намного чаще, чем пишут - каталоги, документы, логи для поиска.