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

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

005549983

Тан Хлаинг Мьинт

«Оптимизация обработки вложенных запросов в многопроцессорной базе данных»

г 7

гч^

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

АВТОРЕФЕРАТ

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

Москва 2014

1 9 ИЮН 23!-}

005549983

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

Научный руководитель: доктор технических наук, профессор,

заслуженный деятель науки РФ, зав. Кафедрой 304 МАИ (НИУ) Брехов Олег Михайлович

Официальные оппоненты: доктор технических наук, доцент,

профессор кафедры «Информатика и системы управления-6», МГТУ имени Н.Э. Баумана Александр Владимирович Брешенков

кандидат технических наук, доцент с.н.с. ФГУП НИИ АРГОН Сальман Леонид Абрамович

Ведущая организация: ОАО «Научно-исследовательский институт

вычислительных комплексов (НИИВК) им. М. А.Карцева», 117437, г. Москва, ул. профсоюзная, д. 108.

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

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

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

Автореферат разослан 2014г.

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

диссертационного совета Д212.125.01

кандидат технических наук, доцент А.В.Корнеенкова

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Проблемами создания и оценки качества ООЗ занимались ряд российских и зарубежных исследователей: Григорьев Ю.А, Кузнецов С.Д, Amol Deshpsnde, Zaccharylves, VijayshankarRaman, Seiinger P.G, Astrahan M.M, Chamberlin D.D и др.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертационного исследования докладывались автором и обсуждались: на на 11-я Международная конференция МАИ «Авиация и космонавтика-2012», 13-15 ноября 2012г года МАИ, Москва, 13-я Международная конференция МАИ «Авиация и космонавтика-2013», 12-15 ноября 2013 года, Московская молодежная конференция «Инновации в авиации и космонавтике», Москва.22-24 апреля 2014года.

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, библиографического списка из 154 наименований. Работа изложена на 115 страницах, содержит 37 таблиц и 32 рисунка.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Пусть запрос представляет собой конъюнкцию элементарных запросов.В простейшем случае вложенный запрос к базе данных можно рассматривать как обращение к таблицам, содержащим множество записей (строк), характеризующихся одинаковым множеством свойств (столбцов), с целью получения множества записей, удовлетворяющих заданному условию вложенного запроса. Будем называть часть запроса, относимую к /- му свойству записи (/' - му столбцу), /' - ым элементарным запросом ЭЗЬ I = 1,к.

При выполнении вложенного запроса для каждой строки необходимо выполнить проверку условия, связанного с ЭЗг, требуемое для этого время обозначим через т; вероятность успеха выполнения условия через р*. Вариация значений времени т,- зависит от формулировки условия Э3; (точечное, интервальное или более сложное условие), а так же от технических и/или программных особенностей реализации (кэширование, диски и др.). Вариация значений вероятности выполнения условия определяется содержимым базы данных.

Основным критерием при определении плана реализации вложенного запроса является время выполнения запроса, которое, вообще говоря, зависит от порядка выполнения элементарных запросов, его составляющих, и указанных параметров элементарных запросов Э3¡ - времени проверки т,- и вероятности успеха Р( вj -ой строке I - го столбца . I = = 1,п

Время выполнения элементарного запроса зависит от метода доступа к столбцу таблицы, при этом выделяются два базовых метода, когда данные в столбцах неупорядочены и когда данные в столбцах упорядочены построчно. В первом случае время выполнения элементарного запроса Э3£ определяется временем проверки всех п строк /'-го столбца таблицы и равно п Т;. Во втором случае, например, при использовании индексной организации обращений к данным, определяется временем проверки п p¡ строк и равно п

Влияние параметров запроса на время выполнения вложенного запроса

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

Пусть запрос 3 использует множество элементарных запросов ЭЗЬ £ = 1, к, выполнение которых осуществляется в порядке, соответствующем упорядочению по значениям параметров т1. и Р(. . При этом запрос 3 образуют два запроса прямой Зп и вложенный Зв, а

именно: Зпр = ЭЗХ& Э33&... & ЭЗ^й ЭЗМ,

Звл = Э32&Э34&... &ЭЗЙ, т.е. в прямом запросе используются элементарные запросы с нечетными номерами, а во вложенном запросе - с четными номерами.

Выполнение вложенных запросов может осуществляться разными вариантами. Мы рассмотрим три варианта:

1. Первыми выполняются элементарные запросы прямого запроса, затем элементарные запросы вложенного запроса;

2. Первыми выполняются элементарные запросы вложенного запроса, затем элементарные запросы прямого запроса;

3. Выполнение элементарных запросов и прямого и вложенного запросов осуществляются интегрировано в соответствующем порядке[1, 2]: Э31( ЭЗ2,..., ЭЗ^ .

Оценим время 7},} — 1,3, выполнения запросов для указанного / - го варианта количественно. Пусть параметры элементарных запросов имеют вид:

Т£ = а1-1, р£ = р, I = 1, к, к - четное.Значения 7} я = 1,3, приведены при к = 12 в таблицах 1.1 и 1.2.

Таблица 1.1

а = 1.06 Вероятность р

Время 0 0.6 0.7 1.0

^ 1 2.918 4.021 1 - а*"1 —-= 16.87 1 - а

1.06 3.077 4.21 16.87

ъя 1 2.735 3.768 16.87

Таблица 1.2

,а= 1.1 Вероятность р

Время 0 0.6 0.7 1.0

ТЦ 1 3.275 4.656 1 — а1"1 -=21.384 1 -а

1.1 3.572 5.02 21.384

Тз.Е 1 2.921 4.159 21.384

Пусть параметры элементарных запросов имеют вид: т, = 1 + ДО - 1 ),Р( =рЛ = 1 ,к.

Значения Ту а ,] = 1,3, приведены при к = 12 в таблицах 1.3и1. 4.

