Своя СУБД на Effect · урок 6: анализ, план, исполнитель, EXPLAIN
Кому это. К этому уроку у тебя собрана вся нижняя половина движка и фронтенд. В уроке 3 выросла куча с seq scan как Stream, в уроке 4 к ней добавился B+Tree, в уроке 5 появился фронтенд: строка SQL режется на токены и собирается в дерево, а ошибка разбора ложится в Result. Но дерево пока висит в воздухе. Оно знает имя name, но не знает, есть ли такая колонка в users.
Зачем именно Effect. Сегодня замыкаем путь запроса: дерево пройдёт три фазы и превратится в строки. Binder сверит имена с каталогом, планировщик выберет seq scan или index scan, исполнитель прогонит план. И тут Effect показывает себя на верхней половине: операторы Volcano это Stream (ленивый, тянет страницы сам), чистые binder и вычислитель бросают EngineError, а граница engineTry ловит бросок в канал ошибок Effect, и, главное, каталог собирает ресурсы каждой таблицы в Scope базы через Layer.build, поэтому файлы куч и индексов закрываются сами, без единого db.close().
Важно про код. Урок большой: это вся верхняя половина движка разом. Но ни одна фаза не возится с байтами. Binder, планировщик и вычислитель это чистые функции над деревьями. Где эталон на голом TS берёт библиотеку ts-pattern для исчерпывающего разбора, мы обходимся обычным switch: компилятор и так проверяет полноту по размеченным объединениям. Пиши по файлам, прогоняй тесты, и поиграй с виджетом планировщика.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + TCP-сервер │ урок 11
├────────────────────────────────────────────────┤
│ Исполнитель (Volcano) + EXPLAIN │ урок 6 ← мы здесь
│ Планировщик (метод доступа, диапазоны) │ урок 6 ← мы здесь
│ Binder (семантический анализ, типы) │ урок 6 ← мы здесь
│ Каталог таблиц (в памяти) │ урок 6 ← мы здесь
│ Парсер SQL (рекурсивный спуск + Pratt) │ урок 5
│ Лексер (строка в токены) │ урок 5
├────────────────────────────────────────────────┤
│ Vacuum │ урок 10
│ MVCC (видимость, снимки) │ уроки 8, 9
│ Блокировки (2PL), менеджер транзакций │ уроки 8, 9
│ WAL (журнал, redo, recovery) │ урок 7
├────────────────────────────────────────────────┤
│ B+Tree индекс │ урок 4
│ Куча (slotted pages, seq scan) │ урок 3
├────────────────────────────────────────────────┤
│ Буферный пул (кэш страниц, вытеснение) │ урок 2
│ DiskManager (страницы поверх файла) │ урок 1
└────────────────────────────────────────────────┘Сегодня закрываем четыре слоя. Заметь, чего тут пока нет: транзакций, WAL, блокировок, MVCC. Движок урока 6 однопользовательский и без долговечности: одна команда за раз, каждая вставка сразу на диске через буферный пул. Поля xmin/xmax в кортеже из урока 3 мы заполняем фиксированным значением ENGINE_XID и игнорируем. Это сознательное упрощение: сначала пусть движок научится отвечать на запросы, а транзакции, журнал и параллелизм навесим в уроках 7, 8 и 9 поверх готового исполнителя.
Конвейер запроса
строка SQL
│ parseCommand (урок 5 + EXPLAIN), возвращает Result
▼
AST (Command)
│ bindStatement (binder): имена ▶ индексы, проверка типов
▼
LogicalPlan (что делаем)
│ планировщик: выбор метода доступа
▼
Stream строк или Effect-счётчик (как делаем)
│ Stream.runCollect / runDml (исполнитель)
▼
результатТри фазы и две формы плана. Логический план говорит, что делаем. Физический план в Effect-порте это Stream операторов. Под всем этим лежит каталог: он знает таблицы, их колонки и файлы. С него и начнём, но сперва заведём ошибки движка.
Размеченные ошибки движка
Binder и вычислитель это чистые функции, и они могут не сложиться: нет такой таблицы, не тот тип, деление на ноль. Как и в уроке 5, чистое ядро бросает ошибку для управления потоком, а граница ловит её в Effect. Заведи src/engine/errors.ts.
// src/engine/errors.ts
import { Data, Effect } from 'effect';
/** Ошибка анализа, планирования или вычисления выражения. */
export class EngineError extends Data.TaggedError('EngineError')<{
readonly message: string;
}> {}
/** Нарушение уникальности (PRIMARY KEY): INSERT или UPDATE дублирует ключ. */
export class UniquenessError extends Data.TaggedError('UniquenessError')<{
readonly message: string;
}> {}
/**
* Запустить чистый код (binder, eval), поймав брошенный EngineError в Effect.fail.
* Любой другой бросок это дефект (баг), пробрасываем дальше как настоящее исключение.
*/
export const engineTry = <A>(thunk: () => A): Effect.Effect<A, EngineError> =>
Effect.try({
try: thunk,
catch: (error) => {
if (error instanceof EngineError) {
return error;
}
throw error;
},
});engineTry это родной брат sqlResult из урока 5, только мостит в Effect, а не в Result: парсер был чистым целиком, а движок ходит на диск, поэтому его канал ошибок это Effect. EngineError несёт человеческое сообщение, UniquenessError отдельный тег (он понадобится тестам уникальности). Оба это Data.TaggedError, как все ошибки слоёв. UniquenessError мы будем создавать через Effect.fail прямо в операторах (это runtime-сбой, не бросок из чистого ядра), поэтому engineTry ловит только EngineError.
Связанное представление
Опишем выход binder-а: типы связанного плана. Это зеркало AST из урока 5, но колонки уже резолвлены в индексы, и каждое выражение несёт тип. Чистые типы, поэтому файл совпадает с TS-треком. Положи в src/engine/bound.ts.
// src/engine/bound.ts
import type { ColumnType } from '~/schema.ts';
import type { BinaryOp } from '~/sql/ast.ts';
import type { Value } from '~/tuple.ts';
/** Тип выражения. 'null' это литерал NULL, совместимый с любой колонкой. */
export type BoundType = ColumnType | 'null';
export interface BoundColumn {
readonly kind: 'column';
readonly index: number;
readonly type: ColumnType;
}
export interface BoundLiteral {
readonly kind: 'literal';
readonly value: Value;
readonly type: BoundType;
}
export interface BoundBinary {
readonly kind: 'binary';
readonly op: BinaryOp;
readonly left: BoundExpr;
readonly right: BoundExpr;
readonly type: BoundType;
}
export interface BoundUnary {
readonly kind: 'unary';
readonly op: 'NOT';
readonly operand: BoundExpr;
readonly type: 'bool';
}
export type BoundExpr = BoundColumn | BoundLiteral | BoundBinary | BoundUnary;
/** Одна выходная колонка проекции: вычисляемое выражение и имя в результате. */
export interface BoundOutput {
readonly expr: BoundExpr;
readonly name: string;
}
/** Одно присваивание UPDATE: индекс колонки и новое значение. */
export interface BoundAssignment {
readonly index: number;
readonly value: BoundExpr;
}
export type LogicalPlan =
| { readonly kind: 'scan'; readonly table: string; readonly filter?: BoundExpr }
| {
readonly kind: 'project';
readonly source: Extract<LogicalPlan, { kind: 'scan' }>;
readonly outputs: readonly BoundOutput[];
}
| { readonly kind: 'insert'; readonly table: string; readonly values: readonly Value[] }
| { readonly kind: 'delete'; readonly table: string; readonly filter?: BoundExpr }
| {
readonly kind: 'update';
readonly table: string;
readonly assignments: readonly BoundAssignment[];
readonly filter?: BoundExpr;
};LogicalPlan это что делаем: scan таблицы с необязательным фильтром, project над ним, и три DML. Решение seq scan против index scan тут ещё нет, это работа планировщика.
Binder
Binder превращает AST в LogicalPlan: резолвит таблицу и имена колонок в индексы по каталогу, проверяет типы, разворачивает *, проверяет арность и NOT NULL у INSERT. JOIN, ORDER BY и LIMIT парсятся, но binder отвергает их как упражнения. Чистый код, бросает EngineError (движок ловит через engineTry). Положи в src/engine/binder.ts. Сначала вход и диспетчеры.
// src/engine/binder.ts
import type {
BoundAssignment,
BoundExpr,
BoundOutput,
BoundType,
LogicalPlan,
} from '~/engine/bound.ts';
import { EngineError } from '~/engine/errors.ts';
import type { Schema } from '~/schema.ts';
import type { BinaryOp, ColumnExpr, Expr, Literal, SelectItem, Statement } from '~/sql/ast.ts';
import { printExpr } from '~/sql/printer.ts';
import type { Value } from '~/tuple.ts';
/** Метаданные таблицы для binder-а: схема плюс индексы обязательных колонок. */
export interface TableMeta {
readonly schema: Schema;
/** Индексы колонок NOT NULL и PRIMARY KEY (в Schema ограничений нет). */
readonly required: ReadonlySet<number>;
}
/** Доступ binder-а к каталогу: разрешение таблицы в её метаданные. */
export interface BindCatalog {
getTable(table: string): TableMeta | undefined;
}
export function bindStatement(statement: Statement, catalog: BindCatalog): LogicalPlan {
switch (statement.kind) {
case 'select': {
return bindSelect(statement, catalog);
}
case 'insert': {
return bindInsert(statement, catalog);
}
case 'update': {
return bindUpdate(statement, catalog);
}
case 'delete': {
return bindDelete(statement, catalog);
}
case 'createTable': {
throw new EngineError({ message: 'CREATE TABLE handled before binding' });
}
}
}
/** Связать выражение по схеме: резолв колонок в индексы, проверка типов. */
export function bindExpr(expr: Expr, schema: Schema, table: string): BoundExpr {
switch (expr.kind) {
case 'literal': {
return bindLiteral(expr.literal);
}
case 'column': {
return bindColumn(expr, schema, table);
}
case 'unary': {
const operand = bindExpr(expr.operand, schema, table);
requireType(operand, 'bool', 'NOT');
return { kind: 'unary', op: 'NOT', operand, type: 'bool' };
}
case 'binary': {
return bindBinary(
expr.op,
bindExpr(expr.left, schema, table),
bindExpr(expr.right, schema, table),
);
}
}
}bindStatement это switch по виду оператора, исчерпывающий по Statement. bindExpr рекурсивно связывает выражение. Дальше разбор отдельных операторов.
// src/engine/binder.ts (продолжение)
function bindSelect(
statement: Extract<Statement, { kind: 'select' }>,
catalog: BindCatalog,
): LogicalPlan {
if (statement.join) {
throw new EngineError({ message: 'JOIN это упражнение урока 6' });
}
if (statement.orderBy) {
throw new EngineError({ message: 'ORDER BY это упражнение урока 6' });
}
if (statement.limit !== undefined) {
throw new EngineError({ message: 'LIMIT это упражнение урока 6' });
}
const schema = requireTable(catalog, statement.from).schema;
const filter = bindFilter(statement.where, schema, statement.from);
const outputs = isStar(statement.items)
? allColumns(schema)
: statement.items.map((item) => bindOutput(item, schema, statement.from));
const source =
filter === undefined
? ({ kind: 'scan', table: statement.from } as const)
: ({ kind: 'scan', table: statement.from, filter } as const);
return { kind: 'project', source, outputs };
}
function bindInsert(
statement: Extract<Statement, { kind: 'insert' }>,
catalog: BindCatalog,
): LogicalPlan {
const meta = requireTable(catalog, statement.table);
const schema = meta.schema;
const targetIndices = statement.columns
? statement.columns.map((name) => resolveColumn(name, schema))
: schema.columns.map((_column, index) => index);
if (statement.values.length !== targetIndices.length) {
throw new EngineError({
message: `INSERT ожидает ${targetIndices.length} значений, получил ${statement.values.length}`,
});
}
const values: Value[] = Array.from({ length: schema.size }, () => null);
const provided = new Set<number>();
for (const [position, columnIndex] of targetIndices.entries()) {
const column = schema.columns[columnIndex]!;
const literal = statement.values[position]!;
checkAssignable(column.name, column.type, meta.required.has(columnIndex), literalType(literal));
values[columnIndex] = literalValue(literal);
provided.add(columnIndex);
}
for (const [index, column] of schema.columns.entries()) {
if (!provided.has(index) && meta.required.has(index)) {
throw new EngineError({ message: `колонка "${column.name}" не может быть NULL` });
}
}
return { kind: 'insert', table: statement.table, values };
}
function bindUpdate(
statement: Extract<Statement, { kind: 'update' }>,
catalog: BindCatalog,
): LogicalPlan {
const meta = requireTable(catalog, statement.table);
const schema = meta.schema;
const assignments: BoundAssignment[] = statement.assignments.map((assignment) => {
const index = resolveColumn(assignment.column, schema);
const column = schema.columns[index]!;
const value = bindExpr(assignment.value, schema, statement.table);
checkAssignable(column.name, column.type, meta.required.has(index), value.type);
return { index, value };
});
const filter = bindFilter(statement.where, schema, statement.table);
return filter === undefined
? { kind: 'update', table: statement.table, assignments }
: { kind: 'update', table: statement.table, assignments, filter };
}
function bindDelete(
statement: Extract<Statement, { kind: 'delete' }>,
catalog: BindCatalog,
): LogicalPlan {
const schema = requireTable(catalog, statement.table).schema;
const filter = bindFilter(statement.where, schema, statement.table);
return filter === undefined
? { kind: 'delete', table: statement.table }
: { kind: 'delete', table: statement.table, filter };
}Каждый bind* сверяет таблицу с каталогом (requireTable), резолвит колонки и проверяет типы. bindSelect отвергает JOIN/ORDER BY/LIMIT: парсер их принимает (урок 5), но исполнять их движок научится в упражнениях. bindInsert проверяет арность, типы и что обязательные колонки (PK, NOT NULL) не остались NULL. Остались проверки типов и резолв имён, тоже чистые.
// src/engine/binder.ts (продолжение)
function bindFilter(where: Expr | undefined, schema: Schema, table: string): BoundExpr | undefined {
if (where === undefined) {
return undefined;
}
const filter = bindExpr(where, schema, table);
if (filter.type !== 'bool' && filter.type !== 'null') {
throw new EngineError({
message: `условие WHERE должно быть булевым, получено ${filter.type}`,
});
}
return filter;
}
function bindBinary(op: BinaryOp, left: BoundExpr, right: BoundExpr): BoundExpr {
if (op === 'AND' || op === 'OR') {
requireType(left, 'bool', op);
requireType(right, 'bool', op);
return { kind: 'binary', op, left, right, type: 'bool' };
}
if (op === 'LIKE') {
requireType(left, 'text', op);
requireType(right, 'text', op);
return { kind: 'binary', op, left, right, type: 'bool' };
}
if (op === '=' || op === '<>' || op === '<' || op === '<=' || op === '>' || op === '>=') {
requireComparable(op, left, right);
return { kind: 'binary', op, left, right, type: 'bool' };
}
requireType(left, 'int', op);
requireType(right, 'int', op);
return { kind: 'binary', op, left, right, type: 'int' };
}
function bindColumn(column: ColumnExpr, schema: Schema, table: string): BoundExpr {
if (column.table !== undefined && column.table !== table) {
throw new EngineError({
message: `неизвестная таблица "${column.table}" в ссылке "${column.table}.${column.name}"`,
});
}
const index = resolveColumn(column.name, schema);
return { kind: 'column', index, type: schema.columns[index]!.type };
}
function bindLiteral(literal: Literal): BoundExpr {
return { kind: 'literal', value: literalValue(literal), type: literalType(literal) };
}
function bindOutput(item: SelectItem, schema: Schema, table: string): BoundOutput {
if (item.kind === 'star') {
throw new EngineError({ message: 'звёздочка не сочетается с другими колонками' });
}
const expr = bindExpr(item.expr, schema, table);
const name = item.alias ?? (item.expr.kind === 'column' ? item.expr.name : printExpr(item.expr));
return { expr, name };
}
function allColumns(schema: Schema): BoundOutput[] {
return schema.columns.map((column, index) => ({
expr: { kind: 'column', index, type: column.type },
name: column.name,
}));
}
function isStar(items: readonly SelectItem[]): boolean {
return items.length === 1 && items[0]?.kind === 'star';
}
function requireTable(catalog: BindCatalog, table: string): TableMeta {
const meta = catalog.getTable(table);
if (meta === undefined) {
throw new EngineError({ message: `неизвестная таблица "${table}"` });
}
return meta;
}
function resolveColumn(name: string, schema: Schema): number {
const index = schema.columns.findIndex((column) => column.name === name);
if (index === -1) {
throw new EngineError({ message: `неизвестная колонка "${name}"` });
}
return index;
}
function requireType(expr: BoundExpr, type: BoundType, context: string): void {
if (expr.type !== type && expr.type !== 'null') {
throw new EngineError({ message: `${context} требует ${type}, получено ${expr.type}` });
}
}
function requireComparable(op: BinaryOp, left: BoundExpr, right: BoundExpr): void {
if (left.type === 'null' || right.type === 'null') {
return;
}
if (left.type !== right.type) {
throw new EngineError({
message: `${op} требует операнды одного типа, получено ${left.type} и ${right.type}`,
});
}
}
function checkAssignable(
columnName: string,
columnType: BoundType,
required: boolean,
valueType: BoundType,
): void {
if (valueType === 'null') {
if (required) {
throw new EngineError({ message: `колонка "${columnName}" не может быть NULL` });
}
return;
}
if (valueType !== columnType) {
throw new EngineError({
message: `колонка "${columnName}" ожидает ${columnType}, получено ${valueType}`,
});
}
}
function literalValue(literal: Literal): Value {
switch (literal.kind) {
case 'number': {
return literal.value;
}
case 'string': {
return literal.value;
}
case 'bool': {
return literal.value;
}
case 'null': {
return null;
}
}
}
function literalType(literal: Literal): BoundType {
switch (literal.kind) {
case 'number': {
return 'int';
}
case 'string': {
return 'text';
}
case 'bool': {
return 'bool';
}
case 'null': {
return 'null';
}
}
}Тут вся семантика: типы сравнений (операнды одного типа), арифметика только над int, AND/OR/NOT булевы, LIKE текстовый, NULL совместим с любым типом. requireTable и resolveColumn это те самые сообщения, которые увидит пользователь при опечатке в имени. Binder бросает EngineError, а ловит его движок снаружи через engineTry.
Вычислитель выражений
Связанное выражение надо уметь вычислить против кортежа. Семантика NULL это трёхзначная логика. Чистый код, бросает EngineError на делении на ноль. Положи в src/engine/eval.ts.
// src/engine/eval.ts
import type { BoundExpr } from '~/engine/bound.ts';
import { EngineError } from '~/engine/errors.ts';
import type { BinaryOp } from '~/sql/ast.ts';
import type { Tuple, Value } from '~/tuple.ts';
type ComparisonOp = '=' | '<>' | '<' | '<=' | '>' | '>=';
type ArithmeticOp = '+' | '-' | '*' | '/';
export function evalExpr(expr: BoundExpr, tuple: Tuple): Value {
switch (expr.kind) {
case 'column': {
return tuple.values[expr.index] ?? null;
}
case 'literal': {
return expr.value;
}
case 'unary': {
const operand = evalExpr(expr.operand, tuple);
if (operand === null) {
return null;
}
return !(operand as boolean);
}
case 'binary': {
return evalBinary(expr.op, evalExpr(expr.left, tuple), evalExpr(expr.right, tuple));
}
}
}
/** Проходит ли строка фильтр: только строго TRUE (NULL и FALSE отсекаются). */
export function passesFilter(value: Value): boolean {
return value === true;
}
function evalBinary(op: BinaryOp, left: Value, right: Value): Value {
if (op === 'AND') {
return logicalAnd(left, right);
}
if (op === 'OR') {
return logicalOr(left, right);
}
// остальные операторы пропагируют NULL: любой NULL-операнд сразу даёт NULL
if (left === null || right === null) {
return null;
}
if (op === 'LIKE') {
return likeMatch(left as string, right as string);
}
if (op === '+' || op === '-' || op === '*' || op === '/') {
return arithmetic(op, left as bigint, right as bigint);
}
return compareOp(op, left, right);
}
function logicalAnd(left: Value, right: Value): Value {
if (left === false || right === false) {
return false;
}
if (left === null || right === null) {
return null;
}
return true;
}
function logicalOr(left: Value, right: Value): Value {
if (left === true || right === true) {
return true;
}
if (left === null || right === null) {
return null;
}
return false;
}
function compareOp(op: ComparisonOp, left: Value, right: Value): boolean {
const ordering = compareValues(left, right);
switch (op) {
case '=': {
return ordering === 0;
}
case '<>': {
return ordering !== 0;
}
case '<': {
return ordering < 0;
}
case '<=': {
return ordering <= 0;
}
case '>': {
return ordering > 0;
}
case '>=': {
return ordering >= 0;
}
}
}
/** Сравнить два ненулевых значения одного типа: -1, 0 или 1. */
function compareValues(left: Value, right: Value): number {
if (typeof left === 'bigint' && typeof right === 'bigint') {
return left < right ? -1 : left > right ? 1 : 0;
}
if (typeof left === 'string' && typeof right === 'string') {
return left < right ? -1 : left > right ? 1 : 0;
}
if (typeof left === 'boolean' && typeof right === 'boolean') {
return Number(left) - Number(right);
}
throw new EngineError({ message: 'cannot compare values of different types' });
}
function arithmetic(op: ArithmeticOp, left: bigint, right: bigint): bigint {
switch (op) {
case '+': {
return left + right;
}
case '-': {
return left - right;
}
case '*': {
return left * right;
}
case '/': {
if (right === 0n) {
throw new EngineError({ message: 'division by zero' });
}
return left / right;
}
}
}
function likeMatch(text: string, pattern: string): boolean {
let source = '^';
for (const character of pattern) {
if (character === '%') {
source += '.*';
} else if (character === '_') {
source += '.';
} else {
source += escapeRegex(character);
}
}
source += '$';
return new RegExp(source, 's').test(text);
}
function escapeRegex(character: string): string {
return /[$()*+.?[\\\]^{|}]/.test(character) ? `\\${character}` : character;
}evalExpr рекурсивно считает выражение. passesFilter это сердце WHERE: строка проходит, только если предикат строго true, поэтому NULL (неизвестно) и false отсекаются одинаково. logicalAnd/logicalOr кодируют таблицы Клини: NULL AND FALSE это FALSE (исход ясен и без NULL), а NULL AND TRUE это NULL. LIKE транслируется в регулярку (% это .*, _ это .). Деление целочисленное с усечением к нулю, деление на ноль бросает EngineError.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.