Partial и Expression индексы

Stripe в 2023 году обработал 1 трлн долларов транзакций. Их PostgreSQL хранит таблицу `charges` с миллиардами записей. Только 0.1% этих charges имеют status='disputed' - но именно по ним строится дашборд compliance отдела, который опрашивает БД 1000 раз в секунду. Если бы они построили полный B-Tree по (status, customer_id, amount) - это 200 GB и 8 часов на REINDEX. Они построили partial index `WHERE status='disputed'` - 200 MB и 30 секунд. Те же запросы в 5x быстрее, потому что индекс целиком влезает в shared_buffers. Эта простая идея 1989 года (Stonebraker и команда Berkeley) сэкономила Stripe 50 млн долларов на инфраструктуре. Партиал и expression индексы - не optimization tricks, а фундаментальный способ масштабировать БД, когда данные неравномерны.

• **Stripe charges**: partial UNIQUE index на active subscriptions + bloom index на metadata колонках для compliance dashboards. Экономия 50+ млн долларов на инфраструктуре
• **GitHub repositories**: expression index по `LOWER(name)` для case-insensitive search через 200M+ репозиториев. Без него autocomplete был бы O(n) seq scan
• **Notion blocks**: JSONB expression индексы для извлечения properties из document payload. GIN на `to_tsvector(content->>'text')` для полнотекстового поиска
• **Linear issues**: partial index на open issues + expression на (LOWER(title), labels) - даёт миллисекундный поиск по миллионам issues в активных проектах
• **OpenAI vector search через pgvector**: HNSW индекс с partial по embedding model version, чтобы не смешивать ada-002 и text-embedding-3-small в одной структуре

Partial Indexes: индекс только горячих строк

В таблице orders 100 миллионов записей, но только 50 000 имеют status='pending' - те, что ждут обработки. WHERE-запросы по pending почти всегда выглядят как `SELECT ... FROM orders WHERE status='pending' AND created_at > '...'`. Полный индекс по (status, created_at) уйдёт в 5 GB. Partial index - `CREATE INDEX ... ON orders (created_at) WHERE status='pending'` - даст 5 MB и тот же план выполнения. Идея проста: индексировать только те строки, что реально участвуют в запросах, остальные физически не появляются в индексе.

Условие WHERE в partial index - это запрос Boolean expression, который PostgreSQL вычисляет для каждой строки при вставке/обновлении. Подходящие условия - immutable: `status='pending'`, `deleted=false`, `priority > 100`. Неподходящие - то, что может измениться без UPDATE: `created_at > now() - interval '1 day'` (now() меняется!). Для time-based фильтров используют материализованные представления или partitioning вместо partial.

Partial unique - элегантная архитектурная штука. `CREATE UNIQUE INDEX users_email_unique ON users(email) WHERE deleted=false` - email уникален среди активных пользователей, но удалённые users могут иметь конфликтующие emails. Это позволяет soft-delete с возможностью повторной регистрации - без partial unique это требует кучу логики на уровне приложения. Похожий приём в ML: HNSW индексы в pgvector часто строятся partial на 'верифицированных' embeddings, чтобы исключить noisy data из retrieval.

Expression Indexes: индекс по функции

В таблице users поле email хранится в смешанном регистре: 'JOHN@example.com', 'john@example.com'. Запрос `WHERE email='john@example.com'` пропустит первую запись. Решение через приложение - всегда class к нижнему регистру при вставке. Решение через DB - **expression index**: `CREATE INDEX ... ON users (LOWER(email))`. Тогда запрос `WHERE LOWER(email) = 'john@example.com'` использует индекс. Это работает не только для LOWER - любая immutable функция: TO_TSVECTOR (полнотекстовый), JSONB операторы, концатенации, числовые выражения.

Главное ограничение - immutability функции. PostgreSQL должен гарантировать, что вычисление `LOWER(email)` даст один и тот же результат при вставке и при поиске. now(), random(), to_char с timezone - не immutable. Они отвергаются с ошибкой 'functions in index expression must be marked IMMUTABLE'. Лекарство - обернуть в свою функцию с явным IMMUTABLE: `CREATE FUNCTION my_lower(t text) RETURNS text AS $$ SELECT LOWER(t) $$ LANGUAGE SQL IMMUTABLE`. Но осторожно - если функция действительно непостоянна, индекс будет давать ложные совпадения.

Expression index стоят в 1.5-2 раза дороже обычного на вставку - каждая операция требует вызова функции. На горячую таблицу с миллионом INSERT в день это заметная нагрузка. Поэтому expression индексы оправданы только когда альтернатива - seq scan, не другой существующий индекс. Аналогия с ML: feature engineering в classical ML - точно те же compute trade-offs. Создание сложных features ускоряет inference, но замедляет training pipeline. Expression index - feature engineering на стороне PostgreSQL.

Bloom: индекс с вероятностной семантикой

Bloom filter - вероятностная структура из 1970-х: множество, в котором тест на принадлежность даёт либо 'точно нет', либо 'возможно да'. Никаких false negatives, лишь false positives с контролируемой вероятностью. PostgreSQL расширение pg_bloom превращает эту идею в индекс. Применение: таблица с десятком одинаково селективных колонок, и запросы фильтруют по разным комбинациям. Создавать B-Tree на каждую комбинацию - bag, держать один многоколоночный - не работает (порядок имеет значение). Bloom индексирует все колонки одинаково и быстро отвечает 'возможно подходит' с false positive rate ~1-5%.