ги- (1+а+Ф 2ра (1+р^)1^;'-:!1^"'

_1-р* , „А ^крЬ^Нк-Ур".. Тз а---г РД--Г?-Па 1-р ^ (1-р)2

Заметим, что разность Г2 а - Г1а = Д (1 —

Таблица 1.3

Вероятность р, Д = 0.08

Время 0 0.6 0.7 1.0

1 2.5436 3.3706 к + Д^у^п=12.5280

Т2,3 1 + Д = 1.08 2.5618 3.3914 к + Д^^ п=12.5280 г

Тъ* 1 2.5240 3.3441 к+д£Й112 „=12.5280 2

Таблица 1.4

Вероятность р,Д =0.17

Время 0 0.6 0.7 1.0

Т1.а 1 3.5366 5.0597 к + д!±^2п =23.2200

т2.а 1 + Д = 1.17 3.9229 5.5009 к + =23.2200 2

7-З.а 1 3.1196 4.4970 к + Ь п =23.2200

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

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

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

Таким образом, в этой главе:

Рассмотрены методы формирования вложенных запросов.

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

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

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

Распределение номеров элементарных запросов по процессорам

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

Можно воспользоваться естественным распределением элементарных запросов по процессорам в соответствии с правилом, показанным в таблице 2.1, где в /-ой строке таблицы указаны номера элементарных запросов выполняемых /-м процессором в порядке слева направо, при этом мы используем (для простоты изложения) в качестве значения числа элементарных запросов к целое четное число, и число процессоров г отвечает условию [к/г]г = к.

В этом случае /' -ый (/ =1,...,/•) процессор получает элементарные запросы с номерами /, г +/', 2г + /, Зг +/, 4/- + /, 5г +/', 6г + /, ...

Таблица 2.1. Распределение номеров элементарных запросов по процессорам

Номера процессоров Номера элементарных запросов

1 1 г+1 2г+1 Зг+1 к-г+1

2 2 /+2 2г+2 Зг+2 А-+1

3 3 г+3 2/4-3 Зг+З

» / гн / 2Н-1 3 г+ / *+ г

г г 2 г 3 г 4 г к

Известен квазиоптимальный метод оптимизации, когда распределение элементарных запросов по процессорам осуществляется в соответствии с правилом, показанным в таблице 2.2, где в /"-ой строке таблицы указаны номера элементарных запросов выполняемых /-м процессором в порядке слева направо, при этом мы так же используем в качестве значения числа элементарных запросов к целое четное число, и число процессоров г отвечает условию [к/г]г=к.

В этом случае / -ый (/ =1,...,г) процессор получает элементарные запросы с номерами /, 2г +1 - /, 2г + 1,4г +] - /'. 4г + ¡,бг + / - /, 6г + /,...

Таблица 2.2. Квазиоптимальное распределение элементарных запросов по

процессорам

Номера процессоров Номера элементарных запросов

1 1 2 г 2г+1 4 г к

2 2 2/--1 2/+2 4г-1 к-1

3 3 2г-2 2г+3 4г-2 к- 2

1 1 2г- (+1 2 г+1 4/-- /+1 к- / +1

г-1 г Л г 2 Зг-1 Зг+2 к-г+2

г г г+1 Зг Зг+1 к-г+1

Обоснование квазиоптимального порядка распределения

Для оценки влияния изменения числа процессоров на изменение времени выполнения запроса рассмотрим два закона задания функций изменения параметров времени Т; (геометрической прогрессии и арифметической прогрессии ) при двух базовых методах доступа к столбцам таблицы, когда данные в столбцах неупорядочены и упорядочены.

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

1. С изменением параметра времени по закону геометрической прогрессии Tj = а1-1, и с постоянным значением параметра вероятности pi = р, i 6 1, к.

2. С изменением параметра времени по закону арифметической прогрессии Tj = 1+(/-/)Д, и с постоянным значением параметра вероятности pt = р, i 6 1, к.

Для простоты, но, не теряя общности, формирования подмножеств элементарных запросов для г процессоров положим, что число процессоров г отвечает условию [к/г]г = к.

Арифметическая прогрессия

Пусть число процессоров вычислительной системы равно г, время выполнения элементарного запроса подчиняется закону арифметической прогрессии, Tj = 1 + A(i - 1 ),р, = p,i = 1,к.

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

Естественный порядок распределения.

Доказано, что время выполнения на /-м процессоре к/г элементарных запросов из общего числа к элементарных запросов при естественном порядке их распределения по процессорам, когда данные в столбцах неупорядочены, равно:

w = (а + а - 1)Л) ^+

Другой вид представления выражения Triae, используемый для обоснования эффективности квазиоптимального порядка распределения:

к

Tr,i.a,e = | (1 + С ~ 1)А + (1 + (Г + i - 1)Д)Р)

