Теория языков программирования
Компиляция DSL
DuckDB написан за 5 лет студентами и превосходит Oracle на аналитических запросах. Секрет - vectorized query execution и compiled query plans вместо 40-летнего Volcano model. Shader compiler в вашем GPU превращает GLSL в специализированный ISA за миллисекунды. Это DSL compilation в действии.
- **DuckDB query compilation**: TPC-H Q1 на 10GB данных - PostgreSQL 8 сек, DuckDB 0.08 сек. Разница не в индексах - в архитектуре компилятора запросов
- **Mesa/RADV Vulkan driver**: open-source Rust GPU driver для AMD. Shader compiler ACO заменил LLVM backend и дал 15-30% FPS в играх - лучшее register allocation под AMD GCN ISA
- **Google Spanner F1**: SQL поверх Spanner использует distributed query compilation. Запрос компилируется в план который выполняется на сотнях машин параллельно
Query Compilation
Query compilation - трансляция SQL/datalog запроса в нативный код. Классические базы данных интерпретируют query plan дерево оператор за оператором (Volcano model). Компилируемые системы генерируют C/LLVM IR - каждый запрос становится отдельной функцией. HyPer database: 10-100x ускорение по сравнению с интерпретацией.
DuckDB использует векторизованное выполнение вместо полной компиляции. ClickHouse - компилирует expressions через LLVM. TPC-H Q1 benchmark: PostgreSQL ~8 сек, DuckDB ~0.1 сек на одних данных. Разница - архитектура выполнения, не индексы.
Почему compiled query plan быстрее Volcano model даже при одинаковом количестве операций?
JIT для DSL
JIT компиляция DSL - генерация нативного кода в runtime на основе конкретных данных и параметров. LuaJIT делает это для Lua. V8 для JavaScript. Регулярные выражения в современных движках - тоже JIT: regex компилируется в machine code при первом использовании.
Почему JIT компиляция regex оправдана только при повторном использовании?
SQL Query Optimizer
SQL optimizer - самый сложный компилятор в практическом применении. Задача: найти оптимальный план выполнения из экспоненциального числа возможных. Две стратегии: rule-based (набор правил трансформации) и cost-based (statistics + cardinality estimation + план с минимальной стоимостью).
Cardinality estimation - главная слабость оптимизаторов. Если статистика устарела или JOIN условия коррелированы, оценка ошибается в 100-1000x. PostgreSQL 14+ ввёл extended statistics для коррелированных столбцов. ClickHouse и DuckDB используют HyperLogLog sketches для точной кардинальности в runtime.
Что такое predicate pushdown и почему это одна из самых важных оптимизаций?
Shader Compilers
Shader compiler - специализированный DSL-компилятор для GPU. GLSL/HLSL/WGSL - высокоуровневые языки для GPU, компилируются в SPIR-V (portable binary) или напрямую в GPU-специфичный ISA. Особенности: SIMT модель (Single Instruction Multiple Threads), отсутствие рекурсии, ограниченная память, векторные операции как примитивы.
DSL компиляторы - это просто трансляция текста в другой текст
SQL optimizer решает NP-hard задачу (оптимальный порядок JOIN). Shader compiler управляет register allocation на GPU с совершенно другой архитектурой. Это одни из сложнейших компиляторов в индустрии
PostgreSQL optimizer: 30+ лет развития, миллионы строк кода. Mesa (open-source GPU driver) содержит компиляторы для 10+ GPU архитектур. DuckDB query compiler: написан за 5 лет командой из 10 человек и обходит Oracle по производительности на аналитических запросах
Почему рекурсия запрещена в shader языках?
Итоги
- **Query compilation**: Volcano model = vtable dispatch на каждой строке. Compiled = нативный код, SIMD, branch-free. 10-100x разница
- **JIT для DSL**: compilation overhead окупается при повторном использовании. Regex, rules engines, expression evaluators - стандартные кандидаты
- **SQL optimizer**: predicate pushdown + join reordering + cardinality estimation. Cost-based > rule-based для сложных запросов
- **Shader compilers**: WGSL/GLSL -> SPIR-V -> GPU ISA. Нет рекурсии (нет стека), register allocation критичен для occupancy
Связанные темы
DSL компиляция применяет классические техники компиляторов:
- IR и оптимизации — SQL plan трансформации аналогичны compiler IR оптимизациям - те же принципы DCE, constant folding
- JIT компиляция — JIT для DSL использует те же техники что V8/LuaJIT - профилирование + специализация
Вопросы для размышления
- DuckDB использует vectorized execution (батчи по 1024 значений), а HyPer - full compilation в LLVM IR. Оба быстрее Volcano. Какой подход лучше и когда?
- SQL optimizer решает задачу оптимизации за polynomial время (dynamic programming), хотя задача NP-hard. Какие упрощения позволяют это сделать, и когда они ломаются?
- Shader compiler должен работать в runtime при загрузке игры. LLVM compilation занимает секунды для сложных шейдеров. Как modern GPU drivers решают эту проблему?