Java Software Engineer

Як виконується SQL-запит

2 хв тому 9 хв читати

Зміст

Етап 0. Що ми маємо на вході
Чому не можна просто "виконати стрінгу"?
Frontend vs Backend
Теорія. Формальні граматики
Етап 1. Лексичний аналіз (Lexer)
Етап 2. Синтаксичний аналіз (Parser) + побудова AST
Етап 3. Семантичний аналіз
Навіщо два плани — логічний і фізичний?
Етап 4. Логічний план (Logical Plan)
Етап 5. Оптимізація логічного плану
Етап 6. Фізичний план (Physical Plan)
- Моделі виконання
- Для зацікавлених. Як виглядає Volcano model у коді
Етап 7. Виконання (Execution)
Повний флоу. Схематично
Висновки
- Найскладніші частини
- Де найбільше впливу на швидкість

Сьогодні розберемо, що відбувається з вашим SELECT * FROM users WHERE age > 21 перед тим, як БД поверне вам дані. Спойлер — на жаль, не магія, а просто багато кроків 🚬

Етап 0. Що ми маємо на вході

SELECT name FROM users WHERE age > 21

Це просто стрінга. База даних не розуміє текст — їй потрібна структура, з якою можна працювати.

Чому не можна просто "виконати стрінгу"?

Проблема в тому, що комп'ютер не розуміє текст. Йому потрібні:

Структура — дерево операцій, а не лінійний текст
Валідація — перевірка що таблиці/колонки існують
Оптимізація — вибір найшвидшого способу виконання

Тому SQL-запит проходить через pipeline обробки, схожий на компіляцію програми. Різниця в тому, що компілятор генерує машинний код, а СУБД генерує план виконання для свого execution engine.

Frontend vs Backend

Весь процес можна розділити на дві частини:

Frontend (фронтенд) — аналіз запиту:

Лексер → Парсер → AST → Семантичний аналіз
Результат: валідне AST дерево

Backend (бекенд) — виконання запиту:

Logical Plan → Optimizer → Physical Plan → Execution
Результат: дані з БД

Це класичний поділ, який є в будь-якому компіляторі/інтерпретаторі.

Теорія. Формальні граматики

Перед тим як розбирати етапи, швидкий екскурс в теорію.

Регулярна граматика (для токенів):

