Сбор, хранение, преобразование и представление данных — основные задачи, стоящие перед дата-инженерами.
Отдел бизнес-аналитики Badoo получает и обрабатывает более 20 миллиардов событий в день, отправляемых с пользовательских устройств, или 2 ТБ входящих данных.
Исследование и интерпретация всех этих данных не всегда является тривиальной задачей; иногда возникает необходимость выйти за рамки возможностей готовых баз данных.
И если вы набрались смелости и решили сделать что-то новое, вам следует сначала ознакомиться с принципами работы существующих решений.
Короче говоря, эта статья адресована любознательным и волевым разработчикам.
В нем вы найдете описание традиционной модели выполнения запросов в реляционных базах данных на примере демонстрационного языка PigletQL. Содержание
Фон Наша группа инженеров работает над бэкендами и интерфейсами, которые предоставляют возможности анализа и исследования данных внутри компании (кстати, мы расширение ).Наши стандартные инструменты — распределенная база данных для десятков серверов (Exasol) и кластер Hadoop для сотен машин (Hive и Presto).
Большинство запросов к этим базам данных являются аналитическими, то есть затрагивают от сотен тысяч до миллиардов записей.
Они занимают минуты, десятки минут или даже часы, в зависимости от используемого решения и сложности запроса.
Для ручной работы пользователя-аналитика это время считается приемлемым, но для интерактивного исследования через пользовательский интерфейс оно не подходит. Со временем мы определили популярные аналитические запросы и запросы, сложно выразить словами SQL и разработали для них небольшие специализированные базы данных.
Они хранят подмножество данных в формате, подходящем для облегченных алгоритмов сжатия (например,streamvbyte), что позволяет хранить данные за несколько дней в памяти одной машины и выполнять запросы за секунды.
Первые языки запросов к этим данным и их интерпретаторы были реализованы по прихоти; нам приходилось постоянно их дорабатывать, и каждый раз это занимало непомерно много времени.
Языки запросов оказались недостаточно гибкими, хотя очевидных причин для ограничения их возможностей не было.
В результате мы обратились к опыту разработчиков интерпретаторов SQL, благодаря чему смогли частично решить возникшие проблемы.
Ниже я расскажу о самой распространенной модели выполнения запросов в реляционных базах данных — Volcano. К статье прилагается исходный код примитивного диалектного интерпретатора SQL — ПятачокQL , поэтому любой желающий может легко просмотреть подробности в репозитории.
Структура интерпретатора SQL 
Большинство популярных баз данных предоставляют интерфейс к данным в форме декларативного языка запросов SQL. Строковый запрос преобразуется анализатором в описание запроса, подобное абстрактному синтаксическому дереву.
Уже на этом этапе можно выполнять простые запросы, но для оптимизации преобразований и последующего выполнения такое представление неудобно.
В известных мне базах данных для этих целей вводятся промежуточные представления.
Реляционная алгебра стала моделью промежуточных представлений.
Это язык, в котором преобразования описываются явно ( операторы ), осуществляемые над данными: выделение подмножества данных по предикату, соединение данных из разных источников и т. д. Кроме того, реляционная алгебра является алгеброй в математическом смысле, то есть для нее формализовано большое количество эквивалентных преобразований.
Поэтому удобно проводить оптимизирующие преобразования над запросом в виде дерева операторов реляционной алгебры.
Между внутренними представлениями в базах данных и исходной реляционной алгеброй имеются важные различия, поэтому правильнее называть ее логическая алгебра .
Проверка валидности запроса обычно осуществляется при компиляции исходного представления запроса в операторы логической алгебры и соответствует этапу семантического анализа в обычных компиляторах.
Роль таблицы символов в базах данных играет каталог базы данных , в котором хранится информация о схеме базы данных и метаданные: таблицы, столбцы таблиц, индексы, права пользователей и т. д. По сравнению с интерпретаторами языков общего назначения интерпретаторы баз данных имеют еще одну особенность: различия в объеме данных и метаинформации о данных, которые предполагается запрашивать.
В таблицах или отношениях с точки зрения реляционной алгебры в некоторых столбцах может быть разное количество данных ( атрибуты отношения) могут строиться индексы и т. д. То есть в зависимости от схемы базы данных и объема данных в таблицах запрос должен выполняться по разным алгоритмам и использоваться в разном порядке.
Для решения этой проблемы вводится еще одно промежуточное представление – физическая алгебра .
В зависимости от наличия индексов по столбцам, объема данных в таблицах и структуры дерева логической алгебры предлагаются разные формы дерева физической алгебры, из которых выбирается оптимальный вариант. Именно это дерево отображается в базе данных в виде плана запроса.
В традиционных компиляторах этот этап условно соответствует этапам выделения регистров, планирования и выбора инструкций.
Последний этап работы интерпретатора — непосредственное выполнение дерева операторов физической алгебры.
Модель вулкана и выполнение запроса Интерпретаторы деревьев физической алгебры в частных коммерческих базах данных использовались почти всегда, но в академической литературе обычно упоминается экспериментальный оптимизатор Volcano, разработанный в начале 90-х годов.
В модели Вулкана каждый оператор дерева физической алгебры превращен в структуру с тремя функциями: открыть, следующий, закрыть.
Помимо функций, оператор содержит рабочее состояние — состояние.
Функция открытия инициирует состояние оператора, следующая функция возвращает либо следующую кортеж (английский кортеж), или NULL, если кортежей не осталось, функция close завершает оператор: 
Операторы могут быть вложены друг в друга, образуя дерево операторов физической алгебры.
Таким образом, каждый оператор перебирает кортежи либо отношения, существующего в реальной среде, либо виртуального отношения, сформированного путем перечисления кортежей вложенных операторов: 
С точки зрения современных языков высокого уровня дерево таких операторов представляет собой каскад итераторов.
Даже промышленные интерпретаторы запросов в реляционных СУБД основаны на модели Volcano, поэтому я взял ее за основу интерпретатора PigletQL.
ПятачокQL 
Чтобы продемонстрировать модель, я разработал интерпретатор для ограниченного языка запросов.
Он написан на C, поддерживает создание таблиц в стиле SQL, но ограничен одним типом: 32-битными положительными целыми числами.
Все таблицы расположены в памяти.
Система работает в одном потоке и не имеет механизма транзакций.
PigletQL не имеет оптимизатора, а запросы SELECT компилируются непосредственно в дерево операторов физической алгебры.
Остальные запросы (CREATE TABLE и INSERT) работают непосредственно из основных внутренних представлений.
Пример пользовательской сессии в PigletQL:
> ./pigletql > CREATE TABLE tab1 (col1,col2,col3); > INSERT INTO tab1 VALUES (1,2,3); > INSERT INTO tab1 VALUES (4,5,6); > SELECT col1,col2,col3 FROM tab1; col1 col2 col3 1 2 3 4 5 6 rows: 2 > SELECT col1 FROM tab1 ORDER BY col1 DESC; col1 4 1 rows: 2
Лексические и парсер-анализаторы
PigletQL — очень простой язык, и его реализация не потребовала использования сторонних инструментов на этапах лексического и синтаксического анализа.Лексический анализатор написан вручную.
Объект анализатора создается из строки запроса ( Scanner_t ), который раздает жетоны один за другим: scanner_t *scanner_create(const char *string);
void scanner_destroy(scanner_t *scanner);
token_t scanner_next(scanner_t *scanner);
Синтаксический анализ осуществляется методом рекурсивного спуска.
Сначала создается объект parser_t , который, получив лексический анализатор (scanner_t), заполняет объект query_t информацией о запросе: query_t *query_create(void);
void query_destroy(query_t *query);
parser_t *parser_create(void);
void parser_destroy(parser_t *parser);
bool parser_parse(parser_t *parser, scanner_t *scanner, query_t *query);
Результат анализа query_t — это один из трёх типов запросов, поддерживаемых PigletQL: typedef enum query_tag {
QUERY_SELECT,
QUERY_CREATE_TABLE,
QUERY_INSERT,
} query_tag;
/*
* .
query_select_t, query_create_table_t, query_insert_t definitions .
**/
typedef struct query_t {
query_tag tag;
union {
query_select_t select;
query_create_table_t create_table;
query_insert_t insert;
} as;
} query_t;
Самый сложный тип запроса в PigletQL — SELECT. Это соответствует структуре данных query_select_t : typedef struct query_select_t {
/* Attributes to output */
attr_name_t attr_names[MAX_ATTR_NUM];
uint16_t attr_num;
/* Relations to get tuples from */
rel_name_t rel_names[MAX_REL_NUM];
uint16_t rel_num;
/* Predicates to apply to tuples */
query_predicate_t predicates[MAX_PRED_NUM];
uint16_t pred_num;
/* Pick an attribute to sort by */
bool has_order;
attr_name_t order_by_attr;
sort_order_t order_type;
} query_select_t;
Структура содержит описание запроса (массив атрибутов, запрошенных пользователем), список источников данных — связей, массив предикатов, фильтрующих кортежи, и информацию об атрибуте, используемом для сортировки результатов.
Семантический анализатор
Фаза семантического анализа в обычном SQL включает проверку существования перечисленных таблиц, проверку существования столбцов в таблицах и проверку типов в выражениях запроса.Для проверок, связанных с таблицами и столбцами, используется каталог базы данных, где хранится вся информация о структуре данных.
В PigletQL нет сложных выражений, поэтому проверка запроса сводится к проверке метаданных таблиц и столбцов в каталоге.
Запросы SELECT, например, проверяются функцией validate_select .
Приведу в сокращенном виде: static bool validate_select(catalogue_t *cat, const query_select_t *query)
{
/* All the relations should exist */
for (size_t rel_i = 0; rel_i < query->rel_num; rel_i++) {
if (catalogue_get_relation(cat, query->rel_names[rel_i]))
continue;
fprintf(stderr, "Error: relation '%s' does not exist\n", query->rel_names[rel_i]);
return false;
}
/* Relation names should be unique */
if (!rel_names_unique(query->rel_names, query->rel_num))
return false;
/* Attribute names should be unique */
if (!attr_names_unique(query->attr_names, query->attr_num))
return false;
/* Attributes should be present in relations listed */
/* .
*/ /* ORDER BY attribute should be available in the list of attributes chosen */ /* .
*/ /* Predicate attributes should be available in the list of attributes projected */ /* .
*/
return true;
}
Если запрос валидный, то следующим шагом будет компиляция дерева разбора в дерево операторов.
Компиляция запросов в промежуточное представление
В полноценных интерпретаторах SQL обычно имеется два промежуточных представления: логическая и физическая алгебра.
Простой интерпретатор PigletQL выполняет запросы CREATE TABLE и INSERT непосредственно из своих деревьев разбора, то есть структур query_create_table_t И query_insert_t .
Более сложные запросы SELECT компилируются в одно промежуточное представление, которое будет выполняться интерпретатором.
Дерево операторов строится от листьев к корню в следующей последовательности:
- Из правой части запроса («… ИЗ отношения1, отношения2,…») получаются имена искомых отношений, для каждого из которых создается оператор сканирования.
- Операторы сканирования, извлекающие кортежи из отношений, объединяются в левостороннее двоичное дерево с помощью оператора соединения.
- Атрибуты, запрошенные пользователем («SELECT attr1, attr2, .
»), выбираются оператором проекта.
- Если указаны какие-либо предикаты («.
WHERE a=1 AND b> 10 .
»), то в верхнюю часть дерева добавляется оператор выбора.
- Если указан метод сортировки результата (".
ORDER BY attr1 DESC"), то оператор сортировки добавляется в начало дерева.
operator_t *compile_select(catalogue_t *cat, const query_select_t *query)
{
/* Current root operator */
operator_t *root_op = NULL;
/* 1. Scan ops */
/* 2. Join ops*/
{
size_t rel_i = 0;
relation_t *rel = catalogue_get_relation(cat, query->rel_names[rel_i]);
root_op = scan_op_create(rel);
rel_i += 1;
for (; rel_i < query->rel_num; rel_i++) {
rel = catalogue_get_relation(cat, query->rel_names[rel_i]);
operator_t *scan_op = scan_op_create(rel);
root_op = join_op_create(root_op, scan_op);
}
}
/* 3. Project */
root_op = proj_op_create(root_op, query->attr_names, query->attr_num);
/* 4. Select */
if (query->pred_num > 0) {
operator_t *select_op = select_op_create(root_op);
for (size_t pred_i = 0; pred_i < query->pred_num; pred_i++) {
query_predicate_t predicate = query->predicates[pred_i];
/* Add a predicate to the select operator */
/* .
*/
}
root_op = select_op;
}
/* 5. Sort */
if (query->has_order)
root_op = sort_op_create(root_op, query->order_by_attr, query->order_type);
return root_op;
}
После формирования дерева обычно проводятся оптимизирующие преобразования, но PigletQL сразу переходит к этапу выполнения промежуточного представления.
Выполнение промежуточного представления
Модель «Вулкан» подразумевает интерфейс для работы с операторами посредством трёх распространённых операций: открыть/следующий/закрыть.
По сути, каждый оператор Volcano представляет собой итератор, из которого один за другим «вытягиваются» кортежи, поэтому такой подход к выполнению еще называют моделью извлечения.
Каждый из этих итераторов сам может вызывать те же функции вложенных итераторов, формировать временные таблицы с промежуточными результатами и преобразовывать входящие кортежи.
Производительность ВЫБРАТЬ запросы в ПятачкеQL: bool eval_select(catalogue_t *cat, const query_select_t *query)
{
/* Compile the operator tree: */
operator_t *root_op = compile_select(cat, query);
/* Eval the tree: */
{
root_op->open(root_op->state);
size_t tuples_received = 0;
tuple_t *tuple = NULL;
while((tuple = root_op->next(root_op->state))) {
/* attribute list for the first row only */
if (tuples_received == 0)
dump_tuple_header(tuple);
/* A table of tuples */
dump_tuple(tuple);
tuples_received++;
}
printf("rows: %zu\n", tuples_received);
root_op->close(root_op->state);
}
root_op->destroy(root_op);
return true;
}
Запрос сначала компилируется функцией compile_select, которая возвращает корень дерева операторов, после чего у корневого оператора вызываются те же функции открытия/следующего/закрытия.
Каждый вызов next возвращает либо следующий кортеж, либо NULL. В последнем случае это означает, что все кортежи были получены и необходимо вызвать функцию close, чтобы закрыть итератор.
Полученные кортежи пересчитываются и выводятся в виде таблицы в стандартный поток вывода.
Операторы
Самое интересное в PigletQL — это дерево операторов.Я покажу структуру некоторых из них.
Интерфейс операторы имеют общий и состоят из указателей на функции открытия/следующего/закрытия и дополнительной служебной функции уничтожения, которая освобождает ресурсы всего дерева операторов сразу: typedef void (*op_open)(void *state);
typedef tuple_t *(*op_next)(void *state);
typedef void (*op_close)(void *state);
typedef void (*op_destroy)(operator_t *op);
/* The operator itself is just 4 pointers to related ops and operator state */
struct operator_t {
op_open open;
op_next next;
op_close close;
op_destroy destroy;
void *state;
} ;
Помимо функций, оператор может содержать произвольное внутреннее состояние (указатель состояния).
Ниже я разберу структуру двух интересных операторов: самого простого сканирования и того, который создает сортировку промежуточным отношением.
оператор сканирования
Оператор, с которого начинается выполнение любого запроса, — scan. Он просто перебирает все кортежи отношения.
Состояние внутреннего сканирования — это указатель на отношение, из которого будут извлечены кортежи, индекс следующего кортежа в отношении и ссылочная структура на текущий кортеж, передаваемый пользователю: typedef struct scan_op_state_t {
/* A reference to the relation being scanned */
const relation_t *relation;
/* Next tuple index to retrieve from the relation */
uint32_t next_tuple_i;
/* A structure to be filled with references to tuple data */
tuple_t current_tuple;
} scan_op_state_t;
Чтобы создать состояние оператора сканирования, требуется отношение источника; все остальное (указатели на соответствующие функции) уже известно: operator_t *scan_op_create(const relation_t *relation)
{
operator_t *op = calloc(1, sizeof(*op));
assert(op);
*op = (operator_t) {
.
open = scan_op_open, .
next = scan_op_next, .
close = scan_op_close, .
destroy = scan_op_destroy, }; scan_op_state_t *state = calloc(1, sizeof(*state)); assert(state); *state = (scan_op_state_t) { .
relation = relation, .
next_tuple_i = 0, .
current_tuple.tag = TUPLE_SOURCE, .
current_tuple.as.source.tuple_i = 0, .
current_tuple.as.source.relation = relation,
};
op->state = state;
return op;
}
Операции открытия/закрытия при сбросе случая сканирования ссылаются обратно на первый элемент отношения: void scan_op_open(void *state)
{
scan_op_state_t *op_state = (typeof(op_state)) state;
op_state->next_tuple_i = 0;
tuple_t *current_tuple = &op_state->current_tuple;
current_tuple->as.source.tuple_i = 0;
}
void scan_op_close(void *state)
{
scan_op_state_t *op_state = (typeof(op_state)) state;
op_state->next_tuple_i = 0;
tuple_t *current_tuple = &op_state->current_tuple;
current_tuple->as.source.tuple_i = 0;
}
Вызов next либо возвращает следующий кортеж, либо NULL, если в отношении больше нет кортежей: tuple_t *scan_op_next(void *state)
{
scan_op_state_t *op_state = (typeof(op_state)) state;
if (op_state->next_tuple_i >= op_state->relation->tuple_num)
return NULL;
tuple_source_t *source_tuple = &op_state->current_tuple.as.source;
source_tuple->tuple_i = op_state->next_tuple_i;
op_state->next_tuple_i++;
return &op_state->current_tuple;
}
оператор сортировки
Оператор сортировки создает кортежи в указанном пользователем порядке.Для этого вам необходимо создать временное отношение с кортежами, полученными из вложенных операторов, и отсортировать его.
Внутреннее состояние оператор: typedef struct sort_op_state_t {
operator_t *source;
/* Attribute to sort tuples by */
attr_name_t sort_attr_name;
/* Sort order, descending or ascending */
sort_order_t sort_order;
/* Temporary relation to be used for sorting*/
relation_t *tmp_relation;
/* Relation scan op */
operator_t *tmp_relation_scan_op;
} sort_op_state_t;
Сортировка осуществляется по указанным в запросе атрибутам (sort_attr_name и sort_order) по временному отношению (tmp_relation).
Все это происходит во время вызова функции open: void sort_op_open(void *state)
{
sort_op_state_t *op_state = (typeof(op_state)) state;
operator_t *source = op_state->source;
/* Materialize a table to be sorted */
source->open(source->state);
tuple_t *tuple = NULL;
while((tuple = source->next(source->state))) {
if (!op_state->tmp_relation) {
op_state->tmp_relation = relation_create_for_tuple(tuple);
assert(op_state->tmp_relation);
op_state->tmp_relation_scan_op = scan_op_create(op_state->tmp_relation);
}
relation_append_tuple(op_state->tmp_relation, tuple);
}
source->close(source->state);
/* Sort it */
relation_order_by(op_state->tmp_relation, op_state->sort_attr_name, op_state->sort_order);
/* Open a scan op on it */
op_state->tmp_relation_scan_op->open(op_state->tmp_relation_scan_op->state);
}
Элементы временного отношения перечисляются с помощью временного оператора tmp_relation_scan_op: tuple_t *sort_op_next(void *state)
{
sort_op_state_t *op_state = (typeof(op_state)) state;
return op_state->tmp_relation_scan_op->next(op_state->tmp_relation_scan_op->state);;
}
Временное отношение освобождается в функции close: void sort_op_close(void *state)
{
sort_op_state_t *op_state = (typeof(op_state)) state;
/* If there was a tmp relation - destroy it */
if (op_state->tmp_relation) {
op_state->tmp_relation_scan_op->close(op_state->tmp_relation_scan_op->state);
scan_op_destroy(op_state->tmp_relation_scan_op);
relation_destroy(op_state->tmp_relation);
op_state->tmp_relation = NULL;
}
}
Это ясно показывает, почему операции сортировки по столбцам без индексов могут занимать довольно много времени.
Примеры работ
Вот несколько примеров запросов PigletQL и соответствующих им деревьев физической алгебры.
Самый простой пример, когда выбираются все кортежи из отношения: > .
/pigletql
> create table rel1 (a1,a2,a3);
> insert into rel1 values (1,2,3);
> insert into rel1 values (4,5,6);
> select a1 from rel1;
a1
1
4
rows: 2
>
Самый простой запрос использует только тот, который извлекает кортежи из отношения сканирования и выделяет из кортежей один атрибут проекта: 
Выбор кортежей с предикатом: > .
/pigletql
> create table rel1 (a1,a2,a3);
> insert into rel1 values (1,2,3);
> insert into rel1 values (4,5,6);
> select a1 from rel1 where a1 > 3;
a1
4
rows: 1
>
Предикаты выражаются оператором select: 
Выбор кортежей с сортировкой: > .
/pigletql
> create table rel1 (a1,a2,a3);
> insert into rel1 values (1,2,3);
> insert into rel1 values (4,5,6);
> select a1 from rel1 order by a1 desc;
a1
4
1
rows: 2
Оператор сортировки сканирования в открытом вызове создает ( материализуется ) временное отношение, помещает туда все входящие кортежи и сортирует их целиком.
Затем при вызове next он выводит кортежи из временного отношения в указанном пользователем порядке: 
Соединение кортежей двух отношений с предикатом: > .
/pigletql
> create table rel1 (a1,a2,a3);
> insert into rel1 values (1,2,3);
> insert into rel1 values (4,5,6);
> create table rel2 (a4,a5,a6);
> insert into rel2 values (7,8,6);
> insert into rel2 values (9,10,6);
> select a1,a2,a3,a4,a5,a6 from rel1, rel2 where a3=a6;
a1 a2 a3 a4 a5 a6
4 5 6 7 8 6
4 5 6 9 10 6
rows: 2
Оператор соединения в PigletQL не использует никаких сложных алгоритмов, а просто формирует декартово произведение из наборов кортежей левого и правого поддеревьев.
Это очень неэффективно, но для демо-интерпретатора вполне подойдет: 
Выводы И последнее замечание: если вы создаете интерпретатор для языка, похожего на SQL, вам, вероятно, следует просто воспользоваться любой из множества доступных реляционных баз данных.
Тысячи человеко-лет были вложены в современные оптимизаторы и интерпретаторы запросов для популярных баз данных, а разработка даже самых простых баз данных общего назначения занимает в лучшем случае годы.
Демо-язык PigletQL имитирует работу интерпретатора SQL, но на самом деле мы используем только отдельные элементы архитектуры Volcano и только для тех (редких!) типов запросов, которые сложно выразить в рамках реляционной модели.
Тем не менее, повторюсь: даже поверхностное знакомство с архитектурой такого рода интерпретаторов будет полезно в тех случаях, когда нужно гибко работать с потоками данных.
Литература Если вас интересуют основные вопросы разработки баз данных, то лучшей книги, чем «Реализация системы баз данных», вам не найти (Гарсия-Молина Х.
, Ульман Дж.
Д.
, Видом Дж.
, 2000).
Единственным ее недостатком является теоретическая направленность.
Лично мне нравится, когда материал сопровождается конкретными примерами кода или даже демо-проектом.
Для этого вы можете обратиться к книге «Проектирование и реализация баз данных» (Sciore E., 2008), в которой представлен полный код реляционной базы данных на Java. В самых популярных реляционных базах данных до сих пор используются вариации темы Volcano. Оригинальная публикация написана вполне доступным языком, и ее легко найти в Google Scholar: «Вулкан — расширяемая и параллельная система оценки запросов» (Graefe G., 1994).
И хотя детали интерпретаторов SQL довольно сильно изменились за последние десятилетия, сама общая структура этих систем не менялась очень долгое время.
Представление об этом можно получить из обзорной работы того же автора «Методы оценки запросов для больших баз данных» (Graefe G. 1993).
Теги: #программирование #C++ #sql #компиляторы #интерпретатор
-
Ротари Проект
19 Oct, 24 -
Настройка Переключения Вкладок В Unix-Версии
19 Oct, 24 -
Китайская Повседневная Жизнь
19 Oct, 24 -
Скайп: Говорите, Нас Не Слышат.
19 Oct, 24
