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

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

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

Содержание

• Предыстория
• Структура интерпретатора SQL
• Модель Volcano и исполнение запросов
• PigletQL
  
  • Лексический и синтаксический анализаторы
  • Семантический анализатор
  • Компиляция запросов в промежуточное представление
  • Исполнение промежуточного представления
  • Операторы
  • Примеры работы
• Выводы
• Литература

Предыстория

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модель Volcano и исполнение запросов

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

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

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

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

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

PigletQL

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

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

Выполнение запросов 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; }

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

Сортировка проводится по указанным в запросе атрибутам (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 >

Для простейшего из запросов используются только извлекающий кортежи из отношения 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

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

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

Выводы

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

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

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

Литература

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

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

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

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