Своя СУБД на Go · урок 6: анализ, план, исполнитель, EXPLAIN
Кому это. К этому уроку у тебя собрана вся нижняя половина движка и фронтенд. В уроке 3 выросла куча с курсором Next() (Item, bool, error), в уроке 4 к ней добавился B+Tree с диапазонным сканом, в уроке 5 появился фронтенд: строка SQL режется на токены и собирается в дерево, а ошибка разбора приходит значением *sql.Error. Но дерево пока висит в воздухе. В нём есть &sql.Column{Name: "name"}, и оно понятия не имеет, есть ли такая колонка в users.
Что сегодня. Замыкаем путь запроса: дерево пройдёт три фазы и превратится в строки. Binder сверит имена с каталогом, планировщик выберет seq scan или index scan, исполнитель прогонит план.
Зачем именно Go. Верхняя половина движка это деревья и их обход. В TS-треке деревья были размеченными объединениями, а разбор шёл через ts-pattern или switch по полю kind. В Go та же идея звучит иначе: узел это маленькая структура, вариант узла это её тип, а множество вариантов держит интерфейс. Разбирает дерево type switch. Операторы плана тоже интерфейс, и вот тут он честно отрабатывает своё место: у Operator пять реализаций, и исполнитель не знает, какая перед ним. Ошибки, как и во всём треке, это значения: каждая фаза отвечает парой (результат, error), а класс ошибки движка лежит в коде dberr.Code, который достаётся через errors.As. И последнее: в Go нет однопоточного цикла событий, поэтому в уроке 11, когда к движку придут запросы из разных горутин, он получит sync.RWMutex. Пока его зовёт один тест в одной горутине.
Важно про код. Урок большой: это вся верхняя половина движка разом. Но ни одна фаза не трогает байты напрямую. Binder, планировщик и вычислитель это чистые функции над деревьями, а операторы ходят в кучу и индекс только через API уроков 3 и 4. Эталон examples/our-db/go/engine уже содержит всё до урока 11: журнал, транзакции, блокировки, видимость MVCC. Листинги этого урока взяты оттуда и урезаны до шестого урока: где у эталона есть TxnContext, журнал или ключ блокировки, мы их убираем и каждый раз говорим, что и в каком уроке вернётся. Всё остальное слово в слово. Модуль тот же, ourdb на Go 1.23, только стандартная библиотека.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + 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
│ disk.Manager (страницы поверх файла) │ урок 1
└────────────────────────────────────────────────┘Сегодня закрываем четыре слоя. Заметь, чего тут пока нет: транзакций, WAL, блокировок, MVCC. Движок урока 6 без долговечности и без изоляции: каждая вставка меняет страницу в буферном пуле, а на диск она попадает при вытеснении или при Close. Поля xmin/xmax в кортеже из урока 3 мы заполняем фиксированным значением autocommitXid и игнорируем. Это сознательное упрощение: сначала пусть движок научится отвечать на запросы, а журнал, транзакции и конкурентные записи навесим в уроках 7, 8 и 9 поверх готового исполнителя.
Конвейер запроса
Разберём путь одного запроса на примере. Пусть пришло SELECT name FROM users WHERE id = 2.
строка SQL
│ sql.ParseCommand (урок 5 + EXPLAIN)
▼
sql.Command (AST)
│ bind: имена в индексы колонок, проверка типов
▼
logicalPlan (что делаем)
│ planOperator: выбор метода доступа
▼
дерево Operator (как делаем)
│ executor: Open, затем Next до nil
▼
ResultПарсер отдаёт *sql.Select с колонкой name и условием id = 2. Binder смотрит в каталог: таблица users есть, name это колонка номер 1 типа text, id колонка номер 0 типа int, сравнение int с int законно. Получается логический план: прочитать users с фильтром колонка 0 = 2 и отдать колонку 1. Планировщик замечает, что по id есть индекс, и строит физический план: Project над IndexScan по диапазону [2, 2]. Исполнитель открывает дерево и дёргает Next, пока тот не вернёт nil.
Три фазы и две формы плана. Под всем этим лежит каталог: он знает таблицы, их колонки и файлы. Начнём с ошибок, потому что их возвращает каждая фаза.
Ошибки движка: dberr
Binder и вычислитель могут не сложиться: нет такой таблицы, не тот тип, деление на ноль. Планировщик и операторы ходят на диск и могут упасть там. Тестам и, позже, сетевому протоколу нужно отличать эти случаи: ошибку анализа клиент исправит в запросе, нарушение уникальности это отказ по данным, а сбой диска вообще не его забота.
В TS-треке каждому классу ошибки отвечал свой класс-исключение. В Go эталон держит один тип с кодом, по образцу SQLSTATE. Это пакет dberr: в этапе изделия он уже лежит готовым и только для чтения, ниже его урезанная до урока 6 версия.
// Package dberr это ошибки движка с SQLSTATE-подобным кодом. Сессия протокола (урок 11)
// отдаёт Code клиенту как есть.
package dberr
import (
"errors"
"fmt"
)
// Code это SQLSTATE-подобный код класса ошибки.
type Code string
const (
Engine Code = "42000" // анализ, план, исполнение
Uniqueness Code = "23505" // дубликат PRIMARY KEY
)
// Error это ошибка движка.
type Error struct {
Code Code
Msg string
}
func (e *Error) Error() string { return e.Msg }
// New собирает ошибку с кодом.
func New(code Code, format string, args ...any) error {
return &Error{Code: code, Msg: fmt.Sprintf(format, args...)}
}
// CodeOf это код ошибки движка или "" для чужой ошибки.
func CodeOf(err error) Code {
var e *Error
if errors.As(err, &e) {
return e.Code
}
return ""
}Здесь два кода из пяти. В готовом dberr этапа есть и остальные три (40001 для конфликта записи, 40P01 для дедлока, 55P03 для занятого лока), но понадобятся они только в уроке 9 вместе с блокировками. Почему отдельный пакет, а не файл в engine? Эти ошибки позже будут создавать и менеджер транзакций, и менеджер блокировок, а engine импортирует оба. Положи тип в engine, и получишь цикл импорта, который Go не прощает. Маленький пакет внизу графа зависимостей снимает вопрос.
Две детали стоит проговорить. New возвращает error, а не *Error. Это привычка, которая бережёт от typed nil: функция, возвращающая конкретный указатель, рано или поздно отдаст nil в переменную типа error, и err != nil окажется истиной. А CodeOf ищет ошибку через errors.As, а не через приведение err.(*Error). errors.As пройдёт по цепочке обёрток: если кто-то выше завернёт нашу ошибку в fmt.Errorf("...: %w", err) или соберёт несколько через errors.Join, код всё равно найдётся. Чужая ошибка, например *sql.Error парсера или сбой os.File, даёт пустой код. Подробнее про As, Is и обёртки в уроке про ошибки.
Связанное представление
Опишем выход binder-а. Это зеркало AST из урока 5, но колонки уже резолвлены в индексы, и каждое выражение знает свой тип. Положи в engine/bound.go.
// Package engine это анализ, план и исполнение (урок 6). Database связывает парсер,
// каталог и исполнитель.
package engine
import "ourdb/tuple"
// BoundType это тип выражения; "null" это литерал NULL, совместимый с любой колонкой.
type BoundType string
const (
BoundInt = BoundType(tuple.TypeInt)
BoundText = BoundType(tuple.TypeText)
BoundBool = BoundType(tuple.TypeBool)
BoundNull BoundType = "null"
)
// BoundExpr это выражение после binder: колонки резолвлены в индексы, у узла есть тип.
type BoundExpr interface{ Type() BoundType }
type BoundColumn struct {
Index int
Typ tuple.ColumnType
}
type BoundLiteral struct {
Value tuple.Value
Typ BoundType
}
type BoundBinary struct {
Op string
Left, Right BoundExpr
Typ BoundType
}
// BoundUnary это NOT.
type BoundUnary struct {
Operand BoundExpr
}
func (e *BoundColumn) Type() BoundType { return BoundType(e.Typ) }
func (e *BoundLiteral) Type() BoundType { return e.Typ }
func (e *BoundBinary) Type() BoundType { return e.Typ }
func (e *BoundUnary) Type() BoundType { return BoundBool }
// Логический план: намерение запроса после анализа. Планировщик переводит его в дерево
// физических операторов.
type (
logicalPlan interface{ plan() }
scanPlan struct {
table string
filter BoundExpr // nil без WHERE
}
output struct {
expr BoundExpr
name string
}
projectPlan struct {
source scanPlan
outputs []output
}
insertPlan struct {
table string
values []tuple.Value
}
deletePlan struct {
source scanPlan
}
assignment struct {
index int
value BoundExpr
}
updatePlan struct {
source scanPlan
assignments []assignment
}
)
func (*projectPlan) plan() {}
func (*insertPlan) plan() {}
func (*deletePlan) plan() {}
func (*updatePlan) plan() {}Здесь два интерфейса, и они устроены по-разному, хотя оба описывают закрытое множество вариантов.
BoundExpr открыт: у него экспортируемый метод Type(), и он нужен по делу. Binder проверяет типы, спрашивая у любого узла его тип, не разбирая, что это за узел. Сами узлы тоже экспортированы, вместе с полями. Это не прихоть: тесты урока живут во внешнем пакете engine_test и собирают выражения руками (&engine.BoundBinary{Op: "=", ...}), чтобы проверить трёхзначную логику без SQL. Типы BoundType строятся из tuple.ColumnType обычным преобразованием BoundType(tuple.TypeInt): у обоих базовый тип string, поэтому int колонки и int выражения это одна и та же строка, и их можно сравнивать.
logicalPlan закрыт так же, как sql.Statement из урока 5: метод-маркер plan() не экспортирован, и чужой пакет не сможет добавить свой вид плана. Наружу план не выходит вовсе: его строит binder и сразу съедает планировщик. Поэтому и структуры с маленькой буквы.
Обрати внимание на scanPlan.filter: отсутствие WHERE это nil. Интерфейсное значение в Go умеет быть nil, и это естественный способ сказать нет фильтра без отдельного флага. Чем этот nil отличается от typed nil из прошлого раздела? Мы никогда не кладём сюда (*BoundBinary)(nil): либо настоящий узел, либо нулевое значение поля.
Binder
Binder превращает AST в логический план: резолвит таблицу и имена колонок в индексы по каталогу, проверяет типы, разворачивает *, проверяет арность и NOT NULL у INSERT. JOIN, ORDER BY и LIMIT парсятся, но binder отвергает их как упражнения. Положи в engine/binder.go. Сначала вход.
package engine
import (
"ourdb/dberr"
"ourdb/sql"
"ourdb/tuple"
)
// tableMeta это то, что binder знает о таблице: схема и обязательные колонки (NOT NULL и
// PRIMARY KEY, в Schema ограничений нет).
type tableMeta struct {
schema tuple.Schema
required map[int]bool
}
type bindCatalog func(table string) (tableMeta, bool)
// bind превращает AST в логический план (урок 6): резолвит таблицу и колонки, проверяет
// типы, разворачивает `*`, проверяет арность и типы INSERT, NOT NULL и PRIMARY KEY. JOIN,
// ORDER BY и LIMIT парсятся, но здесь отвергаются как упражнения урока 6.
func bind(s sql.Statement, catalog bindCatalog) (logicalPlan, error) {
switch s := s.(type) {
case *sql.Select:
return bindSelect(s, catalog)
case *sql.Insert:
return bindInsert(s, catalog)
case *sql.Update:
meta, err := requireTable(catalog, s.Table)
if err != nil {
return nil, err
}
plan := &updatePlan{}
for _, a := range s.Assignments {
index, err := resolveColumn(a.Column, meta.schema)
if err != nil {
return nil, err
}
value, err := bindExpr(a.Value, meta.schema, s.Table)
if err != nil {
return nil, err
}
c := meta.schema[index]
if err := checkAssignable(c.Name, c.Type, meta.required[index], value.Type()); err != nil {
return nil, err
}
plan.assignments = append(plan.assignments, assignment{index, value})
}
plan.source, err = bindScan(s.Table, s.Where, meta.schema)
return plan, err
case *sql.Delete:
meta, err := requireTable(catalog, s.Table)
if err != nil {
return nil, err
}
source, err := bindScan(s.Table, s.Where, meta.schema)
return &deletePlan{source}, err
}
return nil, dberr.New(dberr.Engine, "CREATE TABLE handled before binding")
}Первое, на что стоит посмотреть, это тип bindCatalog. Binder не знает про *Catalog, про файлы и пулы. Ему нужно ровно одно: по имени таблицы получить схему и обязательные колонки, или узнать, что таблицы нет. Это одна операция, и в Go для неё не нужен интерфейс: хватит типа-функции. Каталог отдаст свой метод c.bindCatalog как значение, а тест при желании подсунет литерал функции с захардкоженной схемой. Ответ (tableMeta, bool) это та же идиома запятая-ok, что у чтения из map: нет таблицы, это не сбой, а ответ, и ошибку с человеческим текстом соберёт requireTable. Про функции как значения и замыкания подробно в уроке про функции.
Второе это сам switch s := s.(type). Это type switch: в ветке case *sql.Select переменная s уже имеет тип *sql.Select, и s.From читается без приведения. Затенение имени s тут намеренное и идиоматичное: внутри ветки старое значение интерфейса никому не нужно.
У type switch есть цена, которой не было в TS. Компилятор TypeScript проверял, что switch по kind покрыл все варианты объединения. Go так не умеет: множество реализаций интерфейса открыто для компилятора, даже если мы закрыли его маркером. Поэтому после switch всегда стоит запасной выход. Здесь он ловит *sql.CreateTable, который движок обрабатывает раньше binder-а, и заодно любой будущий оператор, который ты забудешь провести. Забудешь, и тест получит ошибку, а не панику или молчаливый пустой план.
Третье это строка return plan, err в ветке UPDATE. Мы возвращаем план и ошибку вместе, не проверив её. Это законно, потому что вызывающий по соглашению сначала смотрит на ошибку и при ошибке результат не трогает. Тот же приём в return &deletePlan{source}, err. Код получается короче, но держи соглашение в голове: в Go оно не проверяется типами.
Дальше разбор SELECT и INSERT.
func bindSelect(s *sql.Select, catalog bindCatalog) (logicalPlan, error) {
switch {
case s.Join != nil:
return nil, dberr.New(dberr.Engine, "JOIN это упражнение урока 6")
case s.OrderBy != nil:
return nil, dberr.New(dberr.Engine, "ORDER BY это упражнение урока 6")
case s.Limit != nil:
return nil, dberr.New(dberr.Engine, "LIMIT это упражнение урока 6")
}
meta, err := requireTable(catalog, s.From)
if err != nil {
return nil, err
}
source, err := bindScan(s.From, s.Where, meta.schema)
if err != nil {
return nil, err
}
plan := &projectPlan{source: source}
if len(s.Items) == 1 && s.Items[0].Star {
for i, c := range meta.schema {
plan.outputs = append(plan.outputs, output{&BoundColumn{i, c.Type}, c.Name})
}
return plan, nil
}
for _, item := range s.Items {
if item.Star {
return nil, dberr.New(dberr.Engine, "звёздочка не сочетается с другими колонками")
}
expr, err := bindExpr(item.Expr, meta.schema, s.From)
if err != nil {
return nil, err
}
name := item.Alias
if name == "" {
if c, ok := item.Expr.(*sql.Column); ok {
name = c.Name
} else {
name = sql.PrintExpr(item.Expr)
}
}
plan.outputs = append(plan.outputs, output{expr, name})
}
return plan, nil
}
func bindInsert(s *sql.Insert, catalog bindCatalog) (logicalPlan, error) {
meta, err := requireTable(catalog, s.Table)
if err != nil {
return nil, err
}
targets := make([]int, 0, len(meta.schema))
if s.Columns == nil {
for i := range meta.schema {
targets = append(targets, i)
}
}
for _, name := range s.Columns {
i, err := resolveColumn(name, meta.schema)
if err != nil {
return nil, err
}
targets = append(targets, i)
}
if len(s.Values) != len(targets) {
return nil, dberr.New(dberr.Engine, "INSERT ожидает %d значений, получил %d", len(targets), len(s.Values))
}
values := make([]tuple.Value, len(meta.schema))
provided := map[int]bool{}
for pos, i := range targets {
c := meta.schema[i]
lit := bindLiteral(s.Values[pos])
if err := checkAssignable(c.Name, c.Type, meta.required[i], lit.Typ); err != nil {
return nil, err
}
values[i] = lit.Value
provided[i] = true
}
for i, c := range meta.schema {
if !provided[i] && meta.required[i] {
return nil, dberr.New(dberr.Engine, "колонка %q не может быть NULL", c.Name)
}
}
return &insertPlan{s.Table, values}, nil
}
func bindScan(table string, where sql.Expr, schema tuple.Schema) (scanPlan, error) {
scan := scanPlan{table: table}
if where == nil {
return scan, nil
}
filter, err := bindExpr(where, schema, table)
if err != nil {
return scan, err
}
if t := filter.Type(); t != BoundBool && t != BoundNull {
return scan, dberr.New(dberr.Engine, "условие WHERE должно быть булевым, получено %s", t)
}
scan.filter = filter
return scan, nil
}bindSelect начинается с switch без выражения: это цепочка if, записанная столбиком. Парсер урока 5 честно разбирает JOIN, ORDER BY и LIMIT, а binder пока отвечает, что это упражнения. Сообщение говорит ровно это, и тест анализа ловит его по подстроке.
Имя выходной колонки берётся из алиаса, если он есть. Если нет, то для голой колонки это её имя, а для выражения его печать через sql.PrintExpr из урока 5: SELECT age + 1 FROM users вернёт колонку с именем (age + 1). Принтер, который мы писали ради round-trip теста, неожиданно пригодился в боевом коде.
В bindInsert спрятаны две идиомы Go про срезы и карты. Первая: s.Columns == nil отличает INSERT INTO t VALUES (...) от INSERT INTO t (a, b) VALUES (...). Парсер оставляет nil, когда списка колонок нет, и это различимо от пустого списка, хотя len у обоих ноль. Вторая: values := make([]tuple.Value, len(meta.schema)) сразу даёт срез, заполненный nil, то есть строку из одних NULL. Колонки, которые пользователь не назвал, так и останутся NULL, и последний цикл проверит, что среди них нет обязательных. provided[i] для отсутствующего ключа вернёт false, нулевое значение bool, поэтому карту не надо заполнять заранее.
bindScan проверяет, что WHERE булев. WHERE NULL разрешён (тип null совместим с любым), а WHERE id нет: это int, и строку по нему не отфильтровать. Остались выражения и проверки типов.
// bindExpr связывает выражение по схеме. table это таблица из FROM/INTO: квалификатор
// колонки сверяется с ней (JOIN отвергается, таблица одна).
func bindExpr(e sql.Expr, schema tuple.Schema, table string) (BoundExpr, error) {
switch e := e.(type) {
case *sql.Literal:
return bindLiteral(*e), nil
case *sql.Column:
if e.Table != "" && e.Table != table {
return nil, dberr.New(dberr.Engine, "неизвестная таблица %q в ссылке \"%s.%s\"", e.Table, e.Table, e.Name)
}
i, err := resolveColumn(e.Name, schema)
if err != nil {
return nil, err
}
return &BoundColumn{i, schema[i].Type}, nil
case *sql.Unary:
operand, err := bindExpr(e.Operand, schema, table)
if err != nil {
return nil, err
}
return &BoundUnary{operand}, requireType(operand, BoundBool, "NOT")
case *sql.Binary:
left, err := bindExpr(e.Left, schema, table)
if err != nil {
return nil, err
}
right, err := bindExpr(e.Right, schema, table)
if err != nil {
return nil, err
}
return bindBinary(e.Op, left, right)
}
return nil, dberr.New(dberr.Engine, "unknown expression %T", e)
}
func bindBinary(op string, left, right BoundExpr) (BoundExpr, error) {
operand, result := BoundBool, BoundBool
switch op {
case "AND", "OR":
case "LIKE":
operand = BoundText
case "+", "-", "*", "/":
operand, result = BoundInt, BoundInt
default: // сравнения требуют одинаковый базовый тип
l, r := left.Type(), right.Type()
if l != BoundNull && r != BoundNull && l != r {
return nil, dberr.New(dberr.Engine, "%s требует операнды одного типа, получено %s и %s", op, l, r)
}
return &BoundBinary{op, left, right, BoundBool}, nil
}
if err := requireType(left, operand, op); err != nil {
return nil, err
}
if err := requireType(right, operand, op); err != nil {
return nil, err
}
return &BoundBinary{op, left, right, result}, nil
}
func bindLiteral(l sql.Literal) *BoundLiteral {
switch l.Kind {
case sql.LitNumber:
return &BoundLiteral{l.Int, BoundInt}
case sql.LitString:
return &BoundLiteral{l.Str, BoundText}
case sql.LitBool:
return &BoundLiteral{l.Bool, BoundBool}
}
return &BoundLiteral{nil, BoundNull}
}
func requireTable(catalog bindCatalog, table string) (tableMeta, error) {
meta, ok := catalog(table)
if !ok {
return meta, dberr.New(dberr.Engine, "неизвестная таблица %q", table)
}
return meta, nil
}
func resolveColumn(name string, schema tuple.Schema) (int, error) {
i, err := schema.ColumnIndex(name)
if err != nil {
return -1, dberr.New(dberr.Engine, "неизвестная колонка %q", name)
}
return i, nil
}
func requireType(e BoundExpr, want BoundType, context string) error {
if t := e.Type(); t != want && t != BoundNull {
return dberr.New(dberr.Engine, "%s требует %s, получено %s", context, want, t)
}
return nil
}
func checkAssignable(column string, colType tuple.ColumnType, required bool, value BoundType) error {
if value == BoundNull {
if required {
return dberr.New(dberr.Engine, "колонка %q не может быть NULL", column)
}
return nil
}
if value != BoundType(colType) {
return dberr.New(dberr.Engine, "колонка %q ожидает %s, получено %s", column, colType, value)
}
return nil
}Здесь вся семантика нашего SQL в одном месте. Сравнения требуют операнды одного типа. Арифметика бывает только над int. AND, OR и NOT булевы, LIKE текстовый. NULL совместим с чем угодно. bindBinary выражает эти правила таблицей из двух переменных: какой тип нужен операндам и какой получится у результата. Ветка case "AND", "OR": пустая, и в Go это не ошибка: switch не проваливается в следующую ветку без явного fallthrough, поэтому пустая ветка значит оставить значения по умолчанию, то есть bool на входе и bool на выходе.
bindLiteral достаёт значение из того поля литерала, которое соответствует его виду: sql.Literal из урока 5 хранит все варианты в одной плоской структуре. Число превращается в int64, строка в string, булево в bool, а NULL в nil. Это и есть представление значений во всём движке: tuple.Value из урока 3 это any, и внутри него лежит одно из этих четырёх.
resolveColumn переводит ошибку схемы в ошибку движка с кодом 42000. Исходная ошибка ColumnIndex из урока 3 сделана через fmt.Errorf, у неё нет кода, и тест анализа ждёт именно dberr.Engine. Мы её не заворачиваем через %w, а заменяем: текст пользователю нужен свой, на русском и с кавычками.
Вычислитель выражений
Связанное выражение надо уметь вычислить над строкой. Тут главный герой это NULL, и его семантика это трёхзначная логика. Положи в engine/eval.go.
package engine
import (
"math"
"ourdb/dberr"
"ourdb/tuple"
)
// Eval вычисляет выражение над кортежем. NULL это трёхзначная логика Клини: сравнение с NULL
// даёт NULL, AND/OR следуют таблицам истинности. Деление усекает к нулю, деление на ноль и
// выход за int64 это ошибки.
func Eval(e BoundExpr, t tuple.Tuple) (tuple.Value, error) {
switch e := e.(type) {
case *BoundColumn:
return t.Values[e.Index], nil
case *BoundLiteral:
return e.Value, nil
case *BoundUnary:
v, err := Eval(e.Operand, t)
if b, ok := v.(bool); ok {
return !b, err
}
return nil, err
case *BoundBinary:
left, err := Eval(e.Left, t)
if err != nil {
return nil, err
}
right, err := Eval(e.Right, t)
if err != nil {
return nil, err
}
return evalBinary(e.Op, left, right)
}
return nil, dberr.New(dberr.Engine, "unknown expression %T", e)
}
// PassesFilter пропускает только строго TRUE: NULL и FALSE отсекаются.
func PassesFilter(v tuple.Value) bool { return v == true }
func evalBinary(op string, left, right tuple.Value) (tuple.Value, error) {
switch op {
case "AND":
if left == false || right == false {
return false, nil
}
return nullOr(left, right, true), nil
case "OR":
if left == true || right == true {
return true, nil
}
return nullOr(left, right, false), nil
}
if left == nil || right == nil {
return nil, nil // остальные операторы пропагируют NULL
}
switch op {
case "LIKE":
return like([]rune(left.(string)), []rune(right.(string))), nil
case "+", "-", "*", "/":
return arithmetic(op, left.(int64), right.(int64))
}
ord, err := compare(left, right)
if err != nil {
return nil, err
}
switch op {
case "=":
return ord == 0, nil
case "<>":
return ord != 0, nil
case "<":
return ord < 0, nil
case "<=":
return ord <= 0, nil
case ">":
return ord > 0, nil
case ">=":
return ord >= 0, nil
}
return nil, dberr.New(dberr.Engine, "unknown operator %s", op)
}
func nullOr(left, right tuple.Value, v bool) tuple.Value {
if left == nil || right == nil {
return nil
}
return v
}Посмотри на PassesFilter: вся функция это v == true. Здесь v имеет тип any, а true нетипизированная константа. Go сравнивает интерфейс с константой так: константа становится bool, и сравнение истинно, только если внутри интерфейса лежит bool со значением true. nil не равен true, false не равен true, и даже int64(1) не равен true, потому что у него другой динамический тип. Так одна строка кодирует главное правило WHERE: строка проходит только на строго TRUE, а NULL (неизвестно) и FALSE отсекаются одинаково.
Тот же приём в evalBinary: left == false || right == false для AND. Это и есть таблица Клини в одну строку. Если хоть один операнд FALSE, результат FALSE, даже если второй NULL: исход ясен и без него. Иначе nullOr решает: если хоть один NULL, то NULL, иначе TRUE. Для OR то же самое зеркально. Проверь на трёх случаях из теста: NULL AND FALSE это FALSE, NULL AND TRUE это NULL, NOT NULL это NULL.
NOT устроен через приведение с запятой-ok: v.(bool) удаётся только на настоящем булевом, а для nil ветка ok ложна, и мы возвращаем nil. Заметь, что ошибку err мы возвращаем в обеих ветках: если вычисление операнда упало, значение v будет nil, а ошибка поедет наверх.
Дальше в evalBinary приведения без ok: left.(string), left.(int64). Такое приведение паникует, если тип не тот. Почему здесь можно? Потому что binder уже гарантировал типы: до LIKE доходят только text операнды, до арифметики только int, а NULL мы отсекли строкой выше. Паника тут значила бы ошибку в нашем же binder-е, а не в запросе пользователя. Это разумное правило Go: приведение без ok пишут там, где неверный тип это баг программы. Про приведения и type switch подробно в уроке про интерфейсы.
Остались сравнение, арифметика и LIKE.
func compare(left, right tuple.Value) (int, error) {
switch l := left.(type) {
case int64:
if r, ok := right.(int64); ok {
return cmp3(l < r, l > r), nil
}
case string:
if r, ok := right.(string); ok {
return cmp3(l < r, l > r), nil
}
case bool:
if r, ok := right.(bool); ok {
return cmp3(!l && r, l && !r), nil
}
}
return 0, dberr.New(dberr.Engine, "cannot compare values of different types")
}
func cmp3(less, greater bool) int {
switch {
case less:
return -1
case greater:
return 1
}
return 0
}
// arithmetic считает над int64 с проверкой переполнения: у эталона bigint без границ, здесь
// честная ошибка вместо молчаливого заворота.
func arithmetic(op string, a, b int64) (tuple.Value, error) {
var r int64
overflow := false
switch op {
case "+":
r = a + b
overflow = (a > 0 && b > 0 && r < 0) || (a < 0 && b < 0 && r >= 0)
case "-":
r = a - b
overflow = (b < 0 && r < a) || (b > 0 && r > a)
case "*":
r = a * b
overflow = a != 0 && (r/a != b || (a == -1 && b == math.MinInt64))
case "/":
if b == 0 {
return nil, dberr.New(dberr.Engine, "division by zero")
}
overflow = a == math.MinInt64 && b == -1
r = a / b
}
if overflow {
return nil, dberr.New(dberr.Engine, "целое вне диапазона int64")
}
return r, nil
}
// like сопоставляет текст с шаблоном: `%` это любая подстрока, `_` любой один символ.
// Жадный проход с откатом к последнему `%`.
func like(text, pattern []rune) bool {
t, p, star, mark := 0, 0, -1, 0
for t < len(text) {
switch {
case p < len(pattern) && pattern[p] == '%':
star, mark = p, t
p++
case p < len(pattern) && (pattern[p] == '_' || pattern[p] == text[t]):
t++
p++
case star >= 0:
p = star + 1
mark++
t = mark
default:
return false
}
}
for p < len(pattern) && pattern[p] == '%' {
p++
}
return p == len(pattern)
}compare это type switch по левому операнду и приведение с ok по правому. Строки в Go сравниваются операторами < и > побайтово, это лексикографический порядок UTF-8. Для bool порядок такой же, как в Postgres: FALSE меньше TRUE.
arithmetic это место, где Go-порт честно расходится с эталоном. В TS целое было bigint без границ, и 9223372036854775807 + 1 просто давало большее число. В Go int64 при переполнении молча заворачивается: math.MaxInt64 + 1 это math.MinInt64, и никакой паники. Для базы это худший исход: сумма на счёте внезапно становится отрицательной, и никто не узнаёт. Поэтому каждая операция проверяет переполнение после факта.
Разберём сложение, остальное по тому же образцу. Два положительных числа не могут дать отрицательную сумму, а два отрицательных не могут дать неотрицательную. Если дали, значит произошёл заворот. Для умножения проверка через деление обратно: если r / a не равно b, результат не поместился. И отдельный капкан: math.MinInt64 / -1. Математически это MaxInt64 + 1, не помещается, а спецификация Go говорит, что результат равен самому делимому: снова MinInt64, тот же тихий заворот, только у деления. Поэтому деление проверяет этот случай до самой операции. Деление на ноль тоже проверяется заранее, иначе Go запаникует с integer divide by zero.
Деление целочисленное с усечением к нулю: -7 / 2 это -3, а не -4. Так считают Go и Postgres, и тест TestIntegerDivision это фиксирует.
like работает над []rune, а не над строкой. Причина в _: шаблон _ж должен совпасть с ёж, где _ это один символ. Индекс строки в Go адресует байты, а ё в UTF-8 занимает два байта. Преобразование []rune(s) раскладывает строку на кодовые точки, и дальше индекс это номер символа. Сам алгоритм это жадный проход с откатом: встретив %, запоминаем позицию в шаблоне и в тексте, а при несовпадении возвращаемся к последнему % и пробуем отдать ему ещё один символ. Регулярные выражения тут не нужны, и пользовательский шаблон не сможет превратиться в регулярку с катастрофическим откатом. Про руны и байты подробнее в уроке про строки.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.