Цена Bloom - heap recheck. Bitmap scan возвращает кандидаты, потом PostgreSQL читает heap чтобы исключить false positives. При high selectivity (мало row выживает после Bloom) это дёшево. При low selectivity (Bloom возвращает много кандидатов) recheck доминирует и Bloom проигрывает обычному seq scan. Хорошая интуиция: Bloom подходит когда комбинация условий точно targeted (5-50 row), и не подходит для возвращения миллиона строк. Это в точности тот же принцип, что в ANN-индексах для embeddings: HNSW даёт 'возможно похожих' кандидатов, потом точная distance check.

Параметры Bloom: `length` - размер bitmap на одну запись (в битах), больше = меньше false positives но больше места. `col1, col2...` - сколько хэш-функций применяется к каждой колонке. Дефолтные `length=80, col1..colN=2` дают ~5% false positive rate. Уменьшение length до 32 поднимает false positive до 15-20% - терпимо для exploratory analytics, плохо для точных запросов. Connection с Bloom filter в HNSW: pgvector использует тот же principle - approximate match с recheck стадией для точных distance computations.

Когда что использовать

Знание - применение. Partial index - когда есть очевидная горячая подмножина (status='pending', deleted=false, priority > 100) и она составляет менее 10% таблицы. Размер падает в 10-100x, скорость запросов сохраняется. Expression index - когда есть стабильное вычисление (LOWER для case-insensitive поиска, JSONB операторы, time bucket-ing). Заменяет seq scan + per-row compute на O(log n). Bloom - когда таблица с десятком одинаково-селективных колонок и запросы фильтруют разные комбинации; даёт компактность за счёт false positive rechecks. Multi-column B-Tree - когда комбинация колонок жёстко зафиксирована и порядок имеет значение.

Anti-patterns. (1) Partial index на UPDATE-able условие: `WHERE created_at > '2024-01-01'` - устаревает с каждым новым днём; индекс перестаёт работать для свежих данных. (2) Expression index по non-immutable: ошибка при создании. (3) Bloom на 2-колоночной таблице: overkill, multi-column B-Tree быстрее. (4) Partial + expression на UPDATE-heavy таблицу: тройная нагрузка на каждый INSERT/UPDATE; для OLTP-heavy лучше один targeted index. (5) Partial unique без правильного condition: можно проморгать конфликт между active и пустым state.

Современный pgvector использует то же мышление в новом домене. Базовый IVFFlat - это partial + clustering: только некоторое количество cluster centers индексируется детально. HNSW - graph index с многоуровневой структурой, в Postgres-расширении часто конфигурируется partial по quality threshold. Bayesian A/B testing в продакшне ML pipelines: индексировать только variants с confidence > 0.95, остальные - skip. Принципы partial и expression - язык для проектирования специализированных индексов любого домена, не только B-Tree.

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

Partial и expression индексы - это инструменты на основе B-Tree, для проектирования точных индексов под конкретные паттерны запросов:

• B-Tree — Базовая структура, на которую кладутся partial и expression условия
• Covering Index — Комбинируется с partial: `CREATE INDEX ... INCLUDE (...) WHERE ...`
• GIN/GIST — Поддерживают expression-based индексы для JSONB, tsvector, geographic types
• EXPLAIN ANALYZE — Проверяет, что планировщик использует partial/expression индекс как ожидалось

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

• **Partial index** индексирует только подмножество таблицы через WHERE clause. Размер в 10-100x меньше полного, скорость запроса та же. Условие должно быть immutable
• **Expression index** индексирует результат функции от колонки (LOWER, JSONB операторы, time bucket). Заменяет seq scan + per-row compute на O(log n). Функция должна быть IMMUTABLE
• **Bloom index** - вероятностное множество для таблиц с 5-15 равно-селективными колонками. Один компактный индекс покрывает все комбинации запросов с 1-5% false positive rate
• **Комбинации** (partial + covering, partial + expression) дают максимум скорости при минимуме места. Stripe, GitHub, Notion - все используют точечные индексы в production
• **Anti-patterns**: индекс на UPDATE-able условие, expression на non-immutable function, избыточные индексы на INSERT-heavy таблицы. Каждый index - tax на write

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

• На таблице с 1M пользователей нужна uniqueness по email только среди активных (deleted=false). Как реализовать? Какие edge cases возникают с soft-undelete?
• Expression index по `LOWER(email)` в 1.5x медленнее обычного B-Tree на вставку. Когда эта плата оправдана, а когда лучше нормализовать email в нижний регистр на уровне приложения?
• Bloom-индекс даёт 5% false positives. На каких типах запросов 5% - терпимая ошибка, а на каких катастрофа?

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

• pg-12-btree — B-Tree - база, на которую кладутся partial и expression индексы
• pg-13-covering — Covering + partial комбинируется для максимальной точности
• pg-15-gin-gist — GIN/GIST индексы поддерживают expression-based выражения для JSONB и полнотекстового поиска
• pg-18-explain — EXPLAIN ANALYZE проверяет, что планировщик действительно использует partial index
• aie-10-vector-databases — ANN индексы (HNSW в pgvector) - тот же подход: точечное индексирование horizon's подмножества данных
• it-04 — Bloom-индекс - вариант Bloom filter с lossy compression false positives
• db-09-indexes-btree