B-tree, GiST, GIN, BRIN, sargability

Что отвечать

B-tree - сбалансированное дерево из страниц. Корень и внутренние страницы хранят разделители: ключ плюс ссылку на дочернюю страницу. Листья хранят ключи в отсортированном порядке и ссылки на строки кучи (`ctid`). Поиск идёт от корня вниз: на каждом уровне по разделителям выбираем нужную ветку, за несколько шагов (высота дерева) приходим в лист. Высота растёт логарифмом от числа строк, поэтому даже на миллиардах записей это единицы обращений к страницам. Листья связаны ссылками влево-вправо, что даёт быстрый диапазонный обход и `ORDER BY` без отдельной сортировки.

Что хотят услышать

Senior должен: - описать уровни: корень, внутренние страницы с разделителями, листья с ключами и ctid - связать логарифмическую сложность с высотой дерева и числом обращений к страницам - объяснить, почему B-tree хорош для диапазонов и сортировки: листья отсортированы и связаны - упомянуть оптимизации: дедупликация одинаковых ключей и усечение суффикса разделителей экономят место

Подводные камни

• ✗ Думать, что листья B-tree хранят сами строки - они хранят ключ и `ctid`, а строка в куче
• ✗ Считать, что B-tree эффективен для `LIKE '%x'` или неравенства по выражению - порядок там не помогает
• ✗ Забывать, что высота мала: даже на больших таблицах это несколько уровней, а не десятки

Follow-up

• ? Почему B-tree даёт `ORDER BY` без отдельной сортировки?
• ? Что хранится в листе B-tree?
• ? Что такое дедупликация в B-tree и зачем она?

Что отвечать

Индекс по столбцу хранит значения самого столбца. Если в условии столбец завёрнут в функцию или выражение - `WHERE lower(email) = 'a@b.c'`, `WHERE created_at::date = '2024-01-01'`, `WHERE id + 0 = 5` - индекс по сырому столбцу не подходит: в нём нет значений `lower(email)`. То же с `LIKE '%abc'`: ведущий процент убивает возможность спуститься по дереву, потому что неизвестно начало строки. Условие, которое индекс может использовать напрямую, называют sargable. Лечится тремя способами: переписать предикат, чтобы столбец был «голым»; построить индекс по выражению (`CREATE INDEX ON t (lower(email))`); для шаблонов и подстрок взять trigram-индекс (`pg_trgm`).

Что хотят услышать

Senior должен: - объяснить корень: индекс хранит значения столбца, а функция над столбцом даёт другие значения - привести типовые анти-кейсы: функция/каст над колонкой, `LIKE '%...'`, арифметика над столбцом - дать три лечения: переписать предикат, индекс по выражению, trigram для подстрок - знать, что `text_pattern_ops` нужен для `LIKE 'abc%'` в локали, отличной от C

Подводные камни

• ✗ Оборачивать столбец функцией в `WHERE` и ждать, что обычный индекс сработает
• ✗ Строить обычный B-tree и удивляться, что `LIKE '%abc%'` его не берёт - тут нужен trigram
• ✗ Забывать про `text_pattern_ops` для префиксного `LIKE` в не-C локали

Follow-up

• ? Как заставить индекс работать для `WHERE lower(email) = ...`?
• ? Почему `LIKE 'abc%'` индексируется, а `LIKE '%abc'` нет?
• ? Зачем нужен `text_pattern_ops`?

Что отвечать

Составной индекс `(a, b, c)` - это отсортированный список по `a`, внутри равных `a` по `b`, и так далее. Поэтому он работает для условий на левый префикс: `a`, `a` и `b`, `a` и `b` и `c`. По одному только `b` или по паре `b, c` без `a` он бесполезен. Правило: первым ставят столбец, по которому всегда идёт равенство, последним - тот, по которому диапазон или сортировка. Столбец из `WHERE a = ? AND b > ?` хорошо ложится на индекс `(a, b)`, а `(b, a)` тут уже хуже. Порядок столбцов это не косметика, от него напрямую зависит, возьмёт ли планировщик индекс.

Что хотят услышать

Senior должен: - объяснить модель «отсортированный список» и правило левого префикса - дать практическое правило: равенство впереди, диапазон и сортировка в конце - показать на примере `WHERE a = ? AND b > ?`, почему `(a, b)` лучше `(b, a)` - понимать, что лишний широкий составной индекс это цена на запись и место, не только польза на чтение

Подводные камни

• ✗ Ставить диапазонный столбец перед столбцом равенства - индекс отработает только до диапазона
• ✗ Ждать, что `(a, b, c)` поможет запросу по одному `b` - левый префикс не выполнен
• ✗ Плодить составные индексы на все комбинации - каждый замедляет запись и ест место

Follow-up

• ? Почему индекс `(a, b)` не помогает условию только по `b`?
• ? Куда в составном индексе ставить столбец из `ORDER BY`?
• ? Чем платят за каждый лишний индекс на таблице?

