Индексы в разных БД: PostgreSQL, MongoDB, Tarantool

Идея индекса универсальна: структура, которая жертвует местом и скоростью записи ради скорости чтения. Но воплощение этой идеи в трёх разных БД — три разных набора типов, ограничений и идиом. То, что в PostgreSQL — expression-индекс по lower(status), в MongoDB — просто индекс по вложенному полю документа; multikey-индекс MongoDB по массиву не имеет прямого аналога в реляционной модели; а Tarantool разводит индексы по двум движкам — memtx (в памяти) и vinyl (LSM на диске) — и даже к одному и тому же полю применяет разные структуры (TREE, HASH, BITSET, RTREE) в зависимости от типа запроса. Перенос привычки одной БД в другую — частая причина, когда индекс «должен работать», но не работает: в этой статье — что общее у всех трёх, а что нет, на реальных explain-планах из живых стендов.

Это третья статья серии «Индексы в базах данных». Опирается на структуры и практику выбора индексов из статей #1 и #2 — там же разобран PostgreSQL подробно; здесь PostgreSQL — краткая сводка для сравнения, основной фокус на MongoDB и Tarantool.

В статье

• Что общее у всех трёх
• PostgreSQL: сводка
• MongoDB: индексы в документной модели
• Правило ESR на реальном плане
• Tarantool: memtx и vinyl
• Таблица сравнения: класс индекса × три БД
• Что дальше
• Источники

Что общее у всех трёх

Под разными названиями и API все три СУБД решают одну и ту же задачу одним и тем же семейством структур. Упорядоченное дерево (B-tree в PostgreSQL, TREE в Tarantool, дефолтный индекс MongoDB на WiredTiger) — рабочая лошадка для равенства, диапазона и сортировки. Хеш-структура для точного равенства без диапазонов существует и в PostgreSQL (USING hash), и в Tarantool (HASH) как отдельный явный тип; в MongoDB прямого аналога нет — есть только устаревший hashed-индекс для шардирования по ключу, не для ускорения обычных выборок. Составные индексы работают по одному и тому же принципу left-prefix во всех трёх: индекс (a, b, c) обслуживает поиск по a, по (a, b) и по (a, b, c), но не по одному b — физический порядок хранения ключей определяется первой колонкой, и без неё сузить диапазон поиска нечем. И везде индекс имеет смысл ровно тогда, когда предикат селективен: платить дополнительной структурой и её обновлением при записи стоит, только если чтение действительно отбирает малую долю данных — это уже разобрано на PostgreSQL в статье #2 и не специфично для одной БД.

Дальше — расхождения, и они начинаются там, где данные перестают быть плоской строкой с фиксированными типизированными колонками.

PostgreSQL: сводка

PostgreSQL 18.4 — самый богатый набор типов индексов из трёх БД, потому что реляционная модель со строгой типизацией колонок позволяет специализировать структуру под конкретный тип данных. Кратко, без повтора статей #1–2:

• btree — дефолт, диапазон+равенство+сортировка, O(log n);
• hash — только равенство, без диапазонов; на стенде индекс idx_status_hash по низкоселективной колонке status (5 значений на 2 млн строк) весит 94 МБ — больше, чем btree первичного ключа той же таблицы (events_pkey, 43 МБ), из-за оверхеда структуры и низкой селективности;
• GiN (инвертированный) — для JSONB, массивов, полнотекстового поиска: idx_payload_gin по payload @> '{"tag": "a"}' весит 11 МБ и даёт Bitmap Heap Scan, 171.7 мс на 334 319 подходящих строк;
• GiST/SP-GiST — обобщённые деревья для непорядковых предикатов (геометрия, диапазоны);
• BRIN — сводка по блокам, 24 КБ независимо от корреляции данных, но реально ускоряет только при физической кластеризации колонки;
• partial — индекс по подмножеству строк (idx_paid_partial ON events(user_id) WHERE status = 'paid', 5784 КБ, чистый Index Scan за 0.042 мс);
• expression — индекс по выражению, не по значению колонки (idx_status_lower ON events(lower(status))).

Полный разбор устройства каждой структуры — в статье #1, практика выбора, селективности и диагностики «индекс не используется» — в статье #2. Здесь важна одна деталь для сравнения ниже: во всех этих типах индекс строится по значению типизированной колонки или явного выражения над ней, заданного заранее при CREATE INDEX. В документной модели MongoDB эта граница между «колонкой» и «полем произвольной вложенности» устроена иначе.

