В модуле 6 мы вскользь упоминали: executor Postgres работает по volcano model — pull-based дерево итераторов. С этого модуля мы разворачиваем эту тему всерьёз. Почему Postgres быстрый на OLTP, но медленный на аналитике с миллиардом строк? Почему DuckDB и ClickHouse «на тех же данных» легко выигрывают в 10-100 раз? Ответ начинается с того, как именно plan tree превращается в строки.

Что такое volcano

Модель предложил Goetz Graefe в 1994 (статья “Volcano: an Extensible and Parallel Query Evaluation System”). Идея проста: каждый узел плана — это объект с тремя методами:

• open() — инициализация (открыть файл, построить hash table, отсортировать).
• next() — вернуть следующую строку или сигнал «строк больше нет».
• close() — освободить ресурсы.

Дерево узлов выполняется сверху вниз pull’ом: корень спрашивает следующую строку, тот делегирует дочерним, и так до листа (Seq Scan / Index Scan), который читает страницу с диска.

Каждый узел дерева хранит реальное состояние выполнения: указатель на текущую позицию (heap_scan_descriptor для Seq Scan), внутренние буферы для Hash, состояние Sort’а. Это stateful интерфейс — между вызовами next() узел помнит, где остановился, и вычитывает «следующую» строку.

В Postgres это ExecProcNode(node): универсальная точка входа в любой узел плана. Она вызывает функцию-исполнитель типа ExecSeqScan, ExecHashJoin, ExecAgg через таблицу указателей. Postgres называет это tuple-at-a-time.

Конкретная реализация в исходниках: каждый узел плана содержит указатель ExecProcNodeMtd ExecProcNode (это callback), который выставляется в ExecInitNode() при инициализации плана. Дальше ExecProcNodeFirst оптимистично инлайнится в простую обёртку, которая дергает (*node->ExecProcNode)(node). Это и есть тот самый indirect call, оплачиваемый на каждую строку.

В рамках одного запроса полный набор открытых узлов сидит в памяти: PlanState-дерево с состоянием каждого узла, ExprState’ы для всех выражений (WHERE, SELECT-target list), tuple slots под каждый join. На запрос со 5 узлами это уже десятки KiB структур, которые путешествуют между cache levels по мере исполнения.

История модели

Volcano-статья Graefe была не первой работой про итераторы — но именно она формализовала «один интерфейс на любой узел» с открытой расширяемостью. В 1990-х это было революцией: до неё каждый коммерческий движок имел монолитный executor с прямыми переплетёнными вызовами между типами узлов. Volcano дал миру плагинную модель: добавил новый scan-метод (например, columnar fetch) — просто реализуй next(), и planner может его выбрать.

Postgres перенял Volcano с самого начала (середина 1990-х). MySQL, Oracle, SQL Server — тоже Volcano или его варианты. До 2010-х никакая другая модель массово не существовала.

Поворот случился около 2005-2010: статьи MonetDB/X100 и работа над HyPer показали, что на современном hardware (multi-core, SIMD, гигантская разница RAM vs cache) volcano недоиспользует CPU в 30-50 раз. С этого момента началась эпоха vectorized engines.

Плюсы volcano

Почему модель прожила 30 лет?

• Модульность. Любой узел можно реализовать независимо: HashJoin не знает, что у него под собой — Seq Scan, Sort или SubqueryScan. Все они отдают строки через одинаковый интерфейс.
• Любая глубина дерева работает одинаково. Подзапрос, view, CTE, lateral — всё это просто новое поддерево с тем же next().
• Pipeline-friendly. Строка выходит из листа и сразу проходит вверх до корня, без материализации промежутков. Память ограничена work_mem только в blocking-узлах (Sort, Hash, HashAgg).
• Малая задержка. Первая строка вылетает почти мгновенно. Это критично для OLTP: SELECT * FROM orders WHERE id = 42 отдаёт ответ за десяток микросекунд.

Это объясняет, почему Postgres такой ровный на широком классе запросов и почему его не переписали к 2026 году. Volcano выигрывает там, где запросы трогают единицы и десятки строк.

Минусы: где volcano жжёт CPU

Все красивые свойства упираются в одну стену: на каждую строку — функциональный накладной расход.

1. Function call overhead

В упрощённой модели каждый next() — один indirect call через function pointer. На x86 это ~5-10 циклов CPU плюс возможный

Соотношение overhead:useful work на простых аналитических запросах часто 60:1. То есть Postgres платит 98% времени за чисто организационное движение строк через дерево.

2. CPU cache miss

Когда Seq Scan отдаёт строку, executor пишет её в TupleTableSlot. Дальше Filter читает оттуда колонку c, сравнивает с 0. Потом то же делает Aggregate с колонкой a, потом со b. Между ними — переключения контекста узлов плана: указатели прыгают по разным структурам в памяти.

L1-кэш CPU — это 32-64 KiB. План из 5 узлов + tuple slot + buffer page (8 KiB) уже не помещается. Каждый прыжок между узлами — потенциальный

3. Колоночный код, который читает строку

