company_banner

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


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


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


    Словом, любопытствующим и сильным духом разработчикам и адресована эта статья. В ней вы найдёте описание традиционной модели исполнения запросов в реляционных базах данных на примере демонстрационного языка 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).

    Badoo
    197,00
    Big Dating
    Поделиться публикацией

    Похожие публикации

    Комментарии 10

      +1

      Можно подробнее о конечном результате? Судя по первым абзацам, у Баду есть своя СУБД, которая быстрее работает на ваших объемах. Интересно, удалось ли опередить тот же MemSQL, и пытались ли как-то еще решать задачу (писать MapReduce с нуля на C++, например)?

        +1

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


        Словом, в Бадуу много интересных проектов, но (Р)СУБД — не один из них :-) Все проще.


        Данная конкретная система — статический индекс, который генерируется из Хадупа раз в день. В индексе хранятся пользовательские сессии (цепочки событий) в формате, который можно на лету распаковать и проанализировать. Искать интересные сессии для сбора статистики можно на языке вроде регулярных выражений.


        Конкретно интерпретаторы SQL нам были интересны для ограниченного расширения возможностей языка. PigletQL — прототип, на котором я разбирал самый популярный вид интерпретаторов.


        Но, кстати, для наших видов запросов и на наших объемах данных индекс даст MemSQL сто очков вперед как по компактности представления, так и скорости вычисления результатов. Специализация она такая.


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

          +1

          Очень интересно! У меня сейчас есть подобная задача с сохранением всех пользовательских сессий и поиска паттернов, которые соответствуют фроду, поведению потенциальных вип клиентов, других интересных групп клиентов. Сейчас для меня самое непонятное — как из истории сессии (которая переменной длины) собрать нечто вроде вектора Х, который можно использовать для обучения классификатора (который из фиксированного набора фич). Много есть костыльных идей типа булевых фич на то, что было некое событие, использования текстовых классификаторов, но чего-либо красивого пока не видел. Может подскажете, куда копнуть?)

            +1

            Я уже много лет не занимался именно машинным обучением, аж с 2012-2013 года, поэтому тут мои познания не слишком актуальны :-)


            Если работать с векторами, то придется придумывать способ кодировать в них именно последовательности событий. Скажем, ячейка 0 будет показывать наличие 3-граммы из событий ABC, ячейка 1 — BCA и так далее. Длина такого вектора будет зависеть от количества типов событий и длины используемых n-грамм.


            Это только один вариант, полет фантазий тут неограничен, пробовать и пробовать.


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


            А что вы уже запихивать в векторы пробовали?

              +1

              Пока ML под это дело не подключал — только программировал эвристики. Но из того, что думал пробовать, — считать промежутки времени между конкретными парами событий, те же n-граммы, соотношения количества одних и других событий, ну и, отсекать первые n минут сессии (просто выкидывая сессии короче), и строить статистику только по ним.

                +1

                Я бы на вашем месте все же попробовал следующее: взял n-граммы (скажем, четверки или даже длинней) последовательностей событий и сделал байесовский классификатор. Это не какое-то там мощное машинное обучение, но делается легко и быстро, даже безо всяких библиотек. Если будет хоть какая-то ощутимая предсказательная сила, то можно копать в эту сторону.


                Эвристики в этих делах слабо помогают, я пробовал в свое время: довелось работать в небольшой азиатской поисковой компании, где мне поставили задачу классификации сайтов :-)


                Но, опять же, задача звучит вот прям почти типовой, имеет смысл ознакомиться с коллективным опытом.


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

        +1
        В чем рисуют такие диаграмки? Хорошо выглядят, лаконично.
        +3

        Если вдруг есть заинтересовавшиеся в теме, рекомендую почитать про PostgreSQL:



        Автору спасибо за статью, было приятно почитать.

          +2

          Согласен, PostgreSQL вне конкуренции в смысле документации как внешней, так и внутренней. :-) На удивление легко читается, можно рекомендовать не только как пример устройства БД, но и как пример красивого кода на Си.

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

        Самое читаемое