MongoDB: индексы в документной модели

MongoDB 8.2.11 индексирует не колонки таблицы, а пути внутри документа — и ключевое отличие сразу же появляется там, где путь ведёт в массив. Стенд генерирует 200 000 документов детерминированно (сид фиксирован: счётчики nReturned/keysExamined/totalDocsExamined ниже воспроизводимы байт-в-байт при повторном прогоне, а время executionTimeMillis зависит от хоста и колеблется от прогона к прогону). Разница между отсутствием индекса и его наличием видна в executionStats буквально:

--- без индекса: find({userId: 555}) ---
stage: COLLSCAN
nReturned: 5
totalKeysExamined: 0
totalDocsExamined: 200000
executionTimeMillis: 59

--- после createIndex({userId: 1}), тот же запрос ---
stage: FETCH → IXSCAN (indexName: userId_1)
nReturned: 5
totalKeysExamined: 5
totalDocsExamined: 5
executionTimeMillis: 1
indexBounds: userId: ['[555, 555]']

totalDocsExamined падает с 200 000 до 5 — сокращение в 40 000 раз: без индекса COLLSCAN проверяет предикат на каждом документе коллекции, с индексом IXSCAN находит ровно подходящие ключи (все 5 документов с userId: 555) и FETCH поднимает только их. Структурно это тот же переход Seq Scan → Index Scan, что и в PostgreSQL из статьи #1, только термины другие.

Дальше начинаются MongoDB-специфичные типы. Multikey-индекс — то, чего нет в реляционной модели напрямую: если индексируемое поле — массив, MongoDB индексирует каждый элемент массива отдельно, а не массив целиком как одно значение. На стенде createIndex({tags: 1}) при запросе find({tags: 'a'}) даёт план с явным флагом isMultiKey: true (и multiKeyPaths: { tags: ['tags'] }):

stage: FETCH → IXSCAN (indexName: tags_1)
isMultiKey: true
nReturned: 49994
totalKeysExamined: 49994
totalDocsExamined: 49994
dupsTested: 49994

totalKeysExamined здесь равно числу совпадений, а не документов, — по одной проверке ключа на каждое вхождение 'a' в массиве tags любого документа. Это концептуально тот же механизм, что GIN-индекс PostgreSQL по JSONB из раздела выше: индексируется элемент, а не контейнер целиком, только в PostgreSQL это отдельный тип (GiN), а в MongoDB — свойство обычного B-tree-подобного индекса, автоматически становящегося multikey, как только под ним обнаруживается массив.

Partial-индекс MongoDB работает как аналог PostgreSQL, но с другим синтаксисом описания условия — не WHERE в определении, а partialFilterExpression в опциях createIndex. На стенде createIndex({userId: 1}, {name: 'userId_1_partial_paid', partialFilterExpression: {status: 'paid'}}) под запрос find({userId: 555, status: 'paid'}) даёт план с флагом isPartial: true — планировщик MongoDB выбрал именно частичный индекс, несмотря на то, что рядом существует обычный userId_1 без фильтра:

stage: FETCH → IXSCAN (indexName: userId_1_partial_paid)
isPartial: true
nReturned: 1
totalKeysExamined: 1
totalDocsExamined: 1
executionTimeMillis: 1

(На стенде имя индекса пришлось задать явно — сгенерированное по умолчанию имя конфликтовало с уже существующим userId_1, поскольку MongoDB строит имя из key pattern независимо от опций типа partialFilterExpression. Практическая мелочь, но она стоит упоминания: два разных индекса по одному и тому же полю с разными условиями требуют явных разных имён.)

TTL-индекс — вещь, которой в PostgreSQL нет вовсе как встроенного механизма индекса: createIndex({createdAt: 1}, {expireAfterSeconds: 34560000}) (400 дней) не просто ускоряет запросы по createdAt, а превращает коллекцию в самоочищающуюся — фоновый TTL-монитор (интервал около 60 секунд) физически удаляет документы старше указанного порога. На стенде индекс зарегистрирован и виден в getIndexes(); фактическое срабатывание монитора в короткий прогон не проверялось — это не требовало отдельного подтверждения, регистрация индекса с нужными опциями уже наблюдаема напрямую.