Самая болезненная вещь: даже если запрос трогает 1 колонку из 50, Postgres всё равно поднимает всю строку. Heap tuple декодируется целиком (читай: alignment, null bitmap, varlena), а потом из неё достают attr[3]. На широких таблицах это значит чтение десятков KB только чтобы получить один int.

4. Branch misprediction в expression evaluator

Когда volcano выполняет выражение (price * 0.13)::numeric + tax_rate, оно идёт через ExecInterpExpr — interpret-loop поверх dispatch table’а из ~250 операторов (EEOP_INT4_TIMES, EEOP_ADD_NUMERIC и т.д.). Это switch с большим числом case’ов, компилятор не может предсказать ветку — на каждой строке прыгаем по indirect jump. Branch predictor сходит с ума при сложных выражениях.

JIT (см. ниже) частично лечит это, генерируя linear-flow LLVM-IR для конкретного типа выражения. Но и сам JIT не меняет того, что выражение всё равно вычисляется на каждой строке отдельно.

Смотрим volcano своими глазами

Лучше всего разница чувствуется на крупных аналитических запросах. Используем medium-датасет (100K orders) и EXPLAIN ANALYZE:

В выводе обрати внимание на:

• Seq Scan on orders ... rows=100000 ... actual time=X..Y. Поделив Y - X на rows, получаем ns на строку — обычно 100-500 ns. Из них львиная доля — это ExecProcNode + tuple deform.
• HashAggregate ... rows=6. Этот узел блокирующий: он сначала прокачивает все 100K строк, а потом отдаёт результат. Видно через actual rows и actual time для start vs total.

Сравним с запросом, где работа на строку ещё меньше:

И ещё один: попробуем заставить Postgres сделать filter, чтобы увидеть, сколько стоит Filter per row:

Обычно Filter-узел добавляет 30-80 ns на строку. На 100K — это 3-8 мс, на 100M строк (real OLAP) — 3-8 секунд только на одну условную операцию. На vectorized-движке тот же фильтр работает в 50-100 раз быстрее.

Push vs pull: альтернатива не для всех

Чтобы понять volcano лучше, посмотрим на альтернативу — push-based execution. Здесь данные не «тянутся» сверху, а «толкаются» снизу: листья сами решают, когда отдать строку, и шлют её вверх. Так работает HyPer, Snowflake.

Преимущества push:

• Естественный pipeline без stateful итераторов. Лист просто пишет «вот тебе строка, обработай», и забывает.
• Лучше параллельность: morsel-driven execution, work-stealing — всё это легче в push.
• Лучше с code generation: можно сгенерить единственную функцию, которая прокачивает все стадии «по дороге».

Недостатки:

• Сложнее реализовать LIMIT и early exit — лист должен знать, когда корню достаточно. Это backpressure-протокол.
• Сложнее обработка ошибок и cancellation.

Postgres остаётся pull-based по историческим причинам: переписать на push — это переписать executor, что никто не возьмётся без острой необходимости.

Tuple slot и tuple deform — где уходит четверть CPU

Между узлами в Postgres строки движутся не как байтовые блобы, а через TupleTableSlot — структуру, которая лениво распаковывает heap tuple в массивы values[] и isnull[]. Это и есть то, что показывает в perf top под именем slot_getsomeattrs.

Когда Filter обращается к колонке total_cents через slot_getattr(slot, 3), slot декодирует первые 3 колонки tuple’а: читает null bitmap, разбирается с varlena в первой и второй колонке, считает aligned offset для третьей. Сделано лениво (getsomeattrs), но всё равно на каждой строке. На широких таблицах (50+ колонок) deform — основной источник overhead’а: в perf’е он легко набирает 30-40% времени.

В vectorized engine этой проблемы нет вовсе: значения уже лежат как массивы по колонкам, никакой распаковки. SIMD-инструкции работают с raw memory.

Pipeline-breaker узлы

Не все узлы volcano честно pipeline’ят. Есть blocking (или pipeline-breaker) узлы, которые обязаны проглотить всё подмножество перед тем, как отдать первую строку наверх:

• Sort — должен прочитать все строки, чтобы упорядочить.
• Hash (правая часть Hash Join) — строит hash table из всех строк.
• HashAggregate / GroupAggregate — обновляет аккумуляторы по всем строкам.
• Materialize — буферизует выход.

В EXPLAIN это видно как разница между actual time=A..B: A — startup time (когда вылетела первая строка), B — total time. Для blocking-узлов A ≈ B (всё работает в самом начале). Для pipeline-узлов A маленькое, B — большое (строки текут).

Vectorized engine тоже имеет blocking-узлы, но их стоимость на batch level амортизирована: hash table заполняется батчами по 1024 значения с SIMD-хэшированием.

JIT: попытка спасения

В PG 11 добавили

JIT помогает на сложных арифметических выражениях и на широких tuple deform. Но он не меняет архитектуру volcano — всё ещё row-by-row. JIT сокращает constant factor, но не меняет порядок: на 100M строк всё равно 100M итераций. По разным замерам, JIT даёт 1.5-3x speedup на узких аналитических запросах. Vectorized engine — 10-100x. Это разница между «оптимизация» и «другая архитектура».