Что отвечать

Обычный индексный скан находит в индексе `ctid` и идёт в кучу за самой строкой - проверить видимость и забрать остальные столбцы. Если индекс содержит все нужные запросу столбцы (покрывающий, в том числе через `INCLUDE`), хождение в кучу можно было бы пропустить. Но индекс не хранит информацию о видимости версий. Спасает карта видимости (VM): если страница в ней помечена «все версии видны всем», строку из кучи можно не читать. Поэтому index-only scan эффективен только на хорошо провакуумленных таблицах с актуальной VM. Под нагрузкой из UPDATE без своевременного vacuum index-only scan вырождается в обычный с массой `Heap Fetches`.

Что хотят услышать

Senior должен: - объяснить, что index-only scan избегает похода в кучу, если индекс покрывает запрос - связать его с картой видимости: пропуск кучи разрешён только для страниц, помеченных в VM - назвать `INCLUDE` как способ добавить столбцы в индекс без участия их в сортировке/уникальности - понимать роль vacuum: устаревшая VM убивает выгоду, растёт `Heap Fetches`

Подводные камни

• ✗ Ждать index-only scan на таблице, которую давно не вакуумили - VM устарела, идут Heap Fetches
• ✗ Думать, что покрывающего индекса достаточно - без актуальной VM поход в кучу всё равно случится
• ✗ Путать `INCLUDE`-столбцы с ключевыми - INCLUDE не участвуют в поиске и сортировке

Follow-up

• ? Почему index-only scan ходит в кучу, если таблицу не вакуумили?
• ? Что добавляет `INCLUDE` в индексе и чем отличается от ключевых столбцов?
• ? О чём говорит большое число `Heap Fetches` в плане?

Что отвечать

GIN (generalized inverted index) - инвертированный индекс: он хранит не «строка -> значение», а «элемент -> список строк, где он встречается». Это то, что нужно для составных значений: полнотекстовый поиск (слово -> документы), `jsonb` (ключ или путь -> строки), массивы (элемент -> строки). Запрос `WHERE tags @> '{postgres}'` или `WHERE doc @@ to_tsquery('...')` GIN обслуживает напрямую. Цена - дорогая вставка и обновление: один UPDATE документа задевает много элементов индекса. Сглаживает это отложенный список ожидающих записей (`fastupdate`), но он добавляет периодическую дочистку. GIN большой и медленный на запись, зато незаменим на поиске по содержимому.

Что хотят услышать

Senior должен: - объяснить инвертированную модель «элемент -> строки» и почему она подходит для jsonb, массивов, full-text - привести операторы, которые тянет GIN: `@>`, `@@`, `?` и подобные - назвать цену: тяжёлая вставка/обновление, большой размер, роль `fastupdate` - противопоставить B-tree: тот хранит цельное значение и для поиска внутри jsonb/массива не годится

Подводные камни

• ✗ Строить B-tree по `jsonb` и ждать поиск по ключам - для этого нужен GIN
• ✗ Ставить GIN на таблицу с очень частыми обновлениями индексируемого поля без оглядки на стоимость записи
• ✗ Забыть, что GIN с `fastupdate` периодически дочищает отложенный список, и это всплески нагрузки

Follow-up

• ? Какой оператор jsonb обслуживает GIN, а какой нет?
• ? Что делает `fastupdate` и чем он расплачивается?
• ? Почему GIN дороже B-tree на запись?

Что отвечать

BRIN (block range index) хранит не значения строк, а сводку по диапазонам блоков: для каждого участка таблицы запоминает минимум и максимум значения. Индекс получается крошечный - килобайты там, где B-tree занял бы гигабайты. Работает он только при хорошей корреляции: если значения физически растут вместе с порядком строк (типичный пример - столбец времени в таблице, куда пишут по возрастанию), то по диапазону можно сразу отбросить блоки, чьи min/max не подходят. На плохо коррелированных данных BRIN бесполезен: подходящие строки разбросаны по всем блокам, отбрасывать нечего. Это индекс для больших append-only таблиц с естественным порядком.

Что хотят услышать

Senior должен: - описать BRIN как сводку min/max по диапазонам блоков, а не по строкам - подчеркнуть зависимость от корреляции: выгода только когда порядок значений совпадает с физическим порядком - привести нишу: большие append-only таблицы, столбец времени или возрастающий идентификатор - сравнить размер: BRIN на порядки меньше B-tree, ценой грубости поиска

Подводные камни

• ✗ Ставить BRIN на плохо коррелированный столбец - он не сможет отбрасывать блоки и станет бесполезным
• ✗ Ждать от BRIN точечного поиска как у B-tree - он отбраковывает блоки грубо, потом всё равно сканирует кандидатов
• ✗ Не пересобирать BRIN после массовых вставок не по порядку - сводки min/max расплывутся

Follow-up

