Модели и методы планирования и выполнения запросов в колоночных СУБД с поздней материализацией тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Чернышев Георгий Алексеевич

• Чернышев Георгий Алексеевич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Чернышев Георгий Алексеевич

Введение

Глава 1. Обзор

1.1 Исполнение запросов в современных СУБД

1.2 Колоночные СУБД

1.3 Материализация

1.3.1 Поздняя материализация в работах G. Copeland

1.3.2 Поздняя материализацией в проекте Fractured Mirrors

1.3.3 Оператор FlashJoin и эксперименты с поздней материализацией в PostgreSQL

1.3.4 Поздняя материализация в системе C-Store

1.3.5 Поздняя материализация и СУБД в оперативной памяти

1.3.6 Сравнительный анализ подходов к материализации

1.4 История и современное состояние исследований в области колоночных СУБД

1.5 Выводы

Глава 2. Подход к построению исполняемых планов запросов

2.1 Предварительные сведения

2.2 Обзор подхода

2.3 Кортежное и позиционное представление данных

2.4 Кортежные и позиционные операторы

2.4.1 Оператор выборки

2.4.2 Операторы соединения и прямого произведения

2.4.3 Операторы агрегации и сортировки

2.4.4 Операторы проекции и расширенной проекции

2.4.5 Операторы материализации

2.5 Метод ультра-поздней материализации

2.5.1 Планирование запросов

2.5.2 Выполнение запросов

2.6 Выводы

Стр.

Глава 3. Логическая алгебра запросов с поддержкой

ультра-поздней материализации

3.1 Формальное определение класса запросов SPJSAf^

3.2 Логическая алгебра запросов

3.2.1 Базовые объекты алгебры

3.2.2 PT-алгебра

3.3 Классы выражений PT-алгебры

3.4 Семантика SQL-выражений

3.5 Выразимость SQL-запросов в классах выражений PT-алгебры

3.6 Выводы

Глава 4. Программная архитектура исполнения запросов

4.1 О системе

4.2 Данные и их представление

4.2.1 Схема данных

4.2.2 Поддерживаемые типы данных

4.2.3 Управление данными

4.3 Структуры представления и обработки данных в оперативной памяти

4.3.1 Блоки

4.3.2 Заголовки

4.3.3 Итераторы

4.3.4 Билдеры

4.4 Исполнение запросов

4.4.1 Поддержка основных операторов

4.4.2 Считыватели

4.4.3 Вычисление запросов

4.4.4 Тестирующая подсистема

4.5 Выводы

Глава 5. Эксперименты

5.1 Общая схема экспериментов

5.2 Описание Star Schema Benchmark

5.3 Инфраструктура экспериментов

Стр.

5.3.1 Аппаратные и программные характеристики использованного оборудования, методика экспериментов

5.3.2 Подготовка ГсзВЕ

5.4 Сравнение ультра-поздней материализации с классическим строчным подходом (эксперимент 1)

5.5 Сравнение ультра-поздней материализации с методом ранней материализации (эксперимент 2)

5.6 Сравнение ультра-поздней материализации с методом поздней материализации (эксперимент 3)

5.7 Сравнение ультра-поздней материализации и колоночной СУБД MaгiaDB ColumnStoгe (эксперимент 4)

5.8 Выводы и дискуссия

Заключение

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

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

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

Введение диссертации (часть автореферата) на тему «Модели и методы планирования и выполнения запросов в колоночных СУБД с поздней материализацией»

Введение

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

Одним из востребованных на сегодняшний день подходов в этой области является аналитическая обработка данных (Analytical Processing) — эффективное исполнение сложных запросов, которые не меняют исходные данные (Read-Only Queries). В качестве примера можно привести задачи бизнес-планирования — составление отчетов, вычисление различных метрик, предсказание продаж и т.д. Подобные запросы требуют существенных вычислительных ресурсов, поэтому критически важным оказывается их быстродействие.

Колоночный подход (Column-Stores) развивается с конца 80-х годов прошлого века и является одним из возможных путей для решения этой задачи [30]. Он подразумевает "хранение и обработку данных поколоночно" и в отличие от классических, строчных СУБД (Row-Stores) позволяет эффективно использовать не только значения атрибутов, но и их позиции (смещение от начала колонки). Колоночный подход активно развивается в рамках существующих промышленных СУБД, таких как Oracle [117], Microsoft SQL Server [120], IBM DB2 [158]. Кроме того, созданы специализированные колоночные СУБД, такие как Vertica [118], Vector (бывший VectorWise) [94], Hyper [111], SAP HANA [75; 166], Google F1 [195]. И в то же время в этой области активно продолжаются исследования, поскольку ещё не исчерпан весь потенциал этого подхода.

В рамках колоночного подхода важной является стратегия материализации (Materialization Strategy) данных [33]. Речь идет о возможности в рамках выполнения запросов оперировать не с самими данными, а с их позициями, и далее уже в самом конце выполнить финальное считывание данных. Именно в случае колоночного подхода эта возможность полноценно доступна и позволяет добиться значительного повышения производительности при аналитической обработке данных.

Существует два принципиально различных вида стратегий материализации — ранняя материализация и поздняя материализация. Ранняя материали-

зация (Early Materialization) позволяет считывать из базы данных отдельные колонки таблиц, составлять из них записи и продолжать обработку запроса аналогично классическим системам. Таким образом, этот метод позволяет не обрабатывать неиспользуемые в запросе атрибуты, которые строчные СУБД будут вынуждены считать и обработать. Кроме того, ранняя материализация позволяет эффективно использовать компрессию данных. Наконец, следует отметить, что этот метод достаточно прост в реализации и дает существенный прирост производительности на "широких" таблицах в тех случаях, когда запрос затрагивает мало атрибутов. Ранняя материализация используется, практически, во всех индустриальных колоночных СУБД.

Поздняя материализация (Late Materialization) подразумевает, что на ранних стадиях исполнения запроса задействуется минимально необходимый набор реальных значений, а остальные значения представляются позициями — ссылками в исходные таблицы. Значения таких колонок считываются по этим позициям позже, по мере необходимости. Уместно примененный, метод поздней материализации позволяет значительно ускорить выполнение запросов за счет снижения объема считываемых данных и уменьшения размера промежуточных результатов, что особенно актуально для дисковых СУБД. Однако поздняя материализация не всегда оказывается эффективной, приводя в ряде случаев к снижению производительности. Кроме того, ее реализация требует нетривиальных архитектурных решений. При этом является открытым вопрос о том, когда именно при выполнении запроса следует выполнять материализацию данных и каким образом должны быть устроены планы исполнения запросов, а также составляющие их операторы.

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

позволяет уменьшить объем данных, "проводимых" через этот оператор, а также уменьшить размер внутренних структур данных, таких как хеш-таблицы.

Современные СУБД подразделяют [47] на дисковые (Disk-Based) и размещённые в оперативной памяти (Main Memory, In-Memory). Первые предназначены для обработки данных, которые из-за своего размера не могут быть полностью размещены в оперативной памяти и поэтому во время работы СУБД частично находятся на жестком диске. Вторые предназначены для обработки данных, которые целиком находятся в оперативной памяти. Несмотря на активное развитие СУБД, размещенных в оперативной памяти, дисковые СУБД продолжают оставаться актуальными из-за энергозависимости и ограниченности объемов доступной оперативной памяти, ее относительно высокой стоимости, а также феномена больших данных (Big Data). Кроме того, в настоящее время существенно понизилась стоимость магнитных жестких дисков и твердотельных накопителей, успешно коммерциализируются новые типы энергонезависимой памяти.

За всю историю развития колоночного подхода было создано всего несколько академических дисковых СУБД с поддержкой поздней материализации (Fractured Mirrors [157], C-Store [174], FlashJoin [181], а также система G. Copeland и S. Khoshafian [66; 113]). Однако ни одна из них не использует позднюю материализацию одновременно и в выборках, и в соединениях, хотя оба случая, реализованные по отдельности, показали свою эффективность в целом ряде случаев (Fractured Mirrors, C-Store, FlashJoin). Следовательно, есть основания полагать, что их комбинация будет еще более эффективной и сможет значительно повысить производительность колоночной СУБД при выполнении аналитических запросов, в планах которых сочетаются высокоселективные операторы соединения и выборки.

