Исследование и разработка алгоритмов гибридных аналитических запросов для высокопроизводительных гетерогенных вычислительных систем тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Курапов Петр Александрович

• Курапов Петр Александрович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Курапов Петр Александрович

Введение

Глава 1. Обзор подходов к оптимизации аналитических запросов

1.1 Аналитические запросы

1.1.1 СУБД для аналитики

1.1.2 Поисковый анализ данных

1.1.3 Пример

1.1.4 СУБД в основной памяти

1.1.5 Гетерогенные системы

1.1.6 Проблемы использования гетерогенных систем

1.2 Подходы к повышению производительности

1.2.1 Модели исполнения

1.2.2 Использование параллелизма

1.2.3 Организация поиска оптимального плана

1.3 Обзор существующих решений

1.3.1 GDB

1.3.2 Ocelot, HeroDB

1.3.3 Hawk, CoGaDB, Hype, HorseQC

1.3.4 Voodoo

1.3.5 LegoBase

1.3.6 HetExchange

1.3.7 VOILA

1.3.8 OmniDB

1.3.9 HeavyDB (OmniSciDB, Mapd)

1.3.10 Centaur

1.3.11 Открытые проблемы

1.4 Постановка задачи

1.5 Выводы

Глава 2. Аналитические паттерны и модель затрат

2.1 Методология выполнения запросов в гетерогенной среде

2.1.1 Основные понятия графа исполнения запроса

2.1.2 Построение гетерогенного плана

2.1.3 Управление исполнением гетерогенного плана

2.2 Модель затрат

2.2.1 Обзор существующих подходов к построению модели затрат

2.2.2 Прямая оценка характеристик производительности шаблонов

2.3 Аналитические шаблоны (паттерны)

2.3.1 Описание аналитических шаблонов

2.3.2 Реализация шаблонов в СУБД

2.4 Применение шаблонов для аппроксимации стоимости плана

исполнения

2.4.1 TPC-HQ1

2.5 Алгоритм оценки стоимости запроса

2.6 Экспериментальная оценка точности модели затрат

2.7 Оптимизация гетерогенного плана

2.7.1 Формулировка задачи оптимизации гетерогенного плана исполнения

2.7.2 Алгоритм решения задачи поиска оптимального гетерогенного плана

2.8 Выводы

Глава 3. Практическая реализация и результаты экспериментов

3.1 Общая архитектура системы

3.2 Организация генерации и исполнения кода запроса

3.3 Генерация и исполнение кода в гетерогенном режиме

3.3.1 Компиляция

3.3.2 Исполнение

3.3.3 Интеграция нового аппаратного ускорителя

3.4 Экспериментальные результаты

3.5 Дальнейшее развитие

3.5.1 Унификация подхода к исполнению ядер

3.5.2 Разделение компилятора запросов на компоненты

3.5.3 Единое представление для алгоритмов

3.6 Выводы

Заключение

Список литературы

Список рисунков

Список таблиц

Приложение А. Генерируемый код шага

Приложение Б. Запросы набора NYC Taxi

Введение диссертации (часть автореферата) на тему «Исследование и разработка алгоритмов гибридных аналитических запросов для высокопроизводительных гетерогенных вычислительных систем»

Введение

Исторически, анализ данных всегда был прерогативой систем управления базами данных. Первые мейнфреймы создавались именно с целью обработки различных «банков данных». Стремительный рост технологий привел к степенному росту генерации различных данных — от телеметрии промышленных датчиков до персонализированной информации о посещении сайтов. Согласно оценке International Data Corporation (IDC) [1] в 2021 году человечество произвело более 64 зеттабайт данных (1 зеттабайт « 1 миллиард гигабайт). В ближайшие 5 лет ожидается рост этого показателя на 23% в год, что превышает скорость роста производительности вычислительных систем. Меняется не только объем, но также и характеристики данных — от агрегации простой телеметрии до предсказывающей аналитики поведения на сайте. Традиционно эту область называют «большими данными», а процесс анализа и обработки больших данных — аналитикой больших данных. Таким образом, большие данные характеризуются тремя основными признаками:

- большой объем информации,

- высокая скорость изменения информации,

- разнообразие и разнородность данных.

Агрегация и анализ больших данных потребовали развития новых технологий, таких как Hadoop [2], Spark [3] и концепции «озёр данных» [4]. Если традиционно транзакционные базы данных хорошо подходили для обработки большого объема единичных изменений при жестко заданной реляционной схеме таблицы, то с середины 2010-х годов актуальным становиться необходимость дешёвого хранения и обработки большого совместного объема структурированных (например, таблицы), полуструктрированных (например, журналы событий) и неструктурированных (например, изображения) данных, при требованиях производительности как в традиционных базах данных и быстрых преобразований для дальнейшей обработки, например с помощью машинного обучения. В таких системах, с увеличением количества данных и сложности запросов производительности традиционных вычислительных средств оказывается недостаточно и требуются новые пути повышения эффективности обработки и анализа. Один из таких методов - использование специализированных аппаратных ускорителей, таких как графический процессор, для выполнения запросов и расширение

иерархии используемой памяти [5]. Такие изменения влияют на архитектуру СУБД и требуют переработки ключевых решений и механизмов взаимодействия подсистем [6]. Ввиду различий архитектур традиционных ЦПУ и графических ускорителей возникает вопрос - какой тип запросов на каком объеме данных целесообразно выполнять. Сравнение данных производительности для различных аналитических запросов показывает, что нет однозначно-лучшего устройства исполнения запросов (например, различия в производительности на наборе данных NYC Taxi рис. 1, код запросов в приложении Б).

Рисунок 1 — Различия в производительности запросов выполненных на разных

устройствах: ЦПУ и графический процессор.

Таким образом, к существующим задачам добавились новые проблемы. Для решения этих проблем были созданы специализированные СУБД, работающие исключительно на графических ускорителях. Однако, ввиду существенных ограничений памяти ускорителей, а также ограничений типов запросов, которые могут быть эффективно выполнены на ускорителях, стало необходимым управлять процессом выполнения запросов для эффективного использования аппаратуры. Следовательно, для каждого типа данных и типов запросов необходимо подбирать распределение и оптимизировать запросы под целевой ускоритель. Как показано в [7], оптимизация запросов для распределенных систем является

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

Целью диссертационной работы является разработка методов многокритериальной оптимизации исполнения аналитических запросов к СУБД в основной памяти в гетерогенных системах при заданных ограничениях на время оптимизации и используемые ресурсы.

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Разработать методологию гибридного исполнения аналитических запросов в гетерогенной системе.

2. Разработать модель затрат и алгоритм вычисления стоимости плана для гетерогенной системы для ускорения исполнения.

3. Разработать алгоритм балансировки вычислений между устройствами системы выполнения запросов в гибридном режиме.

4. Реализовать исполнение запросов в гибридном режиме.

Объектом исследования являются аналитические запросы.

Предметом исследования является оптимизация аналитических запросов

в гетерогенных системах.

Научная новизна:

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

2. Был разработан новый эффективный алгоритм оптимизации аналитического запроса в гетерогенной системе, основанный на новой модели затрат с использованием характеристических шаблонов и эффективном поиске начальных точек пространства поиска с помощью ЬРт-последовательностей с последующей оптимизацией генетическим алгоритмом и локальным поиском.

Практическая значимость диссертационной работы заключается в том, что все разработанные методы и алгоритмы были использованы в СУБД OmniSci DB и успешно внедрены организацией АО «ИНТЕЛ А/О» для оптимизации задач продукта Intel Distribution of Modin. Разработанные методы и алгоритмы позволили получить существенный прирост производительности на целевых приложениях.

Результаты работы также внедрены в кафедральный курс «Алгоритмическая сложность, неразрешимые задачи и методы оптимизации» кафедры микропроцессорных технологий в интеллектуальных системах управления МФТИ.

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