+ 2гДр2(1 + р) i 2r J п, 1 = 1,г.

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

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

Тг.ио = ((1 + О - 1)Д + (1 + (2Г - 0Д)р)^Е1+ 2гДр2(1 + Р) '""^¿Г рг)п, /=1,г.

Соотношения времени выполнения на /'-м и) -м процессорах

Для естественного порядка распределения элементарных запросов непосредственно из первого выражения для Тг ¡ а е имеем неравенства:

ТгД.а.е Тг,2,а,е ^ '" ^г.па.е•

Для квазиоптимального порядка распределения элементарных запросов так же выполняются аналогичные неравенства: Тгд,а,0 < Тг,2,а,а < ••• < Тг; а о < Тг^а>0 < Тг,г,а,0 < Д — 1 < ] ■

В самом деле, непосредственно из выражения для Тг | а 0 и Тг^ а 0 имеем 1 + (I - 1)Д + (1 + (2г - 0)р < 1 + 0' - 1)Д + (1 + (2г -;)Д)р, что справедливо всегда при любых /</.

Максимальный разброс времени выполнения обработки запросов на г процессорах составляет: - при естественном порядке

ТГ|Г,а.е " Тгд,а,е = (Г- 1)(1 + Р)Д П,

к \

- при квазиоптимальном порядке,Гг гл0 — Тг1а 0 = ^(г — 1)Д(1 — р) ^^ ) п.

Имея в виду, что Тг г а е < Тгд а 0, так как выполняется неравенство 1 + р(1 + гД) < 1 + р(1 4- 2 г- 1), и так же Тгг>а_0 < ТгД_ае, и так как выполняется неравенство 1 + (г — 1)Д + (1 + гД)р < 1 + (г — 1) + (1 + (2г — 1)Д)р, находим, что минимальная и максимальная границы времени выполнения при квазиоптимальном распределении лежат внутри минимальной и максимальной границ при естественном распределении.