JIT в Postgres имеет и проблему «холодного старта»: первый запуск тратит 100-500 мс на LLVM-компиляцию. Если запрос быстрый сам по себе (десятки мс), JIT может оказаться медленнее без него. Параметр jit_above_cost = 100000 ограничивает JIT только дорогими запросами. На production-серверах JIT включают на аналитическом replica, а на OLTP-master часто оставляют выключенным.

Parallel query — параллельный volcano

В PG 9.6 (2016) добавили parallel query: planner может назначить parallel workers, и каждый — это отдельный процесс, выполняющий свою часть Seq Scan и отдающий промежуточные результаты в Gather узел. Это не отменяет volcano: каждый worker выполняет ту же tuple-at-a-time модель в своём процессе, просто параллельно.

Parallel scan даёт линейный speedup до 4-8 workers (упирается в shared buffer manager contention). На 8 ядрах CPU параллельный Seq Scan быстрее последовательного в 3-5 раз. Но это всё ещё в десятки раз медленнее, чем single-threaded vectorized scan на тех же данных, потому что архитектурно мы по-прежнему row-by-row. Parallel — это «volcano × N», не «volcano → vectorized».

Дополнительные параметры, влияющие на параллелизм: max_parallel_workers_per_gather (по умолчанию 2), min_parallel_table_scan_size (минимальный размер таблицы для рассмотрения parallel scan), и parallel_setup_cost (фиксированный overhead запуска workers — около 1000 abstract units). На маленьких таблицах parallel не запустится из-за этого overhead’а.

Почему Postgres не переписали на vectorized

Возникает естественный вопрос: если vectorized engines обогнали volcano на 30-50x в OLAP — почему core PG до сих пор tuple-at-a-time? Ответ — компромисс архитектуры:

• MVCC visibility check на каждой строке. Volcano проверяет xmin/xmax/cid в момент next(). Batched execution требует batched visibility — нетривиально для row-store + индексов с heap-pointers.
• Триггеры, RLS, generated columns — всё это row-level конструкции. Перевод в batched ломает обратную совместимость или требует двойного code-path.
• Heap layout — row store. Даже если executor станет batched, IO остаётся row-by-row, пока хранилище row-based. То есть выигрыш ограничен 3-5x (без column store).
• Огромная codebase. Postgres — ~1.5M строк C, executor — критичный модуль. Переписать без регрессий — годы работы. Сообщество предпочитает инкрементальные улучшения (JIT, partition pruning, parallel) и расширения (Citus columnar, Hydra), а не архитектурную перестройку.

Это нормально: Postgres держит совершенно разные задачи — от микро-OLTP до средних аналитических. Vectorized engine — точечный инструмент под конкретный класс.

Чем платит volcano, когда строк миллиарды

Подведём итог архитектурных компромиссов.

Volcano выигрывает:

• На OLTP-запросах, трогающих единицы и десятки строк.
• На запросах с быстрым early exit (LIMIT, EXISTS).
• На запросах с диким разнообразием планов — модульность приносит дивиденды через гибкость, а не скорость.

Volcano проигрывает:

• На full scan миллиардных таблиц с простыми aggregation.
• На запросах, где CPU — bottleneck (всё в памяти, диск не мешает).
• На сценариях, где можно было бы воспользоваться SIMD/wide registers — то есть на колонко-ориентированных операциях.

В следующем уроке — что делает vectorized execution, чтобы превратить эти минусы в плюсы.

Где смотреть в исходниках Postgres

Если ты хочешь нырнуть в код глубже, отправные точки в исходниках PG:

• src/backend/executor/execMain.c — главный цикл executor’а.
• src/backend/executor/execProcnode.c — диспетчер ExecProcNode и инициализация узлов.
• src/backend/executor/nodeSeqscan.c, nodeHashjoin.c, nodeAgg.c — реализации конкретных узлов.
• src/include/executor/tuptable.h — определение TupleTableSlot и slot operations.
• src/backend/executor/execExpr.c, execExprInterp.c — expression evaluator и JIT path.

Чтение этого кода — медленное, но возвращает абсолютную ясность того, как именно volcano работает в Postgres. Особенно вместе с perf-профилем тяжёлого аналитического запроса: ты буквально видишь, где CPU тратит время, и сопоставляешь с конкретными строками кода.

Чек-лист

• Volcano model — pull-based дерево итераторов; каждый узел реализует open/next/close.
• В Postgres это ExecProcNode, вызываемый через function pointer на каждый next.
• Плюсы: модульность, малая задержка, естественный pipeline, ограниченная память.
• Минусы: function call overhead, CPU cache miss, читает строку даже для одной колонки.
• На простых OLAP-запросах полезная работа = 2-5% CPU; остальное — overhead tuple-at-a-time.
• JIT уменьшает constant factor, но не меняет архитектуру row-by-row.
• Volcano выигрывает на OLTP, проигрывает на full scan миллиардов строк.