Кроме перечисленного, MongoDB поддерживает text-индекс (полнотекстовый поиск, аналог GIN+tsvector в PostgreSQL, но не более одного text-индекса на коллекцию — ограничение, которого нет у GIN), 2dsphere (пространственный индекс по GeoJSON — концептуальный аналог GiST/R-tree, пространственные индексы и их компромиссы разобраны отдельно в серии «Гео-поиск: паттерны и реализации»Скоро) и wildcard-индекс ({"$**": 1} — индексирует все поля документа без заранее известной схемы, полезен, когда набор полей непредсказуем; ближайший аналог в PostgreSQL — GiN по всему JSONB-документу, но wildcard даёт это на уровне произвольной схемы коллекции, а не одной jsonb-колонки).

Правило ESR на реальном плане

Составной индекс в MongoDB подчиняется тому же left-prefix, что и в PostgreSQL, но практическое правило порядка колонок формулируется как ESR — Equality, Sort, Range: сначала поля с точным равенством в запросе, затем поле сортировки, затем поле с диапазонным условием. Порядок не произвольный — он позволяет индексу одновременно сузить диапазон по равенствам и отдать результат уже в нужном порядке сортировки, не выполняя отдельный шаг SORT в памяти после выборки.

На стенде составной индекс {status: 1, createdAt: 1, amount: 1} построен ровно по ESR под запрос find({status: 'paid', amount: {$lt: 100}}).sort({createdAt: 1}) — равенство по status, сортировка по createdAt, диапазон по amount:

stage: FETCH → IXSCAN (indexName: status_1_createdAt_1_amount_1)
nReturned: 4010
totalKeysExamined: 39870
totalDocsExamined: 4010
executionTimeMillis: 68
indexBounds:
  status:    ["paid", "paid"]     (Equality)
  createdAt: [MinKey, MaxKey]     (Sort — обходится по порядку индекса)
  amount:    [-inf, 100)          (Range)