Описує токени (зазвичай через regex, але не обов'язково).
Не може описати вкладені структури типу (a + (b * c)).
Реалізується через FSM (скінченний автомат).

Приклад:

IDENTIFIER = [a-zA-Z_][a-zA-Z0-9_]*
NUMBER     = [0-9]+

Контекстно-вільна граматика (для синтаксису):

Описує синтаксис через правила типу Expression → Term + Term.
Може описати вкладені структури: Expression → ( Expression ).
Формати — BNF, EBNF, або прямо в коді (recursive descent).
Не може описати контекстно-залежні правила (типу "змінна має бути оголошена перед використанням").

Приклад EBNF:

SelectStatement → SELECT ColumnList FROM Identifier (WHERE Condition)?
ColumnList      → Identifier (, Identifier)*
Condition       → Identifier Operator Literal
Operator        → = | > | < | >= | <= | !=

Тепер розберемо як це застосовується на практиці.

FRONTEND. Аналіз запиту

Етап 1. Лексичний аналіз (Lexer)

Що робить — розбиває стрінгу на токени (лексеми), найменші смислові одиниці.

Приклад:

"SELECT name FROM users WHERE age > 21"
↓
[SELECT] [name] [FROM] [users] [WHERE] [age] [>] [21]

Кожен токен має тип:

SELECT → KEYWORD
name → IDENTIFIER
FROM → KEYWORD
users → IDENTIFIER
WHERE → KEYWORD
age → IDENTIFIER
> → OPERATOR
21 → NUMBER

Формальна граматика для лексера зазвичай базується на регулярних виразах, але це не єдиний варіант. Можна писати hand-written лексер (проходити по символах вручну) або використовувати генератори типу ANTLR/Flex.

Приклад через regex:

KEYWORD   = "SELECT" | "FROM" | "WHERE" | ...
IDENTIFIER = [a-zA-Z_][a-zA-Z0-9_]*
NUMBER    = [0-9]+
OPERATOR  = ">" | "<" | "=" | ...

Лексер не розуміє семантику — він просто розпізнає патерни. Навіть SEELCT (з помилкою) він сприйме як IDENTIFIER, бо не знає, що це має бути KEYWORD.

Варіанти реалізації:

ANTLR/Flex (генератори лексерів)
Hand-written лексер (написаний вручну через FSM або посимвольний обхід)
Regex-based (Pattern matching в Java/Python)

Етап 2. Синтаксичний аналіз (Parser) + побудова AST

Що робить — перевіряє граматичну коректність і будує дерево.

Тут є два підходи:

Підхід 1 — Parse Tree, потім AST (класичний):

Parser будує Parse Tree (дослівне відображення граматики)
AST Builder спрощує його до AST

Підхід 2 — одразу AST (сучасний):

Parser будує AST "на льоту", без проміжного Parse Tree
Так роблять багато сучасних БД (PostgreSQL, MySQL)

Ми розглянемо класичний підхід для розуміння.

Parse Tree

Приклад Parse Tree:

SelectStatement
├── SELECT
├── ColumnList
│   └── name
├── FROM
├── TableName
│   └── users
├── WHERE
└── Condition
    ├── age
    ├── >
    └── 21

Parse tree — це дослівне відображення граматики. Тут є всі проміжні вузли (ColumnList, Condition), навіть ті, що не несуть смислового навантаження.

Варіанти реалізації парсера:

ANTLR, Bison (генератори парсерів)
Recursive descent parser (написаний вручну)
Parser combinators (функціональний підхід)
LR/LALR парсери (для складних граматик)

AST (Abstract Syntax Tree)

Що робить AST Builder — спрощує Parse Tree, прибираючи зайві вузли і залишаючи тільки смислові.

Приклад AST:

SelectNode
├── columns: [name]
├── table: users
└── condition:
    └── BinaryOpNode
        ├── left: age
        ├── operator: >
        └── right: 21

AST — це структура даних (зазвичай дерево об'єктів), з якою можна працювати програмно. Це вже не текст і не токени — це Java/C++/Python об'єкти типу SelectNode, BinaryOpNode, тощо.

Код в Java (приблизно):

class SelectNode {
    List<String> columns;
    String table;
    ExpressionNode condition;
}

class BinaryOpNode implements ExpressionNode {
    String left;
    String operator;
    int right;
}

Parse Tree vs AST. В чому різниця?

Parse Tree:

Відображає граматику дослівно
Багато проміжних вузлів
ColumnList → name
Містить токени типу SELECT, FROM

AST:

Відображає структуру програми
Тільки важливі вузли
Просто name
Не містить ключових слів

PS: В деяких оптимізаторах AST може перетворюватися в граф (для common subexpression elimination, мемоізації тощо).

Що парсер НЕ робить

Не перевіряє, чи існує таблиця users в базі.
Не перевіряє, чи є колонка age в цій таблиці.
Не перевіряє типи (чи можна порівнювати age з 21).

Парсер просто каже — "Окей, синтаксично це виглядає як SELECT-запит".

Етап 3. Семантичний аналіз

Що робить — перевіряє змістову коректність запиту.

Перевірки:

Існування таблиць — чи є таблиця users в схемі БД?
Існування колонок — чи є колонка age в таблиці users?
Типи даних — чи можна порівнювати age (INT) з 21 (INT)? А якщо age — це VARCHAR, то помилка.
Права доступу — чи має користувач право читати з users?

Приклад помилок:

SELECT name FROM nonexistent_table WHERE age > 21
-- ERROR: Table 'nonexistent_table' does not exist

SELECT name FROM users WHERE age > 'twenty-one'
-- ERROR: Cannot compare INT with VARCHAR

Семантичний аналізатор працює з метаданими БД (schema catalog) — інформацією про таблиці, колонки, типи, індекси тощо.

Після цього етапу ми маємо валідне AST дерево, готове до перетворення в план виконання.

BACKEND. Виконання запиту

Навіщо два плани — логічний і фізичний?

Логічний план відповідає на питання "ЩО робити?":

Прочитати users
Відфільтрувати age > 21
Вибрати колонку name

Фізичний план відповідає на питання "ЯК саме робити?":

Прочитати через IndexScan чи SequentialScan?
Скільки пам'яті виділити під буфер?
Чи сортувати результат на диску чи в пам'яті?

Розділення дозволяє:

Оптимізувати логічний план (перестановка операцій) незалежно від деталей реалізації
Вибрати найкращий фізичний план залежно від статистики/індексів

Етап 4. Логічний план (Logical Plan)

Що робить — перетворює AST в алгебраїчні операції реляційної алгебри.

Приклад:

AST:
SelectNode(columns=[name], table=users, condition=age>21)

↓

Logical Plan:
Projection(name)
└── Filter(age > 21)
    └── TableScan(users)

Це дерево операторів, де кожен оператор — це абстрактна операція:

TableScan(users) — прочитати всі рядки з users.
Filter(age > 21) — відфільтрувати рядки, де age > 21.
Projection(name) — вибрати тільки колонку name.

Логічний план не залежить від того, як саме дані зберігаються (файли, B-tree, LSM-tree тощо). Це абстракція.

Етап 5. Оптимізація логічного плану

Що робить — перетворює логічний план в ефективніший логічний план.

Приклади оптимізацій:

1. Predicate pushdown (проштовхування фільтрів):

Projection(name)
└── Filter(age > 21)
    └── TableScan(users)

↓ (якщо є індекс на age)

Projection(name)
└── IndexScan(users, age > 21)  ← фільтр застосовується на етапі читання

2. Projection pushdown (проштовхування проекцій):

Projection(name)
└── TableScan(users)  ← читає всі колонки

↓

TableScan(users, columns=[name])  ← читає тільки name

3. Join reordering (для JOIN-ів):

A JOIN B JOIN C
↓
(A JOIN C) JOIN B  ← якщо A JOIN C дає менше рядків

Оптимізатор використовує:

Статистику (скільки рядків в таблиці, розподіл значень).
Інформацію про індекси.
Cost-based model (оцінка вартості виконання кожного плану).

Етап 6. Фізичний план (Physical Plan)

Що робить — перетворює логічний план в конкретні реалізації операторів.

Приклад:

Logical:
Filter(age > 21)

↓

Physical (варіанти):
1. SequentialScanFilter(age > 21)  ← послідовне читання всіх рядків
2. IndexScanFilter(age > 21)       ← використання B-tree індексу на age

Фізичний план залежить від:

Наявності індексів.
Розміру таблиці.
Доступної пам'яті.

Моделі виконання

Volcano model (iterator model) — найпопулярніший:

Кожен оператор має метод next(), який повертає один рядок
Виконання — це ланцюжок викликів next() від кореня до листя
Приклад: ProjectionOp.next() → FilterOp.next() → TableScanOp.next()

Інші моделі:

Materialization model — оператор повертає всі рядки відразу
Vectorized execution (columnar) — обробка батчами (DuckDB, ClickHouse)

Для зацікавлених. Як виглядає Volcano model у коді

interface Operator {
    void open();
    Row next();
    void close();
}

class FilterOperator implements Operator {
    Operator child;
    Predicate condition;
    
    Row next() {
        while (true) {
            Row row = child.next();
            if (row == null) return null;
            if (condition.test(row)) return row;
        }
    }
}

Кожен оператор — це ітератор, який повертає рядки. Виконання — це виклик next() на кореневому операторі.

Етап 7. Виконання (Execution)

Що робить — фізичний план виконується над storage engine.

Приклад для нашого запиту:

1. ProjectionOperator.next()
   ↓
2. FilterOperator.next()
   ↓ (перевіряє умову age > 21)
3. TableScanOperator.next()
   ↓ (читає рядок з диску)
4. StorageEngine.readRow(page_id, slot_id)

Storage Engine читає дані:

З диску (heap file, B-tree, LSM-tree)
З пам'яті (in-memory БД типу Redis, MemSQL)
Гібридний підхід (кешування в пам'яті + диск)

Результат — рядки, що задовольняють умову, повертаються через ітератор.

Повний флоу. Схематично

SQL Query (string)
    ↓
━━━━━━━━━━━━━━━━━━━━━━
    FRONTEND
━━━━━━━━━━━━━━━━━━━━━━
    ↓
Lexer
    ↓
Tokens: [SELECT, name, FROM, users, WHERE, age, >, 21]
    ↓
Parser
    ↓
Parse Tree (дослівне відображення граматики)
    ↓
AST Builder
    ↓
AST (спрощене дерево)
SelectNode(columns=[name], table=users, condition=age>21)
    ↓
Semantic Analyzer
    ↓
Validated AST (перевірка таблиць, колонок, типів, прав)
    ↓
━━━━━━━━━━━━━━━━━━━━━━
    BACKEND
━━━━━━━━━━━━━━━━━━━━━━
    ↓
Logical Planner
    ↓
Logical Plan (реляційна алгебра)
Projection(name) → Filter(age > 21) → TableScan(users)
    ↓
Optimizer
    ↓
Optimized Logical Plan (predicate/projection pushdown)
    ↓
Physical Planner
    ↓
Physical Plan (конкретні реалізації)
IndexScan + Filter + Projection
    ↓
Execution Engine
    ↓
Виконання через ітератори (Volcano model)
    ↓
Storage Engine
    ↓
Читання даних (heap file / B-tree / LSM-tree)
    ↓
Results → User

Висновки

Лексер розбиває стрінгу на токени (зазвичай regex, але може бути hand-written чи генератор).
Парсер будує Parse Tree (CFG).
AST Builder спрощує Parse Tree → AST.
Семантичний аналізатор перевіряє коректність (таблиці, колонки, типи).
Logical Planner будує логічний план (реляційна алгебра).
Optimizer оптимізує план (pushdown, join reordering).
Physical Planner генерує фізичний план (конкретні реалізації).
Execution Engine виконує план (Volcano model, ітератори).
Storage Engine читає дані з диску/пам'яті.

Parse Tree vs AST:

Parse Tree — дослівне відображення граматики (багато зайвих вузлів).
AST — смислова структура програми (тільки важливі вузли).

Найскладніші частини

Optimizer — cost-based оптимізація вимагає точної статистики
Execution Engine — багато edge cases, deadlocks, транзакції
Concurrency Control — ACID, ізоляція, блокування

Де найбільше впливу на швидкість

Вибір індексів (фізичний план) — різниця між seq scan і index scan може бути в 100-1000 разів
Join ordering (оптимізатор) — неправильний порядок JOIN-ів може збільшити час виконання на порядки
Storage Engine (як дані лежать на диску) — row-based vs column-based, compression, partitioning

Machine Learning на пальцях. Детекція фродових запитів

Стратегічний дизайн виключень

Як насправді працює @Async у Spring і коли його використання створює більше проблем, ніж вирішує

Як виконується SQL-запит

Етап 0. Що ми маємо на вході

Чому не можна просто "виконати стрінгу"?

Frontend vs Backend

Теорія. Формальні граматики

Етап 1. Лексичний аналіз (Lexer)

Етап 2. Синтаксичний аналіз (Parser) + побудова AST

Parse Tree

AST (Abstract Syntax Tree)

Parse Tree vs AST. В чому різниця?

Що парсер НЕ робить

Етап 3. Семантичний аналіз

Навіщо два плани — логічний і фізичний?

Етап 4. Логічний план (Logical Plan)

Етап 5. Оптимізація логічного плану

Етап 6. Фізичний план (Physical Plan)

Моделі виконання

Для зацікавлених. Як виглядає Volcano model у коді

Етап 7. Виконання (Execution)

Повний флоу. Схематично

Висновки

Найскладніші частини

Де найбільше впливу на швидкість

Більше від автора

Machine Learning на пальцях. Детекція фродових запитів

Стратегічний дизайн виключень

Як насправді працює @Async у Spring і коли його використання створює більше проблем, ніж вирішує

Вам також сподобається

Як почати вивчення програмування

[Frontend] Універсальні рішення

Роль кібербезпеки у сучасних військових конфліктах

Коментарі (0)

Вам також сподобається

Як почати вивчення програмування

[Frontend] Універсальні рішення

Роль кібербезпеки у сучасних військових конфліктах

Machine Learning на пальцях. Детекція фродових запитів

Теми цього довгочиту:

Стратегічний дизайн виключень

Теми цього довгочиту:

Як насправді працює @Async у Spring і коли його використання створює більше проблем, ніж вирішує

Теми цього довгочиту:

Етап 0. Що ми маємо на вході

Чому не можна просто "виконати стрінгу"?

Frontend vs Backend

Теорія. Формальні граматики

Етап 1. Лексичний аналіз (Lexer)

Етап 2. Синтаксичний аналіз (Parser) + побудова AST

Parse Tree

AST (Abstract Syntax Tree)

Parse Tree vs AST. В чому різниця?

Що парсер НЕ робить

Етап 3. Семантичний аналіз

Навіщо два плани — логічний і фізичний?

Етап 4. Логічний план (Logical Plan)

Етап 5. Оптимізація логічного плану

Етап 6. Фізичний план (Physical Plan)

Моделі виконання

Для зацікавлених. Як виглядає Volcano model у коді

Етап 7. Виконання (Execution)

Повний флоу. Схематично

Висновки

Найскладніші частини

Де найбільше впливу на швидкість

Більше від автора

Machine Learning на пальцях. Детекція фродових запитів

Теми цього довгочиту:

Стратегічний дизайн виключень

Теми цього довгочиту:

Як насправді працює @Async у Spring і коли його використання створює більше проблем, ніж вирішує

Теми цього довгочиту:

Вам також сподобається

Як почати вивчення програмування

Теми цього довгочиту:

[Frontend] Універсальні рішення

Теми цього довгочиту:

Роль кібербезпеки у сучасних військових конфліктах

Теми цього довгочиту:

Коментарі (0)

Вам також сподобається

Як почати вивчення програмування

Теми цього довгочиту:

[Frontend] Універсальні рішення

Теми цього довгочиту:

Роль кібербезпеки у сучасних військових конфліктах

Теми цього довгочиту: