Содержание к диссертации
Введение
Глава 1. Анализ существующих методов оценки времени выполнения запросов вПКСБД 13
1.1. Обзор ПКСБД как современного направления исследований и анализ истоков его появления 14
1.1.1. Традиционные СУБД и их ограничения 14
1.1.2. Колоночное хранение информации 17
1.1.3. Направления исследований в области ПКСБД 20
1.1.4. Преимущество ПКСБД при обработке аналитических запросов 24
1.1.5. Краткий обзор существующих коммерческих ПКСБД 26
1.1.6. Выводы по части 28
1.2. Анализ информационных процессов обработки запросов в ПКСБД 29
1.2.1. Хранение информации на физическом (дисковом) уровне 29
1.2.2. Обработка информации на логическом уровне 31
1.2.3. Синхронный конвейер 32
1.2.4. Итераторная модель 34
1.2.5. Скобочный шаблон 36
1.2.6. Операция материализации 38
1.2.7. Сжатие данных 39
1.2.8. Скрытое соединение 40
1.2.9. Параллельная обработка запросов 43
1.2.10. Выводы по части 45
1.3. Критический анализ существующих методов оценки быстродействия ПКСБД 46
1.3.1. Системный подход к оценке быстродействия ПКСБД на этапе проектирования 46
1.3.2. Экспертная оценка архитектур хранилищ данных з
1.3.3. Опытное сравнение производительности систем баз данных на основании тестирования 50
1.3.4. Существующие математические модели оценки времени выполнения запроса 55
1.3.5. Выводы по части 1.4. Постановка цели, предмета и объекта исследования 58
1.5. Выводы по главе 60
Глава 2. Аналитическая модель оценки времени выполнения запросов в ПКСБД 61
2.1. Общий подход к оценке времени выполнения запросов на базе операционного исчисления 62
2.1.1. Свойства ПЛС и ПФ 62
2.1.2. Пример использования ПЛС иПФ 64
2.2. Анализ выполнения запроса к одной таблице в ПКСБД 66
2.2.1. Формализация процесса выполнения запроса к одной таблице в ПКСБД 67
2.2.2. Вывод ПЛС времени выполнения запроса для последовательного плана с ранней материализацией 68
2.2.3. Вывод ПЛС времени выполнения запроса для последовательного плана с поздней материализацией 70
2.3. Анализ процесса соединения отношений в ПКСБД 72
2.3.1. Формализация процесса соединения отношений в ПКСБД 73
2.3.2. Вывод ПЛС времени соединения отношений в ПКСБД 74
2.4. Анализ процесса обработки запроса к параллельному колоночному хранилищу данных 78
2.4.1. Формализация процесса «скрытого соединения» в ПКСБД 79
2.4.2. Вывод ПЛС времени чтения ключевых атрибутов измерений (этап 1) 80
2.4.3. Вывод ПЛС времени извлечения битовой маски таблицы фактов и передачи значений внешних ключей (этап 2) 81
2.4.4. Вывод ПЛС времени чтения значений атрибутов измерений (этап 3) 83
2.4.5. Итоговое ПЛС времени обработки запроса к ПКХД 84
2.5. Аналитическая модель режимов работы системы 85
2.5.1. Пакетный режим 85
2.5.2. Режим «запрос-ответ» 87
2.5.3. Оценка среднего времени выполнения запроса 89
2.6. Проверка адекватности полученной аналитической модели 91
2.6.1. Адаптация модели 91
2.6.2. Натурное моделирование запроса к одной таблице 92
2.6.3. Выводы по проверке адекватности модели 2.7. Сравнение быстродействия строчной и колоночной системы баз данных на основе моделирования 95
2.8. Сравнение быстродействия режимов работы ПКСБД на примере соединения таблиц 2.8.1. Архитектура SE - режим online 100
2.8.2. Архитектура SN - режим online 102
2.8.3. Пакетный режим 103
2.8.4. Сравнение архитектур параллельных систем 104
2.9. Сравнение быстродействия соединения методом NLJ и скрытого соединения в ПКХД 107
2.10. Выводы по главе ПО
Глава 3. Разработка программного комплекса поддержки принятия решения на этапе проектирования ПКСБД 112
3.1. Обоснование создания и требования кКППРП 112
3.2. Методика проектирования 114
3.3. Функциональное описание системы 116
3.3.1. Ввод информации о моделируемой системе 116
3.3.2. Моделирование и расчет характеристик системы 117
3.3.3. Анализ результатов моделирования
3.4. Структурное описание системы 121
3.5. Проектирование структур данных 123
3.6. Проектирование модуля расчета характеристик системы
3.6.1. Проектирование структуры классов 125
3.6.2. Алгоритм расчета характеристик системы
3.7. Архитектура системы 130
3.8. Выводы по главе 131
Глава 4. Применение разработанного КППРП для проектирования хранилища данных в крупной организации 132
4.1. Описание предметной области 132
4.1.1. Система менеджмента качества 133
4.1.2. Система менеджмента качества в кредитной образовательной организации 134
4.1.3. Процессный подход к СМКв банке 136
4.1.4. Описание показателей эффективности процессов банка 138
4.1.5. Постановка задачи моделирования 141
4.2. Описание проектируемого хранилища данных 142
4.2.1. Концептуальный проект нормализованного хранилища 142
4.2.2. Концептуальный проект ненормализованного хранилища 146
4.2.3. Технический проект централизованной системы 149
4.2.4. Технический проект распределенной системы 150
4.3. Результаты моделирования хранилища данных с помощью КППРП
151
4.3.1. Сравнение колоночной и строчной системы баз данных 152
4.3.2. Сравнение вариантов архитектур хранилища 153
4.3.3. Сравнение вариантов двух схем баз данных 154
4.3.4. Исследование пиковых нагрузок 154
4.4. Рекомендации по итогам моделирования 157
4.5. Выводы по главе 158
5. Заключение 159
Список использованных источников
- Преимущество ПКСБД при обработке аналитических запросов
- Вывод ПЛС времени выполнения запроса для последовательного плана с ранней материализацией
- Моделирование и расчет характеристик системы
- Описание показателей эффективности процессов банка
Введение к работе
Актуальность темы. Являясь одними из наиболее значимых элементов ИТ-инфраструктуры предприятия, базы данных (БД) консолидируют информацию, необходимую для создания достоверных аналитических и управленческих отчетов. Они являются одними из крупнейших источников информации для современных аналитиков и в ближайшей перспективе останутся ключевым компонентом ИТ-инфраструктуры предприятий.
Одним из ключевых показателей функционирования систем БД являются временные характеристики обработки запросов. При оценке производительности БД на этапе проектирования необходимо учитывать особенности предметной области. Результаты различных исследований показывают, что при расчете времени реакции информационной системы важно учесть параметры приложений: алгоритмы, запросы к базе данных и т.д. Время обработки этих запросов в аналитических системах достаточно велико, и её доля в общем времени выполнения прикладных программ превышает 90%.
Методы анализа временных характеристик для параллельных строчных баз данных (Oracle, MS SQL Server и т.д.), учитывающих специфику запросов к базе данных, уже разработаны и представлены в работах Ю.А.Григорьева, А.Д. Плутенко, В.Л. Плужникова. Но в настоящее время в крупных зарубежных и отечественных компаниях внедряются новые системы баз данных с иной организацией хранения данных, которые получили название параллельных колоночных систем баз данных (ПКСБД). Первые внедрения этих систем при разработке больших баз данных, используемых в системах поддержки принятия решения, свидетельствуют о значительном повышении производительности процесса обработки запросов, в частности в аналитических расчетах. При этом имеет место существенное сокращение объема ввода/вывода по сравнению с аналогичными строчными системами и значительное снижение времени выполнения аналитических запросов.
Но пока не существует математических методов оценки времени выполнения запросов в ПКСБД на этапе проектирования системы, позволяющих учитывать специфику сложных запросов к хранилищу данных, используемых в процессе принятия решений. Проектирование систем на основе колоночных систем управления базами данных ведется на интуитивном уровне. Поэтому разработка теоретических методов и средств, позволяющих на этапе проектирования оценить моменты случайного времени выполнения запроса в ПКСБД с учетом взаимосвязей всех компонентов сложной системы: архитектуры аппаратных средств, запросов к БД, параметров БД и т.п. - является актуальной в настоящее время задачей.
В диссертационной работе указанная задача решается путем разработки моделей оценки времени выполнения запросов в параллельной колоночной системе баз данных, учитывающих особенности колоночного хранения данных, состав и параметры выполнения запросов, структуру и наполнение хранилища, механизм распределения таблиц по процессорам
системы, параллелизм выполнения запросов в узлах, режимы работы системы, структуру сложного многопроцессорного аппаратно-программного комплекса.
Цель работы. Целью данной работы является разработка математических методов и программных средств оценки времени выполнения запросов в параллельных колоночных системах баз данных (ПКСБД).
В работе решаются следующие задачи:
-
анализ и сравнение процессов выполнения запросов в параллельной строчной и колоночной системе баз данных;
-
разработка аналитических моделей выполнения запросов в ПКСБД с различными архитектурами, включая хранилища данных ROLAP, на основе операторного метода;
-
разработка комплекса поддержки принятия решений на этапе проектирования ПКСБД на основе полученных аналитических моделей;
-
применение разработанного комплекса для анализа производительности хранилища данных крупной организации на этапе проектирования.
Объект исследования. Объектом исследования являются параллельные системы баз данных с колоночным хранением.
Предмет исследования. Предметом исследования являются процессы обработки запросов в параллельных колоночных системах баз данных.
Область исследования из паспорта специальности 05.13.17.
«1. Исследование, в том числе с помощью средств вычислительной техники, информационных процессов,...»; «2. Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»; «12. Разработка математических, логических, семиотических и лингвистических моделей и методов взаимодействия информационных процессов, ...».
На основе операторного метода (преобразование Лапласа-Стилтьеса) разработан новый класс моделей процессов выполнения запросов к БД применительно к широкому классу современных параллельных систем баз данных, имеющих колоночную структуру.
Научная новизна. В работе получены следующие новые научные результаты:
-
Разработан метод анализа времени выполнения запроса к одной таблице в параллельной колоночной системе баз данных (ПКСБД) для различных архитектур системы, учитывающий планы выполнения запроса с ранней и поздней материализацией.
-
Предложен метод оценки времени соединения таблиц в ПКСБД для различных архитектур (SE, SD, SN) и режимов работы системы (пакетный и «запрос-ответ»).
-
Разработан метод оценки времени выполнения запроса к параллельному колоночному хранилищу данных с учетом особенностей «скрытого соединения» для каждого этапа этого процесса.
Методы исследования. Исследования проводились на базе комплексного системного анализа с использованием операционного исчисления, теории массового обслуживания, теории вероятностей, теории множеств, теории реляционных баз данных, методов численного дифференцирования.
Практическая ценность полученных результатов. В работе проведен анализ адекватности разработанных моделей на примере колоночной СУБД MonetDB и HP Vertica. Погрешность оценки времени выполнения запроса к одной таблице составило не более 30% при следующем распределении: <10% - 70 случаев, >10% и <20% - 20 случаев, >20% и <30% - 30 случаев. Подобное распределение погрешности свидетельствует о возможности применения полученной математической модели оценки времени выполнения запросов на этапе проектирования ПКСБД.
Для практического использования полученных теоретических результатов разработан программный комплекс поддержки принятия решений на этапе проектирования ПКСБД (КППРП), позволяющий проводить оценку времени выполнения запросов выполнения запросов к ПКСБД. Он включает в себя модули расчета для различных типов архитектур и позволяет решать как прямую задачу исследования проектируемой системы (поиск «узкого места» и его устранение с целью повышения производительности системы), так и обратную (построение зависимостей временных показателей системы от параметров ее компонентов с целью поиска локального оптимума целевой функции системы).
Внедрение результатов исследований. Разработанные методы и инструментальное средство были применены в процессе проектирования и анализа качества работы хранилища данных, используемого для расчета ключевых показателей эффективности бизнес-процессов ЗАО АКБ «НОВИ-КОМБАНК» в рамках сертификации по системе менеджмента качества (ISO 9000). Хранилище данных обеспечивает выполнение трех основные задач: накопление данных, их бессрочное хранение и предоставление данных аналитикам. В соответствии с предъявленными требованиями и с учетом специфики предметной области были сформулированы предложения по реализации хранилища.
Публикации по теме. По материалам работы опубликовано 10 печатных работ, 4 из них - в журналах, рекомендованных ВАК.
Апробация работы. Материалы работы были изложены автором на следующих конференциях:
НТС кафедры ИУ-5 МГТУ им. Н.Э. Баумана, М., 2011-2014;
Международная научно-практическая конференция ИНФО-2012 «Инновации на основе информационных и коммуникационных технологий», г. Сочи, 2012;
VII Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», МГУ им. М.В. Ломоносова, 2012;
VIII Международная научно-практическая конференция «Современ
ные информационные технологии и ИТ-образование», МГУ им. М.В.
Ломоносова, 2013;
Шестой Всероссийский форум студентов, аспирантов и молодых уче
ных «Наука и инновации в технических университетах», Санкт-Пе
тербургский Государственный Политехнический Университет, 2012.
Работа удостоена гранта Президента РФ молодым ученым и аспиран
там на 2012-2014 гг.
Объем работы. Диссертационная работа содержит 171 страницу, 63 рисунка и 14 таблиц, список литературы из 142 наименований.
Преимущество ПКСБД при обработке аналитических запросов
Известно, что классические реляционные СУБД обеспечивают наилучшее сочетание простоты, устойчивости, гибкости, производительности, масштабируемости и совместимости, однако их показатели по каждому из этих пунктов не обязательно выше, чем у аналогичных систем, ориентированных на какую-то одну особенность. Согласно Майклу Стоунбрейкеру, пионеру исследований в области больших баз данных [6], такая идея «безразмерное», когда традиционная архитектура СУБД, изначально разработанная и оптимизированная для обработки бизнес-данных, используется для поддержки приложений, требующих обработки больших объемов данных, больше не применима к рынку баз данных. Мир коммерческих СУБД будет дробиться на набор независимых, специализированных средств управления базами данных, эффективных в своей узкой области [3].
У современных развитых коммерческих систем реляционных баз данных имеются, согласно работам [1,2,4,32,33], известные ограничения: обеспечивая широкий набор возможностей, они показывают пиковую производительность только для очень ограниченного набора режимов. Системы OLTP настраиваются на рабочие нагрузки с многочисленными мелкими, одновременно выполняемыми транзакциями типа «приход/расход», а системы поддержки принятия решений OLAP - на рабочие нагрузки с небольшим числом операторов (главным образом, выборки), но с большим числом операций соединения и агрегации. Между тем, в последнее десятилетие появилось много различных задач, связанных с обработкой больших объемов данных, для которых реляционные СУБД неэффективны и не обеспечивают приемлемое соотношение «цена/производительность (время обработки запроса)», и при решении которых от использования РСУБД пришлось отказаться [1].
Данные ограничения, согласно [2], базируются на том факте, что все популярные реляционные СУБД берут свое начало от системы System R, разработанной в 70-е годы прошлого века. Например, СУБД DB2 является прямой наследницей System R, и на первый выпуск этой системы оказала сильнейшее влияние подсистема RDS System R. Аналогично, MS SQL Server - это непосредственный наследник Sybase System 5, на разработку которой очень сильно повлияла System R. Наконец, в первом выпуске Oracle был напрямую реализован пользовательский интерфейс System R.
Все три перечисленные системы были построены более 25 лет тому назад, когда характеристики аппаратуры существенно отличались от тех, которые имеются сегодня. В настоящее время процессоры обладают тысячекратно большей мощностью, а память - тысячекратно большей емкостью. Невероятно возросли объемы дисковой памяти, позволяющие теперь долговременно сохранять огромные объёмы данных. Однако пропускная возможность канала между диском и основной памятью растет гораздо медленнее. Можно было ожидать, что скорость развития компьютерных технологий в последней четверти минувшего столетия приведет к существенным изменениям архитектуры систем баз данных, но, как это ни странно, архитектура большинства СУБД, по существу, остается идентичной архитектуре System R.
Кроме того, в то время, когда задумывались реляционные СУБД, существовал единственный рынок СУБД: рынок систем обработки бизнес-данных. За прошедшие 25 лет образовался ряд других рынков: хранилищ данных, обработки текстовых данных, обработки потоковых данных. В этих областях имеются совсем другие требования, чем в области обработки бизнес-данных.
Наконец, во времена разработки РСУБД основным устройством, поддерживающим интерфейс с конечными пользователями, являлся алфавитно-цифровой терминал, и в качестве конечных пользователей производители имели в виду операторов, вводящих в интерактивном режиме запросы по приглашению, появляющемуся на экране терминала. Теперь конечные пользователи имеют дело с мощными персональными компьютерами, подключенными к Web. На Web-сайтах, на которых используются транзакционные СУБД, редко выполняются интерактивные транзакции, а их пользователям вряд ли предоставляются интерфейсы на основе SQL.
Конечно, с годами в этих архитектурах появились некоторые расширения, включающие поддержку сжатия данных, параллельное управление данными с использованием общей дисковой памяти, битовые индексы (bitmap index), поддержка определяемых пользователями типов данных и операций и т.д. Однако ни одна система ни разу не подверглась полному перепроектированию после ее исходного изготовления [2]. Анализ рынка показывает [1,5], что даже в традиционных прикладных областях имеется возможность значительных инноваций. На рынках аналитики для бизнеса и науки заказчики могут купить петабайты памяти и тысячи процессоров, но доминирующие коммерческие системы баз данных для многих рабочих нагрузок не способны к такому масштабированию. Даже в тех случаях, когда это удается, стоимость программного обеспечения и управления им по отношению к стоимости аппаратуры является непомерной.
В работе [3] показано, что традиционная архитектура СУБД (изначально разработанная и оптимизированная для обработки бизнес-данных) используется для поддержки многих приложений, требующих обработки больших объемов данных, которые обладают очень разными характеристиками, и к которым предъявляются очень разные требования. За прошедшие 30 с лишним лет рынок систем управления данными сильно фрагментировался. Стали известными большие секторы рынка, для которых очень существенна высокая производительность приложений, которая не достигается или достигается с недопустимо большими затратами при использовании (универсальных) «безразмерных» СУБД. Другими словами, экономически целесообразной стала разработка специализированных систем, которые ориентируются на эффективную поддержку заранее известных сценариев использования [33].
Идея «безразмерности» больше не применима к рынку баз данных, и мир коммерческих СУБД дробится на набор независимых средств управления базами данных, некоторые из которых могут быть объединены некоторым общим языковым интерфейсом. Для поддержки своих утверждений в работе [3] приведены примеры из областей систем обработки потоков данных и хранилищ данных -сегмента задач СУБД, который не существовал до начала 90х годов [5,31,32,36]. В соответствии с классическим определением хранилище данных (ХД) - это "копия транзакционных данных, специальным образом структурированная для поддержки выполнения запросов и анализа данных" [35]. В качестве крупнейшего архитектурного решения для хранилищ данных в работах [3,32,33] приводится хранение данных по столбцам, а не по строкам (колоночное хранение), а наиболее успешной из всех известных стратегий анализа сверхбольших наборов данных, согласно [37], рассматривается распределенная или параллельная обработка.
Все основные поставщики СУБД реализуют системы хранения, ориентированные на записи, где атрибуты каждой записи располагаются в области хранения непрерывно. При использовании этой архитектуры «хранения по строкам» для выталкивания на диск всех атрибутов одной строки требуется вывод на диск блока таких строк. Следовательно, такая система является «оптимизированной в расчете на запись», поскольку легко достигается высокая производительность при записях строк. Очевидно, что системы, оптимизированные в расчете на запись, особенно эффективны при поддержке OLTP-приложений, и это является основной причиной использования данной архитектуры в большинстве коммерческих СУБД.
В отличие от этого, системы хранилищ данных нуждаются в «оптимизации в расчете на чтение», поскольку их основная рабочая нагрузка состоит из непредвиденных запросов, затрагивающих большие объемы исторических данных. В таких системах существенно более эффективна модель «хранения по столбцам», которая предполагает непрерывное хранение значений одного атрибута во всех строках. В общем случае под колоночным хранением понимается разделение таблицы данных на столбцы, которые размещаются на физической памяти раздельно друг от друга (Рисунок 1).
Вывод ПЛС времени выполнения запроса для последовательного плана с ранней материализацией
Запросы к базе данных: количество обрабатываемых запросов в день, средний объем данных по каждому запросу, скорость выполнения запросов. Ниже перечислены недостатки экспертного метода сравнения архитектур: 1. Экспертные оценки зачастую носят субъективный характер, могут быть противоречивыми и не проверяемы опытным путем. 2. Среди метрик могут отсутствовать точные количественные показатели производительности и стоимости системы на базе выбираемой архитектуры строчной или колоночной системы баз данных.
При оценке быстродействия работы проектируемой параллельной системы баз данных большое значение имеет анализ количественных временных показателей, которые зависят не только от характеристик аппаратных средств, но и от «тяжести» выполняемых запросов. Но даже опытному проектировщику бывает трудно, а порой невозможно спрогнозировать значения данных временных показателей.
Опытное сравнение производительности систем баз данных на основании тестирования
Существующие системы тестов делятся на два основных класса: компонентные тесты и интегральные тесты. Компонентные тесты производят оценку производительности одного или нескольких компонентов сложной системы: процессора, памяти, системы ввода-вывода, дисков и т. д. Наиболее известны из них тесты SPEC (Standard Performance Evaluation Corporation). [98,99,100].
Тесты, оценивающие производительность систем обработки транзакций, появились в середине 1980-х годов, когда начался новый этап развития компьютерных технологий и их применения в бизнесе. Этот этап характеризовался значительным ростом транзакций в режиме online. Такие вычисления заметно отличались от пакетной обработки данных, и для их обработки был предложен термин On-Line Transactions Processing (OLTP). В процессе развития СУБД появилось несколько различных тестов их производительности, но фактически стандартом индустрии сегодня считаются универсальные интегральные тесты ТРС [109,110]. Компонентные тесты SPEC.
Важность создания пакетов тестов, базирующихся на реальных прикладных программах широкого круга пользователей и обеспечивающих эффективную оценку производительности процессоров, была осознана большинством крупнейших производителей компьютерного оборудования, которые в 1988 году учредили бесприбыльную корпорацию SPEC (Standard Performance Evaluation Corporation) [102,103]. Основной целью этой организации является разработка и поддержка стандартизованного набора специально подобранных тестовых программ для оценки производительности новейших поколений высокопроизводительных компьютеров. Главными видами деятельности SPEC являются:
Разработка и публикация наборов тестов, предназначенных для измерения производительности компьютеров. Перед публикацией объектные коды этих наборов вместе с исходными текстами и инструментальными средствами интенсивно проверяются на предмет возможности импортирования на разные платформы.
Публикация ежеквартального отчета о новостях SPEC и результатах тестирования: "The SPEC Newsletter", что обеспечивает централизованный источник информации о результатах тестирования на тестах SPEC.
Основным результатом работы SPEC являются наборы тестов. Эти наборы разрабатываются SPEC с использованием кодов, поступающих из разных источников. SPEC работает над импортированием этих кодов на разные платформы, а также создает инструментальные средства для формирования из кодов, выбранных в качестве тестов, осмысленных рабочих нагрузок.
В настоящее время имеется два базовых набора тестов SPEC [101], ориентированных на интенсивные расчеты и измеряющих производительность процессора, системы памяти, а также эффективность генерации кода компилятором. При прогоне тестового пакета делаются независимые измерения по каждому отдельному тесту. Обычно такой параметр, как количество запускаемых копий каждого отдельного теста, выбирается исходя из соображений оптимального использования ресурсов, что зависит от архитектурных особенностей конкретной системы. Одной из очевидных возможностей является установка этого параметра равным количеству процессоров в системе. При этом все копии отдельной тестовой программы запускаются одновременно, и фиксируется время завершения последней из всех запущенных программ.
Моделирование и расчет характеристик системы
Важно подчеркнуть, что использование преобразования Лапласа-Стилтьеса позволяет оценить правую границу доверительного интервала времени выполнения запроса с надёжностью а (см. (6)).
Выражение типа (18) представляет собой ПЛС функции распределения вероятностей суммы большого числа независимых случайных величин (если число записей в таблице R велико). Согласно центральной предельной теореме Ляпунова [138] распределение этой суммы близко к нормальному закону. Тогда в (6) для ос=0.683 г=1, для ос=0.955 г=2, для ос=0.997 г=3.
Используя описанный выше подход, можно получать ПЛС времени выполнения сложных запросов с учётом особенностей их обработки в СУБД.
Важно подчеркнуть, что в дальнейшем выводятся ПЛС времени выполнения запросов о одном узле (процессоре). Это и есть ПЛС времени выполнения исходного запроса, т.к. на разных узлах запрос выполняется параллельно. Оценка правой границы доверительного интервала позволяет определить время выполнения запроса на самом медленном узле и быстродействия работы системы в целом.
Анализ выполнения запроса к одной таблице в ПКСБД Используя подход, предложенный в [15], в работах [26,27] выводится преобразование Лапласа-Стилтьеса (ПЛС) времени выполнения запроса к колоночной базе данных. При этом учитываются следующие условия:
Формализация процесса выполнения запроса к одной таблице в ПКСБД Ниже представлено формализованное описание процесса выполнения запроса к одной таблице в ПКСБД (Рисунок 19). Процесс выполнения запроса к одной таблице в ПКСБД. Общее время выполнения запроса можно представить в виде следующих времен: время обработки кортежей всех столбцов, для которых заданы элементарные условия поиска; время обработки кортежей всех остальных необходимых для предоставления результата атрибутов; время фильтрации по условиям; время формирования ответа и его пересылки. 2.2.2. Вывод ПЛС времени выполнения запроса для последовательного плана с ранней материализацией Используя подход, предложенный в [15], в работе [26] выводится преобразование Лапласа-Стилтьеса (ПЛС) времени выполнения запроса к базе G = z - производящая функция (ПФ) числа позиций (записей) проекции R, обрабатываемых на одном процессоре, V - общее число записей в проекции R, п -число процессоров в кластере (или в машине).
Примечание. При хорошей хеш-функции таблица равномерно фрагментируется по ключевому (уникальному) атрибуту с точностью до 0.5%.
Фм (s) - ПЛС времени сохранения атрибута в ОП и его чтения в кэш процессора; Vi -размер атрибута; m-v; - число операций чтения/записи в оперативную память, необходимых для проверки условия по соответствующему атрибуту (для і-го столбца вводится аргумент mi - см. (21)); Pp(s)- ПЛС времени обработки кортежа столбца в процессоре, г - число логических операций, необходимых для проверки условия по соответствующему атрибуту (для і-го столбца вводится аргумент ГІ - см. (21));
Примечание. Будем считать, что кэш процессора - это «чёрная дыра», в которой сохраняются данные процессора, необходимые для вычислений. Из кэша в ОП перемещаются только результирующие материализованные записи, передаваемые по шине (см. далее (s)) процессору, где выполняется сборка. Иллюстрация особенностей последовательного плана запроса. Подобная организация процесса чтения атрибутов позволяет уменьшить количество операций чтения блоков данных с диска. На Рисунок 20 показаны колонки атрибутов. Перечёркнуты те блоки, которые не надо считывать, т.к. соответствующие записи не удовлетворяют условию поиска по предыдущим атрибутам. Ниже приведено полученное в работе [27] преобразование Лапласа-Стилтьеса (ПЛС) времени выполнения запроса к базе данных с планом 71A(CJF(R)) И условием G=zv/n - производящая функция (ПФ) числа позиций (записей) таблицы (отношения) R, обрабатываемых на одном процессоре, V - общее число записей в таблице R, п - число процессоров в кластере (или в машине).
Функция V/i(s,z) учитывает, что читаются кортежи колонок по позициям, которые удовлетворяют условиям поиска по предыдущим атрибутам. Эта функция рекуррентно определяется следующим образом: Фм (5) - ПЛС времени сохранения атрибута в ОП и его чтения в кэш процессора; Vi -размер атрибута; m-v; - число операций чтения/записи в оперативную память, необходимых для проверки условия по соответствующему атрибуту (для і-го столбца вводится аргумент щ - см. (29)); 0рО)- ПЛС времени обработки кортежа столбца в процессоре, г - число логических операций, необходимых для проверки условия по соответствующему атрибуту (для і-го столбца вводится аргумент ГІ - см. (29));
При соединении отношение во внутреннем цикле остается отсортированным по порядку, отношение во внешнем цикле - нет (Рисунок 21). Так как чтение по неотсортированным позициям и последующее соединение может занять продолжительное время, в [21] предлагается для внешнего отношения использовать раннюю материализацию (в оператор соединения сразу подаются готовые кортежи). 36 3S 1 :
В параллельных базах данных нефрагментированная по атрибуту соединения таблица пересылается другим узлам и используется во внешнем цикле. Так как согласно [22] оператор exchange работает покортежно, передавать битовые маски нельзя и для обоих отношений необходимо использовать раннюю материализацию.
Описание показателей эффективности процессов банка
На Рисунок 36 и Рисунок 38 представлены зависимости времени выполнения соединения таблиц от количества процессоров (узлов) для различных архитектур, режимов и нагрузок. Из графиков видно, что при единичной нагрузке (А,=1 и =1) в пакетном режиме запросы обрабатываются дольше. При высоких нагрузках SN-архитектура показывает лучшее время по сравнению с архитектурами SD и SE.
Зависимость времени выполнения запроса от количества процессоров (узлов) для различных режимов работы при единичной нагрузке.
На Рисунок 38 представлена зависимость коэффициента масштабируемости системы (отношение производительности к числу процессоров) от числа процессоров для различных архитектур и режимов работы. Видно, что при пакетном режиме масштабируемость отклоняется от линейной, а в режиме on-line она близка к линейной (т.е. время уменьшается практически пропорционально увеличению количества узлов). Но это, конечно, справедливо, если с ростом числа процессоров накладные расходы параллельной колоночной системы баз данных увеличиваются незначительно.
Сравнение быстродействия соединения методом NLJ и скрытого соединения в ПКХД Ниже приведено сравнение времени выполнения запроса к хранилищу данных для скрытого соединения и соединения методом NLJ. Характеристики ресурсов (интенсивности обработки) были получены с помощью программы синтетических тестов AIDA64 [54]. Расчёты были выполнены при следующих значениях характеристик ресурсов.
Оперативная память - DDR3-1600 РСЗ- 12800. Интенсивность чтения одного байта информации из ОП равна дм= 9586-1024-1024 (1/с). В качестве примера был выбран аналитический запрос Q3 теста ТРС-Н [22]. Схема базы данных тестовой среды приведена на рисунке 6; запрос приведен ниже. Коэффициент sf теста определяет объем обрабатываемых данных. select l_orderkey, sum(l_extendedprice (l-l_discount)) as revenue, oorderdate, oshippriority from customer, orders, lineitem where c_mktsegment = [SEGMENT] and c_custkey = o_custkey and lorderkey = oorderkey 108 and oorderdate date [DATE] awrfl_shipdate date [DATE] group by lorderkey, oorderdate, oshippriority order by revenue desc, о orderdate;
COMMENT NAME о — " REGIONKEY REGIONKEY NAME COMMENT COMMENT Рисунок 39 - Схема базы данных теста ТРС-Н. График зависимости времени выполнения запроса от количества узлов для скрытого соединения и соединения методом NLJ для архитектуры SE представлен на Рисунок 40. Из графика видно, что метод скрытого соединения превосходит по скорости метод NLJ, причем соотношение времени выполнения сохраняется при изменении количества узлов.
Зависимость времени выполнения запроса для различных методов соединения при архитектуре SE (sf=0.01). Ниже (Рисунок 41) приведена зависимость времени выполнения запроса для различных методов соединения и архитектур в зависимости от коэффициента sf теста ТРС-Н. При увеличении объема обрабатываемых данных время обработки при использовании метода NLJ увеличивается быстрее, чем при методе скрытого соединения.
Проведено сравнение быстродействия строчной и колоночной системы баз данных с помощью полученной модели. При этом учитывалось влияние сжатия данных на время выполнения запросов. На конкретных примерах показано, при достаточном сжатии столбцов время выполнения запроса в колоночной системе меньше, чем в строчной системе даже при использовании в запросе 100% атрибутов (см. табл. 7). Для колоночной системы пятнадцатисекундная отметка среднего времени выполнения запроса при 10% используемых в запросе атрибутов достигается при меньшем числе машин (п=2), чем для строчной системы (п=10). Это свидетельствует об экономии вычислительных ресурсов при использовании колоночных СУБД. Показано, что математические модели, в отличие от натурных стендов, позволяют достаточно просто менять различные параметры, строить и сопоставлять зависимости.
Проведено сравнение быстродействия выполнения запроса к колоночному хранилищу данных для скрытого соединения и соединения методом NLJ. Показано превосходство метода скрытого соединения. Полученное соотношение увеличения скорости выполнения запроса (в 2.75 раза) соответствует экспериментально полученному в работе [21] значению.
Разработанная в главе 2 математическая метод оценки быстродействия ПКСБД на базе математической модели времени выполнения запроса в ПКСБД позволяет получить моменты случайного времени выполнения запроса. Однако, эта операция достаточно трудоемка, требует значительного объема расчетов и приближенных компьютерных вычислений, как было показано в части «Оценка среднего времени выполнения запроса». Более того, для использования разработанных методов необходимо обеспечить возможность хранения и сравнения результатов моделирования двух и более вариантов исследуемой системы, а также вывод информации в графическом виде для более удобной работы аналитика.