автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Оптимизация многопроцессорной обработки упорядоченных мультизапросов

На правах рукописи

Вунна Джо Джо

«Оптимизация многопроцессорной обработки упорядоченных

мультизапросов»

Специальность 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ 2 5 I í.-iP 2015

диссертации на соискание учёной степени кандидата технических наук

Москва 2015

005561234

Работа выполнена на кафедре «Вычислительные машины, системы и сети» федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский авиационный институт (национальный исследовательский университет)»

Научный руководитель:

Официальные оппоненты:

доктор технических наук, профессор Брехов Олег Михайлович

доктор технических наук, профессор Иванова Галина Сергеевна, профессор МГТУ им. Баумана

Ведущая организация:

кандидат технических наук, с.н.с. Филиппов Владимир Александрович, профессор МИЭМ НИУ ВШЭ

ОАО « Научно-исследовательский институт вычислительных комплексов (НИИВК) им. М.А.Карцева»

Защита состоится « 27 » апреля 2015г. В 10:00 часов на заседании диссертационного совета Д212.125.01 при Московском авиационном институте (национальном исследовательском университете) по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д.4.

С диссертацией можно ознакомиться в библиотеке Московского авиационного института (национального исследовательского университета).

Отзывы, заверенные печатью, просьба высылать по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д.4, МАИ, Ученый совет МАИ

Автореферат разослан « 1Í » о 2015г.

Ученый секретарь

диссертационного совета Д212.125.01у кандидат технических наук, доцент

А.В.Корнеенкова

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Основным критерием при определении Плана реализации запроса является время выполнения мультизапроса, которое, вообще говоря, зависит от порядка выполнения элементарных запросов, его составляющих, и от времени проверки в строке и вероятности успеха в строке. Время выполнения элементарного мультизапроса зависит от метода доступа к столбцу таблицы. Известным методом увеличения производительности является использование многопроцессорных бортовых ВС.

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

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

Методы исследования. Аналитическое моделирование. Современная методология организации баз данных. Научная новизна

• Предложен и обоснован метод оптимизации по времени выполнения мультизапроса при обращении к базе данных на основе упорядочивания элементарных запросов.

• Доказаны условия, при которых совместная обработка конъюнктивного мультизапроса обеспечивает не большее время выполнения по отношению к независимой обработке.

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

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

• Предложен оптимальный алгоритм распределения элементарных запросов на процессоры.

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

Применяемым математическим аппаратом. Соответствием полученных и известных результатов.

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

Реализация результатов работы. Результаты диссертационной работы используются в учебном процессе кафедры «Вычислительные машины, системы и сети» Московского авиационного института (национального

исследовательского университета) в форме информационного обеспечения блока дисциплин, а также в лекционном курсе «Моделирование».

На защиту выносятся следующие положения:

• Метод обеспечения оптимизации многопроцессорной обработки мультизапросов.

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

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

• Оптимальный план распределения элементарных запросов на процессоры.

Апробация работы. Основные положения и результаты диссертационного исследования докладывались автором и обсуждались на научно-практической конференции студентов и молодых ученых МАИ «Инновации в авиации и космнавтике-2010», 13-ой Международной конференции МАИ «Авиация и космонавтика-2013»,12-15 ноября 2013 года.

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

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения, библиографического списка из 50 наименований. Работа изложена на 145 страницах, содержит 27 таблиц и 28 рисунков. СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Однако с растущей важностью оперативной обработки данных техника разработки и использования более сложных методов оптимизации запросов стала решающей. Для того чтобы быть эффективными, оптимизаторы должны адаптироваться к новым операторам, изменению в методах оценки стоимости и т.д. Эти требования привели к нынешнему поколению оптимизаторов запросов, из которых два оптимизатора Starburst и Volcano являются наиболее представительными. В то время как IBM DB2 оптимизатор основан на Startburst,

Microsoft SQL-Server оптимизатор основан на системе Volcano. Основным различием между подходами является то, каким образом альтернативные планы создаются. Оптимизатор Starburst генерирует планы снизу вверх, тогда как оптимизатор Volcano создает планы сверху вниз.

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

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

