Хабрахабр

Вулканический поросенок, или SQL своими руками

data engineer). Сбор, хранение, преобразование и презентация данных — основные задачи, стоящие перед инженерами данных (англ. Отдел Business Intelligence Badoo в сутки принимает и обрабатывает больше 20 млрд событий, отправляемых с пользовательских устройств, или 2 Тб входящих данных.

И если вы набрались смелости и решили делать что-то новое, то следует сначала ознакомиться с принципами работы существующих решений. Исследование и интерпретация всех этих данных — не всегда тривиальные задачи, иногда возникает необходимость выйти за рамки возможностей готовых баз данных.

В ней вы найдёте описание традиционной модели исполнения запросов в реляционных базах данных на примере демонстрационного языка PigletQL. Словом, любопытствующим и сильным духом разработчикам и адресована эта статья.

Наши стандартные инструменты — распределённая база данных на десятки серверов (Exasol) и кластер Hadoop на сотню машин (Hive и Presto). Наша группа инженеров занимается бэкендами и интерфейсами, предоставляющими возможности для анализа и исследования данных внутри компании (к слову, мы расширяемся).

Их выполнение занимает минуты, десятки минут или даже часы в зависимости от используемого решения и сложности запроса. Большая часть запросов к этим базам данных — аналитические, то есть затрагивающие от сотен тысяч до миллиардов записей. При ручной работе пользователя-аналитика такое время считается приемлемым, но для интерактивного исследования через пользовательский интерфейс не подходит.

Они хранят подмножество данных в подходящем для легковесных алгоритмов сжатия формате (например, streamvbyte), что позволяет хранить в памяти одной машины данные за несколько дней и выполнять запросы за секунды. Со временем мы выделили популярные аналитические запросы и запросы, с трудом излагаемые в терминах SQL, и разработали под них небольшие специализированные базы данных.

Первые языки запросов к этим данным и их интерпретаторы были реализованы по наитию, нам приходилось постоянно их дорабатывать, и каждый раз это занимало непозволительно много времени.

В итоге мы обратились к опыту разработчиков интерпретаторов SQL, благодаря чему смогли частично решить возникшие проблемы. Языки запросов получались недостаточно гибкими, хотя очевидных причин для ограничения их возможностей не было.

К статье прилагается исходный код интерпретатора примитивного диалекта SQL — PigletQL, поэтому все интересующиеся легко смогут ознакомиться с деталями в репозитории. Ниже я расскажу про самую распространённую модель выполнения запросов в реляционных базах данных — Volcano.

Структура интерпретатора

Запрос в виде строки преобразуется синтаксическим анализатором в описание запроса, похожее на дерево абстрактного синтаксиса. Большая часть популярных баз данных предоставляет интерфейс к данным в виде декларативного языка запросов SQL. В известных мне базах данных для этих целей вводятся промежуточные представления. Несложные запросы возможно выполнять уже на этом этапе, однако для оптимизирующих преобразований и последующего исполнения это представление неудобно.

Это язык, где явно описываются преобразования (операторы), проводимые над данными: выбор подмножества данных по предикату, соединение данных из разных источников и т. Образцом для промежуточных представлений стала реляционная алгебра. Кроме того, реляционная алгебра — алгебра в математическом смысле, то есть для неё формализовано большое количество эквивалентных преобразований. д. Поэтому над запросом в форме дерева операторов реляционной алгебры удобно проводить оптимизирующие преобразования.

Существуют важные отличия между внутренними представлениями в базах данных и оригинальной реляционной алгеброй, поэтому правильнее называть её логической алгеброй.

Роль таблицы символов в базах данных играет каталог базы данных, в котором хранится информация о схеме и метаданных базы данных: таблицах, колонках таблиц, индексах, правах пользователей и т. Проверка валидности запроса обычно проводится при компиляции первоначального представления запроса в операторы логической алгебры и соответствует стадии семантического анализа в обычных компиляторах. д.

В таблицах, или отношениях в терминах реляционной алгебры, может быть разное количество данных, на некоторых колонках (атрибутах отношений) могут быть построены индексы и т. По сравнению с интерпретаторами языков общего назначения у интерпретаторов баз данных есть ещё одна особенность: различия в объёме данных и метаинформации о данных, к которым предполагается делать запросы. То есть в зависимости от схемы базы данных и объёма данных в таблицах запрос надо выполнять разными алгоритмами, и использовать их в разном порядке. д.

В зависимости от наличия индексов на колонках, объёма данных в таблицах и структуры дерева логической алгебры предлагаются разные формы дерева физической алгебры, из которых выбирается оптимальный вариант. Для решения этой задачи вводится ещё одно промежуточное представление — физическая алгебра. В обычных компиляторах этому этапу условно соответствуют этапы распределения регистров, планирования и выбора инструкций. Именно это дерево показывают базе данных в качестве плана запроса.

Последним этапом работы интерпретатора является непосредственно исполнение дерева операторов физической алгебры.

Интерпретаторы дерева физической алгебры в закрытых коммерческих базах данных использовались практически всегда, но академическая литература обычно ссылается на экспериментальный оптимизатор Volcano, разрабатывавшийся в начале 90-х.

Помимо функций, оператор содержит рабочее состояние — state. В модели Volcano каждый оператор дерева физической алгебры превращается в структуру с тремя функциями: open, next, close. tuple), либо NULL, если кортежей не осталось, функция close завершает работу оператора: Функция open инициирует состояние оператора, функция next возвращает либо следующий кортеж (англ.

Каждый оператор, таким образом, перебирает кортежи либо существующего на реальном носителе отношения, либо виртуального отношения, формируемого перебором кортежей вложенных операторов: Операторы могут быть вложены друг в друга, чтобы сформировать дерево операторов физической алгебры.

В терминах современных языков высокого уровня дерево таких операторов представляет собой каскад итераторов.

От модели Volcano отталкиваются даже промышленные интерпретаторы запросов в реляционных СУБД, поэтому именно её я взял в качестве основы интерпретатора PigletQL.

Он написан на C, поддерживает создание таблиц в стиле SQL, но ограничивается единственным типом — 32-битными положительными целыми числами. Для демонстрации модели я разработал интерпретатор ограниченного языка запросов PigletQL. Система работает в один поток и не имеет механизма транзакций. Все таблицы располагаются в памяти.

Остальные запросы (CREATE TABLE и INSERT) работают непосредственно из первичных внутренних представлений. В PigletQL нет оптимизатора и запросы SELECT компилируются прямо в дерево операторов физической алгебры.

Пример сессии пользователя в 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 as;
} query_t;