Следует упомянуть об индустриальной активности в РФ в области базы данных и колоночных систем. Известен стартап Яндекса ClickHouse [62] — аналитическая СУБД с открытым исходным кодом. Также компания Яндекс выпустила собственную СУБД YDB [196], которая на данный момент является самой значительной отечественной разработкой в области баз данных. Также можно упомянуть про российскую компанию Postgres Professional, занимающуюся разработкой и адаптацией к российскому рынку известной открытой СУБД Postgres [11]. Наконец, имеется ряд российских проектов в области управления данными, Юнидата [18], ArenaData [10], которые работают с данными на более

высоком уровне, чем СУБД, но также затрагивают различные системные вопросы обработки данных. Также следует упомянуть компанию Radix (член группы компаний DigitalDesign) [12], разрабатывающую системы хранения данных.

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

Степень разработанности темы. Первые исследования по колоночным СУБД появились в 70-е годы (работы G. Wiederhold, R. Lorie, D. S. Batory) [44; 124; 190]. Однако принято считать, что колоночные системы в современном виде были сформированы лишь к концу 80-х исследователями I. Karasalo и P. Svensson (система Cantor) [108; 109; 175], а также G. Copeland и S. Khoshafian [66; 113], причем именно последние ввели такие понятия как NSM (N-ary Storage Model) и DSM (Decomposition Storage Model), обозначившие строчный и колоночный подходы, и эти термины используются до сих пор. Однако в 80-е годы производительность DSM-подхода оказалась неудовлетворительной из-за недостаточной производительности аппаратного обеспечения, и дальнейшего развития этот подход не получил. К нулевым годам существенно выросла производительность оборудования, а также были выделены [77] в отдельный класс аналитические системы (Decision Support Systems, OLAP Systems), которые сняли необходимость поддержки динамического обновления данных. Всё это послужило причиной возобновления интереса к колоночному подходу.

Сначала колоночные системы реализовывались на уровне менеджера буферов (M. Shao, R. A. Hankins, A. Ailamaki, R. Ramamurthy) [37; 88; 157; 165], позднее были созданы полноценные академические колоночные СУБД — MonetDB (M. Kersten, S. Manegold, S. Idreos, Нидерланды) [94] и C-Store (M. Stonebraker, D. Abadi, S. Madden, США) [31; 174].

Говоря о поздней материализации, следует отметить работы G. Copeland и S. Khoshafian, а также системы Fractured Mirrors, C-Store, FlashJoin [181], MonetDB и Hyrise [84]. Две последние системы реализовывали позднюю материализацию в контексте СУБД в оперативной памяти, а остальные либо использовали устаревшую модель выполнения запросов (G. Copeland и S.

Khoshafian), либо предлагали неполную модель поздней материализации (системы Fractured Mirrors, C-Store, FlashJoin). Их неполнота заключалась в том, что они рассматривали позднюю материализацию либо в соединениях, либо в выборках, но не одновременно.

В настоящее время интерес в области колоночных систем сместился в сторону обработки запросов в оперативной памяти, векторизации исполнения запросов, компиляции запросов, систем визуальной и встроенной аналитики, вычислений на периферии. Среди работ этих направлений можно отметить исследования группы HyPer (T. Neumann, A. Kemper, V. Leis, Германия) [111; 121], а также работы по системам H2O (I, Alagiannis, A. Ailamaki, S. Idreos) [38], Peloton (A. Pavlo, P. Menon) [130], DuckDB (M. Raasveldt, H. Mühleisen) [154; 155].

В России тематикой баз данных занимались различные исследователи, среди которых следует упомянуть Л.А. Калиниченко [22; 55; 105; 106], М.Р. Когаловского [7-9], С.А. Ступникова [24; 25; 107; 169]. При этом вопросы исполнения запросов исследовались С.Д. Кузнецовым [13-17; 177], Б.А. Новиковым [1; 19; 20; 46; 116], М.Л. Цымблером [5; 6; 21; 26]. Исполнение запросов непосредственно в колоночных СУБД исследовал Л.Б. Соколинский [2-4], который рассматривал колоночное индексирование в распределенных системах.

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

Объектом исследования является поздняя материализация в дисковых колоночных СУБД, направленная на повышение эффективности работы с позициями при планировании и выполнении запросов к аналитическим базам данных.

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

Целью данной работы является разработка подхода к планированию и выполнению SQL-запросов в дисковых колоночных СУБД, направленного на повышение эффективности использования позиций одновременно в выборках и

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

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

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

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

4. Провести экспериментальное исследование различных видов материализации.

Методология и методы исследования. Методология диссертационного исследования основывается на идеях и подходах в области баз данных, нацеленных на построение высокоэффективных исполнителей запросов. В работе использована блочная модель Volcano (Blocked Pull-Based Volcano Model) [82], подход по созданию логической алгебры запросов (Logical Query Algebra) [137], а также модифицированный индекс соединения (Join Index) [185]. Программная реализация выполнена с помощью языка программирования C++.

Научная новизна полученных в ходе исследования результатов заключается в следующем.

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

2. Предложенная модель формальной семантики SQL-запросов также является новой. Подобные модели, называемые в литературе логическими алгебрами запросов, уже существовали для колоночных систем. Однако они либо ориентированы на обработку данных в оперативной памяти (работы P. Boncz и M. Kersten, Нидерланды) [48], и поэтому имеют иной набор операций, либо имеют другую модель поздней материализации (работы M. Stonebraker и др., D. Abadi и др., США) [32;33; 174].

3. Предложенная программная архитектура является новой: в рамках данного диссертационного исследования была расширена блочная модель Volcano (работы G. Graefe) для поддержки двух различных промежуточных представлений данных — кортежного и позиционного. При этом была разработана новая двухуровневая схема исполнения запросов, где на первом уровне промежуточные результаты представлены позиционными данными, а на втором — в виде записей. Для избегания ромбовидных шаблонов в потоках данных была предложена концепция считывателей, которая также является новой.

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

Достоверность полученных результатов обеспечивается формальными доказательствами, а также экспериментами с использованием индустриального эталонного теста SSB (Star Schema Benchmark) [138].

Результаты диссертационного исследования были доложены на следующих конференциях и семинарах: 11th International Andrei Ershov Memorial Conference on Perspectives of System Informatics (PSI 2017, Москва, Россия) [59]; The Second Conference on Software Engineering and Information Management (SEIM 2017, Санкт-Петербург, Россия) [58]; 24th International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data (DOLAP 2022, Эдинбург, Великобритания) [60]; на семинарах российской секции ACM SIGMOD №177, №202, №232 (2015, 2018, 2023 гг., МГУ, Москва, Россия).

Кроме того, по тематике диссертации были дополнительно сделаны доклады на следующих конференциях и семинарах: 19th East-European Conference on Advances in Databases and Information Systems (ADBIS 2015, Футуроскоп, Пуа-тье, Франция) [57]; Third Conference on Software Engineering and Information Management (SEIM 2018, Санкт-Петербург, Россия) [182]; 9th International Conference on Model and Data Engineering (MEDI 2019, Тулуза, Франция) [133]; 22nd International Workshop On Design, Optimization, Languages and Analytical Processing of Big Data (DOLAP 2020, Копенгаген, Дания) [78]; 10th International

Conference on Model and Data Engineering (MEDI 2021, Таллин, Эстония) [170]; 26th European Conference on Advances in Databases and Information Systems (ADBIS 2022, Турин, Италия) [150].

Публикации. Основные результаты по теме диссертации опубликованы в семи печатных работах [23; 27-29; 58-60], шесть из них зарегистрированы в РИНЦ [23; 27-29; 58; 59]. При этом четыре статьи изданы в журналах рекомендованных ВАК [23; 27-29], четыре статьи опубликованы в изданиях, входящих в базы цитирования Scopus или Web of Science [27; 58-60].

Статьи [28; 29] были написаны автором диссертационной работы единолично. Статьи [23; 27; 58-60] написаны в соавторстве. Личный вклад автора в этих публикациях заключается в следующем.

В статье [23] автор предложил архитектуру системы, варианты реализации межпотокового взаимодействия; соавтор выполнил программную реализацию и провел эксперименты. В статье [27] автор предложил архитектуру системы, подход к построению исполняемых планов запросов, двухуровневую модель выполнения запросов и логическую алгебру запросов; соавторы выполнили программную реализацию. В статье [58] автор разработал архитектуру системы, предложил план исследования и схему экспериментов; соавторы выполнили развёртывание системы и эксперименты. В работе [59] автор создал обзор и представил мотивацию работы, предложил архитектуру системы, а также подход к построению исполняемых планов запросов; соавторы выполнили программную реализацию. В работе [60] автору принадлежит постановка задачи, обзор и анализ существующих решений, формализация трех методов материализации (включая предложенный метод ультра-поздней материализации), архитектура системы, реализация, а также план экспериментов; соавторы выполнили часть экспериментов.

Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения. Полный объём диссертации составляет 180 страниц, включая 52 рисунка и 2 таблицы. Список литературы содержит 1 наименование.

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

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