Абсолютное уменьшение границ времени выполнения запросов при использовании оптимального распределения вместо естественного распределения равно:

6абс = - 1)Д Ц)? 12РП"

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

6„ТН =-,-5а6с . ^ 100% = 100%,

((г-1)Д(1+р)±""

что при практически часто используемом р > 0,25 составляет больше или равно 40 % и при р > 0,5 составляет > 67%.

Эффективность квазиоптимального распределения

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

Итак, время выполнения на /-м процессоре к/г элементарных запросов из общего числа к элементарных запросов при квазиоптимальном порядке их распределения по процессорам равно (здесь, как и ранее, к/г есть целое четное число)

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

1 гг, „ Л-Рк , д 1-кр'с-1+(к-1)р'с,\

- для г =1, Тг=1Да,0 = Тг=1Ла_е = рЛ— (1_р)2 ) П,

-для г=£, Гг=*|д0 = (1 + (£-1)д + р(1+£д)) (1 + р2)+^Др2(1+р)п,

- для г = £ ,Гг=ц а 0 = 1 + ~ 1) Д + р (1 + £ Д) п. -для г-к, Тг=кХа_ о = тг=к_кле = (1 + (к - 1)Д)п .

Приведем ряд численных результатов для этих формул, см. таблицу 2.3 и рис.2.1.

Таблица 2.3. Численные результаты

Л'-Проиессора А=8

Д= 0.4 Д= 0.5

Р=0.5 Р=0.6 Р=0.7 Р=0.5 Р=0.65 Р=0.7

г= 1 2.7641« 3.7984 и 5.4580 п 2.9570« 4.9705 /) 6.0372 «

г= 2 3.4750 и 4.2944 п 5.2962/1 3.8750« 5.3773 /! 5.9870/1

г =4 3.5000 п 3.7600 п 4.0200 п 4« 4.4500 п 4.6000 //

г =8 3.8000 п 4.5000 п

Отметим, что минимальное время выполнения запроса на г процессорах для вероятности успехар<0.65 обеспечивается при промежуточном (не максимальном) числе процессоров г =4.

к=8,р=[0.5М$Л Л=0.4; /с=^=[0.5:0.6;0.7]= А=0.5

-ргосе5ьог

д 1-ргосе550г 2-ргосе550г 4-ргосе$шг

Рис. 2.1. Время выполнения к/г элементарных запросов на г процессорах, арифметическая прогрессия т^

Упорядоченные столбцы таблиц

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

Геометрическая прогрессия

Пусть время выполнения элементарного запроса подчиняется закону геометрической прогрессии Т; = а1-1, а > 1,р; = р, I = 1, к.

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

Естественный порядок распределения.

Доказано, что время выполнения на /-м процессоре к/г элементарных запросов из общего числа к элементарных запросов при естественном порядке их распределения по процессорам, когда данные в столбцах неупорядочены, равно:

Можно представить Тг1д е в другом виде

Очевидно, что эти два выражения идентичны, так как а'-1 + раг+1-1=(а'_1)(1 + раг).

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

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

Доказано, что время выполнения на /Чи процессоре к/г элементарных запросов из общего числа к элементарных запросов при квазиоптимальном порядке их распределения по процессорам, когда данные в столбцах неупорядочены, равно: (для простоты записей будем считать, что к/г есть целое четное число):

Тгл„ -(а'"1 + ра-0 п.« = Г7.

Соотношения времени выполнения на /-м и ) -м процессорах

Для естественного порядка распределения элементарных запросов