Методология и методы исследования. Основываются на базовых принципах системного анализа, правилах проектирования программного обеспечения, теории алгоритмов и теории графов и оптимизации.

Основные положения, выносимые на защиту:

1. Методология гибридного выполнения аналитических запросов в гетерогенных системах. Заключается в создании дополнительного пути исполнения генерируемого кода в плане запроса и оптимизации утилизируемых ресурсов за счет распределения обрабатываемых данных между устройствами.

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

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

4. Реализация механизмов исполнения запросов в гибридном режиме.

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

Апробация работы. Основные результаты работы докладывались на:

- 64-й всероссийской научной конференции МФТИ, 2021;

- VIII Международной конференции «Инжиниринг & Телекоммуникации», 2021;

- семинарах ФРКТ МФТИ, 2020-2021;

- семинарах и технических форумах в компании Intel, 2020-2021;

Личный вклад. Вклад автора заключается:

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

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

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

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

Публикации. Основные результаты по теме диссертации изложены в 5 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК, 2 — в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения и 3 приложений. Полный объём диссертации составляет 114 страниц, включая 15 рисунков и 4 таблицы. Список литературы содержит 113 наименований.

Глава 1. Обзор подходов к оптимизации аналитических запросов

1.1 Аналитические запросы

Существует 3 основных вида запросов:

- OLTP (online transaction processing) — обработка единичных повторяющихся транзакций, например, изменение состояния счета в банке через банкомат. Для этого типа запросов характерны доступ к малой части данных (обновление одной записи), постоянное внесение изменений и, как следствие, возникновение конфликтов синхронизации при параллельной обработке.

- OLAP (online analytical processing) — аналитические запросы с целью выявления дополнительной информации из существующих данных, например, средние квартальные значения выручки от продаж определенного вида товаров. Для этого вида характерны вычислительно-ёмкие (большое количество источников данных и таблиц, высокая вложенность соединений, большое количество и сложность предикатов) запросы с обращением к большой части данных, доступ к данным только на чтение (read-only), и, как следствие, независимость запросов.

- HTAP (hybrid transaction/analytical processing) [6] — гибридная обработка транзакционных малых изменений (OLTP) и аналитических запросов (OLAP). Для этого вида характерны оба паттерна описанные выше. Совмещение обработчиков1 в одной системе позволяет управлять ресурсами для обеспечения необходимой актуальности данных для OLAP запросов.

Типичный OLAP запрос состоит из следующих концептуальных шагов:

- Поиск данных — задача нетривиальна в распределенных системах (например, Hadoop Distributed File System [8]) и при наличии множества источников данных (например, системы управления отношения с клиентами, системы планирования ресурсов предприятия и т.п.).

- Чтение данных — доступ к дисковым накопителям и передача по сети. Данные могут быть распределены и сегментированы (sharding) по вычислительным узлам кластера.

компонента СУБД, отвечающая за оптимизацию и исполнение плана

- Валидация и приведение данных к необходимому виду — предобработка для последующего анализа или использования сторонних библиотек.

- Применение анализа к данным и доставка результатов пользователю.

Мы фокусируемся на аналитических запросах (OLAP) к большим данным в

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

Аналитика над данными выполняет функцию поиска паттернов и корреляций для построения полезных моделей, например для предсказания будущего, (спроса на продукт в следующем месяце, пройдет ли пользователь по рекламной ссылке, вернется ли выданный займ, легитимна ли банковская транзакция и т.п.) и использования этих данных для принятия бизнес решений [9]. Основой построения паттернов могут служить как простейшие аналитические модели, например, средних значений интересующих величин, так и более сложные — алгоритмы машинного обучения, работающие с данными больших размерностей. В больших масштабах значение точности прогноза с увеличением объема обрабатываемых данных возрастает, поэтому использование всех доступных данных становится предпочтительным.

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

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

Поскольку в бизнесе источников данных может быть много, создание единого хранилища данных (data warehouse) для анализа зачастую необходимость. Процесс агрегации данных в хранилищах называется extract, transform and load

(ETL2) и, как показано выше, является частью OLAP. В этом смысле понятие OLAP запросов покрывает множество задач от работы исследователей данных (data scientist) до бизнес-аналитиков. Традиционно, аналитические задачи решались на уровне СУБД.

1.1.1 СУБД для аналитики

Реляционные СУБД предоставляют многочисленные возможности для оптимизации доступа и анализа агрегированных в хранилище данных. За счет абстрагирования методов доступа и алгоритмов обработки СУБД может контролировать способ хранения данных и оптимизировать план исполнения запроса. Под планом запроса имеется в виду граф операторов расширенной реляционной алгебры (эти понятия будут введены в главе 2). Различные виды запросов к одному хранилищу могут снижать общую производительность системы. С одной стороны быстрые транзакционные запросы требуют поддержки механизмов синхронизации для изменений данных, с другой, медленные аналитические запросы требуют консистентности данных на протяжении всего времени их исполнения. Для совмещения видов нагрузок необходимы дополнительные управляющие структуры, такие как «снимки» состояния БД для аналитических запросов, и обновление снимков данными транзакций с некоторой периодичностью [6]. Так, разделение процессов обработки запросов с целью обновления и анализа важно при повторяющихся запросах, например, при сборе данных для их онлайн визуализации и создания инструментальных панелей (dashboard) или переиспользовании данных (поиск новых паттернов и работа бизнес-аналитиков). Строго определенная схема хранилищ данных и специализированная структура хранения (например, физическое дублирование, колончатая организация данных) позволяют повышать производительность выполнения вычислительно-ёмких аналитических запросов (в силу природы аналитических запросов обращение обычно происходит ко всем доступным данным, к примеру, вычисление средних показателей величины столбца требует доступа ко всему столбцу). Количество данных требует распределенности хранения и вычисления, а сложность запросов требует

2https://databricks.com/glossary/extract-transform-load

еще и качественного планирования запроса с точки зрения выбора оптимальных реализаций алгоритмов и уровня параллелизма исполняемых операторов.

1.1.2 Поисковый анализ данных

Типичный сценарий аналитики над данными с целью поиска невыявлен-ных закономерностей отличается от медленно изменяющихся запросов для построения отчетов. Такой сценарий подразумевает произвольные (ad-hoc) [11] запросы в поисковом режиме (exploratory data analysis) [12]. Случайная природа таких запросов накладывает ограничения на возможности оптимизации. К примеру, планы для построения инструментальных панелей и других периодических вычислений можно кэшировать и переиспользовать. В случае произвольных запросов полное переиспользование становится невозможным, однако техники переиспользования более гранулярных результатов оптимизации по-прежнему доступны [13—15].

1.1.3 Пример

Листинг 1.1 TPC-H Q6

SELECT sum(l_extendedprice * l_discount) as revenue FROM lineitem

WHERE l_shipdate >= date '1994-01-01'

AND l_shipdate < date '1994-01-01' + interval '1' year AND l_discount between 0.06 - 0.01 AND 0.06 + 0.01 AND l_quantity < 24;

Рассмотрим типичный пример аналитического запроса из стандартной системы бенчмаркинга СУБД TPC-H [16]. Запрос рассчитывает увеличение дохода при изменениях в политике предоставления скидок на продукты некоторой компании. Оценка производится на основе данных базовой таблицы lineitem, которая содержит данные о продажах и ценах. Для простоты рассмотрим выполнения на одном узле:

1. Получить доступ к таблице Ипекет, то есть найти место в памяти (указатель/дескриптор), по которому она размещена. Для базы данных в основной памяти (т-тетогу) данные уже доступны и обращение к диску не требуется.

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

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

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

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

Все современные СУБД в том или ином виде поддерживают колончатую организацию данных [17] с последующим использованием векторной обработки, которая за раз обрабатывает не скалярные значения кортежей, а вектор значений, также могут применяться техники компиляции, которые будут рассмотрены далее.