Предположим, что база данных D задана как ряд отношений {R1,R2 ,

.....каждое отношение определено на ряде признаков. План доступа

относительно запроса Q - последовательность основных операций, которые дают ответ на запрос Q. Например, имеется Служащий (ID, Имя, Род, Заплата, Город), с очевидными значениями для различных областей. Пусть задан следующий запрос SQL:

Select * From Employeel

Where Род=Ы'М' and Зарплата>=1000 and Город = Ы'Москва', может быть обработан, посредством выполнения следующих задач (Tl) ТЕМР1 := Pofl=N'M' (Т2) ТЕМР2 := Зарплата>=1000 (ТЗ) RESULT := Город = КМосква' Существует ряд возможных альтернатив плана обработки этого запроса.

У задач есть некоторая стоимость, связанная с ними, которая отражает стоимость центрального процессора, стоимость ввода / вывода, требуемых при их обработке. Стоимость плана доступа - стоимость обработки ее составляющих задач. Если имеется ряд запросов Q={Qi,Q2,---,Qn}> то глобальный план доступа относительно Q соответствует плану, который обеспечивает способ вычислить результаты всех п запросов. Глобальный план доступа может быть создан, выбирая один план относительно каждого запроса и затем объединяя их вместе. Объединение в местном масштабе оптимальных планов не обязательно дает глобально оптимальный план. В связи с этим используются эвристические, динамические и другие алгоритмы.

В работах Selinger P.G., Astrahan М.М., Chamberlin D.D., Lorie R.A., Price T.G., Брехова O.M. показано, что минимальное время выполнения запроса может

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

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

Во второй главе разработан метод оптимизации однопроцессорной обработки мультизапросов.

Пусть множество запросов 3;, £ = 1, п, образуют мультизапрос, при этом запросы 3; сформированы конъюнкцией элементарных запросов, из которых ряд элементарных запросов повторно входят в запросы 3£. Назовем такой мультизапрос конъюнктивным мультизапросом.

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

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

--< --, I = 1,/с - 1,

1 -р1 1 - рг+1

и для упорядоченных столбцов таблицы в порядке

Р; _ Рг+1 тг+1

</ , £ = 1, /с — 1, 1 - Р; 1 - Рг+1

где

п- число строк таблицы базы данных, к - число столбцов таблицы,

г(- время обработки I -го элементарного запроса ЭЗг для одной строки таблицы, рг - вероятность успеха при обработке 1 -го элементарного запроса Э3; для одной строки таблицы (данные одной строки таблицы отвечают условию, заданным элементарным запросом Э3£).

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

Общий алгоритм формирования плана совместной обработки конъюнктивного мультизапроса

Алгоритм совместной обработки запросов конъюнктивного мультизапроса состоит в следующем: определяются подмножества совпадающих элементарных запросов, входящих в запросы конъюнктивного мультизапроса. Таких подмножеств может быть несколько, поэтому среди них выделяется одно по соответствующему критерию. Этому подмножеству соответствует

элементарный запрос, который выполняется в первую очередь. Выделенный элементарный запрос удаляется из числа элементарных запросов мультизапроса.

Далее указанная процедура продолжается до тех пор, пока подмножество совпадающих элементарных запросов становится пустым.

В качестве критерия выделения подмножества (элементарного запроса) назовем следующие: номер элементарного запроса; число запросов, в которые входит элементарный запрос (глубина охвата); число элементарных запросов, образующих подмножество (ширина охвата).

Определение. Назовем запрос опорным запросом, если его первые (по условию упорядоченности) элементарные запросы образуют общее подмножество с другим запросом мультизапроса.

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

Пусть множество запросов ЭЗ1, I = 1, к, образуют конъюнктивный мультизапрос, в котором выделим два запроса 3! и 32:

• Зг = ЭЗ(1&ЭЗ;2&...&ЭЗ;г

• 32 = ЭЗА& Э3;2& ... & ЭЗ;1эЗ;и+1& ...& Э3;„

Пусть пересечение запросов 3! и 32 (Зх П 32) даёт подмножество с и элементарными запросами (в обозначениях запроса 32 первыми и элементарными запросами: ЭЗу , ЭЗу , ...,ЭЗуц), т.е. запрос 32 является опорным запросом. По условию упорядоченности элементарные запросы опорного запроса 32 выполняются первыми в порядке, отвечающем условию упорядоченности, т.е. время выполнения запроса 32 остается минимальным. Так как запросы 3! и 32 выполняются совместно, то время выполнения запроса Зх с учетом уже выполненнных элементарных запросов: ЭЗу ,ЭЗу , ...,ЭЗ¡и ограничено выполнением подмножества элементарных запросов

ЗДСЭЗ^ЭЗ^.....Э3/ц) = 33^,33^, ...,ЭЗ;г_и

и равно:

Для неупорядоченных данных

ТсовмД.„ = п(Р]\'Р)2.....Р]и +Р!1т12+Р11Р(2т!3 +•••+ Рь-Р1г-и-г^г-«))'

Для упорядоченных данных

ТссвМ,1,у = п(р]1.р]-2.....Р]и (р;1т,1 + Р11Р12Тк+Р11Р12Р13Т1з +...+ рг1 ...р,г_цт[г_ц)),