2. Модель формальной семантики SQL-запросов для класса SPJSA^^j — варианта конъюнктивного SPJ-класса с поддержкой агрегации, группировки и сортировки; доказана выразимость различных методов материализации (классических ранней и поздней, предложенной ультра-поздней) в рамках предложенной модели.

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

Основные научные результаты

— Подход к построению исполняемых планов запросов на основе использования поздней материализации в выборках и соединениях (см. [60] — раздел 2; [27] — раздел 4; [59] — раздел 5; личный вклад автора диссертации в получении данного результата — 100%).

— Метод ультра-поздней материализации (см. [60] — раздел 4.1; [27] — раздел 4; личный вклад автора диссертации в получении данного результата — 100%).

— Логическая алгебра запросов, позволяющая выражать различные методы материализации (см. [27] приложение А, личный вклад автора диссертации в получении данного результата составляет не менее 80%).

— Программная архитектура исполнителя запросов, поддерживающего несколько методов материализации (см. [60] — раздел 3; [27] — разделы 3-5; [59] — раздел 5; [58] — Раздел 3; [23] — раздел "аспекты межпотокового взаимодействия"; [28] — разделы 3.1, 3.3 и 4; [29] — разделы 2-4; личный вклад автора диссертации в получении данного результата — 100%).

— Экспериментальное исследование методов материализации, выполненное на эталонном тестовом наборе Star Schema Benchmark (см. [60] раздел 5; личный вклад автора диссертации в получении данного результата составляет не менее 80%).

Глава 1. Обзор

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

1.1 Исполнение запросов в современных СУБД

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

Согласно классической работе, описывающей архитектуру СУБД [91], обработка запроса состоит из следующих фаз.

1. Разбор (Query Parsing) и авторизация (Query Authorization).

2. Перезапись запроса (Query Rewrite).

3. Оптимизация запроса (Query Optimization).

4. Выполнение запроса (Query Execution).

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

Разбор и авторизация запроса подразумевают разбор и преобразование его исходной текстовой строки в промежуточное представление с помощью синтаксического анализатора. Эта стадия необходима для проверки синтаксической корректности запроса, а также для обеспечения удобства реализации последующих шагов. В случае успешного разбора создается промежуточное представление запроса и запускается процесс разрешения имен и ссылок (Name and Reference Resolution), в рамках которого выполняется приведение к канонической форме используемых имен таблиц и замена псевдонимов. Затем

проверяется корректность обращения к таблицам и атрибутам, выполняется проверка существования таблиц, а также проверка типов различных выражений, их корректности. Таким образом можно обнаружить несовпадение типов данных, например, попытку умножения строкового типа на число с плавающей точкой. Помимо этого проверяется допустимость теоретико-множественных операций над таблицами, таких как объединение, выражаемое ключевым словом UNION из SQL. Наконец, выполняется авторизация — проверка допустимости тех или иных действий запроса. Так, например, пользователю может быть отказано в доступе к какой-то таблице или атрибуту. Эта проверка вынесена на данный этап, поскольку чем раньше обнаружатся факты каких-либо запретов, тем раньше можно будет прекратить выполнение запроса, сэкономив вычислительные ресурсы. Отметим, что авторизацию не всегда возможно полностью выполнить до запуска запроса. Существуют СУБД, поддерживающие безопасность на уровне строк (Row-Level Security), в которых невозможно определить допустимость действий до момента непосредственного выполнения запроса.

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

— раскрытие представлений,

— вычисление константных подвыражений,

— логическую перезапись предикатов,

— семантическую оптимизацию,

— «уплощение» подзапросов.

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

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

на выдачу пользователю

на выдачу пользователю

х Tl.id = T2.ref

G

Хеш-

соединение

х Tl.id = T2.ref

Последовательное сканирование

G

Выборка по индексу

T1.a > 10

T2.a = 100

T1.a > 10 T2.a = 100

б) Физический план запроса

а) Логический план запроса

Рисунок 1.1 — Планы запроса SELECT * FROM T1, T2 WHERE T1.a > 10 AND

T2.a = 100 AND T1.id = T2.id

Существует два основных типа планов запросов — логический и физический (Logical and Physical Query Plan) [137]. В логическом плане (см. рис. 1.1а) каждый оператор является абстрактным и принадлежит логической алгебре запросов. Логический план строится только на основе доступа к каталогу СУБД, но не к самим данным. В большинстве случаев он не пригоден для непосредственного исполнения, так как обычно имеет высокую стоимость выполнения. Кроме того, он не содержит необходимых деталей: например, в случае распределенной системы он может не иметь информации об узлах исполнения. Однако, такой тип плана может быть использован для выполнения различных преобразований запроса с целью его оптимизации (трансформационная оптимизация). После выполнения этих преобразований по логическому плану уже строится физический план, возможно, с применением методов стоимостной оптимизации.

В противоположность логическому, физический план запроса (см. рис. 1.1б) более конкретен, так как имеет доступ к непосредственным данным. Он содержит все детали выполнения, такие как способ выполнения и оцениваемая стоимость выполнения операторов, узлы исполнения (в случае распределенных запросов), различные настройки СУБД и прочее. На рис. 1.1 демонстрируется, что в случае физического плана оператор соединения конкретизируется до оператора хеш-соединения, а выборка из таблицы T2 осуществляется с помощью индекса.

10