1.1.4 СУБД в основной памяти

За более чем 50-ти летнюю историю развития СУБД разработано множество принципов и подходов к оптимизации запросов на разных уровнях — от

архитектурных решений до конкретных алгоритмических методов, см., например, [18—20]. Основной целью таких методов традиционно было повышение эффективности использования аппаратуры. Однако, по мере развития индустрии, а также стремительного увеличения объема данных, направленность оптимизаций менялась [21; 22]. Так, классические СУБД требуют от разработчика наибольшего внимания ко взаимодействию с относительно медленным дисковым накопителем. Минимизация количества обращений и времени доступа породила множество оптимизаций, например, по способам хранения данных (сжатие), по способам доступа к данным (индексирование), по точности ответа (фильтры Блума) и т.д. Также появилась модель выполнения операторов «производитель/потребитель», которая позволяет как можно дольше оставлять записи внутри процессора — кэши, регистры [18].

С другой стороны, увеличение объемов оперативной памяти до нескольких терабайт и ее удешевление привело к появлению баз данных в основной памяти [22]. Использование основной памяти для хранения данных меняет характеристики производительности алгоритмов, разработанных для классических СУБД. Фокус на оптимизацию наиболее узкого места — доступа к данным на диске — смещается в сторону исполнения [23]. СУБД становится выгодно учитывать и использовать иерархию памяти — от кэшей до диска, механизмы упреждающей выборки команд (prefetching). Использование вторичных индексов становится менее актуальным [24]. Количество инструкций, необходимых для выполнения запроса, становится важным фактором, наряду с производительностью подсистемы памяти [17]. Скорости доступа к данным хватает для задействования физического параллелизма уровня множества ядер и векторных инструкций [25]. Наконец, исчерпание ресурса этих техник [26] привело индустрию к исследованию возможностей повышения эффективности за счет использования специализированных аппаратных модулей [27].

1.1.5 Гетерогенные системы