Ключевое в этом плане — то, чего в нём нет: стадии SORT. План — FETCH ← IXSCAN, без отдельного шага сортировки в памяти, хотя запрос требует sort({createdAt: 1}). Индекс уже хранит документы упорядоченными по createdAt внутри каждого значения status, поэтому MongoDB просто идёт по индексу в нужном порядке — ровно то, что даёт связный список листьев B-tree в PostgreSQL для ORDER BY без отдельной сортировки (статья #1). totalKeysExamined: 39870 при nReturned: 4010 показывает цену диапазонного условия по третьему полю ESR: индекс проверяет ключи по всему диапазону createdAt (Sort-поле обходится целиком, MinKey..MaxKey), а amount < 100 отфильтровывает уже внутри — отсюда keysExamined на порядок больше nReturned, но всё равно не 200 000 (то есть не полный скан).

Генератор данных стенда теперь детерминированный (фиксированный сид), поэтому числа nReturned/keysExamined выше воспроизводимы байт-в-байт при повторном прогоне — это не «типичный прогон», а конкретный, повторяемый результат. Воспроизводимый и не зависящий от конкретных чисел факт остаётся тем же — план FETCH ← IXSCAN без стадии SORT, и это то, что ESR-правило обещает и подтверждает.

Tarantool: memtx и vinyl

Tarantool 3.7.0 подходит к индексам иначе, чем PostgreSQL и MongoDB: индекс здесь — не дополнительная структура поверх таблицы, а часть определения самого спейса (space), и разных типов индекса можно назначить нескольким индексам одного спейса одновременно, каждый — под свой класс запросов. На стенде спейс events (50 000 строк, memtx-движок — данные полностью в памяти) несёт все четыре типа индекса memtx разом: primary (TREE), by_user (HASH, unique), by_flags (BITSET), by_geo (RTREE).

TREE — тот же принцип B-tree, что и btree PostgreSQL: упорядоченное дерево, годится для равенства, диапазона, сортировки. Диапазонный запрос primary:select({1}, {iterator = 'GE', limit = 3}) (id ≥ 1, лимит 3) вернул ровно 3 кортежа — упорядоченный доступ по индексу работает, как и ожидается от TREE.

HASH — как и hash-индекс PostgreSQL, только равенство, зато формально O(1). На стенде by_user:select{42} (равенство по user_id) вернул ровно один кортеж:

[42, 42, "shipped", 143, [52.55, -173.32]]

(id=42, user_id=42 — HASH-индекс by_user в этой схеме unique, что и объясняет ровно одно совпадение вместо нескольких).

BITSET — тип, которого нет как отдельной структуры ни в PostgreSQL (там bitmap — только стратегия сканирования планировщика поверх обычного индекса, см. статью #2), ни в MongoDB: в Tarantool это персистентный индекс специально под битовые флаги. Запрос by_flags:select(1, {iterator = 'BITS_ANY_SET'}) (любой из битов флага установлен) на стенде вернул 24 902 совпадения из 50 000 строк — около половины, что соответствует тестовым данным с примерно одним установленным младшим битом на две строки. Битовый поиск здесь — не эмуляция через AND/OR битовых карт на лету, а прямая поддержка на уровне индекса.

RTREE — пространственный индекс, тот же принцип вложенных ограничивающих прямоугольников (MBR), что и R-tree под капотом GiST в PostgreSQL или 2dsphere в MongoDB (концептуально; детали пространственных индексов, включая сравнение R-tree/geohash/S2/H3, — в серии «Гео-поиск: паттерны и реализации»Скоро). На стенде поле by_geo хранит координату как единое поле-массив {lat, lon}, а не два отдельных числовых поля — это требование Tarantool 3.x к RTREE-индексу: он ожидает ровно одно поле типа array, а не пару скалярных полей.

Отдельно от memtx на стенде создан спейс events_lsm с engine = 'vinyl' — LSM-движок Tarantool, данные на диске вместо памяти. Общая идея LSM (запись всегда последовательна в memtable, чтение может требовать слияния нескольких SSTable, фоновая компакция) уже разобрана в статье #1 этой серии; здесь же — только факт, что Tarantool даёт выбор движка per-space, то есть в одном кластере можно держать горячие данные в памяти (memtx) и холодные или объёмные — на диске (vinyl), без смены СУБД. Более глубокий разбор компромиссов vinyl против memtx на реальных нагрузках — в статье «Вычисления в оперативной памяти»готовится, с 23 сентября, где Tarantool сравнивается с Redis, Picodata, Aerospike и другими in-memory/LSM системами.

(Пять практических адаптаций схемы под Tarantool 3.x, обнаруженных при подготовке стенда: запуск через tt connect вместо устаревшего tarantool < script.lua; RTREE требует единое array-поле координаты; диапазон генератора user_id расширен, чтобы не ломать unique HASH-индекс дубликатами; вывод накапливается в таблицу и возвращается через return, а не печатается в stdout напрямую; os.exit(0) убран, чтобы не гасить уже работающий инстанс. Детали — специфика тестового стенда, не самих индексов, здесь не разбираются подробно.)

Таблица сравнения: класс индекса × три БД

Прочерк в ячейке не означает «невозможно» — значит, что задача решается на уровне приложения или другим механизмом той же БД, а не отдельным типом индекса.

Что дальше

Эта статья показала, как один и тот же набор задач — равенство, диапазон, сортировка, поиск по контейнеру, пространственный поиск, самоочистка — решается разными структурами и разным API в PostgreSQL, MongoDB и Tarantool, и где привычка одной БД не переносится в другую напрямую (multikey, ESR, BITSET, разделение memtx/vinyl). Дальше — куда чаще ведут реальные инциденты: over-indexing и write-amplification на реальных числах, неиспользуемые и дублирующие индексы, bloat — статья #4, «Паттерны и антипаттерны индексирования». И как ORM и язык приложения на Go и Java незаметно ломают использование индекса — N+1, неявные приведения типов, prepared statements — статья #5, «Индексы и языки/ORM»готовится, с 30 июля. Для хранилищ, где транзакционность вокруг индексов устроена совсем иначе (KV/документные под конкурентной записью) — статья «KV и документные: транзакций почти нет».

Источники

• MongoDB Manual — Indexes, Index Types, ESR (Equality, Sort, Range) Rule
• MongoDB Manual — TTL Indexes, Partial Indexes, Wildcard Indexes
• Tarantool Documentation — Indexes, Vinyl engine
• PostgreSQL Documentation — Chapter 11. Indexes
• Стенд: digital-cookbook/databases/db-indexes (PostgreSQL 18.4, MongoDB 8.2.11, Tarantool 3.7.0)