где параметры (г(1, р^), (т,2, р,2),... (г,г_ц, р(г_ц) - параметры соответствующих элементарных запросов: Э3(1, Э31г,..., 33¡г_ц.

Очевидно, что время выполнения запроса Зг и, следовательно, времени выполнения обоих запросов 3! и 32 при совместной обработке всегда не больше времени выполнения при независимой обработке.

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

Пример формирования плана совместной обработки конъюнктивного

мультизапроса для мультизапроса.

Пусть мультизапрос состоит из четырех запросов

• Зг- ЭЗХ & Э32 & Э33 & Э34 & Э35 & Э36 & Э38 & Э39

• з2 = эз3&эз4&эз6&эз7&эз10&эз11

• з3 = эз4&эз6&эз7&эз12

• з4 = эз3&эз4&эз6&эз7&эз10

Сформируем план обработки этого мультизапроса на основе общего алгоритма формирования плана совместной обработки конъюнктивного мультизапроса.

Время выполнения конъюнктивного мультизапроса при независимой обработке равно сумме времен обработки запросов 31, 32, З3 и 34:

для неупорядоченных данных

Тнез.н = Т1>н + Т2 „ + Т3 н + Т4 н ,

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

Алгоритм 1

В алгоритме 1 запрос 3 образует опорный запрос, элементарные запросы Э34, Э36 которого образуют общее подмножество и выполняются первыми.

Шаг 1: Выделяем элементарный запрос Э34 на основе Л З^-щ = Э34 Шаг 2: Выделяем элементарный запрос Э36 на основе П 3;(-;=^^у\(Э34 ) = Э36 Шаг 3: Выделяем элементарный запрос Э33 на основе

ПЗШ=1^)\(Э34&Э36) = эз3

Шаг 4: Выделяем элементарный запрос Э37 на основе

Л 3£(£=2д)\(ЭЗз&Э34 &Э36) = Э37

Шаг 5: Выделяем элементарный запрос Э310 на основе

Л 3(С£=2д)\033 & 334 & Э36&Э37) = Э310

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

Алгоритм 2

В алгоритме 2 запросы 2 и 4 образует опорный запрос, элементарные запросы Э33,Э34,Э36 которого образуют общее подмножество и выполняются первыми.

Шаг 1: Выделяем элементарный запрос Э33 на основе П Зщ=124) = Э33 Шаг 2: Выделяем элементарный запрос Э34 на основе П 3£(£=124Д(Э33 ) = Э34 Шаг 3: Выделяем элементарный запрос Э36 на основе П 3((£=2д)\(Э33 &Э34) = Э36

Шаг 4: Выделяем элементарный запрос Э37 на основе Л 3£((=2Л)\(Э33 &Э34&Э36) = Э37 Шаг 5: Выделяем элементарный запрос Э310 на основе П 3£(£=2д)\(Э33 &Э34&Э36&Э37) = Э310

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

Совместная обработка лучше независимой обработки по алгоритму 1 для неупорядоченных данных, если справедливо неравенство Тнез.н ^ Тсовм 3 н, которое здесь имеет вид

- Р4РбРз) + (Р1-Р4РбРзР1)г2 + (2 + Р1Р2-Р4Р6 )т3 + (2р3 + р!р2р3)г4 + (Р1Р2РзР4-Р4РбРзР1Р2)г5 + СР1Р2Р3 Р4Р5 + 2р3р4)г6 + РзР4РбТ7 + Р3Р4Р6Р7Т10 > О,

Это неравенство выполняется при любых значениях параметров.

Оценка времени выполнения мультизапроса

Сформулируем ряд утверждений.

Пусть мультизапрос состоит из п запросов 3£, I — 1,п, элементарные запросы которых образуют упорядоченные множества $£,1 = 1,п, с последовательными (без пропусков) номерами элементарных запросов.

Пусть выполняются следующие условия: Вложение множеств: % э 52 э ••• э^э ••• г>

Пересечение множеств: 5 = 5„ = П"=:1зг.

Утверждение 1. Выполнение элементарных запросов подмножеств Б, в порядке 1 = п, 1, обеспечивает уменьшение времени совместного выполнения запросов мультизапроса.

Доказательство следует по индукции:

Обозначим параметры элементарного запроса: т; - время, требуемое для выполнения элементарного запроса Э3|, и р, - вероятность успеха при его выполнении, £ = 1, п.

Пусть запрос Зи_| образован элементарными запросами с последовательными номерами:

ЭЗл+1. ЭЗл+2..., 33 /1+£, ЭЗл+1+1, ЭЗл+(+2,.., ЭЗл+1+т, 33 ¡1+1+т+1, ЭЗ^+^т+г,.., ЭЗ/,+1+771+с и запрос 3„ образован элементарными запросами, соответственно: ЭЗ/ц-г-ц, ЭЗ^+г+2,..., 33^+;+т.

При несовместном выполнении этих двух запросов имеем следующее

время:

для запроса Зп_1:

для запроса 3„:

Тзп - т/г+(+1 + Р/1+г+1тл+1+2 Н I" (И^иХТ+г Р])Тн+1+,

При совместном выполнении этих запросов получаем:

Очевидно, разность

/ / Ь4£+т \\ т /?!+!+¡-1

больше 0.

Последовательно проводя аналогичные рассуждения для пар запросов (3„_£+1, 3n_£), i = 2,п — 1, полностью завершаем доказательство. Утверждение 2. Пусть пересечение множеств элементарных запросов s;, i = есть подмножество s = sn = n"=i5£. Если подмножество s образовано элементарными запросами с последовательными номерами, начиная с первого элементарного запроса Э3[_ то выполнение элементарных запросов подмножества s первыми обеспечивает уменьшение времени совместного выполнения относительно несовместного выполнения запросов мультизапроса на время (п-1) Ts, где Ts - время выполнения элементарных запросов подмножества s.

Доказательство следует из факта, что выполнение элементарных запросов подмножества s первыми не нарушает оптимальный по времени порядок обработки всех п запросов.

В третьей главе рассматривается время выполнения мультизапроса в многопроцессорной ВС.

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

В случаях, когда запросы не удовлетворяют Утверждениям 1 и 2 эффективность совместной обработки по критерию времени выполнения мультизапроса зависит от параметров т; и р, и не всегда лучше не совместной обработки запросов.

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

Пусть запросы мультизапроса определены следующими параметрами: к - число элементарных запросов, образующих запросы мультизапроса 3i , , ..., 3V, элементарные запросы образуют d групп по и элементарных запросов в каждой группе, каждый запрос 3, i = 1, v, содержит две группы элементарных запросов с номерами:

1-ая группа: ЭЗ(,•.;>+/ >•••! Э3,„ ,..., Э37у„+^ц+ (,_/;„+/,..., Э37у„+ ЭЗ (,-.

i)U+i,..., ЭЗ fj-i)(v+i)u*iu, j = 0,d — 1, 2-ая группа: ЭЗ „,+/,•••, ЭЗга+и .

Рис. 3.1. иллюстрирует мультизапрос при значениях параметров к = 32, d= 2, и=4, v = 3.

3,к

эз;э?2 эз,эз4

и

N--►

Э332

ЭЗ,

—

эз.

33,9 Э3£2

э7

Рис. 3. 1. Мультизапрос при значениях параметров к = 22,(1 =2, и=4, V = 3

Определим время выполнения мультизапроса при совместном и несовместном выполнении запросов (далее для упорядоченных таблиц). Степенная зависимость времени обработки элементарных запросов Совместное выполнение запросов мультизапроса. СЗ

Пусть время т; обработки элементарных запросов в строке таблицы соответствует степенной зависимости (СЗ).

Время выполнения мультизапроса при совместном выполнении запросов: при г = 1

при Г > 1

С^+Р

2 ,г.

Несовместное выполнение запросов мультизапроса. СЗ

Время выполнения мультизапроса при несовместном выполнении запросов: При г - 1

т„

При г > 1

Сравнение совместной и несовместной обработки запросов. СЗ

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

Совместное выполнение запросов мультизапроса имеет смысл, если выполняется неравенство Тс несов > Тссов, т.е. если

Рассмотрим два частных случая: 1 ) При d. = 1 находим

Это выражение, по крайней мере, больше О, если

vри > 1, или

2) Пусть значение вероятности р -» 0.

Тогда, например, при г > 1 имеем:

avu — 1

Тс.„есов.г>и = п(а' 1 + ра2г О _ + о(р)

Т,с,соВ,г>1,7 = "(a'"1 + pa2l-')a™ + о(р)

Поэтому совместная обработка запросов требует меньше времени, чем несовместная, если

Т'с.несов,г>и - 7-с,сов,г>и = пСа'"1 + ра2^) (gj - а"") + о(р) >0.7 = 27F, или

/а™ - 1 \

или если + 2. Например, для а = 1.1, v — 4, и = 6 находим:

l.l6 H—-тт < 2 или 1.8731 <2. î.i24

Поэтому здесь совместная обработка запросов требует меньше времени, чем несовместная. Для а = 1.1, v — 4, и = 8 получаем:

т.е. здесь несовместная обработка запросов требует меньше времени, чем совместная.

В диссертации и на рис. 3.2 представлены сравнительные результаты расчетов времени совместной и несовместной обработки запросов мультизапроса.

4000

а 3500 -

-j 3000 -

а 2500 -

2000 -

5 1500 -

5ч 1000 -

о 500 ~

«Г 0 -

X.

к н » 7¡ r-» » н п » г*.

Ч " " " fl ^

о. а. о. CL

r-число процессоров, р- вероятность успеха |=1.2(совм) -э~а=1.2(нез)

» » Н (Ч w Ш

tiltil

Рис.3.2. Время выполнения мультизапроса при совместной и несовместной обработки запросов/n (а =1.2,0.8 > р > 0.7). СЗ Очевидно, что совместная обработка запросов мультизапроса обеспечивает меньшее время по отношению к несовместной обработке при возрастании вероятности успеха, кроме того, увеличение числа процессоров может привести не к уменьшению, а к увеличению времени выполнения мультизапроса.

Линейная зависимость времени обработки элементарных запросов Совместное выполнение запросов мультизапроса. JI3

Пусть время t¡ обработки элементарных запросов в строке таблицы соответствует линейной зависимости (JI3).

Время выполнения мультизапроса при совместном выполнении запросов: При г = 1

w,++»i-dp(d;i:;:;ti)p2ud+

Р- ^ + + + +

При г > 1

(1 + (( - 1) Д + (1 + (2г - 1>Д)р)-—(1 + ир"?) + ^—^-ис (1 ■ 1-рг 1-рг

+ (» + + гр г)рт I -—-- 1

и-1

\ (1 ~РгУ Д Р7 )

Несовместное выполнение запросов мультизапроса. ЛЗ

Время выполнения мультизапроса при несовместном вь При, г - 1

Т„=, =П— + +

При г > 1

13

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

1-Уш , .(»-Ои-р*" , , а1, д ^-¿рЬ-о*+

--^г + иД-г---+ -т-5-г;-

1-р"1 2 1 -р-> (1~р'"}г

+ „р»1 (1 + и;Д)тфг + р-ВД(г+ 1}- (1_р:,)г

1—ир"-1 + (и - 1)ри 1 - рМа + ^--Т^Г

1-рг

((1 + 0-

- Нч Н -

1 + р^ iv -г р^кг^д!-^ i

\i-p-'/

- 1)4) + (1 + (2г - О д)р) (

\1_Р'Г/ ч- ■

Сравнение совместной и несовместной обработки запросов. ЛЗ

Рассмотрим два случая. При г = 1, <2 = 1 имеем:

Т^..^, ^ = 1) = + + р-г(1 + + (г + г>р») рД

т«^ V = 1) = ((1 + ™д) + Ри (г + цАг'(г~1)^ + (1 + гр-)

Тогда,

= 1) -т„„,г=1(а = 1)

+

г - кр*-1 + (к - Ир* ,

--(Г^5-(г'_1)

+ ри(иД)

Легко показать, что если V > 2, то

тл,несов,г=10^ = 1) — ТЛС0В;Г=1(^ = 1)

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

1) Пусть значение вероятности р -> 0.

Тогда при г > 1 имеем:

Тл,несов.г>1,; = V + (/ - 1)А + цД ^ ~2 + + (2г - /)Д + иД (г7 ~ ^ + о(р)

Тл.сов.г>1,; = (1 + 0' - 1)Д + ииД) + р( 1 + (2г - у)Д + ииД) + о(р)

При V > 2 всегда совместная обработка запросов требует меньше времени, чем

несовместная.

При V — 2 имеем:

7"несову = 2 (1 + 0' - 1)Д + и^д) + 2р (1 + (2г - ;)д + иД + о(р) ^сову = 1 + 0' - 1)Д + 2иД + р(1 + (2г - ;)Д + 2иД) + о(р),у = 2^,

Тл,несов,г>1,; ~ Тл_сОВ,г>1,7 = 1 + 0' ~ 1)Д ~ иД + р(1 + (2Г - _/')Д) - риД + о(р),

Следовательно, совместная обработка запросов требует меньше времени, чем несовместная, когда и < У - 1 + 1/Д.

В диссертации представлены сравнительные результаты расчетов времени совместной и несовместной обработки запросов мультизапроса.

Совместная обработка запросов мультизапроса обеспечивает всегда меньшее время по отношению к несовместной обработке при й = 1, но при (I > 1 это не всегда, кроме того, увеличение числа процессоров может привести не к уменьшению, а к увеличению времени выполнения мультизапроса. В четвертой главе будем считать, что реализация плана выполнения мультизапроса осуществляется в многопроцессорной базе данных.

Не умоляя общих выводов, далее проведем исследование для неупорядоченных таблиц.

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

Пусть мультизапрос состоит из пяти со сложной структурой запросов, образованных 24-мя элементарными запросами, см. Рис. 4.1:

• зх=эз1&эз2& эз3 & эз4 & ЭЗ- & эз6 & эз7 & эз8& эз, &эз10&эзи& зз12 & эз13 & эз.

& Э315&Э316& Э317 & Э3|2 Э319 & ЭЗ^л&ЭЗл^ ЭЗ22 & & эз,4

• з2 = эзг & эзг & эз3 & эз4 & эз5 & эз10& эзп & эз1:&ЭЗ 17 & Э313 &Э315 & эз:о

• З3 = ЭЗ3 & ЭЗ, & ЭЗ- & Э36& ЭЗИ & ЭЗ12& эз13 &эзк& эз,» & эз20&эз21 & ЭЗ22

• = 33- & Э36 & Э37 & ЭЗ3 & 33^5 & Э314& Э315 & Э316& Э3:1 & Э322&Э323 & эзм

• 35 = ЭЗ1 & Э32 & зз3 & Э37 & Э38 & Э35& эз13 & Э314& Э315 & Э315 &Э320 & ЭЗЛ

эзл

рз3

№

ЭЗ?

I I

Рис. 4.1. Мультизапрос, состоящий из пяти запросов.

Время выполнения конъюнктивного мультизапроса при независимой обработке равно сумме времен обработки запросов 31( 32, З3,34и 35.

Пусть мультизапрос образует конъюнкции элементарных запросов:

• со степенным изменением параметра времени выполнения элементарных запросов по правилу Г; = а1-1 и со значением параметра вероятности р£ = р, £ е 1,... и

• с линейным изменением параметра времени по правилу Т] = 1+0-1)Д и со значением параметра вероятности р£ = р, £ £ 1, ....

Совместная обработка запросов мультизапроса

Обработка элементарных запросов мультизапроса может быть выполнена, используя 3 возможных алгоритма. Алгоритм I

В алгоритме запрос 1,2 и 4 образуют опорные запросы, элементарные запросы которого образуют общее подмножество и выполняются первыми. Запрос 2 и 3 образуют опорные запросы, элементарные запросы Э33,Э313,Э314, Э319, Э320, Э321 которого образуют общее подмножество и выполняются первыми.

Шаг 1: Выделяем элементарный запрос ЭЗ! на основе П Зщ=-щ = ЭЗ!

Шаг 2: Выделяем элементарный запрос 332 на основе П 3£(£= ^гДСЭЗ! ) = Э32 Шаг 3: Выделяем элементарный запрос Э33 на основе П З^-щ^ЭЗ! &Э32) = Э33

Шаг 4: Выделяем элементарный запрос Э34 на основе

пз{(,=1^\0з1&эз2&эз3)= Э34

Шаг 5: Выделяем элементарный запрос Э39 на основе

П 3£(£=Х2)\(Э31&332& Э33&Э34) = 339

Шаг 6: Выделяем элементарный запрос Э310 на основе

п 3£(,=^2)\СЭ31&Э32&ЭЗз&Э34&Э39) = Э310

Шаг 7: Выделяем элементарный запрос Э31:1 на основе

п 3£(£=тд\(Э31&Э32& Э33&Э34& Э39&3310) = ЭЗц

Шаг 8: Выделяем элементарный запрос Э312 на основе

п 3£(г=1^)\(Э31&332& Э33&Э34& ЭЗд&ЭЗю&ЭЗц) = Э312

Шаг 9: Выделяем элементарный запрос Э317 на основе

пз£(£=1д\(эз1&эз2&эз3&эз4&эз9&эз10&эз11&эз12) = Э317

Шаг 10: Выделяем элементарный запрос Э318 на основе п 3£(£=1^)\СЭ31&Э32& Э33&Э34& Э39&Э310&Э311& Э312&Э317) = Э318 Шаг 11: Вьщеляем элементарный запрос Э319 на основе

п з£(£=1^\(эз1&эз2& эз3&эз4& Э39&ЭЗЮ&ЭЗЦ& зз12&эз17& эз18) = эз19

Шаг 12: Выделяем элементарный запрос Э320 на основе П 3£(£=1^)\(Э31&Э32& Э33&Э34& Э39&Э310&3311& 3312&Э317&Э318) = 3320 Шаг 13: Вьщеляем элементарный запрос Э35 на основе П З^-щ = Э35 Шаг 14: Выделяем элементарный запрос Э36 на основе П 3£(£=щ\(Э35 ) = Э36 Шаг 15: Выделяем элементарный запрос Э37 на основе ЛЗ£(£=Тд)\035&Э36) = Э37

Шаг 16: Выделяем элементарный запрос Э38 на основе

П 3£(£=Щ\(Э35 & Э36& 337) = Э38

Шаг 17: Выделяем элементарный запрос Э313 на основе

П 3£(£=щ\(335 & Э36& Э37&Э38) = Э313

Шаг 18: Выделяем элементарный запрос Э314 на основе

ПЗ£(£=м)\(Э35&Э36&Э37&Э38&Э313) = эз14

Шаг 18: Вьщеляем элементарный запрос Э315 на основе Л 3£(£=щ\(Э35 & Э36& Э37&Э38& Э313&Э314) = Э315 Шаг 20: Выделяем элементарный запрос Э316 на основе П 3£(£=1д)\(Э35 & Э36& Э37&338& Э313&Э314&Э315) = Э316 Шаг 21: Вьщеляем элементарный запрос Э321 на основе

пз£(£=1д)\(эз5&эз6&эз7&эз8&эз13&эз14&эз15&эз1б) = Э321

Шаг 22: Вьщеляем элементарный запрос Э322 на основе Л 3£(-£=щ\(Э35 & Э36& Э37&Э38& 3313&Э314&Э315& 3316&3321) = Э322

Шаг 23: Выделяем элементарный запрос Э323 на основе

пзг(г=1д\(эз5&эз6&эз7&эз8&эз13&эз14&эз15&эз16&эз21&эз22) = Э323

Шаг 24: Выделяем элементарный запрос Э324 на основе

П 3;(г=щ\(Э35 & Э36& эз7&эза& эз13&эз14&эз15& Э316&Э321& Э322&Э323) = эз24

Шаг 25: Выделяем элементарный запрос Э33 на основе П = Э33

Шаг 26: Выделяем элементарный запрос Э313 на основе П Згу=3^)\(Э33 ) = Э313

Шаг 27: Выделяем элементарный запрос Э314 на основе

п Зг(1=3^)\(Э33 & Э313 ) = Э314

Шаг 28: Выделяем элементарный запрос Э319 на основе

п 31(г=3^)\(Э33 &Э313&Э314) = Э319

Шаг 29: Выделяем элементарный запрос Э320 на основе

п 3;((=3^)\(Э33 &Э313&Э314&Э319) = Э320

Шаг 30: Выделяем элементарный запрос Э321 на основе

П 31(£=з^\СЭ33 &эз13&эз14&эз19&эз20) = Э321

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

Граф обработки запросов по алгоритму 1 приведен на рис. 4.2.

ЭЗу

4» *

*

э3<>

эз. ЭЗ,

V +

Ч6 эз2

*

33 7 ЭЗ.

+

ЭЗ О ЭЗ,

**

эз9

1 1

1 4-

X з?!

*

эзм

i

X

эз» X

4-

,эз21 ЭЗ 15

/ "-

\

\

т

э?

\ Т

Г

ЭЗ,

э? ?

Рис. 4.2. Граф обработки запросов по алгоритму 1.

Минимальное время выполнения мультизапроса при степенном изменении параметра времени

Оптимальное время выполнения мультизапроса при степенном изменении параметра времени для г процессоров определяются в диссертации, в частности, для трех процессоров при распределении запросов по процессорам в соответствии с Таблицей_

Число процессоров Порядок обработки ЭЗ

1 1,2,3,4,9,10,11,12,17,18,19,20

2 5,6,7,8,13,14,15,16,21,22,23,24

3 3,13,14,19,20,21,4,5,6,11,12,22,1,2,7,8,9,15

= "(с2 +Р°12 + рга13 + р3а1е + р4а" + р5аг0 +р'а10 +р15а11 +р"а"

+ р6 + р7а + рЕа5 + р'а7 +р1!!й6 + р11о")

С учетом завершения работы трех процессоров время выполнения мультизапроса равно максимальному времени для этих процессоров: Тст,совм,з ~~ п. (шах(Тст совиД З .ТСТ1С0ВИ|2,3,ТСТ,С0ВМ,3,3))-

Минимальное время выполнения мультизапроса при линейном изменении параметра времени

Оптимальное время выполнения мультизапроса при линейном изменении параметра времени для г определяются в диссертации, в частности, для трех процессоров при распределении запросов по процессорам в соответствии с Таблицей

Число процессоров Порядок обработки ЭЗ

1 1,2,3,4,9,10,11,12,17,18,19,20

2 5,6,7,8,13,14,15,16,21,22,23,24

3 3,13,14,19,20,21,4,5,6,11,12,22,1,2,7,8,9,15

= п0 + рС1 + Д) + р2(1 + д2) + р3( 1 + ДЗ) + р4( 1 + Д8)

+ р5( 1 + Д9) + р6( 1 + Д10) + р7( 1 + Д11) + р8( 1 + Д16) + р9( 1 + Д17) + р10(1 + Д18) + р"( 1 + Д19)) Тл'сОВи,2.з = «((1 + Д4) + р( 1 + Д5) + р2(1 + Д6) + р3(1 + Д7) + р4(1 + Д12) + р5(1 + Д13) + р6( 1 + Д14) + р7(1 + Д15) + р8( 1 + Д20) + р9(1 + Д21) + р10(1 + Д22) + рп(1 + Д23))

Т^.мдз = "(О- + д2) + РС1 + Д12) + Р2( 1 + Д13) + р3( 1 + Д18)

+ р4(1 + Д19) + р5(1 + Д20) + рб(1 + ДЗ) + р7(1 + Д4) + р8( 1 + Д5) + р9(1 + Д10) + р10(1 + ДИ) + Р1Х(1 + Д21) + рб + р7( 1 + Д) + р8(1 + Д6) + р9(1 + Д7) + р10( 1 + Д8) + р11(1+Д14))

С учетом завершения работы трех процессоров время выполнения мультизапроса равно максимальному времени для этих процессоров:

Тл^совм.З = п (тах( Тл!совмД,3 1 ^л,совм,2,3' ^л.сови.з.з))

Алгоритм 2

В алгоритме 2, запросы 1, 2 и 3 образуют опорные запросы, элементарные запросы Э33,Э34,Э311,Э3121Э319,Э320 которых образуют общее подмножество и выполняются первыми. Запрос 4 и 5 образуют опорные запросы, элементарные запросы Э37, Э38, Э313, Э314, Э315, Э321 которыхобразуют общее подмножество и выполняются первыми.

Алгоритм 3

В алгоритме 3, запросы 2,3 и 5 образуют опорные запросы, элементарные запросы Э33, Э319, Э320 которых образуют общее подмножество и выполняются первыми. Запрос 1 и 4 образуют опорные запросы, элементарные запросы Э35, Э36, Э37, Э38, Э313, Э314, Э315, Э316, Э321, Э322, Э323, Э324 которых образуют общее подмножество и выполняются первыми.

Формирование оптимального плана выполнения мультизапроса при степенном изменении параметра времени

В диссертации и таблицах 4.3 и 4.4 приведены минимальные времена выполнения мультизапроса при совместном и несовместном выполнении образующих его запросов при степенном и линейном изменениях параметра времени для алгоритмов 1, 2 и 3 для г процессоров.

Таблица 4.3

р г К=24

а=1.1

1 ст.совм гр а2 1 ст.совм Таз 1 ст.совм Т 'ст.несови

0.4 1 5.34538 6.0291 7.5722 9.7590 1 ст.совм

2 4.25837 3.4629 4.9101 5.4431 1 ст.совм

3 3.61718 3.45479 5.7207 4.1541 гра2 1 ст.совм

4 3.6070 3.5504 5.7207 3.3520 т Аст.несовм

0.5 1 7.15334 8.0586 10.1379 12.0486 Та1 1 ст.совм

2 5.25824 4.5297 6.7324 6.7021 Т«а2 1 ст.совм

3 5.01863 4.48819 6.8634 5.1104 грЭ2 1 ст.совм

4 4.9686 5.0273 6.8634 4.1200 т 1 ст.несовм

0.6 1 10.0551 11.5634 14.2044 16.0049 Та1 1 ст,совм

2 7.20652 6.3466 9.4697 8.9066 Та2 А ст.совм

3 7.20652 6.17144 8.3802 6.7886 грЭ 2 1 ст.сови

4 7.0062 7.2839 8.3802 5.4708 т 1 ст.несовм

0.7 1 15.1211 18.2678 21.4017 23.6827 Та1 1 ст.совм

2 10.8309 9.7939 13.9863 13.1891 грЭ2 1 ст.сови

3 10.8309 9.15141 10.5715 10.0526 Та2 1 ст.сови

4 10.1293 10.6360 10.5715 8.1011 т 1 ст.несови

0.8 1 25.0494 32.7634 35.7316 40.2614 Та1 1 ст,совм

2 17.3258 17.0313 22.1869 22.0741 *Га2 * ст.совм

3 17.3107 15.732 14.1557 16.8294 Таз 1 ст.сови

4 15.0944 15.4833 14.1557 13.5662 т 1 ст.несовм

0.9 1 48.2132 69.1557 68.3955 80.6487 грЭ! 1 ст.совм

2 32.0877 35.9788 38.2220 40.9444 »га1 1 ст.совм

3 29.8064 35.9788 30.1735 31.2313 Та1 1 ст.сови

4 25.2942 24.8870 25.2942 25.1877 гра 2 1 ст.сови

Таблица 4.4

Р г К=24

Д=0.4

Та1 1л,совм •уа2 1 л,совм Таз 1л,совм Т 1 л.несовм

0.4 1 8.15808 10.6973 12.106 16.1353 ,ра1 1 л,сови

2 5.97696 6.53988 7.25843 8.3540 Та1 1 л.совм

3 5.96663 6.52999 9.88252 7.9178 Та1 1 л.совм

4 5.9595 6.51581 9.88252 5.6703 т 1 л.несовм

0.5 1 11.2456 14.18 16.2116 22.1801 Та1 1 л.совм

2 8.23438 8.39707 10.0037 11.5596 Та1 1 л.сови

3 8.17979 8.34307 11.5969 10.9580 г«а ! 1 л.сови

4 8.1483 8.27275 11.5969 7.8206 т 1 л.несовм

0.6 1 16.238 19.9814 22.7508 33.2437 Та1 1 л.совм

2 11.6711 11.4154 14.2163 17.4571 грЭ2 1 л.совм

3 11.4406 11.1763 13.8943 16.5505 Та2 1 л.совм

4 11.3282 11.0136 13.8943 11.7867 4 л.совм

1 25.1876 30.6837 34.306 55.3091 Та1 1 л.совм

0.7 2 17.3056 16.8481 21.3675 29.1793 Та2 1 л.совм

3 16.4742 15.9402 17.3171 27.6644 Та2 1 л.совм

4 16.1195 15.4215 17.3171 19.6927 Та2 1 л.совм

1 44.0209 53.1009 57.1404 102.8575 Tai 1 л.совм

0.8 2 27.4158 27.6947 34.7528 53.8058 1 л.совм

3 24.7617 25.4062 23.1764 51.0104 Таз 1 л.совм

4 23.7322 22.0195 23.1764 36.3398 Та2 1 л.совм

1 95.7552 107.874 108.735 213.8461 Tai 1 л.совм

0.9 2 47.123 56.9411 61.6042 106.9504 А л.совм

3 39.4506 56.9411 47.1313 101.3358 Tai 1 л.совм

4 39.2801 39.3514 39.2801 72.2773 грэг 1 л.совм

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

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

При линейном возрастании параметра времени (Д =0.4, 0,5) предпочтительной по достижению минимального времени выполнения мультизапроса является совместное выполнение мультизапроса по алгоритмам 1 и 2, однако для конкретных значений числа процессоров г и вероятности успеха р требуется выбор алгоритма 1 или алгоритма 2.

п

i

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

Доказаны условия, при которых совместная обработка конъюнктивного мультизапроса обеспечивает не большее время выполнения по отношению к независимой обработке.

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

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

Основные публикации по теме диссертации Брехов О.М., Вунна Джо Джо, Тан Хлаинг Мьинт. Оптимизация плана выполнения мульти и вложенных запросов // Журнал «Наукоёмкие технологии» 2014г. №1, с. 101-106.

Брехов О.М., Вунна Джо Джо. Оценка времени выполнения мультизапроса // Электронный журнал «Труды МАИ», 2014г. №(76).

Тираж 100 экз

Отпечатно в Московском авиационном институте (национальном исследовательском университете) г. Москва, А-80, ГСП-3, Волоколамское шоссе, д.4. http://www.mai.ru//