Под гетерогенностью мы понимаем возможность совместного исполнения некоторой задачи на двух или более устройствах с различной архитектурой. Это могут быть ядра ЦПУ предоставляющие различные возможности (к примеру,

наличие дополнительного векторного исполнителя, математического сопроцессора, либо устройства с различной моделью программирования (как связка ЦПУ и графического процессора, тензорного процессора, аппаратных ускорителей для методов искусственного интеллекта (задачи распознавания, классификации, машинного обучения и т. д.) например, Habana Gaudi3, Ali-NPU4, аппаратные ускорители с большим числом процессорных ядер (MIC), например Xeon Phi^ др.).

Различия в наборе инструкций и микроархитектурных особенностях позволяют адаптировать аппаратуру для оптимизации определенного класса задач. Это позволяет снижать энергопотребление или количество тактов, требуемого для завершения задачи [28]. Например, графический процессор имеет большую пропускную способность памяти, чем ЦПУ и позволяет использовать значительно больше потоков одновременно. Однако, за счет относительной простоты каждого ядра, сложные арифметические операции (например, деление) и нетривиальный поток исполнения (ветвление) оказываются менее эффективны.

Из-за различий в наборе инструкций, для использования различных устройств в одной системе требуются пути для генерации исполняемого кода (кодогенерации) и поддержка со стороны среды исполнения (runtime). Модели программирования устройств могут отличаться. Например, в случае графического процессора, исполнением необходимо управлять с ЦПУ Графический же процессор, выполняет специально упакованные программы, называемые ядрами (kernel).

Помимо гетерогенности на уровне исполнителей, неоднородности возникают в следующих характеристиках системы:

- доступ к оперативной памяти различного типа (DRAM, HBM — High Bandwidth Memory, PMEM — Persistent Memory) — требуемые свойства — время доступа, пропускная способность, объем, персистентность;

- расположение данных в дисковой иерархии (SDD, HDD) и удаленности относительно запрашивающего узла в архитектуре с неравномерной памятью (NUMA - Non Uniform Memory Access);

- типы сетевого соединения.

3https://towardsdatascience.com/training-on-aws-with-habana-gaudi-3l26el83048

4https://www.alibabacloud.com/blog/alibaba-unveils-ai-chip-to-enhance-cloud-computing-power_595409

5https://ark.intel.com/content/www/ru/ru/ark/products/94035/intel-xeon-phi-processor-7250-l6gb-l-40-ghz-68-core.html

Использование гетерогенных систем для оптимизации запросов позволило ускорить работу некоторых классов отдельных операторов [29; 30] и запросов целиком [31; 32].

1.1.6 Проблемы использования гетерогенных систем

Использование гетерогенных систем для дальнейшей оптимизации запросов сопряжено с трудностями [33]. Переход на графический ускоритель в качестве основного исполнительного устройства вычисления запросов не дает автоматического прироста производительности по всем типам запросов. Напротив, в широком классе запросов графический процессор проигрывает обычному ЦПУ, даже если данные локальны по отношению к графическому процессору (то есть, без учета издержек на копирование) [33]. Зависимость производительности от типа нагрузки создает необходимость выбора соответствующего устройства/устройств для выполнения запроса или его специфических частей. Высокоскоростные сети в центрах обработки данных (ЦОД), новые типы быстрой неволатильной памяти и передача данных между устройствами в системе представляют новый класс задержек в системе с характерным временем в микросекунды [34]. При снижении времени ответа операций ввода-вывода и обращений в нелокальную память, пропускная способность вычислителей будет падать. Текущие методы скрытия задержек на обращение в память полагаются на параллелизм уровня инструкций, а ввод-вывод — на механизмы операционной системы, такие как смена контекста. Оба подхода плохо масштабируются на операции в микросекундном диапазоне: параллелизм уровня инструкций ограничен и его недостаточно, а смена контекста сравнима по времени с передачей данных из нелокальной памяти [34] и будет вносить значимые задержки. Поэтому, необходима разработка новых алгоритмов эффективного использования гетерогенных систем. Кроме того, задача дополнительно усложняется в распределенных системах.

Таким образом, разработчику СУБД с использованием гетерогенных устройств необходимо решить следующие проблемы:

1. Необходима эффективная модель для использования доступного параллелизма и векторизации. Модели программирования различных про-

цессоров могут различаться. Архитектура СУБД должна учитывать эти различия и позволять эффективно планировать запрос.

2. Передача данных между устройствами снижает производительность. Требуется механизм определения наилучшей конфигурации устройств и размещения входных и промежуточных данных в иерархии памяти для минимизации расходов связанных с перемещением данных.

3. За счет появления неоднородностей ресурсов растет пространство поиска оптимального плана. Для оптимизатора требуются эффективные алгоритмы поиска, новые эвристики.

Список литературы диссертационного исследования кандидат наук Курапов Петр Александрович, 2022 год

Список литературы

1. URL: https://www.idc.com/getdoc.j'sp?containerId=prUS47560321.

2. A comprehensive view of Hadoop research—A systematic literature review [Текст] /1. Polato [и др.] // Journal of Network and Computer Applications. — 2014. — Т. 46. — С. 1—25. — URL: https://www.sciencedirect.com/science/ article/pii/S1084804514001635.

3. Spark: Cluster Computing with Working Sets [Текст] / M. Zaharia [и др.] // Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. — Boston, MA : USENIX Association, 2010. — С. 10. — (HotCloud'10).

4. Miloslavskaya, N. Big data, fast data and data lake concepts [Текст] / N. Miloslavskaya, A. Tolstoy // Procedia Computer Science. — 2016. — Т. 88. — С. 300-305.

5. Кузнецов, С. В ожидании нативных архитектур СУБД на основе энергонезависимой основной памяти [Текст] / С. Кузнецов // Труды Института системного программирования РАН. — 2020. — Т. 32, № 1. — URL: https: //ispranproceedings.elpub.ru/jour/article/view/1271.

6. The Case For Heterogeneous HTAP [Текст] / R. Appuswamy [и др.]. — 2017.

7. Wang, C. On the complexity of distributed query optimization [Текст] / C. Wang, M.-S. Chen // IEEE Transactions on Knowledge and Data Engineering. — 1996. — Т. 8, № 4. — С. 650—662.

8. Borthakur, D. HDFS architecture [Текст] / D. Borthakur // Document on Hadoop Wiki. URL http://hadoop. apache. org/common/docs/r0. — 2010. — Т. 20.

9. Silberschatz, A. Database System Concepts, Seventh Edition [Текст] / A. Silberschatz, H. F. Korth, S. Sudarshan. — McGraw-Hill Book Company, 2020. — URL: https://www.db-book.com/db7/index.html.

10. Synapse: A Microservices Architecture for Heterogeneous-Database Web Applications [Текст] / N. Viennot [и др.] // Proceedings of the Tenth European Conference on Computer Systems. — Bordeaux, France : Association for Computing Machinery, 2015. — (EuroSys '15). — URL: https://doi.org/10. 1145/2741948.2741975.

11. The Seattle Report on Database Research [Текст] / D. Abadi [и др.] // SIGMOD Rec. — New York, NY, USA, 2020. — Февр. — Т. 48, № 4. — С. 44—53. — URL: https://doi.org/10.1145/3385658.3385668.

12. Tukey, J. W. Exploratory Data Analysis [Текст] / J. W. Tukey. — Addison-Wesley, 1977.

13. Plan Stitch: Harnessing the Best of Many Plans [Текст] / B. Ding [и др.] // Proc. VLDB Endow. — 2018. — Июнь. — Т. 11, № 10. — С. 1123—1136. — URL: https://doi.org/10.14778/3231751.3231761.

14. Accelerating Analytics with Dynamic In-Memory Expressions [Текст] / A. Mishra [и др.] // Proc. VLDB Endow. — 2016. — Сент. — Т. 9, № 13. — С. 1437—1448. — URL: https://doi.org/10.14778/3007263.3007280.

15. Shared Workload Optimization [Текст] / G. Giannikis [и др.] // Proc. VLDB Endow. — 2014. — Февр. — Т. 7, № 6. — С. 429—440. — URL: https://doi.org/ 10.14778/2732279.2732280.

16. URL: http://www.tpc.org/tpch/.

17. Neumann, T. Efficiently Compiling Efficient Query Plans for Modern Hardware [Текст] / T. Neumann // Proc. VLDB Endow. — 2011. — Июнь. — Т. 4, № 9. — С. 539—550. — URL: https://doi.org/10.14778/2002938.2002940.

18. Graefe, G. Encapsulation of Parallelism in the Volcano Query Processing System [Текст] / G. Graefe // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data. — Atlantic City, New Jersey, USA : Association for Computing Machinery, 1990. — С. 102—111. — (SIGMOD '90). — URL: https://doi.org/10.1145/93597.98720.

19. How to Architect a Query Compiler [Текст] / A. Shaikhha [и др.] // Proceedings of the 2016 International Conference on Management of Data. — San Francisco, California, USA : Association for Computing Machinery, 2016. — С. 1907—1922. — (SIGMOD '16). — URL: https://doi.org/10.1145/2882903. 2915244.

20. Distributed Join Algorithms on Thousands of Cores [Текст] / C. Barthels [и др.] // Proc. VLDB Endow. — 2017. — Янв. — Т. 10, № 5. — С. 517—528. — URL: https://doi.org/10.14778/3055540.3055545.

21. Stonebraker, M. "One Size Fits All": An Idea Whose Time Has Come and Gone [Текст] / M. Stonebraker, U. Cetintemel // Proceedings of the 21st International Conference on Data Engineering. — USA : IEEE Computer Society, 2005. —

C. 2—11. — (ICDE '05). — URL: https://doi.org/10.1109/ICDE.2005.1.

22. Implementation Techniques for Main Memory Database Systems [Текст] /

D. J. DeWitt [и др.] // SIGMOD Rec. — New York, NY, USA, 1984. — Июнь. — Т. 14, № 2. — С. 1—8. — URL: https://doi.org/10.1145/971697.602261.

23. DBMSs on a Modern Processor: Where Does Time Go? [Текст] / A. Ailamaki [и др.] // Proceedings of the 25th International Conference on Very Large Data Bases. — San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 1999. — С. 266—277. — (VLDB '99).

24. Kester, M. S. Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? [Текст] / M. S. Kester, M. Athanassoulis, S. Idreos // Proceedings of the 2017 ACM International Conference on Management of Data. — Chicago, Illinois, USA : Association for Computing Machinery, 2017. — С. 715—730. — (SIGMOD '17). — URL: https://doi.org/ 10.1145/3035918.3064049.

25. Everything You Always Wanted to Know about Compiled and Vectorized Queries but Were Afraid to Ask [Текст] / T. Kersten [и др.] // Proc. VLDB Endow. — 2018. — Сент. — Т. 11, № 13. — С. 2209—2222.

26. Vbench: Benchmarking Video Transcoding in the Cloud [Текст] / A. Lottarini [и др.] // Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems. — New York, NY, USA : Association for Computing Machinery, 2018. — С. 797—809. — URL: https://doi.org/10.1145/3173162.3173207.

27. Karnagel, T. Adaptive Work Placement for Query Processing on Heterogeneous Computing Resources [Текст] / T. Karnagel, D. Habich, W. Lehner // Proc. VLDB Endow. — 2017. — Март. — Т. 10, № 7. — С. 733—744. — URL: https: //doi.org/10.14778/3067421.3067423.

28. A Hardware/Software Stack for Heterogeneous Systems [Текст] / J. Castrillon [и др.] // IEEE Transactions on Multi-Scale Computing Systems. — 2018. — Т. 4, № 3. — С. 243—259.

29. Chrysogelos, P. Hardware-conscious Query Processing in GPU-accelerated Analytical Engines [Текст] / P. Chrysogelos, P. Sioulas, A. Ailamaki // CIDR. — 2019.

30. Kara, K. FPGA-Based Data Partitioning [Текст] / K. Kara, J. Giceva, G. Alonso // Proceedings of the 2017 ACM International Conference on Management of Data. — Chicago, Illinois, USA : Association for Computing Machinery, 2017. — С. 433—445. — (SIGMOD '17). — URL: https://doi.org/ 10.1145/3035918.3035946.

31. Heterogeneity-Aware Operator Placement in Column-Store DBMS [Текст] / T. Karnagel [и др.] // Datenbank-Spektrum. — 2014. — Нояб. — Т. 14. — С. 211—221. — URL: https://doi.org/10.1007/s13222-014-0167-9.

32. He..ro DB: A Concept for Parallel Data Processing on Heterogeneous Hardware [Текст] / M. Müller [и др.] //. — 07.2020. — С. 82—96.

33. One size does not fit all: accelerating OLAP workloads with GPUs [Текст] / Y. Zhang [и др.] // Distributed and Parallel Databases. — 2020. — Дек. — Т. 38.

34. Attack of the Killer Microseconds [Текст] / L. Barroso [и др.] // Commun. ACM. — New York, NY, USA, 2017. — Март. — Т. 60, № 4. — С. 48—54. — URL: https://doi.org/10.1145/3015146.

35. Graefe, G. Volcano/spl minus/an extensible and parallel query evaluation system [Текст] / G. Graefe // IEEE Transactions on Knowledge and Data Engineering. — 1994. — Т. 6, № 1. — С. 120—135.

36. PosDB: An Architecture Overview [Текст] / G. Chernishev [и др.] // Programming and Computer Software. — 2018. — Янв. — Т. 44. — С. 62—74.

37. Pipelined Query Processing in Coprocessor Environments [Текст] / H. Funke [и др.] // Proceedings of the 2018 International Conference on Management of Data. — Houston, TX, USA : Association for Computing Machinery, 2018. — С. 1603—1618. — (SIGMOD '18). — URL: https://doi.org/10.1145/3183713. 3183734.

38. Raducanu, B. Micro Adaptivity in Vectorwise [Текст] / B. Râducanu, P. Boncz, M. Zukowski // Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. — New York, New York, USA : Association for Computing Machinery, 2013. — С. 1231—1242. — (SIGMOD '13). — URL: https://doi.org/10.1145/2463676.2465292.

39. Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age [Текст] / V. Leis [и др.] // Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. — Snowbird, Utah, USA : Association for Computing Machinery, 2014. — С. 743—754. — (SIGMOD '14). — URL: https://doi.org/10.1145/2588555.2610507.

40. Hekaton: SQL Server's Memory-Optimized OLTP Engine [Текст] / C. Diaconu [и др.] // Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. — New York, New York, USA : Association for Computing Machinery, 2013. — С. 1243—1254. — (SIGMOD '13). — URL: https://doi.org/10.1145/2463676.2463710.

41. The MemSQL Query Optimizer: A Modern Optimizer for Real-Time Analytics in a Distributed Database [Текст] / J. Chen [и др.] // Proc. VLDB Endow. — 2016. — Сент. — Т. 9, № 13. — С. 1401—1412. — URL: https://doi.org/10. 14778/3007263.3007277.

42. Impala: A modern, open-source sql engine for hadoop [Текст] / M. Kornacker [и др.] // In Proc. CIDR'15. — 2015.

43. Р. Бучацкий, Е. Ш. и. Обзор методов динамической компиляции запросов [Текст] / Е. Ш. и Р. Бучацкий // Труды Института системного программирования РАН. — 2018. — Т. 29, № 3. — URL: https://ispranproceedings.elpub. ru/jour/article/view/284.

44. Krikellas, K. Generating code for holistic query evaluation [Текст] / K. Krikellas, S. Viglas, M. Cintra //. — 01.2010. — С. 613—624.

45. Boncz, P. MonetDB/X100: Hyper-pipelining query execution [Текст] / P. Boncz, M. Zukowski, N. Nes // In CIDR. — 2005.

46. Compiled Query Execution Engine using JVM [Текст] / J. Rao [и др.] // 22nd International Conference on Data Engineering (ICDE'06). — 2006. — С. 23—23.

47. Improving Execution Efficiency of Just-in-Time Compilation Based Query Processing on GPUs [Текст] / J. Paul [и др.] // Proc. VLDB Endow. — 2020. — Окт. — Т. 14, № 2. — С. 202—214. — URL: https://doi.org/10.14778/3425879. 3425890.

48. Hardware-Conscious Hash-Joins on GPUs [Текст] / P. Sioulas [и др.] //. — 04.2019. — С. 698—709.

49. Scaling up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-Aware Data and Task Placement [Текст] /1. Psaroudakis [и др.] // Proc. VLDB Endow. — 2015. — Авг. — Т. 8, № 12. — С. 1442—1453. — URL: https: //doi.org/10.14778/2824032.2824043.

50. Access Path Selection in a Relational Database Management System [Текст] / P. G. Selinger [и др.] // Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data. — Boston, Massachusetts : Association for Computing Machinery, 1979. — С. 23—34. — (SIGMOD '79). — URL: https: //doi.org/10.1145/582095.582099.

51. Starburst Mid-Flight: As the Dust Clears [Текст] / L. M. Haas [и др.] // IEEE Trans. on Knowl. and Data Eng. — USA, 1990. — Март. — Т. 2, № 1. —

C. 143—160. — URL: https://doi.org/10.1109/69.50910.

52. Graefe, G. The EXODUS Optimizer Generator [Текст] / G. Graefe,

D. J. DeWitt // SIGMOD Rec. — New York, NY, USA, 1987. — Дек. — Т. 16, № 3. — С. 160—172. — URL: https://doi.org/10.1145/38714.38734.

53. Graefe, G. The Cascades Framework for Query Optimization [Текст] / G. Graefe // Data Engineering Bulletin. — 1995. — Т. 18.

54. Ioannidis, Y. E. Query Optimization [Текст] / Y. E. Ioannidis // ACM Comput. Surv. — New York, NY, USA, 1996. — Март. — Т. 28, № 1. — С. 121—123. — URL: https://doi.org/10.1145/234313.234367.

55. How Good Are Query Optimizers, Really? [Текст] / V. Leis [и др.] // Proc. VLDB Endow. — 2015. — Нояб. — Т. 9, № 3. — С. 204—215. — URL: https: //doi.org/10.14778/2850583.2850594.

56. Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches [Текст] / G. Cormode [и др.] // Found. Trends Databases. — Hanover, MA, USA, 2012. — Янв. — Т. 4, № 1—3. — С. 1—294. — URL: https://doi.org/10.1561/1900000004.

57. Rusu, F. Sketches for Size of Join Estimation [Текст] / F. Rusu, A. Dobra // ACM Trans. Database Syst. — New York, NY, USA, 2008. — Сент. — Т. 33, № 3. — URL: https://doi.org/10.1145/1386118.1386121.

58. Join Size Estimation Subject to Filter Conditions [Текст] / D. Vengerov [и др.] // Proc. VLDB Endow. — 2015. — Авг. — Т. 8, № 12. — С. 1530—1541. — URL: https://doi.org/10.14778/2824032.2824051.

59. LEO - DB2's LEarning Optimizer [Текст] / M. Stillger [и др.] // Proceedings of the 27th International Conference on Very Large Data Bases. — San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 2001. — С. 19—28. — (VLDB '01).