class AbstractNode{ private:

AbstractNode* LChild; AbstractNode* RChild; void* Data; public :

int Open () ; int Close () ; void* GetNext () ;

Рисунок 1.2 — Интерфейс итератора

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

Список литературы диссертационного исследования кандидат наук Чернышев Георгий Алексеевич, 2025 год

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

1. Домбровская Г. Р., Новиков Б. А. Настройка приложений баз данных.— БХВ-Петербург, 2006. — С. 236.

2. Иванова Е. В., Соколинский Л. Б. Колоночный сопроцессор баз данных для кластерных вычислительных систем // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. — 2015. — Т. 4, № 4. — С. 5-31.

3. Иванова Е. В., Соколинский Л. Б. Параллельная декомпозиция реляционных операций на основе распределенных колоночных индексов // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. — 2015. — Т. 4, № 4. — С. 80-100.

4. Иванова Е. В., Соколинский Л. Б. Методы параллельной обработки сверхбольших баз данных с использованием распределенных колоночных индексов // Программирование. — 2017. — Т. 43, № 3. — С. 3-21.

5. Иванова Е. В., Цымблер М. Л. Внедрение концепции матричного профиля в реляционную СУБД для интеллектуального анализа временных рядов // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. — 2021. — Т. 10, № 3. — С. 72-87.

6. Зыкин В. С., Цымблер М. Л. Обновление многотабличных представлений на основе коммутативных преобразований базы данных // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. — 2019.— Т. 8, № 2. — С. 92-106.

7. Когаловский М. Р. Энциклопедия технологий баз данных: Эволюция технологий, технологии и стандарты, инфраструктура, терминология. — Финансы и статистика, 2002. — С. 800.

8. Когаловский М. Р. Перспективные технологии информационных систем. — ДМК-Пресс, 2003. — С. 288.

9. Когаловский М. Р., Калиниченко Л. А. Концептуальное и онтологическое моделирование в информационных системах // Программирование. — 2009. — Т. 35, № 5. — С. 3-25.

10. Компания ArenaData // https://network.arenadata.io/.— [Online; accessed 12/06/2025].

11. Компания Postgres Professional // https://postgrespro.ru. — [Online; accessed 12/06/2025].

12. Компания Radix // https://www.raidix.ru.— [Online; accessed 12/06/2025].

13. Кузнецов С. Д. Объектные модели ODMG и SQL десять лет спустя: нет противоречий // Труды Института системного программирования РАН. — 2015. — Т. 27, № 1. — С. 173-192.

14. Кузнецов С. Д. Новые устройства хранения данных и их влияние на технологию баз данных // Программная инженерия.— 2018.— № 4.— С. 147-155.

15. Кузнецов С. Д. В ожидании нативных архитектур СУБД на основе энергонезависимой основной памяти // Труды Института системного программирования РАН. — 2020. — Т. 32, № 1. — С. 153-180.

16. Кузнецов С. Д. Типизированные неизвестные значения: шаг к решению проблемы представления отсутствующей информации в реляционных базах данных // Труды Института системного программирования РАН. — 2023. — Т. 35, № 2. — С. 73-100.

17. Кузнецов С. Д., Велихов П. Е., Фу Ц. Аналитика в реальном времени: преимущества, ограничения и компромиссы // Программирование. — 2023. — Т. 49, № 1. — С. 3-31.

18. Кузнецов С. В., Цырюльниковов А. В., Кознов Д. В. Unidata: открытая компонентная платформа для разработки MDM-решений // Труды Института системного программирования РАН.— 2021.— Т. 33, № 6.— С. 149-160.

19. Новиков Б. А., Графеева Н. Г., Михайлова Е. Г. Базы данных: современный пейзаж в исторической перспективе // Компьютерные инструменты в образовании. — 2016. — № 2. — С. 3-12.

20. Павлов В. А., Новиков Б. А. Базы данных для обработки массивов: взгляд изнутри // Труды Института системного программирования РАН. — 2018. — Т. 30, № 1. — С. 137-160.

21. Пан К. С., Соколинский Л. Б., Цымблер М. Л. Интеграция параллелизма в СУБД с открытым кодом // Открытые системы. СУБД. — 2013. — № 9. — С. 56-58.

22. Скворцов Н. А., Калиниченко Л. А., Ковалев Д. Ю. Концептуальное моделирование предметных областей с интенсивным использованием данных // Труды DAMDID/RCDL'2016 «Аналитика и управление данными использованием данных», Ершово, 11-14 октября 2016.— 2016.— С. 7-15.

23. Смирнов К.К., Чернышев Г.А. Сетевые и многопоточные аспекты архитектуры распределенных СУБД // Программные продукты и системы. — 2011. — № 1. — С. 164-168.

24. Ступников С.А. Спецификация и реализация разномодельных правил интеграции данных (Specification and Implementation of Multimodel Data Integration Rules) // Труды XIX Международной конференции «Аналитика и управление данными в областях с интенсивным использованием данных» (DAMDID/RCDL'2017), Москва, Россия, 10-13 октября 2017.— 2017. —С. 197-205.

25. Ступников С. А., Скворцов Н. А., Брюхов Д. О. Перспективные методы реализации инкрементального обновления материализованных представлений в современных реляционных системах управления базами данных // Системы и средства информ. — 2025. — Т. 35, № 1. — С. 95-110.

26. Цымблер М. Л. Обзор методов интеграции интеллектуального анализа данных в реляционные СУБД // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. — 2019. — Т. 8, № 2. — С. 32-62.

27. Чернышев Г.А., Галактионов В.А и др. PosDB: обзор архитектуры // Программирование. — 2018. — № 1. — С. 60-76.

28. Чернышев Г.А. Обзор подходов к организации физического уровня в СУБД // Труды СПИИРАН. — 2013. — Т. 1, № 24. — С. 222-276.

29. Чернышев Г.А. Организация физического уровня колоночных СУБД // Труды СПИИРАН. — 2013. — Т. 7, № 30. — С. 204-222.

30. Abadi D., Boncz P., Harizopoulos S. The Design and Implementation of Modern Column-Oriented Database Systems. — Hanover, MA, USA : Now Publishers Inc., 2013.

31. Abadi D., Madden S., Ferreira M. Integrating compression and execution in column-oriented database systems // Proceedings of the 2006 ACM SIGMOD international conference on Management of data. — SIGMOD '06. — New York, NY, USA : ACM, 2006. — P. 671-682.

32. Abadi D., Madden S., Hachem N. Column-stores vs. row-stores: how different are they really? // Proceedings of the 2008 ACM SIGMOD international conference on Management of data. — SIGMOD '08. — New York, NY, USA : ACM, 2008. — P. 967-980.

33. Abadi D., Myers D., et al. Materialization Strategies in a Column-Oriented DBMS // 2007 IEEE 23rd International Conference on Data Engineering. — 2007. — April. — P. 466-475.

34. Abdel Kader R., Boncz P., et al. ROX: Run-time Optimization of XQueries // Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. — SIGMOD '09.— New York, NY, USA : ACM, 2009.— P. 615-626.

35. Abello A., Romero O. OLAP // Encyclopedia of Database Systems. — Springer US, 2009. —P. 1947-1947.

36. Abuzaid F., Kraft P., et al. DIFF: A Relational Interface for Large-Scale Data Explanation // Proc. VLDB Endow.— 2018. —Dec.— Vol. 12, no. 4.— P. 419-432.

37. Ailamaki A., DeWitt D., et al. Weaving Relations for Cache Performance // Proceedings of the 27th International Conference on Very Large Data Bases. — VLDB '01.— San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 2001. —P. 169-180.

38. Alagiannis I., Idreos S., Ailamaki A. H2O: A Hands-free Adaptive Store // Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. — SIGMOD '14.— New York, NY, USA : ACM, 2014.— P. 1103-1114.

39. Albahli S., Melton A. RDF Data Management: A Survey of RDBMS-Based Approaches // Proceedings of the 6th International Conference on Web Intelligence, Mining and Semantics.— WIMS '16.— New York, NY, USA : Association for Computing Machinery, 2016. — 4 p.

40. Alvarez V., Schuhknecht F., et al. Main Memory Adaptive Indexing for Multi-Core Systems // Proceedings of the Tenth International Workshop on Data Management on New Hardware.— DaMoN '14.— New York, NY, USA : ACM, 2014. — 10 p.

41. ANSI/ISO/IEC International Standard (IS) Database Language SQL — Part 2: Foundation (SQL/Foundation). ISO/IEC 9075-2:1999 (E).— https://courses.cms.caltech.edu/cs123/sql99std/ansi-iso-9075-2-1999.pdf. — 1999. — Acessed: 05/06/2025.

42. Arulraj J., Pavlo A., Menon P. Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads // Proceedings of the 2016 International Conference on Management of Data. — SIGMOD '16. — New York, NY, USA : ACM, 2016. — P. 583-598.

43. Athanassoulis M., B0gh K., Idreos S. Optimal Column Layout for Hybrid Workloads // Proc. VLDB Endow.— 2019. —Sep.— Vol. 12, no. 13.— P. 2393-2407.

44. Batory D. On Searching Transposed Files // ACM Trans. Database Syst.— 1979. — Dec. — Vol. 4, no. 4. — P. 531-544.

45. Bellatreche L., Benkrid S. A Joint Design Approach of Partitioning and Allocation in Parallel Data Warehouses // Data Warehousing and Knowledge Discovery. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2009. — P. 99-110.

46. Bobrov N., Chernishev G., Novikov B. Workload-Independent Data-Driven Vertical Partitioning // New Trends in Databases and Information Systems. — Cham : Springer International Publishing, 2017.— P. 275-284.

47. Boncz P. Main Memory DBMS // Encyclopedia of Database Systems. — New York, NY : Springer New York, 2016. — P. 1-2.

48. Boncz P., Kersten M. MIL Primitives for Querying a Fragmented World // The VLDB Journal. — 1999.— Oct. — Vol. 8, no. 2. —P. 101-119.

49. Boncz P., Kersten M., Manegold S. Breaking the memory wall in MonetDB // Commun. ACM. — 2008. — December. — Vol. 51. —P. 77-85.

50. Boncz P., Manegold S., Kersten M. Database Architecture Optimized for the New Bottleneck: Memory Access // Proceedings of the 25th International Conference on Very Large Data Bases. — VLDB '99. — San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 1999. — P. 54-65.

51. Boncz P., Zukowski M., Nes N. MonetDB/X100: Hyper-Pipelining Query Execution // CIDR 2005, Second Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2005, Online Proceedings. — 2005. — P. 225-237.

52. Böttcher S., Link S., Zhang L. Pulling Conjunctive Query Equivalence out of the Bag // Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. — CIKM '14. — New York, NY, USA : ACM, 2014. — P. 41-50.

53. Braun L., Etter T., et al. Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database // Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. — SIGMOD '15. — New York, NY, USA : ACM, 2015. — P. 251-264.

54. Campero Durand G., Piriyev R., et al. Automated Vertical Partitioning with Deep Reinforcement Learning // New Trends in Databases and Information Systems.— Cham : Springer International Publishing, 2019.— P. 126-134.

55. Ceri S., Kalinichenko L., et al. SIGMOD Sister Societies // SIGMOD Rec.— 2000. — Vol. 29, no. 1. — P. 4-15.

56. Chandramouli B., Goldstein J., et al. Trill: A High-Performance Incremental Query Processor for Diverse Analytics // Proc. VLDB Endow. — 2014. — Dec. — Vol. 8, no. 4. — P. 401-412.

57. Chernishev G. Towards Self-management in a Distributed Column-Store System // New Trends in Databases and Information Systems: ADBIS 2015 Short Papers and Workshops, BigDap, DCSA, GID, MEBIS, OAIS, SW4CH, WISARD, Poitiers, France, September 8-11, 2015. Proceedings.— 2015.— P. 97-107.

58. Chernishev G., Galaktionov V., et al. A study of PosDB Performance in a Distributed Environment // Proceedings of the 2017 Software Engineering and Information Management. — SEIM '17. — 2017.

59. Chernishev G., Galaktionov V., et al. PosDB: A Distributed Column-Store Engine // Perspectives of System Informatics. — Cham : Springer International Publishing, 2018. —P. 88-94.

60. Chernishev G., Galaktionov V., et al. A Comprehensive Study of Late Materialization Strategies for a Disk-Based Column-Store // DOLAP@EDBT'22. — 2022. — P. 21-30.

61. Claussen J., Kemper A., et al. Optimization and evaluation of disjunctive queries // IEEE Transactions on Knowledge and Data Engineering. — 2000. — Vol. 12, no. 2. —P. 238-260.

62. ClickHouse — open source distributed column-oriented DBMS // https://clickhouse.yandex/.— [Online; accessed 20/01/2018].

63. ClickHouse and ColumnStore in the Star Schema Benchmark // https://www.percona.com/blog/clickhouse-and-columnstore-in-the-star-sche ma-benchmark/.— [Online; accessed 29/10/2023].

64. Codd E. F. A relational model of data for large shared data banks // Commun. ACM. — 1970. —Jun. —Vol. 13, no. 6.—P. 377-387.

65. Codd E. F. Relational Completeness of Data Base Sublanguages // Research Report / RJ / IBM / San Jose, California. — 1972. — Vol. RJ987.

66. Copeland G., Khoshafian S. A decomposition storage model // SIGMOD Rec. — 1985. —Vol. 14, no. 4.—P. 268-279.

67. Damme P., Habich D., et al. Lightweight Data Compression Algorithms: An Experimental Survey (Experiments and Analyses) // Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017. — OpenProceedings.org, 2017. — P. 72-83.

68. Damme P., Ungethüm A., et al. MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model // Proc. VLDB Endow. — 2020. —Jul. —Vol. 13, no. 12. —P. 2396-2410.

69. Das S., Agrawal D., El Abbadi A. G-Store: a scalable data store for transactional multi key access in the cloud // Proceedings of the 1st ACM symposium on Cloud computing. — SoCC '10.— New York, NY, USA : ACM, 2010.— P. 163-174.

70. Durand G., Pinnecke M., et al. GridFormation: Towards Self-Driven Online Data Partitioning Using Reinforcement Learning // Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management. — aiDM'18. — New York, NY, USA : ACM, 2018. — 7 p.

71. Dziedzic A., Wang J., et al. Columnstore and B+ Tree — Are Hybrid Physical Designs Important? // Proceedings of the 2018 International Conference on Management of Data. — SIGMOD '18. — New York, NY, USA : ACM, 2018. — P. 177-190.

72. Eisner M., Severance D. Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases //J. ACM.— 1976. — Oct.— Vol. 23, no. 4. — P. 619-635.

73. Faerber F., Kemper A., et al. Main Memory Database Systems // Foundations and Trends® in Databases. — 2017. — Vol. 8, no. 1-2. — P. 1-130.

74. Fang Y., Zou C., Chien A. Accelerating Raw Data Analysis with the ACCORDA Software and Hardware Architecture // Proc. VLDB Endow. — 2019. —Jul. —Vol. 12, no. 11. —P. 1568-1582.

75. Farber F., May N., et al. The SAP HANA Database — An Architecture Overview // IEEE DEBull. — 2012. — Vol. 35, no. 1. — P. 28-33.

76. Freedman C., Ismert E., Larson P. Compilation in the Microsoft SQL Server Hekaton Engine // IEEE Data Eng. Bull.— 2014.— Vol. 37, no. 1.— P. 22-30.

77. French C. "One size fits all" database architectures do not work for DSS // SIGMOD Rec. — 1995. — Vol. 24. — P. 449-450.

78. Galaktionov V., Klyuchikov E., Chernishev G. Position Caching in a Column-Store with Late Materialization: An Initial Study // Proceedings of the 22nd International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data co-located with EDBT/ICDT 2020 Joint Conference, Copenhagen, Denmark, March 30, 2020. — 2020. — P. 89-93.

79. Garcia-Molina H., Ullman J., Widom J. Database systems - the complete book (2nd ed.).— Pearson Education, 2009.

80. Ghita B., Tomé D., Boncz P. White-box Compression: Learning and Exploiting Compact Table Representations // 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings. — 2020.

81. Graefe G. Query Evaluation Techniques for Large Databases // ACM Comput. Surv. — 1993. — Jun. — Vol. 25, no. 2. — P. 73-169.

82. Graefe G. Volcano — An Extensible and Parallel Query Evaluation System // IEEE Trans. on Knowl. and Data Eng.— 1994. — Feb.— Vol. 6, no. 1.— P. 120-135.

83. Graefe G., Kuno H. Self-selecting, self-tuning, incrementally optimized indexes // Proceedings of the 13th International Conference on Extending Database Technology. — EDBT '10. — New York, NY, USA : ACM, 2010.— P. 371-381.

84. Grund M., Krueger J., et al. Optimal query operator materialization strategy for hybrid databases // Proceedings of the 2011 Third International Conference on Advances in Databases, Knowledge, and Data Applications. — DBKDA '11. —IARIA, 2011.—P. 169-174.

85. Halim F., Idreos S., et al. Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores // Proc. VLDB Endow. — 2012. —Feb. —Vol. 5, no. 6.—P. 502-513.

86. Hamirwasia V., Karlapalem K., Valluri S. FAST: Fragment Assisted Storage for Efficient Query Execution in Read-Only Databases // Proceedings of RealTime Business Intelligence and Analytics.— BIRTE 2019.— New York, NY, USA : ACM, 2019. — 10 p.

87. Hammer M., Niamir B. A heuristic approach to attribute partitioning // Proceedings of the 1979 ACM SIGMOD international conference on Management of data. — SIGMOD '79. — New York, NY, USA : ACM, 1979. — P. 93-101.

88. Hankins R., Patel J. Data morphing: an adaptive, cache-conscious storage technique // Proceedings of the 29th international conference on Very large data bases. — VLDB '2003. — VLDB Endowment, 2003. — P. 417-428.

89. Harizopoulos S., Abadi D., Boncz P. Column-Oriented Database Systems, VLDB 2009 Tutorial.— 2009.— URL: nms.csail.mit.edu/~stavros/pubs/tutorial2009-column_stores.pdf.

90. Hellerstein J., Stonebraker M. Readings in Database Systems: Fourth Edition.— The MIT Press, 2005.

91. Hellerstein J., Stonebraker M., Hamilton J. Architecture of a Database System // Found. Trends Databases.— 2007. — Feb.— Vol. 1, no. 2.— P. 141-259.

92. Hoffer J., Severance D. The use of cluster analysis in physical data base design // Proceedings of the 1st International Conference on Very Large Data Bases. —VLDB '75. — New York, NY, USA : ACM, 1975. — P. 69-86.

93. Holloway A., Raman V., et al. How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans // Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. — SIGMOD '07. — New York, NY, USA : ACM, 2007. — P. 389-400.

94. Idreos S., Groffen F., et al. MonetDB: Two Decades of Research in Column-oriented Database Architectures // IEEE Data Eng. Bull. — 2012.— Vol. 35, no. 1. — P. 40-45.

95. Idreos S., Kersten M., Manegold S. Database Cracking // CIDR.— 2007.— P. 68-78.

96. Idreos S., Kersten M., Manegold S. Updating a Cracked Database // Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. — SIGMOD '07. — New York, NY, USA : ACM, 2007. — P. 413-424.

97. Idreos S., Kersten M., Manegold S. Self-organizing tuple reconstruction in column-stores // Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. — SIGMOD '09. — New York, NY, USA : ACM, 2009. — P. 297-308.

98. Idreos S., Manegold S., Graefe G. Adaptive Indexing in Modern Database Kernels // Proceedings of the 15th International Conference on Extending Database Technology. — EDBT '12. — New York, NY, USA : ACM, 2012.— P. 566-569.

99. Ivanova M., Kersten M., et al. An architecture for recycling intermediates in a column-store // Proceedings of the 35th SIGMOD international conference on Management of data. — SIGMOD '09. — New York, NY, USA : ACM, 2009. — P. 309-320.

100. Ivanova M., Kersten M., et al. An Architecture for Recycling Intermediates in a Column-store // ACM Trans. Database Syst. — 2010. — Oct. — Vol. 35, no. 4. — P. 24:1-24:43.

101. Ivanova M., Kersten M., Nes N. Self-organizing strategies for a column-store database // Proceedings of the 11th international conference on Extending database technology: Advances in database technology. — EDBT '08. — New York, NY, USA : ACM, 2008. — P. 157-168.

102. Jiang H., Elmore A. Boosting Data Filtering on Columnar Encoding with SIMD // Proceedings of the 14th International Workshop on Data Management on New Hardware. — DAMON '18.— New York, NY, USA : ACM, 2018.— 10 p.

103. Jiang H., Liu C., et al. PIDS: Attribute Decomposition for Improved Compression and Query Performance in Columnar Storage // Proc. VLDB Endow. — 2020. —Feb. —Vol. 13, no. 6. —P. 925-938.

104. Jindal A., Palatinus E., et al. A Comparison of Knives for Bread Slicing // Proc. VLDB Endow.—2013. —Apr. —Vol. 6, no. 6.—P. 361-372.

105. Kalinichenko L., Fazliev A., et al. New Data Access Challenges for Data Intensive Research in Russia // Selected Papers of the XVII International Conference on Data Analytics and Management in Data Intensive Domains (DAMDID/RCDL 2015), Obninsk, Russia, October 13-16, 2015.— 2015.— P. 215-237.

106. Kalinichenko L., Kogalovsky M., et al. Database Research Activities in Russia. a Brief Overview // Proceedings of Chalenges, 2000 ADBIS-DASFAA Symposium on Advances in Databases and Information Systems, Enlarged Fourth East-European Conference on Advances in Databases and Information Systems, Prague, Czech Republic, September 5-8, 2000. — Matfyz Press, Vydavatelstvi, Matematicko-Fyzikalni Fakulty, Unverzity Karlovy, 2000. — P. 234-245.

107. Kalinichenko L. A., Stupnikov S. A., Martynov D. O. SYNTHESIS. a Language for Canonical Information Modeling and Mediator Definition for Problem Solving in Heterogeneous Information Resource Environments. — IPI RAN, 2007. —P. 171.

108. Karasalo I.a, Svensson P. An Overview of Cantor. A New System for Data Analysis // Proceedings of the 2nd International Workshop on Proceedings of the Second International Workshop on Statistical Database Management.— SSDBM'83. — Berkeley, CA, US . Lawrence Berkeley Laboratory, 1983.— P. 315-324.

109. Karasalo I., Svensson P. The design of cantor. a new system for data analysis // Proceedings of the 3rd international workshop on Statistical and scientific database management.— Berkeley, CA, US . Lawrence Berkeley Laboratory, 1986. — P. 224-244.

110. Kastrati F., Moerkotte G. Optimization of Disjunctive Predicates for Main Memory Column Stores // Proceedings of the 2017 ACM International Conference on Management of Data. — SIGMOD '17.— New York, NY, USA . ACM, 2017. —P. 731-744.

111. Kemper A., Neumann T. HyPer: A Hybrid OLTP&OLAP Main Memory Database System Based on Virtual Memory Snapshots // Proceedings of the 2011 IEEE 27th International Conference on Data Engineering. — ICDE '11. — Washington, DC, USA : IEEE Computer Society, 2011. — P. 195-206.

112. Kernert D., Köhler F., Lehner W. SLACID — Sparse Linear Algebra in a Column-Oriented in-Memory Database System // Proceedings of the 26th International Conference on Scientific and Statistical Database Management.— SSDBM '14. — New York, NY, USA : ACM, 2014. — 12 p.

113. Khoshafian S., Copeland G., et al. A Query Processing Strategy for the Decomposed Storage Model // Proceedings of the Third International Conference on Data Engineering. — Washington, DC, USA : IEEE Computer Society, 1987. — P. 636-643.

114. Kim A., Madden S. Optimizing Disjunctive Queries with Tagged Execution // Proc. ACM Manag. Data. — 2024.— May. — Vol. 2, no. 3. — 25 p.

115. Klug A. On conjunctive queries containing inequalities //J. ACM.— 1988.— Jan. —Vol. 35, no. 1. —P. 146-160.

116. Kuralenok I., Trofimov A., et al. FlameStream: Model and Runtime for Distributed Stream Processing. — BeyondMR'18. — New York, NY, USA : ACM, 2018. —2 p.

117. Lahiri T., Neimat M., Folkman S. TimesTen: An In-Memory Database for Enterprise Applications // IEEE DEBull. — 2013. — Vol. 36, no. 3. — P. 6-13.

118. Lamb A., Fuller M., et al. The Vertica Analytic Database: C-store 7 Years Later // Proc. VLDB Endow.— 2012. —Aug.— Vol. 5, no. 12.— P. 1790-1801.

119. Larson P. Data reduction by partial preaggregation // Proceedings 18th International Conference on Data Engineering. — 2002.— P. 706-715.

120. Larson P., Clinciu C., et al. Enhancements to SQL Server Column Stores.— SIGMOD '13.—New York, NY, USA : ACM, 2013.—P. 1159-1168.

121. Leis V., Radke B., et al. Query optimization through the looking glass, and what we found running the Join Order Benchmark // The VLDB Journal. — 2018. —Oct. —Vol. 27, no. 5.—P. 643-668.

122. Lemke C., Sattler K., et al. Speeding Up Queries in Column Stores // Data Warehousing and Knowledge Discovery. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2010. —P. 117-129.

123. Liu H., Ji Y., et al. TICC: Transparent Inter-Column Compression for Column-Oriented Database Systems // Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. — CIKM '17. — New York, NY, USA : ACM, 2017. — P. 2171-2174.

124. Lorie R., Symonds A. A relational access method for interactive applications. — Prentice Hall, 1971.

125. Manegold S., Boncz P., et al. Cache-conscious Radix-decluster Projections // Proceedings of the Thirtieth International Conference on Very Large Data Bases. — VLDB '04. — VLDB Endowment, 2004. — P. 684-695.

126. Manegold S., Boncz P., Kersten M. Generic Database Cost Models for Hierarchical Memory Systems // Proceedings of the 28th International Conference on Very Large Data Bases. — VLDB '02. — VLDB Endowment, 2002. — P. 191-202.

127. Many-Sorted Language // https://planetmath.org/manysortedlanguage.— [Online; accessed 03/10/2024].

128. MariaDB ColumnStore.— https://mariadb.com/kb/en/mariadb-column store/. —Accessed: 28/02/2021.

129. McShane D., Kraines R., et al. TOD: A Software System for the Aramis Data Bank // Computer. — 1979. —nov. —Vol. 12, no. 11.—P. 34-40.

130. Menon P., Ngom A., et al. Permutable compiled queries: dynamically adapting compiled queries without recompiling // Proc. VLDB Endow. — 2020. — Oct. —Vol. 14, no. 2.—P. 101-113.

131. MonetDB - anyone uses it in production? — https://stackoverflow.com/questions/10087647/monetdb-anyone-uses-it-in-production. — Accessed: 09/03/2018.

132. Moran B. "The Devil's in the DeWitt Clause" (published 2003-04-03).— https://web.archive.org/web/20160719145221/http://sqlmag.com/sql-server/ devils-dewitt-clause. — 2003. — Retrieved 2018-01-11.

133. Mukhaleva N., Grigorev V., Chernishev G. Implementing Window Functions in a Column-Store with Late Materialization // MEDI'19. — Vol. 11815 of LNCS. — Springer, 2019. — P. 303-313.

134. Mullins C., Lim L., Lang Ch. Query-Aware Compression of Join Results // Proceedings of the 16th International Conference on Extending Database Technology. — EDBT '13. — New York, NY, USA : ACM, 2013. — P. 29-40.

135. Nagel F., Boncz P., Viglas S. Recycling in Pipelined Query Evaluation // Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013).— ICDE '13.— USA : IEEE Computer Society, 2013.— P. 338-349.

136. Neumann T. Efficiently Compiling Efficient Query Plans for Modern Hardware // Proc. VLDB Endow.— 2011. — Jun. — Vol. 4, no. 9. —P. 539-550.

137. Neumann Thomas. Query Optimization (in Relational Databases) // Encyclopedia of Database Systems. — New York, NY : Springer New York, 2016. — P. 1-7.

138. O'Neil P., O'Neil E., Chen X. The Star Schema Benchmark (SSB). — http://www.cs.umb.edu/~poneil/StarSchemaB.PDF. — 2009. — Accessed: 10/09/2017.

139. Özcan F., Tian Y., Tözün P. Hybrid Transactional/Analytical Processing: A Survey // Proceedings of the 2017 ACM International Conference on Management of Data. — SIGMOD '17.— New York, NY, USA : ACM, 2017.— P. 1771-1775.

140. Ozsu T., Valduriez P. Principles of Distributed Database Systems. — Springer Publishing Company, Incorporated, 2016.

141. Padmanabhan S., Malkemus T., et al. Block Oriented Processing of Relational Database Operations in Modern Computer Architectures // Proceedings of the 17th International Conference on Data Engineering. — Washington, DC, USA : IEEE Computer Society, 2001. — P. 567-574.

142. Palpanas T. Data Series Management: The Road to Big Sequence Analytics // SIGMOD Rec. — 2015. — Aug. — Vol. 44, no. 2. — P. 47-52.

143. Park H., Zhai S., et al. StreamBox-TZ: Secure Stream Analytics at the Edge with TrustZone // 2019 USENIX Annual Technical Conference (USENIX ATC 19). — Renton, WA : USENIX Association, 2019.— Jul. — P. 537-554.

144. Patel J., Deshmukh H., et al. Quickstep: A Data Platform Based on the Scal-ing-up Approach // Proc. VLDB Endow.— 2018. — Feb. — Vol. 11, no. 6.— P. 663-676.

145. Petraki E., Idreos S., Manegold S. Holistic Indexing in Main-Memory Column-Stores // Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. — SIGMOD '15.— New York, NY, USA : ACM, 2015. —P. 1153-1166.

146. Pham M., Passing L., et al. Deriving an Emergent Relational Schema from RDF Data // Proceedings of the 24th International Conference on World Wide Web.— WWW '15.— International World Wide Web Conferences Steering Committee, 2015. — P. 864-874.

147. Pham M. D. Self-organizing structured RDF in MonetDB // 2013 IEEE 29th International Conference on Data Engineering Workshops (ICDEW).— 2013. — April. — P. 310-313.

148. Plattner H. The Impact of Columnar In-Memory Databases on Enterprise Systems: Implications of Eliminating Transaction-Maintained Aggregates // Proc. VLDB Endow. —2014. —Aug. —Vol. 7, no. 13.—P. 1722-1729.

149. Polychroniou O., Ross K. Towards Practical Vectorized Analytical Query Engines // Proceedings of the 15th International Workshop on Data Management on New Hardware. — DaMoN'19. — New York, NY, USA : ACM, 2019. — 7 p.

150. Polyntsov M., Grigorev V., et al. Implementing the Comparison-Based External Sort // ADBIS'22. — Springer, 2022. — P. 500-511.

151. PostgreSQL.— https://www.postgresql.org/.— 2020.— Retrieved 2020-14-12.

152. Psallidas F., Wu E. Demonstration of Smoke: A Deep Breath of Data-Intensive Lineage Applications // Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018. —ACM, 2018. —P. 1781-1784.

153. Psallidas F., Wu E. Smoke: Fine-grained Lineage at Interactive Speed // Proc. VLDB Endow. —2018. —Vol. 11, no. 6. —P. 719-732.

154. Raasveldt M., Mühleisen H. DuckDB: An Embeddable Analytical Database // Proceedings of the 2019 International Conference on Management of Data. — SIGMOD '19. — New York, NY, USA : ACM, 2019. — P. 1981-1984.

155. Raasveldt M, Mühleisen H. Data Management for Data Science — Towards Embedded Analytics // 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings. — 2020.

156. Ramakrishnan R, Gehrke J. Database Management Systems. — 2nd edition. — USA : McGraw-Hill, Inc., 2000.

157. Ramamurthy R., DeWitt D., Su Q. A case for fractured mirrors // Proceedings of the 28th international conference on Very Large Data Bases. — VLDB '02. — VLDB Endowment, 2002. — P. 430-441.

158. Raman V., Attaluri G., et al. DB2 with BLU Acceleration: So Much More than Just a Column Store // Proc. VLDB Endow. — 2013.— Aug. — Vol. 6, no. 11. —P. 1080-1091.

159. Rockset Beats ClickHouse and Druid on the Star Schema Benchmark (SSB) // https://rockset.com/blog/rockset-beats-clickhouse-druid-star-schema-bench mark/. — [Online; accessed 29/10/2023].

160. Rödiger W., Mühlbauer T., et al. High-Speed Query Processing over Highspeed Networks // Proc. VLDB Endow. — 2015.— Dec. — Vol. 9, no. 4.— P. 228-239.

161. Sagiv Y., Yannakakis M. Equivalences Among Relational Expressions with the Union and Difference Operators //J. ACM.— 1980. —Oct. — Vol. 27, no. 4. — P. 633-655.

162. Schwalb D., Girish Kumar B.K., et al. Hyrise-NV: Instant Recovery for In--Memory Databases Using Non-Volatile Memory // Database Systems for Advanced Applications. — Cham : Springer International Publishing, 2016.— P. 267-282.

163. Shanbhag A., Madden S., Yu X. A Study of the Fundamental Performance Characteristics of GPUs and CPUs for Database Analytics // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. — SIGMOD '20. — New York, NY, USA : ACM, 2020. — P. 1617-1632.

164. Shang Z., Zgraggen E., et al. Davos: A System for Interactive Data-Driven Decision Making // Proc. VLDB Endow.— 2021.— Vol. 14, no. 12.— P. 2893-2905.

165. Shao M., Schindler J., et al. Clotho: decoupling memory page layout from storage organization // Proceedings of the Thirtieth international conference on Very large data bases. — VLDB '04. — VLDB Endowment, 2004. — P. 696-707.

166. Sherkat R., Florendo C., et al. Page As You Go: Piecewise Columnar Access In SAP HANA // Proceedings of the 2016 International Conference on Management of Data. — SIGMOD '16.— New York, NY, USA : ACM, 2016.— P. 1295-1306.

167. Shrinivas L., Bodagala S., et al. Materialization strategies in the Vertica analytic database: Lessons learned // 2013 IEEE 29th International Conference on Data Engineering (ICDE). — 2013.— April. — P. 1196-1207.

168. Silberschatz A., Korth H., Sudarshan S. Database System Concepts, Seventh Edition. — McGraw-Hill Book Company, 2020.

169. Skvortsov Nikolay A., Stupnikov Sergey A. A Semantic Approach to Workflow Management and Reuse for Research Problem Solving // Data Intelligence. — 2022. — 04. — Vol. 4, no. 2. — P. 439-454.

170. Slesarev A., Klyuchikov E., et al. Revisiting Data Compression in Column-Stores // LNCS. —Vol. 12732. —Springer, 2021. —P. 279-292.

171. Snowflake. Database of databases entry.— https://dbdb.io/db/snowflake.— 2021. —Accessed: 20/09/2021.

172. Sprenger S., Schäfer P., Leser U. Multidimensional Range Queries on Modern Hardware // Proceedings of the 30th International Conference on Scientific and Statistical Database Management. — SSDBM '18.— New York, NY, USA : ACM, 2018. — 12 p.

173. Stonebraker M. Technical Perspective: One Size Fits All: An Idea Whose Time Has Come and Gone // Commun. ACM. — 2008.— Dec. — Vol. 51, no. 12.— P. 76-76.

174. Stonebraker M., Abadi D., et al. C-Store: A Column-oriented DBMS // Proceedings of the 31st International Conference on Very Large Data Bases. — VLDB '05. —VLDB Endowment, 2005. —P. 553-564.

175. Svensson P. The Evolution of Vertical Database Architectures — A Historical Review (Keynote Talk) // Proceedings of the 20th international conference on Scientific and Statistical Database Management.— SSDBM '08.— Berlin, Heidelberg : Springer-Verlag, 2008. — P. 3-5.

176. Taniar D., Leung C., et al. High-Performance Parallel Database Processing and Grid Databases. — Wiley Series on Parallel and Distributed Computing, 2008.

177. Taranov I., Shcheklein I., et al. Sedna: native XML database management system (internals overview) // Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data.— SIGMOD '10.— New York, NY, USA : ACM, 2010. — P. 1037-1046.

178. TPC Benchmark DS. Decision Support. Version 3.2.0.— http://www.tpc.org/tpcds. — Accessed: 29/10/2023.

179. TPC Benchmark H. Decision Support. Version 2.17.3.— http://www.tpc.org/tpch. — Accessed: 29/10/2017.

180. Transactions | MonetDB.— https://www.monetdb.org/Documentation/Man uals/SQLreference/Transactions. — Accessed: 09/03/2018.

181. Tsirogiannis D., Harizopoulos S., et al. Query Processing Techniques for Solid State Drives // Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. — SIGMOD '09. — New York, NY, USA : ACM, 2009. — P. 59-72.

182. Tuchina A., Grigorev V., Chernishev G. On-the-Fly Filtering of Aggregation Results in Column-Stores // SEIM-2018. — 2018. — P. 53-60.

183. Turner M., Hammond R., Cotton P. A DBMS For Large Statistical Databases // Fifth International Conference on Very Large Data Bases, 1979. — 1979. — Oct. — P. 319-327.

184. Vaisman A., Zimanyi E. Data Warehouse Systems — Design and Implementation. Data-Centric Systems and Applications. — Springer, 2014.

185. Valduriez P. Join Indices // ACM Trans. Database Syst.— 1987. — Jun.— Vol. 12, no. 2. —P. 218-246.

186. Wang H., Zheng K., et al. SharkDB: An In-Memory Storage System for Massive Trajectory Data // Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. — SIGMOD '15. — New York, NY, USA : ACM, 2015. —P. 1099-1104.

187. Wang Z., Xue J., Shao Z. Heracles: An Efficient Storage Model and Data Flushing for Performance Monitoring Timeseries // Proc. VLDB Endow. — 2021. —Feb. —Vol. 14, no. 6. —P. 1080-1092.

188. Weiss Y., Cohen S. Reverse Engineering SPJ-Queries from Examples // Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. — PODS '17. — New York, NY, USA : ACM, 2017.— P. 151-166.

189. Wesley R., Terlecki P. Leveraging Compression in the Tableau Data Engine // Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. — SIGMOD '14.— New York, NY, USA : ACM, 2014.— P. 563-573.

190. Weyl S., Fries J., et al. A modular self-describing clinical databank system // Computers and Biomedical Research.— 1975. — Vol. 8, no. 3.— P. 279-293.

191. Wu E. Systems for Human Data Interaction (keynote) // Proceedings of the 2nd Workshop on Search, Exploration, and Analysis in Heterogeneous Datastores (SEA-Data 2021) co-located with 47th International Conference on Very Large Data Bases (VLDB 2021), Copenhagen, Denmark, August 20, 2021.— 2021.

192. Wu L., Lottarini A., et al. Q100: The Architecture and Design of a Database Processing Unit // Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems. — ASPLOS '14. — New York, NY, USA : ACM, 2014. — P. 255-268.

193. Xin R., Rosen J., et al. Shark: SQL and Rich Analytics at Scale // Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. — SIGMOD '13. — New York, NY, USA : ACM, 2013. — P. 13-24.

194. Yan W., Larson P. Eager Aggregation and Lazy Aggregation // Proceedings of the 21th International Conference on Very Large Data Bases. — VLDB '95. — San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 1995.— P. 345-357.

195. Yang J., Rae I., et al. F1 Lightning: HTAP as a Service // Proc. VLDB Endow. — 2020. —Aug. —Vol. 13, no. 12. —P. 3313-3325.

196. YDB — an open source Distributed SQL Database // https://ydb.tech/.— [Online; accessed 12/06/2025].

197. Zarubin M., Damme P., et al. SIMD-MIMD Cocktail in a Hybrid Memory Glass: Shaken, Not Stirred // Proceedings of the 14th ACM International Conference on Systems and Storage. — SYSTOR '21. — New York, NY, USA : ACM, 2021. — 12 p.

198. Zhan C., Su M., et al. AnalyticDB: Real-Time OLAP Database System at Alibaba Cloud // Proc. VLDB Endow. — 2019.— Aug. — Vol. 12, no. 12.— P. 2059-2070.

199. Zheng B., Wang H., et al. SharkDB: An in-Memory Column-Oriented Storage for Trajectory Analysis // World Wide Web.— 2018. — Mar.— Vol. 21, no. 2. — P. 455-485.

200. Zukowski M., Nes N., Boncz P. DSM vs. NSM: CPU Performance Tradeoffs in Block-oriented Query Processing // Proceedings of the 4th International Workshop on Data Management on New Hardware. — DaMoN '08. — New York, NY, USA : ACM, 2008. — P. 47-54.

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

1.1 Планы запроса SELECT * FROM T1, T2 WHERE T1.a > 10 AND T2.a

= 100 AND T1.id = T2.id................................................16

1.2 Интерфейс итератора......................................................17

1.3 Исполняемый план запроса................................................18

1.4 Запрос Q1* в системе Fractured Mirrors: два подхода к выполнению . 27

1.5 Запрос Q19 в системе Fractured Mirrors: два подхода к выполнению . 27

1.6 Пример работы оператора FlashJoin....................................29

1.7 Блок мультиколонки (изображение взято из работы [30]) ............30

1.8 Варианты выполнения запроса: ранняя материализация, поздняя материализация (рисунок взят из статьи [33]) ..........................30

2.1 Кортежное и позиционное представление................................49

2.2 Возможные классы операторов в предлагаемом подходе ..............50

2.3 Использование оператора явной материализации ......................53

2.4 Схема работы генерирующего оператора................................53

2.5 Вычисление предиката для запроса SELECT * FROM T WHERE X >

100 AND Y > 50............................................................56

2.6 Фильтрация на кортежах значений ......................................57

2.7 Вариант гибридной материализации, называемый в [33] ранней материализацией (изображение взято из оригинальной статьи) ... 58

2.8 Пример расположения материализующих операторов в плане запроса 62

2.9 Пример разбиения плана запроса на уровни............................65

2.10 Методы материализации ..................................................66

2.11 Пример запроса............................................................67

2.12 План запроса, построенный с помощью метода ультра-поздней материализации ............................................................68

2.13 Пример ромбовидного шаблона в потоке данных........................71

3.1 Выражения 6 (слева) и 6 (справа)........................................94

3.2 Выражения 6 (слева) и 6 (справа)........................................96

3.3 Выражения 6 (слева) и 6 (справа)........................................97

3.4 Запрос ф' е PT-QLlm......................................................99

3.5 Запрос ф е PT-QL™ ..........................100

4.1 Архитектура PosDB............................103

4.2 Компоненты подсистемы Исполнитель запросов............104

4.3 Схема хранения данных..........................105

4.4 Иерархия типов данных..........................108

4.5 Представление колонки на диске.....................110

4.6 Иерархия блоков данных.........................112

4.7 Иерархия заголовков ...........................114

4.8 Иерархия итераторов по блокам данных ................116

4.9 Интерфейс итератора по блокам данных................117

4.10 Иерархия билдеров для блоков данных.................119

4.11 Вариант плана запроса без считывателей................123

4.12 Вариант плана запроса со считывателями ...............123

4.13 Планы в PosDB ..............................124

4.14 Пример задания запроса в коде .....................127

5.1 Схема данных Star Schema Benchmark (рисунок взят из работы [138]) 135

5.2 Запрос Q1.1 из Star Schema Benchmark.................138

5.3 План запроса SSB Q1.1 построенный методом ультра-поздней материализации..............................139

5.4 План запроса SSB Q1.1 построенный методом ранней материализации 141

5.5 План запроса SSB Q1.1 построенный методом поздней материализации..............................142

5.6 Сравнение ультра-поздней материализации и PostgreSQL.......143

5.7 Сравнение ультра-поздней материализации и ранней материализации 144

5.8 Сравнение ультра-поздней материализации и поздней материализации 146

5.9 Сравнение различных методов материализации с MariaDB ColumnStore ................................147

5.10 Все методы против MariaDB ColumnStore и PostgreSQL........148

5.11 Фактор масштабирования 40.......................150

5.12 Фактор масштабирования 80.......................151

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

1 Классификация подходов к поздней материализации (ПМ)...... 33

2 Время выполнения всех рассмотренных методов и систем (сек.) . . . 149