Ему соответствует структура данных query_select_t: Самый сложный вид запросов в PigletQL — SELECT.

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 включает проверку существования перечисленных таблиц, колонок в таблицах и проверку типов в выражениях запроса.

Запросы SELECT, например, проверяются функцией validate_select. В PigletQL сложных выражений не бывает, поэтому проверка запроса сводится к проверке метаданных таблиц и колонок по каталогу. Приведу её в сокращённом виде:

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 промежуточных представлений, как правило, два: логическая и физическая алгебра.

Более сложные запросы SELECT компилируются в единственное промежуточное представление, которое и будет исполняться интерпретатором. Простой интерпретатор PigletQL запросы CREATE TABLE и INSERT выполняет непосредственно из своих деревьев разбора, то есть структур query_create_table_t и query_insert_t.

Дерево операторов строится от листьев к корню в следующей последовательности:

  1. Из правой части запроса ("… FROM relation1, relation2, …") получаются имена искомых отношений, для каждого из которых создаётся оператор scan.

  2. Извлекающие кортежи из отношений операторы scan объединяются в левостороннее двоичное дерево через оператор join.

  3. Атрибуты, запрошенные пользователем ("SELECT attr1, attr2, …"), выбираются оператором project.

  4. Если указаны какие-либо предикаты ("… WHERE a=1 AND b>10 …"), то к дереву сверху добавляется оператор select.

  5. Если указан способ сортировки результата ("… ORDER BY attr1 DESC"), то к вершине дерева добавляется оператор sort.

Компиляция в коде PigletQL:

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 — итератор, из которого кортежи «вытягиваются» один за другим, поэтому такой подход к исполнению ещё называется pull-моделью. Модель Volcano подразумевает интерфейс работы с операторами через три общие для них операции open/next/close.

Каждый из этих итераторов может сам вызывать те же функции вложенных итераторов, формировать временные таблицы с промежуточными результатами и преобразовывать входящие кортежи.