60. Deep Unsupervised Cardinality Estimation [Текст] / Z. Yang [и др.] // Proc. VLDB Endow. — 2019. — Нояб. — Т. 13, № 3. — С. 279—292. — URL: https: //doi.org/10.14778/3368289.3368294.

61. Sun, J. An End-to-End Learning-Based Cost Estimator [Текст] / J. Sun, G. Li // Proc. VLDB Endow. — 2019. — Нояб. — Т. 13, № 3. — С. 307—319. — URL: https://doi.org/10.14778/3368289.3368296.

62. Neo: A Learned Query Optimizer [Текст] / R. Marcus [и др.] // Proc. VLDB Endow. — 2019. — Июль. — Т. 12, № 11. — С. 1705—1718. — URL: https: //doi.org/10.14778/3342263.3342644.

63. Bao: Making Learned Query Optimization Practical [Текст] / R. Marcus [и др.] // Proceedings of the 2021 International Conference on Management of Data. — Virtual Event, China : Association for Computing Machinery, 2021. — С. 1275—1288. — (SIGMOD/PODS '21). — URL: https://doi.org/10. 1145/3448016.3452838.

64. Steering Query Optimizers: A Practical Take on Big Data Workloads [Текст] / P. Negi [и др.] // Proceedings of the 2021 International Conference on Management of Data. — Virtual Event, China : Association for Computing Machinery, 2021. — С. 2557—2569. — (SIGMOD/PODS '21). — URL: https: //doi.org/10.1145/3448016.3457568.

65. Horng, J.-T. A genetic algorithm for database query optimization [Текст] / J.-T. Horng, C.-Y. Kao, B.-J. Liu // Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence. — 1994. — 350—355 vol.1.

66. Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects [Текст] / C. Lutz [и др.] // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. — Portland, OR, USA : Association for Computing Machinery, 2020. — С. 1633—1649. — (SIGMOD '20). — URL: https://doi.org/10.1145/3318464.3389705.

67. Shanbhag, A. A Study of the Fundamental Performance Characteristics of GPUs and CPUs for Database Analytics [Текст] / A. Shanbhag, S. Madden, X. Yu // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. — Portland, OR, USA : Association for Computing Machinery, 2020. — С. 1617—1632. — (SIGMOD '20). — URL: https://doi.org/ 10.1145/3318464.3380595.

