Своя СУБД на Rust · урок 6: анализ, план, исполнитель, EXPLAIN
Кому это. К этому уроку у тебя собрана вся нижняя половина движка и фронтенд. В уроке 3 выросла куча с seq scan как итератором HeapScan, в уроке 4 к ней добавился B+Tree с range_scan, в уроке 5 появился фронтенд: строка SQL режется на токены и собирается в дерево из enum-ов, а ошибка разбора приходит как Error::Sql в Result. Но дерево пока висит в воздухе. Оно знает имя name, но не знает, есть ли такая колонка в users.
Зачем именно Rust. Сегодня замыкаем путь запроса: дерево пройдёт три фазы и превратится в строки. Binder сверит имена с каталогом, планировщик выберет seq scan или index scan, исполнитель прогонит план. На верхней половине Rust показывает себя с трёх сторон. Связанное дерево и план это enum-ы, и match проверяет полноту за тебя. Операторы Volcano это трейт-объекты Box<dyn Operator + 'a>, которые не копируют план, а заимствуют его, и компилятор следит, чтобы план жил дольше дерева операторов. А close из классической модели исчезает совсем: его работу делает Drop. И ещё одна деталь, которую в JS было не выразить дёшево: арифметика над i64 через checked_add и его братьев, так что переполнение это ошибка движка, а не тихий перенос через край.
Важно про код. Урок большой: это вся верхняя половина движка разом. Но ни одна фаза не возится с байтами. Binder, планировщик и вычислитель это чистые функции над деревьями. Грязь только в каталоге (он заводит файлы куч и индексов) и в DML-операторах (они зовут heap.insert_tuple и btree.insert из прошлых уроков). Крейт тот же ourdb, только std, edition 2021, rust-version = "1.84". Сегодня в нём появляется модуль engine из шести файлов: catalog.rs, binder.rs, eval.rs, operators.rs, planner.rs, executor.rs и mod.rs с Database.
Одна оговорка про листинги. Эталонный крейт examples/our-db/rust это движок целиком, с журналом, транзакциями, блокировками и vacuum. В его операторах уже есть поля vis: Visibility (снимок MVCC) и write: WriteCtx (локи и журнал), а Database ведёт транзакции. Здесь показана версия урока 6: без этих полей, с физическим удалением из урока 3. Каждое место, где эталон богаче, я отмечаю прямо в тексте, и ты увидишь, куда в уроках 7, 8 и 9 вставятся новые детали. Сигнатуры и имена функций совпадают с эталоном.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + 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 и игнорируем, как и в TS- и Effect-треке. Сначала пусть движок научится отвечать на запросы, а транзакции, журнал и параллелизм навесим в уроках 7, 8 и 9 поверх готового исполнителя.
Конвейер запроса
строка SQL
│ parse_command (урок 5 + EXPLAIN), Result<Command>
▼
AST (Command)
│ bind_select / bind_insert / ... : имена ▶ индексы, проверка типов
▼
LogicalPlan (что делаем)
│ plan_select / plan_dml: выбор метода доступа
▼
Box<dyn Operator + 'a> (как делаем)
│ while let Some(row) = operator.next()? (исполнитель)
▼
ExecResultТри фазы и две формы плана. Логический план говорит, что делаем. Физический план это дерево операторов, корень которого исполнитель дёргает за next(), пока тот не скажет None. Под всем этим лежит каталог: он знает таблицы, их колонки и файлы.
Если ты шёл по TS-треку, конвейер тот же. Разница в том, как фазы общаются с ошибками и временем жизни данных, и с ошибок мы начнём.
Ошибки движка: тот же Result
В TS-треке binder и вычислитель бросали EngineError. В Effect-треке они тоже бросали, а граница engineTry ловила бросок в канал ошибок. В Rust никакой границы нет: ошибка это просто значение Err, которое ? поднимает на уровень выше. Ни один слой не может её «уронить» мимо сигнатуры, потому что Result в сигнатуре и есть канал ошибок. Если ты помнишь урок про обработку ошибок, здесь ровно та же механика, только на масштабе целого движка.
Варианты ошибок у нас уже есть: ourdb::Error завели в уроке 1 и с тех пор расширяли. Движку нужны два:
// src/error.rs (фрагмент)
#[derive(Debug)]
pub enum Error {
/// Ошибка ввода-вывода (диск, сокет).
Io(io::Error),
/// Ошибка разбора SQL: сообщение уже с позицией и стрелкой, offset в символах.
Sql { message: String, offset: usize },
/// Ошибка анализа, планирования или исполнения.
Engine(String),
/// Нарушение уникальности PRIMARY KEY.
Uniqueness(String),
// ... Serialization, LockWait, Deadlock появятся в уроках 8 и 9
/// Нарушен формат байтов или контракт API (RangeError/TypeError эталона).
Invalid(String),
}
pub type Result<T> = std::result::Result<T, Error>;
pub(crate) fn engine(message: impl Into<String>) -> Error {
Error::Engine(message.into())
}Error::Engine несёт человеческое сообщение: «неизвестная таблица», «не тот тип», «деление на ноль». Error::Uniqueness отдельный вариант, потому что тестам и, позже, сетевому протоколу важно отличить нарушение PRIMARY KEY от прочих ошибок (в уроке 11 они получат разные SQLSTATE-коды через Error::sqlstate()). Помощник engine принимает impl Into<String>, поэтому годится и &'static str, и String из format!: engine("division by zero") и engine(format!("неизвестная колонка \"{name}\"")) читаются одинаково.
Заметь ещё одно отличие от Effect. Там ошибки нижних слоёв (IoError, BufferPoolError) и ошибки движка жили в объединении типов, и подпись оператора перечисляла их все. Здесь один enum на весь крейт, и From<io::Error> for Error из урока 1 заворачивает ошибку диска в Error::Io прямо на ?. Подпись короче, цена в том, что тип не говорит, какие варианты реально возможны в данной функции. Для учебного движка это честный размен.
Связанное представление
Опишем выход binder-а: типы связанного плана. Это зеркало AST из урока 5, но колонки уже резолвлены в индексы, и каждое выражение несёт тип. Положи в src/engine/binder.rs, в начало файла.
// src/engine/binder.rs
use std::fmt;
use crate::engine::catalog::{Catalog, TableHandle};
use crate::error::{engine, Result};
use crate::sql::{print_expr, BinaryOp, Delete, Expr, Insert, Literal, Select, SelectItem, Update};
use crate::tuple::{ColumnType, Schema, Value};
/// Тип выражения. Null это литерал NULL, совместимый с любой колонкой.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum BoundType {
Column(ColumnType),
Null,
}
impl fmt::Display for BoundType {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
BoundType::Column(ty) => f.write_str(ty.name()),
BoundType::Null => f.write_str("null"),
}
}
}
const INT: BoundType = BoundType::Column(ColumnType::Int);
const TEXT: BoundType = BoundType::Column(ColumnType::Text);
const BOOL: BoundType = BoundType::Column(ColumnType::Bool);
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum BoundExpr {
Column {
index: usize,
ty: ColumnType,
},
Literal {
value: Value,
ty: BoundType,
},
Binary {
op: BinaryOp,
left: Box<BoundExpr>,
right: Box<BoundExpr>,
ty: BoundType,
},
Not(Box<BoundExpr>),
}
impl BoundExpr {
pub fn ty(&self) -> BoundType {
match self {
BoundExpr::Column { ty, .. } => BoundType::Column(*ty),
BoundExpr::Literal { ty, .. } | BoundExpr::Binary { ty, .. } => *ty,
BoundExpr::Not(_) => BOOL,
}
}
pub fn literal(value: Value, ty: BoundType) -> BoundExpr {
BoundExpr::Literal { value, ty }
}
}Разберём, что тут от Rust.
BoundType это не строковый литерал 'int' | 'null', как в TS, а enum с вложенным ColumnType из урока 3. Он Copy: два байта, которые дешевле копировать, чем заимствовать. Display нужен ради сообщений об ошибках: format!("{context} требует {ty}, получено {actual}") печатает int или null без ручного match в каждом месте.
Три константы INT, TEXT, BOOL это просто сокращения. Так как BoundType реализует PartialEq, их можно сравнивать через == (ty != BOOL), а match по ним не нужен.
BoundExpr это рекурсивный тип, и рекурсия идёт через Box<BoundExpr>. Без Box размер BoundExpr был бы бесконечным: вариант Binary содержал бы два BoundExpr, каждый из которых может быть Binary. Box кладёт ребёнка в кучу и оставляет в узле указатель фиксированного размера. Тот же приём ты видел в AST урока 5, и это прямое продолжение урока про умные указатели.
#[derive(Clone, Debug, PartialEq, Eq)] на всём связанном представлении это подарок тестам: assert_eq! сравнивает целые деревья, и при расхождении Debug печатает оба. В TS для такого сравнения нужен был toEqual с глубоким обходом, здесь его пишет компилятор.
Дальше выход проекции, присваивание и сам логический план.
/// Выходная колонка проекции: выражение и имя в результате.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BoundOutput {
pub expr: BoundExpr,
pub name: String,
}
/// Присваивание UPDATE: индекс колонки и новое значение.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BoundAssignment {
pub index: usize,
pub value: BoundExpr,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct LogicalScan {
pub table: String,
pub filter: Option<BoundExpr>,
}
/// Намерение запроса после анализа; планировщик переводит его в операторы Volcano.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum LogicalPlan {
Project {
source: LogicalScan,
outputs: Vec<BoundOutput>,
},
Insert {
table: String,
values: Vec<Value>,
},
Delete(LogicalScan),
Update {
scan: LogicalScan,
assignments: Vec<BoundAssignment>,
},
}LogicalScan вынесен в отдельную структуру, и это решение аккуратнее TS-версии. Там project ссылался на Extract<LogicalPlan, { kind: 'scan' }>, то есть на вариант того же объединения. Здесь скан это самостоятельный тип, который входит в три варианта плана (Project, Delete, Update), и планировщик строит скан одной функцией build_scan(&LogicalScan, ...), не разбирая план заново. А Insert скана не имеет вовсе: в нём уже готовые значения, собранные binder-ом.
Binder
Binder превращает AST в LogicalPlan: резолвит таблицу и имена колонок в индексы по каталогу, проверяет типы, разворачивает *, проверяет арность и NOT NULL у INSERT. JOIN, ORDER BY и LIMIT парсятся, но binder отвергает их как упражнения. Каталог мы напишем ниже, пока binder-у от него нужен один метод get(name) -> Option<&TableHandle>, а от TableHandle поля schema и required.
SELECT
pub fn bind_select(statement: &Select, catalog: &Catalog) -> Result<LogicalPlan> {
if statement.join.is_some() {
return Err(engine("JOIN это упражнение урока 6"));
}
if statement.order_by.is_some() {
return Err(engine("ORDER BY это упражнение урока 6"));
}
if statement.limit.is_some() {
return Err(engine("LIMIT это упражнение урока 6"));
}
let schema = &require_table(catalog, &statement.from)?.schema;
let filter = bind_filter(statement.where_.as_ref(), schema, &statement.from)?;
let outputs = if let [SelectItem::Star] = statement.items.as_slice() {
all_columns(schema)
} else {
statement
.items
.iter()
.map(|item| bind_output(item, schema, &statement.from))
.collect::<Result<_>>()?
};
Ok(LogicalPlan::Project {
source: LogicalScan {
table: statement.from.clone(),
filter,
},
outputs,
})
}Две идиомы стоит запомнить, они встретятся в binder-е ещё не раз.
Первая: if let [SelectItem::Star] = statement.items.as_slice(). Это образец среза: он совпадает, только если в списке ровно один элемент и это Star. SELECT * разворачивается во все колонки, а SELECT *, id до этой ветки не дойдёт и упадёт в bind_output с понятной ошибкой. В TS тут была проверка items.length === 1 && items[0].kind === 'star', здесь форма и проверка слиты в одну строку.
Вторая: .map(...).collect::<Result<_>>()?. Каждый bind_output возвращает Result<BoundOutput>, а нам нужен Vec<BoundOutput> или первая ошибка. collect умеет собирать итератор Result<T, E> в Result<Vec<T>, E>: он останавливается на первой ошибке и отдаёт её. Подчёркивание в Result<_> просит компилятор вывести Vec<BoundOutput> из типа поля outputs. Это ровно то, что в уроке про итераторы называлось «FromIterator для Result».
Обрати внимание и на statement.where_.as_ref(). Поле where_: Option<Expr> (подчёркивание, потому что where ключевое слово Rust), а функции нужно Option<&Expr>: заимствовать условие, не забирая его из AST. as_ref превращает &Option<T> в Option<&T> без копии.
INSERT
pub fn bind_insert(statement: &Insert, catalog: &Catalog) -> Result<LogicalPlan> {
let handle = require_table(catalog, &statement.table)?;
let schema = &handle.schema;
let targets: Vec<usize> = match &statement.columns {
Some(names) => names
.iter()
.map(|name| resolve_column(name, schema))
.collect::<Result<_>>()?,
None => (0..schema.len()).collect(),
};
if statement.values.len() != targets.len() {
return Err(engine(format!(
"INSERT ожидает {} значений, получил {}",
targets.len(),
statement.values.len()
)));
}
let mut values = vec![Value::Null; schema.len()];
let mut provided = vec![false; schema.len()];
for (&column_index, literal) in targets.iter().zip(&statement.values) {
let column = &schema.columns()[column_index];
let required = handle.required.contains(&column_index);
check_assignable(&column.name, column.ty, required, literal_type(literal))?;
values[column_index] = literal_value(literal);
provided[column_index] = true;
}
for (index, column) in schema.columns().iter().enumerate() {
if !provided[index] && handle.required.contains(&index) {
return Err(engine(format!(
"колонка \"{}\" не может быть NULL",
column.name
)));
}
}
Ok(LogicalPlan::Insert {
table: statement.table.clone(),
values,
})
}INSERT INTO t (id) VALUES (2) перечисляет не все колонки. Binder сначала строит targets: номера колонок, в которые пишем. Без списка колонок это 0..schema.len(), диапазон тоже итератор, и collect превращает его в Vec<usize>. Потом заводит строку из одних NULL (vec![Value::Null; schema.len()] клонирует значение нужное число раз) и раскладывает литералы по местам. Колонки, которые не упомянуты, остаются NULL, и второй цикл проверяет, что среди них нет обязательных.
targets.iter().zip(&statement.values) идёт двумя итераторами в ногу. Образец (&column_index, literal) сразу снимает ссылку с usize (он Copy), а литерал оставляет ссылкой, потому что Literal::String владеет строкой и копировать её незачем.
UPDATE и DELETE
pub fn bind_update(statement: &Update, catalog: &Catalog) -> Result<LogicalPlan> {
let handle = require_table(catalog, &statement.table)?;
let schema = &handle.schema;
let assignments = statement
.assignments
.iter()
.map(|assignment| {
let index = resolve_column(&assignment.column, schema)?;
let column = &schema.columns()[index];
let value = bind_expr(&assignment.value, schema, &statement.table)?;
let required = handle.required.contains(&index);
check_assignable(&column.name, column.ty, required, value.ty())?;
Ok(BoundAssignment { index, value })
})
.collect::<Result<_>>()?;
let filter = bind_filter(statement.where_.as_ref(), schema, &statement.table)?;
Ok(LogicalPlan::Update {
scan: LogicalScan {
table: statement.table.clone(),
filter,
},
assignments,
})
}
pub fn bind_delete(statement: &Delete, catalog: &Catalog) -> Result<LogicalPlan> {
let schema = &require_table(catalog, &statement.table)?.schema;
let filter = bind_filter(statement.where_.as_ref(), schema, &statement.table)?;
Ok(LogicalPlan::Delete(LogicalScan {
table: statement.table.clone(),
filter,
}))
}В bind_update замыкание внутри map само возвращает Result, поэтому ? внутри него работает: ошибка выходит из замыкания, а не из всей функции, и collect::<Result<_>>() подхватывает её. Правая часть присваивания это полноценное выражение (SET id = id + 1000), поэтому она проходит bind_expr, а не превращается в литерал, как у INSERT.
Выражения
Сердце binder-а: рекурсивный обход выражения.
/// Связать выражение по схеме таблицы `table` (квалификатор колонки сверяется с ней).
pub fn bind_expr(expr: &Expr, schema: &Schema, table: &str) -> Result<BoundExpr> {
match expr {
Expr::Literal(literal) => Ok(BoundExpr::literal(
literal_value(literal),
literal_type(literal),
)),
Expr::Column {
table: qualifier,
name,
} => {
if let Some(qualifier) = qualifier.as_deref().filter(|&q| q != table) {
return Err(engine(format!(
"неизвестная таблица \"{qualifier}\" в ссылке \"{qualifier}.{name}\""
)));
}
let index = resolve_column(name, schema)?;
Ok(BoundExpr::Column {
index,
ty: schema.columns()[index].ty,
})
}
Expr::Not(operand) => {
let operand = bind_expr(operand, schema, table)?;
require_type(&operand, BOOL, "NOT")?;
Ok(BoundExpr::Not(Box::new(operand)))
}
Expr::Binary { op, left, right } => bind_binary(
*op,
bind_expr(left, schema, table)?,
bind_expr(right, schema, table)?,
),
}
}users.name в SQL приходит из парсера как Expr::Column { table: Some("users"), name: "name" }. Строчка с as_deref().filter(...) делает две вещи сразу. as_deref превращает &Option<String> в Option<&str>, а filter оставляет квалификатор, только если он не совпадает с таблицей запроса. Если результат Some, это чужая таблица, и мы отвечаем ошибкой. SELECT users.name FROM users проходит, SELECT wrong.name FROM users падает с неизвестная таблица "wrong".
match здесь исчерпывающий. Если в уроке 5 ты добавишь в Expr новый вариант, например IsNull, компилятор откажется собирать binder, пока ты его не обработаешь. TS-эталон для такой гарантии брал библиотеку ts-pattern, Effect-порт полагался на switch с проверкой never. Здесь гарантия встроена в язык.
fn bind_binary(op: BinaryOp, left: BoundExpr, right: BoundExpr) -> Result<BoundExpr> {
let context = op.as_str();
let ty = match op {
BinaryOp::And | BinaryOp::Or => {
require_type(&left, BOOL, context)?;
require_type(&right, BOOL, context)?;
BOOL
}
BinaryOp::Like => {
require_type(&left, TEXT, context)?;
require_type(&right, TEXT, context)?;
BOOL
}
BinaryOp::Eq | BinaryOp::Ne | BinaryOp::Lt | BinaryOp::Le | BinaryOp::Gt | BinaryOp::Ge => {
let (l, r) = (left.ty(), right.ty());
if l != BoundType::Null && r != BoundType::Null && l != r {
return Err(engine(format!(
"{context} требует операнды одного типа, получено {l} и {r}"
)));
}
BOOL
}
BinaryOp::Add | BinaryOp::Sub | BinaryOp::Mul | BinaryOp::Div => {
require_type(&left, INT, context)?;
require_type(&right, INT, context)?;
INT
}
};
Ok(BoundExpr::Binary {
op,
left: Box::new(left),
right: Box::new(right),
ty,
})
}Правила типов в одной таблице. AND/OR хотят булевы операнды, LIKE текстовые, сравнения одинаковый базовый тип, арифметика только int. Во всех случаях литерал NULL подходит к чему угодно: id = NULL законно связывается (а при исполнении даст NULL, к этому вернёмся в вычислителе). bind_binary забирает left и right по значению и перекладывает их в Box без копии: детей только что построил рекурсивный bind_expr, больше они никому не нужны.
Фильтр, проекция и помощники
fn bind_filter(where_: Option<&Expr>, schema: &Schema, table: &str) -> Result<Option<BoundExpr>> {
let Some(where_) = where_ else {
return Ok(None);
};
let filter = bind_expr(where_, schema, table)?;
let ty = filter.ty();
if ty != BOOL && ty != BoundType::Null {
return Err(engine(format!(
"условие WHERE должно быть булевым, получено {ty}"
)));
}
Ok(Some(filter))
}
fn bind_output(item: &SelectItem, schema: &Schema, table: &str) -> Result<BoundOutput> {
let SelectItem::Expr { expr, alias } = item else {
return Err(engine("звёздочка не сочетается с другими колонками"));
};
let name = match (alias, expr) {
(Some(alias), _) => alias.clone(),
(None, Expr::Column { name, .. }) => name.clone(),
(None, expr) => print_expr(expr),
};
Ok(BoundOutput {
expr: bind_expr(expr, schema, table)?,
name,
})
}
fn all_columns(schema: &Schema) -> Vec<BoundOutput> {
schema
.columns()
.iter()
.enumerate()
.map(|(index, column)| BoundOutput {
expr: BoundExpr::Column {
index,
ty: column.ty,
},
name: column.name.clone(),
})
.collect()
}let Some(where_) = where_ else { return Ok(None); }; это let-else: разобрать значение или выйти. Без него тело функции съехало бы на уровень вправо внутрь if let. Тот же приём в bind_output: если элемент списка это Star, а мы пришли сюда, значит * стоит рядом с другими колонками.
Имя выходной колонки выбирается match по кортежу из двух образцов. Алиас побеждает всегда, голая колонка даёт своё имя, а любое другое выражение печатается обратно в SQL принтером из урока 5: SELECT age + 1 FROM users вернёт колонку с именем (age + 1). Принтер пригодился второй раз, ради этого его и писали.
И мелкие помощники, на которые опирается всё выше.
fn require_table<'c>(catalog: &'c Catalog, table: &str) -> Result<&'c TableHandle> {
catalog
.get(table)
.ok_or_else(|| engine(format!("неизвестная таблица \"{table}\"")))
}
fn resolve_column(name: &str, schema: &Schema) -> Result<usize> {
schema
.columns()
.iter()
.position(|column| column.name == name)
.ok_or_else(|| engine(format!("неизвестная колонка \"{name}\"")))
}
fn require_type(expr: &BoundExpr, ty: BoundType, context: &str) -> Result<()> {
let actual = expr.ty();
if actual != ty && actual != BoundType::Null {
return Err(engine(format!("{context} требует {ty}, получено {actual}")));
}
Ok(())
}
fn check_assignable(
name: &str,
column: ColumnType,
required: bool,
value: BoundType,
) -> Result<()> {
match value {
BoundType::Null if required => {
Err(engine(format!("колонка \"{name}\" не может быть NULL")))
}
BoundType::Null => Ok(()),
BoundType::Column(ty) if ty != column => Err(engine(format!(
"колонка \"{name}\" ожидает {column}, получено {ty}"
))),
BoundType::Column(_) => Ok(()),
}
}
fn literal_value(literal: &Literal) -> Value {
match literal {
Literal::Number(number) => Value::Int(*number),
Literal::String(text) => Value::Text(text.clone()),
Literal::Bool(flag) => Value::Bool(*flag),
Literal::Null => Value::Null,
}
}
fn literal_type(literal: &Literal) -> BoundType {
match literal {
Literal::Number(_) => INT,
Literal::String(_) => TEXT,
Literal::Bool(_) => BOOL,
Literal::Null => BoundType::Null,
}
}В require_table впервые в этом уроке появляется явное время жизни 'c. Сигнатура говорит: возвращённая ссылка на TableHandle живёт столько же, сколько заимствование каталога, и не зависит от строки table. Без аннотации компилятор не смог бы выбрать между двумя входными ссылками и потребовал бы её. Этот же приём, «результат заимствует из одного аргумента, а не из другого», встретится в планировщике на каждом шагу. Подробно правила вывода времён жизни разобраны в уроке про лайфтаймы.
check_assignable это match со охранными условиями: BoundType::Null if required ловит NULL в обязательную колонку раньше, чем общий BoundType::Null. Порядок веток тут значим, и компилятор проверит, что все случаи покрыты.
ok_or_else вместо ok_or: сообщение с format! строится только если колонки нет. На горячем пути, где колонка находится сразу, мы не платим за аллокацию строки.
Вычислитель выражений
Binder дал дерево с типами. Вычислитель берёт его и кортеж и отдаёт Value. Положи в src/engine/eval.rs.
// src/engine/eval.rs
use std::cmp::Ordering;
use crate::engine::binder::BoundExpr;
use crate::error::{engine, Result};
use crate::sql::BinaryOp;
use crate::tuple::{Tuple, Value};
pub fn eval_expr(expr: &BoundExpr, tuple: &Tuple) -> Result<Value> {
match expr {
BoundExpr::Column { index, .. } => {
Ok(tuple.values.get(*index).cloned().unwrap_or(Value::Null))
}
BoundExpr::Literal { value, .. } => Ok(value.clone()),
BoundExpr::Not(operand) => Ok(match eval_expr(operand, tuple)? {
Value::Null => Value::Null,
Value::Bool(flag) => Value::Bool(!flag),
other => return Err(engine(format!("NOT требует bool, получено {other:?}"))),
}),
BoundExpr::Binary {
op, left, right, ..
} => eval_binary(*op, eval_expr(left, tuple)?, eval_expr(right, tuple)?),
}
}
/// Проходит ли строка фильтр: только строго TRUE (NULL и FALSE отсекаются).
pub fn passes_filter(value: &Value) -> bool {
*value == Value::Bool(true)
}Value из урока 3 это enum из четырёх вариантов: Null, Int(i64), Text(String), Bool(bool). NULL здесь не отдельный «отсутствующий» объект, а полноправный вариант, и match обязан про него помнить.
tuple.values.get(*index).cloned().unwrap_or(Value::Null): binder гарантирует, что индекс в границах схемы, но вычислитель всё равно не индексирует через [], а берёт get, получая Option<&Value>. cloned делает из него Option<Value>. Клонировать приходится, потому что результат вычисления это новое значение, а кортеж остаётся у вызывающего. Для Int и Bool клон бесплатен, для Text это копия строки.
passes_filter пропускает только строго TRUE. И FALSE, и NULL строку отсекают. Отсюда классика SQL: WHERE name = 'alice' не вернёт строку, где name это NULL, и WHERE name <> 'alice' тоже не вернёт.
Трёхзначная логика и checked-арифметика
fn eval_binary(op: BinaryOp, left: Value, right: Value) -> Result<Value> {
use Value::{Bool, Int, Null, Text};
Ok(match (op, left, right) {
(BinaryOp::And, l, r) => match (l, r) {
(Bool(false), _) | (_, Bool(false)) => Bool(false),
(Null, _) | (_, Null) => Null,
_ => Bool(true),
},
(BinaryOp::Or, l, r) => match (l, r) {
(Bool(true), _) | (_, Bool(true)) => Bool(true),
(Null, _) | (_, Null) => Null,
_ => Bool(false),
},
// остальные операторы пропагируют NULL
(_, Null, _) | (_, _, Null) => Null,
(BinaryOp::Like, Text(text), Text(pattern)) => Bool(like_match(&text, &pattern)),
(BinaryOp::Add, Int(l), Int(r)) => Int(l.checked_add(r).ok_or_else(overflow)?),
(BinaryOp::Sub, Int(l), Int(r)) => Int(l.checked_sub(r).ok_or_else(overflow)?),
(BinaryOp::Mul, Int(l), Int(r)) => Int(l.checked_mul(r).ok_or_else(overflow)?),
(BinaryOp::Div, Int(_), Int(0)) => return Err(engine("division by zero")),
(BinaryOp::Div, Int(l), Int(r)) => Int(l.checked_div(r).ok_or_else(overflow)?),
(op, l, r) => {
let ordering = compare_values(&l, &r)?;
Bool(match op {
BinaryOp::Eq => ordering == Ordering::Equal,
BinaryOp::Ne => ordering != Ordering::Equal,
BinaryOp::Lt => ordering == Ordering::Less,
BinaryOp::Le => ordering != Ordering::Greater,
BinaryOp::Gt => ordering == Ordering::Greater,
BinaryOp::Ge => ordering != Ordering::Less,
_ => {
return Err(engine(format!(
"{} не применим к {l:?} и {r:?}",
op.as_str()
)))
}
})
}
})
}
fn overflow() -> crate::error::Error {
engine("integer overflow")
}Это, пожалуй, самая красивая функция урока, и вся её красота в одном match по тройке (оператор, левое, правое). Ветки читаются как таблица истинности.
AND и OR идут первыми, потому что они не пропагируют NULL слепо. Это трёхзначная логика Клини: FALSE AND NULL это FALSE (неважно, что там неизвестно, ложь уже решила исход), а TRUE AND NULL это NULL. Для OR зеркально. Образец (Bool(false), _) | (_, Bool(false)) через | ловит ложь с любой стороны одной веткой. Если мысленно заменить Value::Bool и Value::Null на Option<bool>, получится ровно таблица Some(false), None, Some(true).
Строка (_, Null, _) | (_, _, Null) => Null закрывает все остальные операторы разом: сравнение с NULL, арифметика с NULL, LIKE с NULL дают NULL. Порядок веток гарантирует, что AND/OR до неё не дойдут.
Арифметика это то место, где Rust честнее и TS, и JS. В эталоне на TS числа колонок были bigint, а ему переполнение неведомо: bigint растёт без предела, и 9223372036854775807 + 1 там просто даёт число за границей int64, которое потом не влезет в восемь байт кортежа. В Rust i64 фиксирован, и у него есть три поведения на переполнение. Обычный + в debug-сборке паникует, в release тихо переносится через край, и i64::MAX + 1 становится i64::MIN. Ни то, ни другое движку не подходит: паника роняет сервер из-за одного запроса, а перенос молча врёт. Поэтому мы берём checked_add, checked_sub, checked_mul, checked_div, которые возвращают Option<i64>: None на переполнении. ok_or_else(overflow)? превращает None в Error::Engine("integer overflow"). Почему перенос вообще возможен и как устроен дополнительный код, разобрано в уроке про целые числа.
С делением два отдельных случая. Деление на ноль ловится явной веткой (BinaryOp::Div, Int(_), Int(0)) раньше общей, иначе checked_div тоже вернул бы None, и пользователь увидел бы «integer overflow» вместо «division by zero». А вот i64::MIN / -1 это настоящее переполнение: результат 2^63 не влезает в i64, и checked_div честно отвечает None. Обычный / тут запаниковал бы даже в release. Само целочисленное деление в Rust усекает к нулю: -7 / 2 это -3, а не -4, ровно как требует SQL и как вёл себя bigint в эталоне.
Последняя ветка ловит все сравнения. compare_values даёт Ordering, и шесть операторов выражаются через него без дублирования. Ветка _ => внутри недостижима после binder-а, но компилятор не знает, что binder уже всё проверил, поэтому мы честно возвращаем ошибку, а не unreachable!(): если когда-нибудь binder ошибётся, движок ответит ошибкой, а не упадёт.
/// Сравнить два ненулевых значения одного типа.
fn compare_values(left: &Value, right: &Value) -> Result<Ordering> {
match (left, right) {
(Value::Int(l), Value::Int(r)) => Ok(l.cmp(r)),
(Value::Text(l), Value::Text(r)) => Ok(l.cmp(r)),
(Value::Bool(l), Value::Bool(r)) => Ok(l.cmp(r)),
_ => Err(engine("cannot compare values of different types")),
}
}Value не реализует Ord, и это сознательно: сравнивать Int с Text бессмысленно, а derive(Ord) упорядочил бы варианты по порядку объявления и молча разрешил бы 1 < 'a'. Поэтому сравнение явное и падает на разных типах.
LIKE
/// LIKE: `%` это любая последовательность символов, `_` ровно один символ.
fn like_match(text: &str, pattern: &str) -> bool {
let text: Vec<char> = text.chars().collect();
let pattern: Vec<char> = pattern.chars().collect();
// классический жадный матчер с откатом к последнему `%`
let (mut t, mut p) = (0, 0);
let mut star: Option<(usize, usize)> = None;
while t < text.len() {
match pattern.get(p) {
Some('%') => {
star = Some((p, t));
p += 1;
}
Some(&c) if c == '_' || c == text[t] => {
t += 1;
p += 1;
}
_ => match star {
Some((star_p, star_t)) => {
p = star_p + 1;
t = star_t + 1;
star = Some((star_p, star_t + 1));
}
None => return false,
},
}
}
pattern[p..].iter().all(|&c| c == '%')
}TS-эталон переводил шаблон LIKE в регулярное выражение. В Rust без крейтов регулярок нет, и это к лучшему: матчер на двух указателях проще, чем экранирование всех спецсимволов регулярки (тест a.c против abc проверяет как раз то, что точка тут обычный символ). Матчер жадный: на % он запоминает позицию в star, а при несовпадении откатывается туда и пробует съесть на один символ текста больше.
Обрати внимание на первые две строки. str в Rust это UTF-8, и индекс text[t] по строке дал бы байт, а не символ. Шаблон _ж% против ёжик должен совпасть: _ это одна буква ё, хотя в UTF-8 она занимает два байта. Поэтому оба аргумента сначала разворачиваются в Vec<char>, где каждый элемент это один скалярный символ Unicode. Тот же выбор лексер урока 5 сделал для смещений в сообщениях об ошибках.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.