непосредственно из выражений для Тг[де , £ = 1, г, г >/, имеем неравенства:

Тг,1,д,е ^ Тг,2,д,е < < Тг,г,д,е-Для квазноптимального порядка распределения элементарных запросов

на основании выражений для Тг1д>0 , I = 1,г, г >/,

при ра2 > 1 имеем неравенства: ТгЛд0 > Тг 2,д,о > > Тгг-1до > Тггдо

В самом деле, неравенство Тгг_1д0 > Тг гд „выполняется тогда и только тогда, когда аг~2 + раг+1 > а7"1 + раг или когда раг(а - 1) > аг-2(а - 1) или когда ра2 > 1. Неравенство Гг г_2,5,0 > Тг.т-1,д,о выполняется, когда раг+1(а — 1) > аг_3(а — 1) или когда ра* > 1, что выполняется при

ра2 > 1 и так далее. Наконец, неравенство Тгд &0 > Тс 2&0 выполняется, когда ра2г_2(а — 1) > а — 1 или когда ра2(г-1) > 1, что естественно выполняется при ра2 > 1. Обобщая, находим, что все исходные неравенства выполняются при ра2 > 1,что и т.д.

Максимальный разброс времени выполнения запросов здесь составляет:

тг.1,д,о - Тг.г.д.0 = (а1-1 - 1)(раг - 1)

При ра2 < 1, но при ра4 > 1, выполняется следующая цепочка неравенств: ТтХдо > Тг2до > ••• > Тгг_1до < Тггд о, при этом неравенство ТгД &0 > Тгг,&0 выполняется, если 1 + ра2г_1 > аг-1 + раг или если раг > 1 (г> 4).

п.

Напротив, неравенство Тг1до < Тггдо выполняется, если раг < 1, (г< 3). Аналогично, при ра4 < 1,ра6 > 1 имеем неравенства:

ТгЛ.д.о ^ Тг,2,д,о ^ Тг,г-2,д,о ^ Тг,т-1.д,о ^г,г,д,о >

и вообще, при ра21 < 1, ра2(1+1) >1, I = 1,г — 2, имеем:

^г,1,5,0 ^ Тг,2,д,о Тг,г~1,д,о ^ 1+1,3,0 < Тг,г,д,о ■

Наконец, при ра2(г_1^ < 1 имеем:

Тг,1,д,о ТГ 2,д,о < < Тг,г-2,д,о ^ < "" < Тг г д 0 .

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

ра2(г-1) < 1 составляет: Гг,г.5,0 - ГгД,д,0 = (а1"-1 - 1)(1 - раг) (^Е^?)

Минимальная и максимальная границы времени выполнения

Имея в виду, что выполняется Тг1де < Тг1д о, так как (1+раг)<(1+ра2г~1) или 1 < аг_1, при г > 1 и а > 1, и что выполняется Гггдо < Тггде,

так как аг-1 + раг < аг(1 + раг) или ра(аг — 1) + (а — 1) > О, находим, что минимальная и максимальная границы времени выполнения . при оптимальном распределении лежат внутри минимальной и максимальной границы при естественном распределении.

Максимальный разброс времени выполнения обработки запросов на г процессорах составляет:

- при естественном порядке

Тгю. -Тгхд*. = ^Са7""1 - 1) - (1 + раП \ ^ ) п

- при квазиоптимальном порядке

к

Тгхд.о - Тг,г,д,о = О7-1 - 1 )(раг - 1 при ра2 > 1,

к

Тг.г,д.о - Тг.1.д,о = (а1"-1 - 1)(1 - рО «.при раг < 1.

Абсолютное уменьшение границ времени выполнения запросов при использовании оптимального распределения вместо естественного распределения равно:

вабсо = - 1)(1 + раг) - (а-1 - 1)(1 - I "=

Относительное уменьшение границ времени выполнения запросов при оптимальном распределении.

<- __5абсо___ 2раг

"отно /

(1+раг)

Эффективность квазиоптимального распределения

Время выполнения на /-м процессоре к/г элементарных запросов из общего числа к элементарных запросов при квазиоптимальном порядке их распределения по процессорам равно:

Максимальное время завершения обработки к/г элементарных запросов на

всех процессорах в частных случаях равно:

, „ (1 ~(ра)к\ „

-для г=\,Т1Хд:0 = {-т:^-)п,

- для г = ^, при ра2 > 1

к --------2 ^ , Т к. __ = (!+ рак/2~1)(1 + (рак»)2п,

к , г=-л,д,о

при ра2г-2 < 1 Тт=ккё0=(а* 1 + ра4^ 1 + (ра^ п,

- для г = -, при ра2 > 1, Тг^к = (1 + рак г)л,

,2г-2

< 1,

к,

Т кк = сё (1 + ра)п,

2'2

при ра'

- для г = к, Тг=кХд1е =( ак-1)тг.

Приведем ряд численных результатов для этих формул при к=8; а=1.15, 1.2,1.25,1.3; р=0.6,0.7, см. таблицу 2.4:

Л;-Процессора к= 8

а =1.15 а =1.2

Р=0.6 Р=0.7 Р=0.6 Р=0.7

Г= 1 3.0601 71 4.2239 П 3.3135 П 4.7008 71

г =2 3.1167 71 3.8340 П 3.5573 71 4.4547 71

г=4 2.5960 71 2.8620 71 3.1499 71 3.5082 П

г=к 2.6600 71 3.5832

Л?-Г1роцессора /с=8

а =1.25 а =1.3

Р=0.6 п Р=0.7 Р=0.6 Р=0.7

;•= 1 3.5995 П 5.2511 71 3.9227 71 5.8861 П

г=2 4.0807 П 5.1990 п 4.7018 71 6.0897 П

г=4 3.8610 71 4.3379 п 4.7649 71 5.3924 П

г=к 4.7684 71 6.2749 71

Отметим, что минимальное время обработки для вероятности успеха р < 0.75 обеспечивается при промежуточном (не максимальном) числе процессоров г =4.

я £=£,и=[0.б,0.7], а=1.15; а=1.2, ¿=$¿>=[0.6,0.7]. а=1.15: а=12,

5 к=8,р=фА0.Ц а=1.25: ¿2=1.2, й=%р=[ОД0.7]= я=1.15: а=13,

5 ' ......................................................................................................................................................................................................................................................................

3 6-

Ьргосевзог 2-рГОСе55<Ж 4-рГ0Се55СГ 8-рГОСе55СГ

Рис. 2.2. Время выполнения к/г элементарных запросов на г процессорах, геометрическая прогрессия т.

Упорядоченные столбцы таблиц

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

Таким образом, в этой главе:

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

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

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

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

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

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

Утверждение 1. В многопроцессорной базе данных минимальное время выполнения вложенного запроса, для неупорядоченных данных таблиц достигается при совместной обработке / -ым (/' =1 ,...,/■) процессором объединенного множества элементарных запросов всех таблиц. При этом элементарные запросы в соответствии с квазиоптимальным методом оптимизации распределены по процессорам с номерами /', 2г +1 - /, 2г + /', 4г +1

- /, 4г + /, 6г +1 -1, 6г +/,... в соответствующем порядке.

В самом деле. Пусть titj - время обработки / -ым (/ = 1,...,г) процессором у-го элементарного запроса,у = (/, 2г +1 - /, 2г + /, 4г +1 - /, 4г + ¡, 6г +1 - /, ... , к- /+1). - вероятность успеха при обработке у-го элементарного запроса.

Время обработки элементарных запросов в порядке, заданным условием *и < ^ , где у и / - номера соседних элементарных запросов, является минимальным и определяется выражением:

+ РиСг,2г-1+1 + РиР1\2г-1-1^',2г+1' + Р1,1Р(,2г-1 + 1Р1,2г+1С1,4г-1+1 + "* + Р1,[Р1,2г-г+1Р(,2г+£ •••-Рг.к-гг+г ■■■ Утверждение 2. В многопроцессорной базе данных минимальное время выполнения вложенного запроса, для упорядоченных данных таблиц достигается при совместной обработке / -ым (/ =1,...,г) процессором объединенного множества элементарных запросов всех таблиц. При этом элементарные запросы в соответствии с квазиоптимальным методом оптимизации распределены по процессорам с номерами г, 2г + \ - /, 2г + г, Аг +1

- /', 4г + /, 6г +1 - /, 6г + /, ... в соответствующем порядке.

Время обработки элементарных запросов в порядке, заданным условием Р'.; < Ра ^ Где jи /_ номера соседних элементарных запросов, является

минимальным и определяется выражением:

Рц(?и + Р1,2г-1+11:1,2г-1+1 + Р1,2г-1+1Р1,2г+1^1,2г+1 + "'

Численные результаты

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

Геометрическая прогрессия

Несовместное выполнение вложенных запросов

Пусть заданы четыре (для простоты изложения) таблицы (Tl, Т2, ТЗ, Т4), для которых выполняются вложенные запросы, с параметрами, соответствующими геометрической прогрессии, где т£j = а/'1 - время обработки /-го ЭЗ, pij = pj, j G 1 ,kj, для таблицы Tj. Выполнение вложенных запросов может осуществляться 24 последовательными вариантами этих таблиц: Tl, Т2, ТЗ, Т4; Т1, Т2, Т4, ТЗ; Т1, ТЗ, Т2, Т4 и т.д. с сохранением внутреннего порядка элементарных запросов указанных таблиц. Время выполнения вложенных запросов, например, для варианта неупорядоченных таблиц Tl, Т2, ТЗ, Т4 для г процессорной базы данных определяется выражением:

W (а,- + РЛ-) (^Щ) + PlMa2- + Р2а2-) +

Р^Саз-1 + Рзаз2г_') + + р4а п.

i= TP,

Время выполнения вложенных запросов для упорядоченных таблиц Tl, Т2, ТЗ, Т4 при последовательном их выполнении для г процессорной базы данных определяется выражением:

Т^.з.^р.Са/- + Piai—) +

/

PikiP2k2P3k3P4(a4i-1+P4a42r_i) пл=т~р

Для числовых значений таблиц Tl, Т2, ТЗ, Т4, заданных в таблице 3.1.-3.2 , время выполнения вложенных запросов при г =1 приведено в таблице.

Таблица 3.1

k=8

Ti Pj ai

Tl 0.82 1.15

T2 0.82 1.2

T3 0.838 1.25

T4 0.838 1.3

Таблица 3.2

Варианты Время вариантов

T1,T2,T3,T4 8.6274n

T2,T1,T3,T4 9.4171 n

T1,T3,T2,T4 8.9361 n

T3,T2,T1,T4 11.2358«

T1,T4, T2,T3 9.2354 n

T4,T1,T2, T3 12.7606 n

Ясно,что при < а2 < а3 < а4, минимальное время выполнения вложенных запросов достигается при обработке таблиц Tj в порядке Tl, Т2, ТЗ, Т4 (время Т1>2,з.4 =8.6274 п).

Аналогичный порядок выполнения таблиц сохранятся и для г > 1 процессоров.

Совместное выполнение вложенных запросов

При совместном выполнении вложенного запроса для неупорядоченных Таблиц Т.1-Т.4 необходимо провести переупорядочение порядка выполнения

элементарных запросов с тем, что бы обеспечить выполнение неравенств:

Г-1 Т? Toi То 2

—-—<—-—< ••■ <———<———

1-Pt 1 -р2 1 - Р31 1 - Р32

На основе этих неравенств определен соответствующий порядок выполнения элементарных запросов Таблиц T. 1-Т.4.

Арифметическая прогрессия

Несовместное выполнение вложенных запросов

Пусть заданы четыре таблицы (Т5, Т6, Т7, Т8), образующие вложенные запросы, с параметрами, соответствующими арифметической прогрессии, где Tjj — 1 + (i — 1)Д - время обработки i-ro ЭЗ, pitj = pjt j 6 1, kj, для таблицы Tj. Время выполнения вложенных запросов для неупорядоченных таблиц Т5, Тб, Т7, Т8 для г процессорной базы данных определяется выражением:

(ki\ / uj ill—2 (к 1 \

i^j+2гл1р12(1+Pl) (^гн +

/ к2\ / fc2 ^--2 (kl \ —\ Pifcl(l + (i - 1)Д2 + d + (2 Г - ОД z)P2) (т^г) + 2rA2p/a + p2) +

pifc'p2k2(l + (i - 1)Д, + (1 + (2r - 0Д,)Рз) (^g) + 2гДзРз2(1 + Рз) +

Р1к1Р2к2Рзкза + а - 1)л4 + (1 + (2г - од«)?«)

2гл4Р42(1+р4) (). п. £=и.

Время выполнения вложенных запросов для упорядоченных таблиц Т5, Т6, Т7, Т8 для г процессорной базы данных определяется выражением:

я 1г

~Р1г)2

Тим-=РхС1 + (« - 1)^1 + (1 + С2г - ОМл) + 2гД1р12(1 + Р1) (1 Ч"-^'

/ ы\

Р^РгО- + (I - 1)Д2 + (1 + (2 г - ОД2)р2)

+2гд2Р2Ч1+Р2) ( 2г (1_р;:;2 1 )+ /

р/'Р^РзС! + 0 - 1)Дэ + (1 + (2г - 0Дз)Рз) ' 1 ~ ?3

1~Рз2 /

+ 2гД3р32(1 + р3) | 2г (1_р;г2}г2 ;

р1к1р2к2р3к1р< I (1 + а - 1)д4 + (1 + (2г - ОД4)р4) '1 Р4'

1-Р42

Совместное выполнение вложенного запроса

При совместном выполнении вложенного запроса для неупорядоченных Таблиц Т.5-Т.8 необходимо провести переупорядочение порядка выполнения элементарных запросов.

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

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

Число процессоров г ¿=32

рг = 0.82, р2 = 0.838; а1=Д.15,а2 = 1.2,а3 = 1.25,а4=1.3; Дх= 0.4, Д2= 0.5, Д3= 0.6, Д4= 0.7

несовместное совместное

неупорядоченные упорядоченные неупорядоченные упорядоченные

арифм геомет арифм геомет арифм геомет арифм геомет

1 9.6262 10.2142 9.4470 7.0836 7.9772 9.2644 6.9152 5.7856

2 11.0238 9.8301 10.7776 8.1025 10.4126 8.3110 9.1547 7.0642

4 10.4727 10.0750 10.0994 8.3380 10.9213 8.7474 9.3553 6.9707

8 7.8943 8.1463 7.1952 6.7557 8.7303 7.5034 7.1184 6.1360

16 5.2022 6.1454 4.8742 5.1318 5.8380 6.1454 4.8742 5.1318

32 5.9 6.27 4.9442 5.2542 5.9 6.27 4.9442 5.2542

1-ргосе55ог 2-ргосе5ьог 4-ргосе8$ог В-ргосеввог Н-ргосезгаг 32-ргосеззаг

-Ф-К=32,р_1=0.82,р_2=0.338,Л_1=0.4,Л_2=0,5,й_В=0.6,й_4=0.7 Н»~К=32,р_1=0.82,р_20.838,з_1= 1.15,3_2=1.2,а_3=1.25.а_4=1.4

Рис. 3.1. Сравнительное время выполнения, несовместный порядок обработки

Х-ргосевгог 2-ргоее5вог 4-ргосеззог 8-ргосе88ог 1 б-ргосеззог 32-рг0се880г

—«~к;=ЗД,р_1=О.82,р_2=0.В38,Л_1=О.4,й_2=О.5,Д_3=С.6,г!_4=О.7 ™»™К=32,р_1=0.82,р_2=0.838,а_1= 1.15.о_2=1.2.л_3=1.25,з_4=1.4

Рис. 3.2. Сравнительное время выполнения, совместный порядок обработки

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

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

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

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

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

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

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

Основные публикации по теме диссертации

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

2. Брехов О.М. , Тан Хлаинг Мьинт. Обоснование квазиоптимального порядка распределения элементарных запросов в многопроцессорной базе данных // Электронный журнал «Труды МАИ», 2014, № 74.

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

4. Тан Хлаинг Мьинт. Оптимизация обработка вложенных запросов в однопроцессорной базе данных.//11-я Международная конференция «АВИАЦИЯ и КОСМОНАВТИКА-2012». 13-15 ноября 2012года. Москва, МАИ. Тезисы докладов, с 325- 326.

5. Тан Хлаинг Мьинт. Оптимизация обработка вложенных запросов в многопроцессорной базе данных.//12-я Международная конференция «АВИАЦИЯ и КОСМОНАВТИКА-2013». 12-15 ноября 2013года. Москва, МАИ. Тезисы докладов, с 515- 516.

6. Тан Хлаинг Мьинт. Выполнение запросов при квазиоптимальном порядке распределения элементарных запросов.// Московская молодежная конференция «Инновации в авиации и космонавтике». 2224 апреля 2014года. Москва, МАИ. Тезисы докладов, с 182- 183.

ч

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