68. In-Depth Analysis of OLAP Query Performance on Heterogeneous Hardware [Текст] / D. Broneske [и др.] // Datenbank-Spektrum. — 2021. — Июль. — Т. 21.

69. Heimel, M. A First Step Towards GPU-assisted Query Optimization [Текст] / M. Heimel, V. Markl // International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures -ADMS 2012, Istanbul, Turkey, August 27, 2012 / под ред. R. Bordawekar, C. A. Lang. — 2012. — С. 33—44. — URL: http://www.adms-conf.org/heimel% 5C_adms12.pdf.

70. X-Device Query Processing by Bitwise Distribution [Текст] / H. Pirk [и др.] // Proceedings of the Eighth International Workshop on Data Management on New Hardware. — Scottsdale, Arizona : Association for Computing Machinery, 2012. — С. 48—54. — (DaMoN '12). — URL: https://doi.org/10.1145/2236584. 2236591.

71. Relational Query Coprocessing on Graphics Processors [Текст] / B. He [и др.] // ACM Trans. Database Syst. — New York, NY, USA, 2009. — Дек. — Т. 34, № 4. — URL: https://doi.org/10.1145/1620585.1620588.

72. Furst, E. Profiling a GPU Database Implementation: A Holistic View of GPU Resource Utilization on TPC-H Queries [Текст] / E. Furst, M. Oskin, B. Howe // Proceedings of the 13th International Workshop on Data Management on New Hardware. — Chicago, Illinois : Association for Computing Machinery, 2017. — (DAMON '17). — URL: https://doi.org/10.1145/3076113.3076119.

73. Hardware-Oblivious Parallelism for in-Memory Column-Stores [Текст] / M. Heimel [и др.] // Proc. VLDB Endow. — 2013. — Июль. — Т. 6, № 9. — С. 709—720. — URL: https://doi.org/10.14778/2536360.2536370.

74. Stone, J. E. OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems [Текст] / J. E. Stone, D. Gohara, G. Shi // Computing in Science Engineering. — 2010. — Т. 12, № 3. — С. 66—73.

75. Generating Custom Code for Efficient Query Execution on Heterogeneous Processors [Текст] / S. Breß [и др.] // The VLDB Journal. — Berlin, Heidelberg, 2018. — Дек. — Т. 27, № 6. — С. 797—822. — URL: https://doi.org/10.1007/ s00778-018-0512-y.

76. Rahman, R. Intel Xeon Phi Coprocessor Architecture and Tools: The Guide for Application Developers [Текст] / R. Rahman. — 1st. — USA : Apress, 2013.

77. Breß, S. Why It is Time for a HyPE: A Hybrid Query Processing Engine for Efficient GPU Coprocessing in DBMS [Текст] / S. Breß, G. Saake // Proc. VLDB Endow. — 2013. — Авг. — Т. 6, № 12. — С. 1398—1403. — URL: https://doi. org/10.14778/2536274.2536325.

78. GPU-Accelerated Database Systems: Survey and Open Challenges [Текст] / S. Breß [и др.] // Transactions on Large-Scale Data- and Knowledge-Centered Systems XV: Selected Papers from ADBIS 2013 Satellite Events / под ред. A. Hameurlain [и др.]. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2014. — С. 1—35. — URL: https://doi.org/10.1007/978-3-662-45761-0_1.

79. Funke, H. Efficient Generation of Machine Code for Query Compilers [Текст] / H. Funke, J. Mühlig, J. Teubner // Proceedings of the 16th International Workshop on Data Management on New Hardware. — Portland, Oregon : Association for Computing Machinery, 2020. — (DaMoN '20). — URL: https: //doi.org/10.1145/3399666.3399925.

80. Kohn, A. Adaptive Execution of Compiled Queries [Текст] / A. Kohn, V. Leis, T. Neumann // 2018 IEEE 34th International Conference on Data Engineering (ICDE). — 2018. — С. 197—208.

81. Kohn, A. Making Compiling Query Engines Practical [Текст] / A. Kohn, V. Leis, T. Neumann // IEEE Trans. on Knowl. and Data Eng. — USA, 2021. — Февр. — Т. 33, № 2. — С. 597—612. — URL: https://doi.org/10.1109/TKDE.2019. 2905235.

82. Voodoo - a Vector Algebra for Portable Database Performance on Modern Hardware [Текст] / H. Pirk [и др.] // Proc. VLDB Endow. — 2016. — Окт. — Т. 9, № 14. — С. 1707—1718. — URL: https://doi.org/10.14778/3007328.3007336.

83. Lattner, C. LLVM: An Infrastructure for Multi-Stage Optimization [Текст] : дис.... маг. / Lattner Chris. — Urbana, IL : Computer Science Dept., University of Illinois at Urbana-Champaign, 12.2002.

84. Shaikhha, A. Building Efficient Query Engines in a High-Level Language [Текст] / A. Shaikhha, Y. Klonatos, C. Koch // ACM Trans. Database Syst. — New York, NY, USA, 2018. — Апр. — Т. 43, № 1. — URL: https://doi.org/10. 1145/3183653.

85. Rompf, T. Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs [Текст] / T. Rompf, M. Odersky // Commun. ACM. — New York, NY, USA, 2012. — Июнь. — Т. 55, № 6. — С. 121—130. —URL: https://doi.org/10.1145/2184319.2184345.

86. URL: https://colfaxresearch.com/compiler-comparison/.

87. URL: https://gist.github.com/zeux/3ce4fcc3a43072b4315abde95319ecb6.

88. Weld : A Common Runtime for High Performance Data Analytics [Текст] / S. Palkar [и др.] //. — 2016.

89. HetExchange: Encapsulating Heterogeneous CPU-GPU Parallelism in JIT Compiled Engines [Текст] / P. Chrysogelos [и др.] // Proc. VLDB Endow. — 2019. — Янв. — Т. 12, № 5. — С. 544—556. — URL: https://doi.org/10.14778/ 3303753.3303760.

90. Gubner, T. Charting the Design Space of Query Execution Using VOILA [Текст] / T. Gubner, P. Boncz // Proc. VLDB Endow. — 2021. — Февр. — Т. 14, № 6. — С. 1067—1079. — URL: https://doi.org/10.14778/3447689.3447709.

91. Menon, P. Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together at Last [Текст] / P. Menon, T. C. Mowry, A. Pavlo // Proc. VLDB Endow. — 2017. — Сент. — Т. 11, № 1. — С. 1—13. — URL: https://doi.org/10.14778/3151113.3151114.

92. OmniDB: Towards Portable and Efficient Query Processing on Parallel CPU/GPU Architectures [Текст] / S. Zhang [и др.] // Proc. VLDB Endow. — 2013. — Авг. — Т. 6, № 12. — С. 1374—1377. — URL: https://doi.org/10. 14778/2536274.2536319.

93. Ramakrishnan, R. Database Management Systems [Текст] / R. Ramakrishnan, J. Gehrke. — 3-е изд. — USA : McGraw-Hill, Inc., 2002.

94. Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources [Текст] / E. Begoli [и др.] // Proceedings of the 2018 International Conference on Management of Data. — Houston, TX, USA : Association for Computing Machinery, 2018. — С. 221—230. — (SIGMOD '18). — URL: https://doi.org/10.1145/3183713.3190662.

95. Centaur: A Framework for Hybrid CPU-FPGA Databases [Текст] / M. Owaida [и др.] // 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). — 2017. — С. 211—218.

96. Mueller, R. Streams on Wires: A Query Compiler for FPGAs [Текст] / R. Mueller, J. Teubner, G. Alonso // Proc. VLDB Endow. — 2009. — Авг. — Т. 2, № 1. — С. 229—240. — URL: https://doi.org/10.14778/1687627.1687654.

