В настоящее время многие компании сталкиваются с задачами обработки большого количества данных. Данные обрабатываются, перерабатываются и исследуются бизнес-аналитиками, специалистами по машинному обучению, учеными. Однако, если данных оказывается слишком много, при работе с ними могут возникнуть затруднения. В таких случаях может быть полезно профилирование данных — совокупность методов, направленная на извлечение метаданных из набора данных [1] (иначе — получение данных о данных). Благодаря профилированию можно обнаружить различные закономерности, сокрытые в данных, что позволяет сделать некоторые выводы о структуре этих данных и исправить различные ошибки. Существует множество различных методов профилирования, каждый из которых представляет поиск некоторой формально описанной закономерности или правила. Такие закономерности будем называть примитивами. Например, один из самых широко известных примитивов — функциональная зависимость [10]. Примитивы позволяют узнать внутреннюю структуру таблицы, понять, как связаны между собой разные таблицы, они полезны [1] при очистке и интеграции данных, оптимизации и нормализации баз данных. Кроме того, нахождение закономерностей в данных полезно и учёным для анализа результатов экспериментов, специалистам по машинному обучению для выбора параметров моделей, аналитикам для выдвижения гипотез. Один из таких полезных примитивов — зависимости включения. Неформально, между двумя столбцами (возможно из разных) таблиц удерживается зависимость, если множество всех значений одного столбца содержится в множестве всех значений из другого. Такие зависимости применяются в различных алгоритмах работы с базами данных: например, самое часто упоминаемое в литературе применение — поиск первичных ключей [8]. Также зависимости включения используются [12] при оптимизации запросов, проектировании баз данных, интеграции данных.
Для поиска зависимостей включения был разработан ряд алгоритмов, сравнение производительности которых было произведено в статье [12]. Среди этих алгоритмов выделяется Faida — алгоритм приближенного поиска зависимостей включения. В отличие от других алгоритмов, он с небольшой вероятностью может выдавать ложноположительные результаты, однако это позволяет ему работать в несколько раз быстрее точных state-of-the-art алгоритмов. Реализация Faida, а также реализации многих других алгоритмов профилирования были собраны в платформе Metanome — инструменте для профилирования данных, полностью написанном на Java. Инструмент ориентирован на работу с данными и позволяет запускать различные алгоритмы профилирования на входных наборах данных. Однако исследования [5] показали, что производительности реализаций на Java не всегда достаточно для требовательных к ресурсам вычислений на больших объемах данных. Кроме того, перед началом использования Metanome необходимо правильно сконфигурировать и развернуть на машине пользователя, что может быть затруднительно для аналитиков, которые не так тесно связаны с миром разработки.
Чтобы избавиться от описанных недостатков, была разработана платформа Desbordante — инструмент для профилирования данных с открытым исходным кодом, идейный наследник Metanome, написанный на языке C++. Инструмент поддерживает несколько примитивов, в том числе и функциональные зависимости, однако на момент начала настоящей работы поддержка зависимостей включения отсутствовала. Таким образом, было принято решение реализовать алгоритм приближенного поиска зависимостей включения Faida на языке C++, и внедрить код алгоритма в инструмент. Благодаря этому будет создана производительная open-source реализация этого алгоритма.
В ходе работы над созданием высокопроизводительной реализации алгоритма Faida в рамках профайлера данных Desbordante были выполнены следующие задачи:
• произведён краткий обзор предметной области зависимостей включения и алгоритма Faida, выделены три основные стадии работы алгоритма: препроцессинг, генерация кандидатов и валидация;
• алгоритм реализован на языке C++, в качестве эталонной реализации была взята Java-реализация алгоритма из Metanome;
• исследована производительность кода и реализованы оптимизации:
• сторонняя хеш-таблица,
• буферизация,
• векторизация с использованием SIMD-инструкций,
• распараллеливание;
• проведено сравнение производительности С++-реализации с существующей Java-реализацией алгоритма из Metanome. Эксперименты показали, что все предложенные оптимизации улучшают производительность, и оптимизированная C++-реализация работает в среднем в 3.7 раз быстрее Java-реализации.
На основе результатов работы была подготовлена статья [9], которая была принята на конференцию FRUCT’23 (публикуется в IEEE Xplore и индексируется в Scopus). Код алгоритма доступен1 на Github.