• ? Почему BRIN бесполезен на случайно распределённом столбце?
• ? Насколько BRIN меньше B-tree и за счёт чего?
• ? Какой тип таблиц - идеальный кандидат для BRIN?

Что отвечать

GiST (generalized search tree) - каркас для деревьев по «неточным» предикатам: геометрия и `PostGIS` (пересечение, близость), диапазонные типы, поиск ближайших соседей (`ORDER BY point <-> target`). SP-GiST - его родственник для несбалансированных структур: квадродеревья, префиксные деревья, данные с естественным разбиением пространства. GIN - инвертированный индекс для составных значений: full-text, jsonb, массивы. Грубое правило: ищешь по геометрии, диапазонам и ближайшим соседям - GiST; по содержимому документа, массива или jsonb - GIN; экзотическая пространственная структура с неравномерным разбиением - SP-GiST. У каждого свой набор классов операторов под конкретные типы.

Что хотят услышать

Senior должен: - закрепить ниши: GiST для геометрии/диапазонов/KNN, GIN для содержимого, SP-GiST для неравномерных пространственных структур - привести KNN-поиск (`<->`) как фирменную возможность GiST - понимать, что выбор определяется типом данных и доступными классами операторов - не противопоставлять их как «лучше/хуже»: они про разные классы задач

Подводные камни

• ✗ Считать, что GIN и GiST взаимозаменяемы - они решают разные задачи
• ✗ Брать GiST для полнотекстового поиска по умолчанию - чаще выгоднее GIN, GiST лишь для специфики
• ✗ Забывать, что под тип нужен подходящий класс операторов, иначе индекс не построится

Follow-up

• ? Какой индекс обслуживает поиск ближайших соседей `ORDER BY p <-> q`?
• ? Для полнотекстового поиска что обычно лучше - GIN или GiST?
• ? Где уместен SP-GiST?

Что отвечать

Индекс сам по себе не знает, как сравнивать значения конкретного типа - это знание даёт класс операторов (operator class). Он связывает тип данных и метод доступа с набором операторов и опорных функций: для B-tree это «меньше, меньше-равно, равно, больше» и функция сравнения. Поэтому у одного типа бывает несколько классов под разные задачи. Канонический пример - `text`: класс по умолчанию сортирует по локали и обслуживает `=` и `ORDER BY`, но не годится для префиксного `LIKE` в не-C локали; для него есть `text_pattern_ops`, который сравнивает побайтово и делает `LIKE 'abc%'` индексируемым. Указывают класс при создании индекса: `CREATE INDEX ON t (col text_pattern_ops)`.

Что хотят услышать

Senior должен: - определить класс операторов как связку «тип плюс метод доступа плюс набор операторов и опорных функций» - объяснить, зачем у типа несколько классов, на примере `text` и `text_pattern_ops` - связать это с предыдущим: правильный класс делает `LIKE 'abc%'` sargable в любой локали - знать, что классы видны в каталоге (`pg_opclass`) и выбираются явно при нестандартной задаче

Подводные камни

• ✗ Строить индекс по `text` в локали ru и ждать, что `LIKE 'abc%'` его возьмёт - нужен `text_pattern_ops`
• ✗ Думать, что у типа всегда один класс операторов - их бывает несколько под разные операторы
• ✗ Игнорировать класс операторов при создании индекса под специфический поиск

Follow-up

• ? Зачем нужен `text_pattern_ops` и когда он не нужен?
• ? Что входит в класс операторов для B-tree?
• ? Почему у одного типа бывает несколько классов операторов?

Что отвечать

Hash-индекс хранит хеш значения и обслуживает только равенство (`=`): ни диапазонов, ни сортировки, ни префиксного поиска. За это он компактнее B-tree на длинных ключах и на чистом `=` может быть чуть быстрее. До PostgreSQL 10 hash-индексы не писались в WAL и не переживали сбой - поэтому их избегали; начиная с 10 они полноценные и реплицируются. На практике их ниша узкая: B-tree тоже прекрасно делает равенство и заодно умеет диапазоны и сортировку, поэтому по умолчанию берут B-tree, а hash - только когда ключ длинный, нужно строго равенство и размер индекса важен.

Что хотят услышать

Senior должен: - назвать единственную операцию hash-индекса - равенство - и отсутствие диапазонов и сортировки - знать историю: до версии 10 без WAL и без надёжности, с 10 полноценный - объяснить, почему по умолчанию всё равно B-tree: он покрывает равенство и больше - очертить редкую нишу hash: длинный ключ, строгое равенство, экономия размера

Подводные камни

• ✗ Брать hash-индекс ради диапазонного запроса - он только для `=`
• ✗ Помнить старое правило «hash ненадёжен» - с версии 10 это не так
• ✗ Ставить hash по умолчанию вместо B-tree без веской причины по размеру ключа

Follow-up

• ? Что изменилось для hash-индексов в версии 10?
• ? Почему B-tree обычно предпочитают даже для чистого равенства?
• ? В каком случае hash-индекс реально выигрывает?