97. Mueller, R. Glacier: A Query-to-Hardware Compiler [Текст] / R. Mueller, J. Teubner, G. Alonso // Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. — Indianapolis, Indiana, USA : Association for Computing Machinery, 2010. — С. 1159—1162. — (SIGMOD '10). — URL: https://doi.org/10.1145/1807167.1807307.

98. Date, C. J. Relational theory for computer professionals : what relational database are really all about [Text] / C.J. Date. — 1st ed. — CA : O'Reilly Media, 2013. —284 p.

99. Date, C. J. Databases, Types And the Relational Model: The Third Manifesto [Text] / C. J. Date, H. Darwen. — 3rd ed. — NY : Addison-Wesley, 2006. — 556 p.

100. Lan, H. A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration [Текст] / H. Lan, Z. Bao, Y. Peng // Data Science and Engineering. — 2021. — Март. — Т. 6, № 1. — С. 86—101. — URL: https://doi.org/10.1007/s41019-020-00149-7.

101. Du, W. Query optimization in a heterogeneous dbms [Текст] / W. Du, R. Krishnamurthy, M.-C. Shan // VLDB. Т. 92. — Citeseer. 1992. — С. 277—291.

102. Boulos, J. A neural networks approach for query cost evaluation [Текст] / J. Boulos, Y. Viemont, K. Ono // Transaction of Information Processing Society of Japan. — 1997. — Т. 38, № 12. — С. 2566—2575.

103. Predicting query execution time: Are optimizer cost models really unusable? [Текст] / W. Wu [и др.] // 2013 IEEE 29th International Conference on Data Engineering (ICDE). — 2013. — С. 1081—1092.

104. Liu, F. Forecasting the Cost of Processing Multi-Join Queries via Hashing for Main-Memory Databases [Текст] / F. Liu, S. Blanas // Proceedings of the Sixth ACM Symposium on Cloud Computing. — Kohala Coast, Hawaii: Association for Computing Machinery, 2015. — С. 153—166. — (SoCC '15). — URL: https: //doi.org/10.1145/2806777.2806944.

105. Boulos, J. Cost Estimation of User-Defined Methods in Object-Relational Database Systems [Текст] / J. Boulos, K. Ono // SIGMOD Rec. — New York, NY, USA, 1999. — Сент. — Т. 28, № 3. — С. 22—28. — URL: https://doi.org/ 10.1145/333607.333610.

106. The Landscape of Parallel Computing Research: A View from Berkeley [Текст]: тех. отч. / K. Asanovic [и др.] ; EECS Department, University of California, Berkeley. — 12.2006. — UCB/EECS-2006—183. — URL: http://www2.eecs. berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html.

107. Voss, M. Pro TBB: C++ Parallel Programming with Threading Building Blocks [Текст] / M. Voss, R. Asenjo, J. Reinders. — 1st. — USA : Apress, 2019.

108. Graph Pattern Matching: From Intractable to Polynomial Time [Текст] / W. Fan [и др.] // Proc. VLDB Endow. — 2010. — Сент. — Т. 3, № 1/2. — С. 264—275. — URL: https://doi.org/10.14778/1920841.1920878.

109. Valiente, G. An Algorithm for Graph Pattern-Matching [Текст] / G. Valiente, C. Martinez. — 1997. — Янв.

110. Соболь, И. М. Выбор оптимальных параметров в задачах со многими критериями [Текст] / И. М. Соболь, Р. Б. Статников. — 2-е изд. — М. : Дрофа, 2006. — 175 с.

111. A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II [Текст] / K. Deb [и др.] // Parallel Problem Solving from Nature PPSN VI / под ред. M. Schoenauer [и др.]. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2000. — С. 849—858.

112. Мелик-Адамян, А. Ф. Исследование и разработка алгоритмов многокритериальной оптимизации библиотечных элементов при проектировании нанометровых СБИС : дис. ... канд. техн. наук : 05.13.12 [Текст] / А. Ф. Мелик-Адамян. — М., 2009. — 176 с.

113. Yang, X.-S. Nature-Inspired Metaheuristic Algorithms [Текст] / X.-S. Yang. — Luniver Press, 2008.

Список рисунков

1 Различия в производительности запросов выполненных на разных

устройствах: ЦПУ и графический процессор................ 6

1.1 Принципиальная схема исполнения запроса в СУБД...........19

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

1.3 Сегментирование и секционирование таблицы в памяти.........44

2.1 Пример гетерогенного плана (сам план выделен синим цветом) для запроса select quantity from A join B on id=id_A where shipped>=2022-05-01 and shipped<=2022-05-31 and type=1

order by quantity limit 5........................51

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

2.3 Сравнение времени исполнения запроса содержащего сортировку и наивных реализаций шаблона........................66

2.4 Зависимость времени исполнения запроса от количества данных, к которым производится обращение......................69

2.5 Средняя ошибка предсказания стоимости физического плана запроса

в зависимости от класса соответствующего шаблона...........71

3.1 Принципиальная схема выполнения запроса в гетерогенной системе. . 81

3.2 Схема планирования задач в гетерогенной системе............83

3.3 Компоненты для компиляции и исполнения кода на графических процессорах Intel (слева)...........................85

3.4 Зависимость времени исполнения запросов набора NYC Taxi от распределения вычислений между устройствами.............87

3.5 Зависимость времени исполнения запросов набора NYC Taxi от распределения вычислений между устройствами с оптимизацией объединения ядер для графического процессора..............88

3.6 Схема исполнения кода через единый интерфейс.............90

Список таблиц

1 Отношение А. Хранит доступные позиции, их типы и описание.....47

2 Отношение B. Хранит данные о поставках позиций таблицы 1......47

3 Базовые операторы реляционной алгебры.................47

4 Результат запроса select quantity from A join B on id=id_A where shipped>=2022-05-01 and shipped<=2022-05-31 and

type=1.....................................48

Приложение А Генерируемый код шага

Листинг А.1 Пример сгенерированного промежуточного представления для NYC Taxi Q1 для ЦПУ

Function Attrs: uwtable define void @query_group_by_template(i8** nocapture readnone %byte_stream, i8* nocapture readonly %literals, i64* nocapture readnone %row_count_ptr , i64* nocapture readonly %frag_row_off_ptr, i32* %max_matched_ptr, i64* %agg_init_val, i64** %group_by_buffers, i32 %frag_idx, i64* %join_hash_tables , i32* %total_matched, i32* %error_code) #25 { .entry:

i8** %byte_stream, i32 0

5

15

%byte_stream, i32 1

%0 = getelementptr i8*, %1 = load i8*, i8** %0 %2 = getelementptr i8*, i8* %3 = load i8*, i8** %2

%row_count = load i64, i64* %row_count_ptr, align 8

%4 = load i32, i32* %max_matched_ptr, align 8

%crt_matched = alloca i32

%old_total_matched = alloca i32

%5 = call i32 @pos_start_impl(i32* %error_code)

%6 = call i32 @pos_step_impl()

%7 = call i32 @group_buff_idx_impl()

%8 = sext i32 %5 to i64

%9 = getelementptr i64*, i64** %group_by_buffers, i32 %7 %col_buffer = load i64*, i64** %9, align 8

%result_buffer = call i64* @init_shared_mem_nop(i64* %col_buffer, i32 0)

%10 = icmp slt i64 %8, %row_count

br i1 %10, label %.loop.preheader, label %.exit

loop.preheader: %11 = sext i32 %6 to i64 br label %.forbody

; preds = %.entry

preds = %.forbody, %

,forbody:

.loop.preheader

%pos = phi i64 [ %8, %.loop.preheader ], [ %13, %.forbody ] %12 = call i32 @row_func(i64* %result_buffer, i32* %crt_matched, i32* % total_matched, i32* %old_total_matched, i32* %max_matched_ptr, i64* %

35

40

45

50

55

agg_init_val, i64 %pos, i64* %frag_row_off_ptr, i64* %row_count_ptr, i8* %literals, i8* %1, i8* %3, i64* %join_hash_tables) %13 = add i64 %pos, %11 %14 = icmp slt i64 %13, %row_count br i1 %14, label %.forbody, label %._crit_edge

._crit_edge: ; preds = %.forbody

br label %.exit

.exit: ; preds = %._crit_edge, %

.entry

call void @write_back_nop(i64* %col_buffer, i64* %result_buffer, i32 0) ret void

}

; Function Attrs: alwaysinline

define i32 @row_func(i64* %group_by_buff, i32* %crt_matched, i32* % total_matched, i32* %old_total_matched, i32* %max_matched, i64* % agg_init_val, i64 %pos, i64* %frag_row_off, i64* %num_rows_per_scan, i8* %literals, i8* %col_buf0, i8* %col_buf1, i64* %join_hash_tables) #26 {

entry:

br i1 true, label %filter_true, label %filter_false

filter_true: ; preds = %entry

%0 = call i64 @fixed_width_int_decode(i8* %col_buf0, i32 2, i64 %pos) %1 = trunc i64 %0 to i16 %2 = sext i16 %1 to i64

%3 = call i64* @get_group_value_fast_keyless(i64* %group_by_buff, i64 %2,

i64 0, i64 0, i32 3) %agg_col_ptr = getelementptr i64, i64* %3, i32 0 %4 = sext i16 %1 to i64

call void @agg_id(i64* %agg_col_ptr, i64 %4)

%5 = call i64 @fixed_width_int_decode(i8* %col_buf1, i32 8, i64 %pos)

%agg_col_ptr1 = getelementptr i64, i64* %3, i32 1

%6 = call i64 @agg_sum_skip_val(i64* %agg_col_ptr1, i64 %5, i64

-9223372036854775808) %agg_col_ptr2 = getelementptr i64, i64* %3, i32 2 %7 = call i64 @agg_count_skip_val(i64* %agg_col_ptr2, i64 %5, i64

-9223372036854775808) br label %filter_false

filter_false: ; preds = %filter_true, %

entry

ret i32 0

}

Листинг А.2 Пример сгенерированного промежуточного представления для NYC Taxi Q1 для графического процессора.

define i64* @init_smem_func(i64*, i32) { .entry:

%thread_index = call i64 @get_thread_index()

%shared_mem_buffer = call i64* @declare_dynamic_shared_memory() %is_thread_inbound = icmp slt i64 %thread_index, 1 br i1 %is_thread_inbound, label %.body, label %.exit

.body: ; preds = %.entry

%byte_offset = mul i64 8, %thread_index

%dest_byte_stream = bitcast i64* %shared_mem_buffer to i8* %2 = getelementptr i8, i8* %dest_byte_stream, i64 %byte_offset %dest_slot_adr_0 = addrspacecast i8* %2 to i32 addrspace(3)* store i32 0, i32 addrspace(3)* %dest_slot_adr_0 %3 = add i64 %byte_offset, 4

%4 = getelementptr i8, i8* %dest_byte_stream, i64 %3 %dest_slot_adr_1 = addrspacecast i8* %4 to i32 addrspace(3)* store i32 0, i32 addrspace(3)* %dest_slot_adr_1 br label %.exit

10

15

20

25

30

; preds = %.body, %.entry

.exit:

call void @sync_threadblock() ret i64* %shared_mem_buffer

}

define void @reduce_from_smem_to_gmem(i64* %dest_buffer_ptr, i64* %

src_buffer_ptr, i32 %buffer_size) { .entry:

call void @sync_threadblock() %thread_index = call i64 @get_thread_index() %is_thread_inbound = icmp slt i64 %thread_index, 1 br i1 %is_thread_inbound, label %.body, label %.exit

.body: ; preds = %.entry

%src_byte_stream = bitcast i64* %src_buffer_ptr to i8* %dest_byte_stream = bitcast i64* %dest_buffer_ptr to i8* %0 = trunc i64 %thread_index to i32

%1 = call i32 @reduce_one_entry_idx(i8* %dest_byte_stream, i8* % src_byte_stream, i32 %0, i32 1, i8* null, i8* null, i8* null)

br label %.exit

45

55

65

.exit: ; preds = %.body, %.entry

ret void

}

; Function Attrs: uwtable

define void @query_group_by_template(i8** nocapture readnone %byte_stream, i8* nocapture readonly %literals, i64* nocapture readnone %row_count_ptr , i64* nocapture readonly %frag_row_off_ptr, i32* %max_matched_ptr, i64* %agg_init_val, i64** %group_by_buffers, i32 %frag_idx, i64* %join_hash_tables , i32* %total_matched, i32* %error_code) #25 { .entry:

%0 = getelementptr i8*, i8** %byte_stream, i32 0 %1 = load i8*, i8** %0

%row_count = load i64, i64* %row_count_ptr, align 8

%2 = load i32, i32* %max_matched_ptr, align 8

%crt_matched = alloca i32

%old_total_matched = alloca i32

%3 = call i32 @pos_start_impl(i32* %error_code)

%4 = call i32 @pos_step_impl()

%5 = call i32 @group_buff_idx_impl()

%6 = sext i32 %3 to i64

%7 = getelementptr i64*, i64** %group_by_buffers, i32 %5 %col_buffer = load i64*, i64** %7, align 8

%result_buffer = call i64* @init_smem_func(i64* %col_buffer, i32 8)

%8 = icmp slt i64 %6, %row_count

br i1 %8, label %.loop.preheader, label %.exit

.loop.preheader: ; preds = %.entry

%9 = sext i32 %4 to i64 br label %.forbody

.forbody: ; preds = %.forbody, %

.loop.preheader

%pos = phi i64 [ %6, %.loop.preheader ], [ %11, %.forbody ] %10 = call i32 @row_func(i64* %result_buffer, i32* %crt_matched, i32* % total_matched, i32* %old_total_matched, i32* %max_matched_ptr, i64* % agg_init_val, i64 %pos, i64* %frag_row_off_ptr, i64* %row_count_ptr, i8* %literals, i8* %1, i64* %join_hash_tables) %11 = add i64 %pos, %9 %12 = icmp slt i64 %11, %row_count br i1 %12, label %.forbody, label %._crit_edge

,_crit_edge: ; preds = %.forbody

br label %.exit

.exit: ; preds = %._crit_edge, %

.entry

call void @reduce_from_smem_to_gmem(i64* %col_buffer, i64* %result_buffer,

i32 8) ret void

Приложение Б Запросы набора NYC Taxi

Данные набора NYC Taxi1 содержат информацию о 1.1 миллиардов совершенных поездок на такси в Нью-Йорке за шесть лет, начиная с января 2009 года.

Листинг Б.1 NYC Taxi Q1.

SELECT cab_type,

count(*) FROM trips GROUP BY cab_type;

Листинг Б.2 NYC Taxi Q2.

SELECT passenger_count,

avg(total_amount) FROM trips

GROUP BY passenger_count;

Листинг Б.3 NYC Taxi Q3.

SELECT passenger_count, extract( year

from pickup_datetime ) AS pickup_year, count(*) FROM trips

GROUP BY passenger_count, pickup_year;

5

Листинг Б.4 NYC Taxi Q4.

SELECT passenger_count, extract( year

from pickup_datetime ) AS pickup_year,

cast(trip_distance as int) AS distance, count(*) AS the_count FROM trips

1https://toddwschneider.com/posts/analyzing-1-1-billion-nyc-taxi-and-uber-trips-with-a-vengeance/

5

GROUP BY passenger_count, pickup_year, distance ORDER BY pickup_year, the_count desc;