Выполнение запросов SELECT в PigletQL:

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;
}

Каждый вызов next возвращает либо следующий кортеж, либо NULL. Запрос сначала компилируется функцией compile_select, возвращающей корень дерева операторов, после чего у корневого оператора вызываются те самые функции open/next/close. В последнем случае это означает, что все кортежи были извлечены, и следует вызвать закрывающую итератор функцию close.

Полученные кортежи пересчитываются и выводятся таблицей в стандартный поток вывода.

Операторы

Я покажу устройство некоторых из них. Самое интересное в PigletQL — дерево операторов.

Интерфейс у операторов общий и состоит из указателей на функции open/next/close и дополнительной служебной функции destroy, высвобождающей ресурсы всего дерева операторов разом:

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;
} ;

Помимо функций, в операторе может содержаться произвольное внутреннее состояние (указатель state).

Ниже я разберу устройство двух интересных операторов: простейшего scan и создающего промежуточное отношение sort.

Оператор scan

Он просто перебирает все кортежи отношения. Оператор, с которого начинается выполнение любого запроса, — scan. Внутреннее состояние 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;

Для создания состояния оператора scan необходимо отношение-источник; всё остальное (указатели на соответствующие функции) уже известно:

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;
}

Операции open/close в случае scan сбрасывают ссылки обратно на первый элемент отношения:

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;
}

Оператор sort

Для этого надо создать временное отношение с кортежами, полученными из вложенных операторов, и отсортировать его. Оператор sort выдаёт кортежи в заданном пользователем порядке.

Внутреннее состояние оператора:

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;

Всё это происходит во время вызова функции open: Сортировка проводится по указанным в запросе атрибутам (sort_attr_name и sort_order) над временным отношением (tmp_relation).

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
>

Для простейшего из запросов используются только извлекающий кортежи из отношения scan и выделяющий у кортежей единственный атрибут project:

Выбор кортежей с предикатом:

> ./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 он выводит кортежи из временного отношения в указанном пользователем порядке: Оператор сортировки scan в вызове open создает (материализует) временное отношение, помещает туда все входящие кортежи и сортирует целиком.

Соединение кортежей двух отношений с предикатом:

> ./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

Это очень неэффективно, но для демонстрационного интерпретатора сойдет: Оператор join в PigletQL не использует никаких сложных алгоритмов, а просто формирует декартово произведение из множеств кортежей левого и правого поддеревьев.

В современные оптимизаторы и интерпретаторы запросов популярных баз данных вложены тысячи человеко-лет, и разработка даже простейших баз данных общего назначения занимает в лучшем случае годы. Напоследок замечу, что если вы делаете интерпретатор языка, похожего на SQL, то вам, вероятно, стоит просто взять любую из многочисленных доступных реляционных баз данных.

Демонстрационный язык PigletQL имитирует работу интерпретатора SQL, но реально в работе мы используем только отдельные элементы архитектуры Volcano и только для тех (редких!) видов запросов, которые трудно выразить в рамках реляционной модели.

Тем не менее повторюсь: даже поверхностное знакомство с архитектурой такого рода интерпретаторов пригодится в тех случаях, где требуется гибко работать с потоками данных.

D., Widom J., 2000), вы не найдёте. Если вам интересны основные вопросы разработки баз данных, то книги лучше, чем “Database system implementation” (Garcia-Molina H., Ullman J.

Лично мне нравится, когда к материалу прилагаются конкретные примеры кода или даже демонстрационный проект. Единственный её недостаток — теоретическая направленность. За этим можно обратиться к книге “Database design and implementation” (Sciore E., 2008), где приводится полный код реляционной базы данных на языке Java.

Оригинальная публикация написана вполне доступным языком, и её легко найти в Google Scholar: “Volcano — an extensible and parallel query evaluation system” (Graefe G., 1994). Популярнейшие реляционные базы данных по-прежнему используют вариации на тему Volcano.

Получить представление о ней можно из обзорной работы того же автора “Query evaluation techniques for large databases” (Graefe G. И хотя в деталях интерпретаторы SQL довольно сильно изменились за последние десятилетия, но самая общая структура этих систем не менялась уже очень давно. 1993).

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть