Своя СУБД на Haskell · урок 5: свой SQL, лексер и парсер

Кому это. Ты прошёл урок 4: хранилище готово, у таблиц есть индексы. Пользоваться им пока можно только из Haskell-кода. Сегодня начинается верхняя половина движка: строка SQL превратится в дерево, с которым движок сможет работать. Тот же урок есть в TS-треке, и диалект там тот же до последнего ключевого слова. Для Haskell это родная территория: лексер это сопоставление с образцом по списку символов, AST это алгебраические типы, парсер это монада над списком токенов, и все три шага это чистые функции с результатом Either DbError. Если ты писал парсер-комбинаторы с нуля, половина урока покажется знакомой.

Важно про код. В этом уроке нет ни одной строки в IO. Всё, что ты напишешь, проверяется в GHCi одной строкой: parse "SELECT * FROM t". Пользуйся этим, гоняй каждую функцию сразу, как напишешь.

Где мы в движке

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 11
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Парсер, лексер, pretty-printer                  │  урок 5  ← мы здесь
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 10
│  Блокировки (2PL), граф ожидания                 │  урок 9
│  MVCC, менеджер транзакций                       │  урок 8
│  WAL (журнал, redo, recovery)                    │  урок 7
├────────────────────────────────────────────────┤
│  B+Tree индекс                                   │  урок 4
│  Куча (slotted pages, seq scan)                  │  урок 3
├────────────────────────────────────────────────┤
│  Буферный пул (кэш страниц, вытеснение)           │  урок 2
│  DiskManager (страницы поверх файла)              │  урок 1
└────────────────────────────────────────────────┘

Это первый слой, который ничего не знает про хранилище. Парсер не видит ни страниц, ни таблиц. Он даже не знает, существует ли таблица users: это проверит binder в уроке 6. Его работа одна: превратить строку в дерево или объяснить, где в строке ошибка.

Что мы парсим

Парсер начинается с грамматики. Мы берём небольшое подмножество SQL, которого хватает на весь воркшоп. Записывается грамматика в EBNF, и каждое правило станет одной функцией парсера.

command     = "BEGIN" | "COMMIT" | "ROLLBACK" | [ "EXPLAIN" ] statement ;
statement   = createTable | insert | select | update | delete ;

createTable = "CREATE" "TABLE" ident "(" columnDef { "," columnDef } ")" ;
columnDef   = ident type [ "PRIMARY" "KEY" | "NOT" "NULL" ] ;
type        = "INT" | "TEXT" | "BOOL" ;

insert      = "INSERT" "INTO" ident [ "(" ident { "," ident } ")" ]
              "VALUES" "(" literal { "," literal } ")" ;

select      = "SELECT" ( "*" | projection )
              "FROM" ident [ join ]
              [ "WHERE" expr ]
              [ "ORDER" "BY" ident [ "ASC" | "DESC" ] ]
              [ "LIMIT" number ] ;
projection  = expr [ "AS" ident ] { "," expr [ "AS" ident ] } ;
join        = ( "INNER" | "LEFT" ) "JOIN" ident "ON" expr ;

update      = "UPDATE" ident "SET" assignment { "," assignment } [ "WHERE" expr ] ;
delete      = "DELETE" "FROM" ident [ "WHERE" expr ] ;
assignment  = ident "=" expr ;

expr        = primary { binop primary } ;           (* приоритеты по таблице *)
binop       = "OR" | "AND" | "=" | "<>" | "<" | "<=" | ">" | ">=" | "LIKE"
            | "+" | "-" | "*" | "/" ;
primary     = literal | column | "(" expr ")" | "NOT" primary ;
column      = [ ident "." ] ident ;
literal     = number | string | "TRUE" | "FALSE" | "NULL" ;

Операторы начинаются с ключевого слова, по которому их сразу видно: посмотреть на первый токен и вызвать нужную функцию. Выражения устроены иначе. У операторов внутри выражения есть приоритеты: OR слабее AND, тот слабее сравнений, те слабее сложения, то слабее умножения. Вместо лесенки из пяти почти одинаковых функций мы разберём выражения одной функцией с таблицей приоритетов. Это Pratt-парсер, мы дойдём до него в середине урока.

В TS-эталоне EXPLAIN и транзакционные команды добавляются к парсеру позже, в уроках 6 и 7. В Haskell-порте верхнеуровневая command есть сразу, и тесты этого урока её уже проверяют. Это три строки кода, а не новая идея.

JOIN, ORDER BY и LIMIT парсер понимает, а движок в уроке 6 отвергнет их как упражнения. Парсить их сейчас полезно: грамматика сразу целая, и упражнения урока 6 не будут трогать фронтенд.