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

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

Мьо Тант

«УПРАВЛЕНИЕ ПРОИЗВОДИТЕЛЬНОСТЬЮ ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ ПРИ ОБРАБОТКЕ ЗАПРОСОВ

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

АВТОРЕФЕРАТ

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

г * янв 701з

Москва 2012

005048566

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

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

Брехов Олег Михайлович

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

доктор технических наук, профессор Ильин Валерий Николаевич кандидат технических наук, доцент Сальман Леонид Абрамович

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

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

Защита состоится <£g> января 2013г. в I/ часов на заседании диссертационного совета Д212.125.01 при московском авиационном институте (национальном исследовательском университете) - МАИ по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д.4.

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

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

Автореферат разослан » 19 2012г.

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

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

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

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

Проблемами создания и оценки качества 003 занимались ряд российских и зарубежных исследователей: Григорьев Ю.А, Кузнецов С.Д, АтоШезЬрапёе, 2ассЬагу1уез, УцауБЬапкагКатап, БеИ^егР.С, АвЬ-аЬапМ.М, СИатЬегИпО-Б и др.

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

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

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

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

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

Методы исследования. Аналитическое и имитационное моделирование. Эксперименты с СУБД. Научная новизна

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения, библиографического списка из 142 наименований и одно приложение. Работа изложена на 127 страницах, содержит 23 таблиц и 34 рисунка.

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

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

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

80 8 70

3 бо

2 50 40 30

« С.

а

л...

|1ППППП^

20 10 0

Выполнение плана

— • без оптимизации

• оптимизации

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

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

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

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

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

Основным критерием при определении Плана реализации запроса является время выполнения запроса, которое, вообще говоря, зависит от порядка выполнения элементарных запросов, его составляющих, и указанных параметров элементарных запросов ЭЗ; - времени проверки в строке тг и вероятности успеха в строке рь

Время выполнения элементарного запроса зависит от метода доступа к столбцу таблицы. Мы рассмотрим два базовых метода, когда данные в столбцах неупорядочены и когда данные в столбцах упорядочены построчно. В первом случае время выполнения элементарного запроса ЭЗг определяется временем проверки всех г строк ьго столбца таблицы и равно г Т;. Во втором случае, например, при использовании индексной организации обращений к данным, определяется временем проверки г р^трок и равно г

Время выполнения запроса определяется Теоремами 1 и 2.

Теорема 1. Минимальное время Гт|пуп обработки запроса для упорядоченных столбцов таблицы, состоящего из к конъюнкций элементарных запросов (ЭЗ), достигается при выполнении элементарных запросов в порядке 1,2,...,,к, который обусловлен выполнением условия:

Р; тг „ Рг+1 тг+1

<? . 1 = 1,к-1,

1 - VI 1 - Р1+1' при этом минимальное время

Тгшпуп = Т1 П}=1 РУ'

где

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

тг время обработки ¡-го ЭЗ для одной строки таблицы,

Pi - вероятность успеха (данные отвечают заданному условию) при обработке 1-го ЭЗ для одной строки таблицы. Доказательство проведем по индукции. 1. Пусть к =2.

При обработке элементарных запросов в порядке 1, 2 получаем, что при обработке 1-го ЭЗ потратим время т± (пр±), при этом остается пр! строк, отвечающих требованию 1-го ЭЗ. При обработке 2-го ЭЗ потратим время т2(пр1р2). Суммарное время обработки запроса равно Тг = пСр^ + Р1Р2Т2)-Аналогично, суммарное время при обработке элементарных запросов в порядке

2 и 1 равно Т2 = п(р2т2 + Р^г^х)- 1

Очевидно, что < Т2 при обработке запросов в порядке 1,2, когда

выполняется условие < при этом имеем минимальное время Тт1п = ' 1-р1 1~р2 |

П(р1Т1 + Р!Р2Т2).

2. Пусть к=3. ;

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

Таблица 1

Номер последовательности Последовательность Время выполнения

1 123 Тг = п(р1т1 + р!р2т2 + Р1Р2Р3Т3)

2 132 Т2 = п(р1т1 + РгРзЪ + Р1Р2Р3Т2)

3 2 1 3 Т3 = п(р2т2 + РгРг*! + Р1Р2Р3Т3)

4 23 1 Т4 = п(р2т2 + Р2Р3Т3 + Р1Р2Р3Т1)

5 3 1 2 Т5 = п(р3т3 + РхРзт1 + Р1Р2Р3Т2)

6 32 1 Т6 = п(р3т3 + р2р3т2 + Р1Р2Р3Т1)

Из сравнения последовательностей 1 и 2 следует, что время выполнения Т1меньше времени выполнения Т2 тогда и только тогда, когда выполняется

условие Р2*2 Рз*з 1-р2 1-рз" Аналогично,

„ Р1Т1 . р3Т3

Т, < Т4 тогда и только тогда, когда —— < -—,

л ** 1—р1 1—Рз

„, Р1Т1 , Р2*2

Те < Тй тогда и только тогда, когда —— < ——.

э а 1—Р1 1—Р2

Кроме этого, для последовательностей 1,3 и последовательностей 2,5 имеем:

„ Р1Т1 - Р2Т2

Т-, < Т3 тогда и только тогда, когда —— < ——.

1 о 1—р1 р2

Т7 < Т5 тогда и только тогда, когда —— < ——-.

^ => 1—Р1 1—Рз

Следовательно, минимальное время Тг = min (Т\) = nfaтх -I- PiP2T2 +

Pl*l ^ Р2*2 ^ РЗтЗ

Р1Р2Р3Т3) тогда и только тогда, когда — < — < —.

3. Пусть теорема 1 справедлива для случая, когда запрос состоит из (к-1)-го элементарных запросов, для которых заданы параметры: п,т£ = 1, k,pL = 1, к.

4. Докажем, что теорема справедлива для запроса из к элементарных запросов.

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

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

через Тг_

Среди (к-1)! последовательностей, начинающихся с элементарного запроса 1, минимальное время обработки запроса определяется последовательностью с номером 1, для которой.

Г1= nplTl + Pin (Ef=2 тг П}=2 Р;), т.к. для элементарных запросов i, i=2, к, выполняется предположение пункта 3 (n=k-l) при выполнении условия

^_<B±lI1±x ,i=2l(fc-l), 1 -Pi i-Pt+i

т.е. минимальное время Гг = min(Tj), i = 1, (fc — 1)!.

Среди (к-1)! последовательностей, начинающихся со Э32, минимальное время обработки запроса достигается для последовательности с номером (1+(к-1)!), т.е. минимальное время Ti+Ck-I)! = minle(l+(k-l)!,2(k-l)!) Ti , при выполнении условия

PlTl Р3Т3 < Р4Т4 < ... < Pfeife 1-Р! I-Рз 1-Р4 1 -Рк

Аналогично, среди (к-1)!-ой последовательностей, начинающихся с 1-ого ЭЗ, имеем минимальное время: 7l+a-l)(k-l)! = Ш1Пге(1+0-1)к-1и(к-1)!)^1. при выполнении условия Р 1*1 <-...< Pi-1 Ti-1 < Pi+lTi+l < ... < PfcTfc

1-P1 _IJPi-1 1-Pi+1 I-Pfc'

где i =2, к — 1.

Наконец, для последовательностей, начинающихся с ЭЗк, имеем минимальное время:

Tl+Cfc-DCfc-l)! = minle(l+(k-l)k-l!.k!) Tl> при выполнении условия £ilL<Ei±iIi±lii = i,fc-2.

1 -р£ i-Pi+i

Таким образом, минимальное время обработки запросов последовательностей, начинающихся с ЭЗ,, достигается при выполнении соответствующих неравенств для последовательностей элементарных запросов с номерами (1+а-1)(к-1)!, 1=1, к, т.е. эти к последовательностей являются доминантными для (к-1)! своих (с первыми номерами ЭЗ,) последовательностей.

В свою очередь, соответствующие (к-1) последовательности с номерами (1+(1-2)(к-2)' 1=2, к, из группы последовательностей, начинающихся с Э31? являются доминантными для выше указанных последовательностей с номерами (1+(1-1)(к-1)!, 1=2, к, при выполнении соответствующих неравенств.

В самом деле, время выполнения последовательностей с номерами 1 и (1+(к-1)! равны соответственно:

Тг = пСрл + р1р2т2 + £?=з Ч П;=1 Р;).

Тц-Ск-1)' = п(р2т2 + Р1Р2Т1 +£?= зЪ П}=1 Р;)> Из сравнения этих выражений следует, что Т1< Т1+(к-1)! выполняется тогда и только тогда, когда выполняется условие

Р1Т1 ^ Р2Т2

1-Р1 1-Р2'

и для последовательностей 1+Кк-2)! и (1+0+1)(к-1)!, ¡=0, к- 2, Т1+«к-2)! <Т1+а+1)(к-1)!

выполняется тогда и только тогда, когда выполняется условие 1-Р1 1 -Р]

Следовательно, минимальное время

= шт(Г,)д = 1ЛТ выполняется тогда и только тогда, когда выполняется условие

Р1Ч К Р1+1Ч+1 1 =

1-Р1 1-Р;+1

при этом минимальное время имеет вид: Тщтну = т1 = "Й=1ТгП;=1Ру>

ЧТО И Т. д. ел

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

Теорема2. Минимальное время Тттну обработки запроса для

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

элементарных запросов (ЭЗ), достигается при выполнении элементарных

запросов в порядке 1,2,....,к,:

Т1 . т£+1

1 - р; 1 - Р;+]

при этом

Тт |„ „у = П( тг +11=2 Ч Пу=1 РД

где

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

1 = 1,к-1,

тг время обработки ьго ЭЗ для одной строки таблицы,

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

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

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

Следствие 1. Условия порядка обработки:-^- < т'+1 и < ~'+1 т'+1, £ =

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

Доказательство следует на основе двух частных примеров:

1. Для значений к = 2, 0.8, тг = 1 и р2=0.6, т2 = 2.2 получаем различный оптимальный порядок выполнения.

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

запросов имеет вид 1,2, т.к. —— = 5, что меньше, чем —= 5.5

1-Р1 1-Р2

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

запросов имеет вид 2,1, т. к. = 4, что больше, чем = 3.3.

1-Р1 1-Р2

2. Для значений к — 2, р^О.8, = 1.5 и р2= 0.6, т2 -- 2.2 получаем одинаковый оптимальный порядок выполнения.

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

запросов имеет вид 2,1, т.к. = 7.5, что больше, чем —^— = 5.5, аналогичный

1 -р£ 1-Р2

порядок сохраняется для упорядоченной таблицы, т.к. £1^1= 6, что больше, чем = 3.3.

1-Р1 1-р2

Следствие 2. Минимальное время 7*т}Пуп обработки запроса, состоящего из к конъюнкций элементарных запросов, достигается при использовании таблиц с упорядоченными столбцами при выполнении элементарных запросов в порядке

1,2,.....к, в соответствии с условием:

Р1 Т1 _ Р/+1 т£+1

< 7 , Ь-I, к -1,

1 -VI 1 — Рг+1' при этом

^гшпуп = п £¡=1 П}=1Ру-Доказательство следует при сохранении порядка выполнения элементарных запросов для неупорядоченных и упорядоченных столбцов таблицы непосредственно из сравнения выражений для минимального времени обработки запроса. При не сохранении порядка выполнения элементарных запросов для неупорядоченных и упорядоченных столбцов таблицы требуется

дополнительное доказательство, которое, например, для к = 2имеет следующий

вид.

Пусть

_Е1_ < Р2 т2 ^ Р1 Т1

1-Р1 1-Р2* 1-Р2 1-Р1 ' Тогда

Р1 „ Т2 „ Т! Откуда р!>р2.

Отсюда следует справедливость неравенствап(р1т2 + р1р2т1) < п(т1 + р1т2), т.к. О < тх (1 — ргр2) +т2( - р2),т. е. справедливость Следствия 2 .

Эффективность метода оптимизации Эффективность предложенного метода оптимизации продемонстрируем на простом примере. Пусть запрос образуют конъюнкции к элементарных запросов с параметрами ^ = а1-1, p¡ = р, 1 е 1,к.

Минимальное время выполнения запроса для неупорядоченной таблицы в соответствии с теоремой 2 равно

Тт,„ = п- У (ар)' = п-1~(ар)'С.

/—| 1 — ар

¡ео,к-1

При выполнении обработки элементарных запросов в обратном порядке, находим:

Тобр = п(ак-1 + р ■ ак~2 + ... + рк~2 ■ а + р1*"1 ■ 1) = = пак_1 У (р/аУ = пак-11" (р/а)к.

Поэтому для упорядоченной и неупорядоченной таблиц при изменении параметра времен т1 — а1-1и постоянного значения параметра вероятности Р1 = р, I 6 1, к, и эффективность оптимального порядка обработки элементарных запросов лучше в С раз по отношению к обратному порядку обработки элементарных запросов:

к-! 1-(р/а)к

т _ а -

„ _ 'обр __1-р/а

1-ар

Тогда, прик=12, а=1.1 ир=0.7 получаем:

1-ГП77112 1— (—I12

Тт|„ == п ■ = 4.16П, То6р = п ■ 1.111--Щ- = 7,81п, С = 1,88.

1 и

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

Для оценки влияния изменения значений параметров времени Г; и вероятности р1 на изменения времени выполнения запроса рассмотрим два

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

Для упорядоченной и неупорядоченной таблиц минимальное время выполнения запроса в соответствии с теоремами 1 и 2 при изменении параметра времени т, по закону геометрической прогрессии равно, соответственно:

l-(gp)fc т „ i-(gp)fc

' minyn = пР i—ap ' J min ну ap

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

П-Рк 1 - fcpk"1 + (fc ~ Ï)P \ T^y = n[TZ¥ + РД-}

Л-рк . 1 -fcpfc-^Çfc-Dp^ Tiay«=np{— + pà-^-)

Представленные выше результаты для параметров времени а=1.2 или 1.J, Д=0 5при к=6, и а= 1.1,Д=0.2 при к=12, демонстрируют одну и ту же тенденцию - при изменении параметра веРоятностиР1 до значения 0.5 время выполнения запроса возрастает незначительно. Параметр вероятности р, существенно влияет на время выполнения запроса при значениях более 0.5.

Ггмстрткм! «|»т«£«»д.1« иеупиричкяч«« таблвци

е./ a ï о я Г/Л 0.С n i ия ач »грмпшгтьпшгятяк р

«рфпэтк»» чмрии «суотрютии»»« tai.wiiu

ai at <и as es »' a» м

огро*шпь тмимя p

-*— SWS) -0-j^.twH №»1 •-».•ЧПММ V

Гп»|«1"|,""«л «Ч»Т*«"Я -V'« »«РМПГ..Й

md.mUM

m аз as a* « ä.e о» os в.» •qwmom. ятасясяяя î>

M ¡И 86 il «>

крякипиинтмтр

В общем случае запрос О образует множество с! дизъюнкций конъюнкций элементарных запросов:

(3 = СЕ(21 v... v CEQiv-.iv СЕСМ, где

конъюнкция >

СЕСИ= Е(31Л...Л Е(^л.|л Еды,

ЕСУ- элементарный запрос Время выполнения запроса (3 равно сумме времени выполнения всех конъюнкций элементарных запросов, в" соответствии с теоремами 1 и/или 2, плюс время объединения всех с1 таблиц, полученных на этапе реализации б конъюнкций. I

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

Будем считать, что нумерация образующих конъюнкцию элементарных запросов отвечает условиям теоремы 1 (или теоремы 2).

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

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

ОбозначимГг;-, ] =1,...,г, - время выполнения _)-го подмножества элементарных запросов на .¡-м из г процессоров, при этом формируется г таблиц. Пусть также Тг - время, требуемое для завершения параллельной работы г процессоров, т.е. для завершения первого этапа, тогдаГг = шах,- ТГ],] — 1, ...,г. Существует задача формирования подмножеств элементарных запросов для достижения минимального значения времени завершения первого этапа.

На втором этапе посредством объединения по номеру (имени) образуют результирующую таблицу. При объединении этих таблиц, по х = пргстрок в каждой таблице, где вероятность q - р^для каждой строки будем считать постоянной, что и задает верхнюю границу.

Требуется выполнить два шага. На первом шаге необходимо определить за время поиска Ьп имеется ли одноименная строка в текущей таблице. Если строка с заданным именем присутствует (вероятность я), то после выполнения второго шага - формирование строки за время процесс объединения строк продолжается. Иначе (с вероятностью (1- я)) процесс формирования

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

объединенной таблицы.

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

М = l(tn + Сф) + 1(1 - q)tn + q(l - q) * ((tn + Сф) + t„) + q2( 1 - q) * (2(tn + Сф) + tn) + - + <Г2( 1 - q)((r - 2) (tn + + tn)) + «ГЧ(r - 1) *

(tn + = ^ * (tn + + (1 " q^tn.

Тогда среднее время объединения всех строк г таблиц равно:

То= М прг.

Поэтому общее время выполнения запроса в г - процессорной ВС равно: Т= Тг+ То

Влияние числа процессоров на время выполнения запроса

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

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

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

вероятностирг = р, £ 6 1, fc.

2. С изменением параметра времени по закону арифметическои nporpeccraxi = l+(i-l)A, и с постоянным значением параметра вероятностир£ = р, i 6 1, fc.

В главе 2 показано, что параметр вероятности р; существенновлияет на время выполнения запроса при значениях более 0.5, поэтому влияние изменения числа процессоров на изменение времени выполнения запроса мы рассмотрим при 0.5< р^ < 0.9. При этом, исходя из практических условий вариации значений времени ть диапазон изменения времени Ti пусть находится в интервале от1 до 4, что, в частности, при к =6 приводит к а = 1.2 или 1.3, т.к. 1.25 = 2.488 или 1.35 = 3.713, а Д = 0.5, и при к =12 приводит к а = 1.1, т.к.

1.111=2.853, а Д = 0.2.

Для неупорядоченной таблицы оптимальное (Минимальное) время выполнения запроса в соответствии с теоремой 2 при изменении параметра времени по закону геометрической прогрессии для г процессоров равно:

Тчнг= пСау-^^СрСаУУ = j = W.

Тгнг = maXj=li3 Т3 j=TrrHr. Для k=12 и г =3 имеем:

т Т -Т__г~\2 1-(р(а)3)4

' знг -тах;=1,з *з;нг - 'ззнг — 1_р(а)з •

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

к

Тдуг= пр^ау-^.^МаУУ = пр1^^. j =1,...,г. Для к=12 и г =3 имеем: Тзуг = тах7=1,з Т3]уг=Т33уг= пр(а)2 •

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

,1-рк/г 1л ач ■ а1-с7)рк/г-1+(к/г-1)рк/г, Тг]на= ПС"Т7" А) + —-)

^гна = г ^гуна=Тггна-

Для к=12 и г =3 имеем:

Г3на = тах;=1,3 Г3;на=Т33на= п (1 + 2Д ) + ЗрА^^/ ).

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

Тпуа =ПР(-Т^~ С1+0-1) А) + фД—--),

^гуа — тах;=1г ТГ]уа=ТГ1уа.

Для к=12 и г =3 имеем:

^Зуа = тах/=1,3 ^зу'уа

Т3уа = тах;=1,з Г3;уа=Г33уа = пр(^ (1 + 2Д ) + ЗрА

Полученные результаты демонстрируют одну и ту же тенденцию - при значении параметра вероятности Р1>= 0.5 минимальное время выполнения запроса достигается не всегда при максимальном значении числа процессоров.

Квазиоптимальный план алгоритма распределения ЭЗ на процессоры

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

Существует задача формирования подмножеств элементарных запросов для достижения минимального значения времени завершения Тг первого этапа, которое равно:

Тг = тщ-Тг],]=1,...,т.

гдеГг,-, 3 =1,...,г, - время выполнения З-го подмножества элементарных запросов

на >м из г процессоров.

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

В качестве квазиоптимального алгоритма распределения элементарных запросов на процессоры для случая, когда число процессоров г отвечает условию [к/г]г = к, предлагается алгоритм чередования, при котором ь-ый (1 =1,...,г) процессор получает элементарные запросы с номерами и 2т +1 - 1, 2г + 1, 4г +1 -1, 4г +1, 6г+1 -1, 6г + ь.... Например, для к = 12 распределение имеет вид:

План АЛЯ 2 процессора

1_2__П 1 * Тт 1т«-» Т 11 | 1

Время выполнения запроса при значениях параметров т£ ир;: приведено в таблице 2.

Таблица2

к=12

р=(0.3,0.4,0.7,0.5,0.9,0.2,0.2,0.3,0.9.0.3,0.4,0.8)

т=Г7,5,6,2,3,3,2,4,8,9,2,41

N процессора Порядок обработки ЭЗ тг

1 1,2,3,4,5,6,7,8,9,10,11,12 - 2.73

1,4,5,8,9,12 3.174 4.285

2 2,3,6,7,10,11 4.285

1,6,7,12 3.75 4.78

3 2,5,8,11 4.78

3,4,9,10 4.28

1,8,9 4.16 5.04

2,7,10 5.04

4 3,6,11 4.24

4,5,12 4.48

1,12 3.6

2,11 3.2

6 3,10 3.8 7.8

4,9 5

5,8 6.7

6,7 7.8

12 1 до 12 9

Оптимальный алгоритм распределения ЭЗ на процессоры

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

_ТаблицаЗ

к=12

р=(0.3,0.4,0.7,0.5,0.9,0.2,0.2,0.3,0.9.0.3,0.4,0.8)

г,:=[7,5,6,2,3,3,2,4,8,9,2,4]

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

1 1,2,3,4,5,6,7,8,9,10,11,12 - 2.72

2 11,6,4,2,12,5 3.662 3.66

7,8,1,10,3,9 3.444

6,8,2,3 4.244 4.24

3 11,4,12,5 4.08 4

7,1,10,9 4.084

4,8,5 4.45

л 2,7,10 4.76 4.76

6,1,3 4.64

11,2,12 4.28

2,5 6.2

8,12 5.2

6 4,9 6 6.2

6,3 4.2

11,10 5.6

7,1 3.4

12 1 до 12 9

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

к=12

р=(0.3,0.4,0.7,0.5,0.9,0.2,0.2,0.3,0.9.0.3,0.4,0.8)

т,=Г7,5,б,2,3,3,2,4,8,9,2,4]

N процессора Кавзиопт имальный план Оггтималь ный план Разница результата % результата

1 2.72 2.72 0 0

2 4.285 3.66 0.625 14.58576

3 4.78 4.244 0.536 11.21339

4 5.04 4.76 0.28 5.555556

6 7.8 6.2 1.6 20.51282

12 9 9 0 0

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

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

Входными параметрами являются: количество элементарных запросов (к), количество строк (п), вероятности выполнения элементарных запросов (р;, 1=[1. к]), времена на их обработку (тг, 1=[1. к]),) и число процессоров (г=[1, к]). Язык программирования был выбран С++, программа написана под ОС ЦЬипШ. В общем случае, формула для нахождения времени оптимального запроса для одной строки в таблице:

Т=т1+р1*(т2+р2*(т3+р3(т3 + - + р,с-1 * тк)...), Для сортировки используется соотношение:

1 - Р! 1 - р2 1 - Рк

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

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

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

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

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

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

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

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

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

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

1. Мьо Тант. Организация параллельного выполнения запросов многопроцессорной машине баз данных с иерархической архитектурой.// работы научно-практической конференции студентов и молодых ученых МАИ «Инновации в авиации и космонавтике-2010». 26-27 апреля 2010г.Москва. Тезисы докладов.-М.:Изд-во МАИ, 2010. с.52.

2. Мьо Тант. Аналитическая оценка оптимальной обработки запросов в однопроцессорной базе данных.// работы научно-практической конференции студентов и молодых ученых МАИ «Инновации в авиации и космнавтике-2012». 13-15 ноября 2012г.Москва. Тезисы докладов. -296 с.

3. Брехов О.М., Мьо Тант. Оптимизация обработки запросов в многопроцессорной базе данных. // Журнал «Вестник Московского Авиационного Института» 2012г. №(5), с.138-265.

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

Содержание.

Введение.

Глава 1. Архитектура параллельных систем баз данных и обработка оптимизации запросов

1.1. Оптимальная обработка запросов (003).1.

1.1.1. Оптимизация запросов к базам данных.

1.1.2. Построение оптимального плана выполнения запроса.

1.1.3. Параллельная оптимизация запроса.

1.1.4. Обработка запроса в параллельной СУБД.

1.2. Математические методы для оценки методов 003.

1.2.1. Построение гистограмм для 003.

1.2.2. Глобальные оптимизации в реляционных системах управления БД.

1.3. Анализ оптимизации выполнения запроса.

1.3.1. Анализа моделей доступа к базам данных распределенных систем обработки данных.

1.3.2. Алгоритмы выполнения запросов к ООСУБД.

1.3.3. Анализ схемы базы данных.

1.3.4. Использование памяти.

1.3.5. Постановка задача.

Выводы по главе 1.

Глава 2. Метод оптимизации однопроцессорной обработки запросов.

2.1. Введение.!.

2.2. Время выполнения запроса для упорядоченных столбцов таблицы.

2.3. Время выполнения запроса для неупорядоченных столбцов таблицы.

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

2.5. Эффективность метода оптимизации.

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

2.7. Общий случай задания запроса.

Выводы по главе 2.

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

3.1. Введение.

3.2. Влияние числа процессоров на время выполнения запроса.:.

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

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

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

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

3.7. Квазиоптимальный план алгоритма распределения ЭЗ на процессоры.

3.8. Оптимальный алгоритм распределения ЭЗ на процессоры.

Выводы по главе 3.

Глава 4. Модуль формирования и оценки плана времени выполнения запроса.

4.1. Текст программы.

4.2. Описание программы.

4.3. Тестирование работы программы.

4.4. Анализ оптимизации плана выполнения запросов. Моделирование на СРБЗ/Н

4.4.1. Однопроцессорный вариант.

4.4.2. Многопроцессорный вариант.

Выводы по главе 4.

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

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

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

Одновременно с этим пользователи ожидают от применения СУБД высокой производительности и надежности.

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

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

Актуальность темы

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

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

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

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

Основным критерием при определении Плана реализации запроса является время выполнения запроса, которое, вообще говоря, зависит от порядка выполнения элементарных запросов, его составляющих, п указанных параметров элементарных запросов Э31 - времени проверки в строке т1 и вероятности успеха в строке р1. Время выполнения элементарного запроса зависит от метода доступа к столбцу таблицы. Существуют два базовых метода, когда данные в столбцах не упорядочены и когда данные в столбцах упорядочены. Известным методом увеличения производительности является использование многопроцессорных бортовых ВС.

Цель диссертационной работы

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

Методы исследования

Аналитическое и имитационное моделирование. Эксперименты с СУБД.

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

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

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

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

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

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

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

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

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

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

Практическая значимость

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

Реализация результатов работы

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

Вычислительные машины и системы» Московского авиационного института (государственного технического университета).

Апробация работы

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

Публикации

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

Структура и объем диссертации

Диссертация состоит из введения, четырёх глав, заключения, библиографического

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

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

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

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

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

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

1. Андреев А.Н., Воеводин Вл.В., Жуматий С.А. Кластеры и суперкомпьютеры -близнецы или братья? // Открытые системы. -2000.

2. Байкова И., Кулагин М. Современные дисковые системы RAID //Открытые системы. 1995.

3. Барон Г.Г. Параллельные архитектуры серверов баз данных // СУБД,-1995.

4. Баженова И. Ю. Основы проектирования приложений баз данных, ИНТУИТ.ру, 2006.

5. Безкоровайный М.М., Костогрызов А.И., Львов В.М. Инструментально-моделирую-щий комплекс для оценки качества функционирования информационных систем "КОК". М.:СИНТЕГ, 2000.

6. Брехов О.М., Мьо Тант. Оптимизация обработки запросов в многопроцессорной базе данных. // Журнал «Вестник Московского Авиационного Института» 2012г. №(5), с. 138-265.

7. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. -М.: Мир, 1985.

8. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем. -М: Изд-во МГУ, 1994.

9. Герберт Шилдт. Полный справочник по С. Изд-во Вильяме, 2009.

10. Гольдштейн М.Л. Мультипроцессорная вычислительная система на базе транспьютерной идеологии // Алгоритмы и программные средства параллельных вычислений: Сб. науч. тр. / ИММ УрО РАН.Екатеринбург: УрО РАН, 1995.

11. П.Григорьев Ю.А. Разработка научных основ проектирования архитектуры распределенных систем обработки данных: Дис. д-ра техн. наук. МГТУ им. Н.Э. Баумана, 17.10.96 г.

12. H.A. Гребенников, В.М. Постников //Организация баз данных, 2002 г. (Московский государственный технический университет им. Н.Э. Баумана).

13. Когаловский М.Р. Энциклопедия технологий баз данных. -М: Финансы и статистика, 2002.

14. Корнеев В. Архитектуры с распределенной разделяемой памятью // Открытые системы.

15. Корнеев B.B. Параллельные вычислительные системы. -М.: "Нолидж", 1999.

16. Корнеев В.В., Гареев А.Ф., Васютин C.B., Райх В.В. 'Базы данных. Интеллектуальная обработка информации. 2-е издание. -М.: Нолидж, 2001.

17. Кузнецов С.Д. «Базы данных: языки и модели», Москва, Бином, 2008, 720 с.

18. Кузнецов С.Д. Основы баз данных. М.: Изд-во "Интернет-университет информационных технологий - ИНТУИТ.ру", 2005.

19. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД // Программирование.

20. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД // Сб. Итоги науки и техники. Вычислительные науки. -Т.1. -М: ВИНИТИ, 1989.

21. Кузнецов С.Д. Операционные системы для управления базами данных // СУБД.

22. Кузнецов С.Д. СУБД и файловые системы. -М: Майор, 2001.

23. Кузьминский М, Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. -1995.

24. Лисянский К., Слободяников Д. СУБД Teradata для ОС UNIX // СУБД. 1997.

25. Постников В.М., Гребенников H.A. Технология обработки запросов пользователей в СУБД ORACLE // Вестник МГТУ им. Н.Э. Баумана. Сер. "Приборостроение". 2001. №2. С. 106-126.

26. Соколинский Л.Б. Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой // Программирование.

27. Соколинский Л.Б. Параллельные машины баз данных // Природа. Естественнонаучный журнал Российской академии наук. -2001.

28. Сиротюк В.О. Модели и методы синтеза оптимальных логических структур и базы метаданных репозитария распределенных баз данных в АСУ // Автоматика и телемеханика (М.). 1999. № 1.

29. Хаманн Ф. Отказоустойчивая операционная система TandemNonStop Kernel // Открытые системы.

30. Шмидт В. Системы 1BMSP2 // Открытые системы.

31. Шнитман В. Отказоустойчивые серверы ServerNet // Открытые системы.

32. An Environment for the Design and Performance Evaluation of Portable Parallel Software: Final EDPEPPS Simulator: Report / Center for Parallel Computing University of Westmin-ster. EDPEPPS/41. London, July 1997.

33. Amza C., et al. ThreadMarks: Shared Memory Computing on Networks of Workstations // IEEE Computer. -1996. -Vol. 29, No. 2.

34. Amol Deshpande, Zacchary Ives, Vijayshankar Raman Adaptive Query Processing // Foundations and Trends in Databases. -2007. -Vol.1,No. 1(2007), p. 1-140.

35. Apers P.M.G., van den Berg C.A., Flokstra J., Grefen P.W.P. J., Kersten M.L., Wilschut A.N. Prisma/DB: a Parallel Main-Memory Realational DBMS // IEEE Transactions on Knowledge and Data Engineering. -1992. -Vol. 4, No. 6.

36. Ballinger C., Fryer R. Born To Be Parallel: Why Parallel Origins Give Teradata an Enduring Performance Edge // IEEE Data Engineering Bulletin. -1997. -Vol. 20, No. 2.

37. Baru C. K., et al. DB2 Parallel Edition // IBM System Journal. -1995. -Vol. 34, No. 2.

38. Bell C.G., Gray J. What's next in high-performance computing? // Communications of the ACM. -2002. -Vol. 45, No. 2.

39. Bellman R.E. Dynamic Programming, Princeton University Press, Princeton, N; Jersey, 1975.

40. Bergsten B., Couprie M., Valdurez P. Overview of Parallel Architectures for Databases // The Computer Journal. -1993. -Vol. 36, No. 8.

41. Boral H„ Alexander W., Clay L., Copeland G„ Sanforth S., Franklin M., Hart B„ Smith M., Valduriez P. Prototyping Bubba: a Highly Parallel Database System // IEEE Trans, on Knowledge and Data Engineering. -1990. Vol. 2, No. 1.

42. Boral H., De Witt D.J. Applying Data Flow Techniques to Data Base Machines // IEEE Computer. -1982. -Vol. 15, No. 8.

43. Bultzingsloewen G. Optimizing SQL Queries for Parallel Execution // ACM SIGMOD Record.-1989. -Vol. 18, No. 4.

44. Bultzingsloewen G.v., et al. KARDAMOM A Dataflow Database Machine For RealTime Applications // SIGMOD Record.-1988. -Vol. 17, No. 1.

45. Codd, Edgar Frank: "Is Your DBMS Really Relational?", Computerworld, 14. October 1985.

46. Chen M.-S., Yu P.S., Wu K.-L. Optimization of Parallel Execution for Multi-Join Queries // IEEE Transactions on Knowledge and Data Engineering. -1996. -Vol. 8, No. 3.

47. Chen M.-S., Yu P.S., Wu K.-L. Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries // Proceedings of the Eighth International Conference on Data Engineering, February 3-7, 1992, Tempe, Arizona. -IEEE Computer Society, 1992.

48. Cheng J.M., et al. IBM Database 2 Performance: Design, Implementation, and Tuning // IBM Systems Journal. -1984. -Vol. 23, No. 2.

49. Christodoulakis S. Estimating record selectivities // Information Systems. -1983. -Vol. 8, No. 2.

50. Clay D. Informix Parallel Data Query (PDQ) // Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems (PDIS 1993), Issues,

51. Architectures, and Algorithms, San Diego, CA, USA, January 20-23, 1993. -IEEE Computer Society, 1993.

52. Copeland G.P., Keller T. A Comparison Of High-Availability Media Recovery Techniques // roceedings of the 1989 ACM S1GMOD International Conference on Management of Data, Portland, Oregon, May 3 1 June 2, 1989. -ACM Press, 1989.

53. Dasgupta S. A Hierarchical Taxonomic System for Computer Architectures // IEEE Computer.-1990.-Vol. 23, No. 3.

54. Davison W. Parallel Index Building in Informix OnLine 6.0 // Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. -ACM Press, 1992.

55. DeWitt D.J., Gerber R.H. Multiprocessor Hash-Based Join Algorithms // VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden. -Morgan Kaufmann, 1985.

56. DeWitt D.J., et al. The Gamma database machine project // IEEE Transactins on Knowledge and Data Engineering. -1990. -Vol. 2, No. 1.

57. Effelsberg W., Haerder T. Principles of Database Buffer Management // ACM Trans, on Database Systems. 1984. -Vol. 9, No. 4.

58. E.F. Codd: "Relational Completeness of Data Base Sublanguages" (presented at Courant Computer Science Symposia Series 6, "Data Base Systems", New York City, N.Y., May 24th-25th, 1971).

59. Englert S., Glasstone R., Hasan W. Parallelism and its Price: A Case Study of NonStop SQL/MP // ACM SIGMOD Record. -1995. -Vol. 24, No. 4.

60. Flynn M.J. Computer Organization and Architecture // Operating Systems, An Advanced Course. -Springer, 1978 (Lecture Notes in Computer Science; Vol. 60).

61. Flynn M.J. Very High Speed Computing Systems // Proc. IEEE. -1966. -Vol. 54. -P. 1901-1909.

62. Flynn M.J., Rudd K.W. Parallel architectures // ACM Computing Surveys. 1996. -Vol. 28, No. 1.

63. Gardarin G., Sha F., Tang Z.-H. Calibrating the query optimizer cost model of IRO-DB an objectoriented federated database system // Proceedings of the 22nd International Conference on VLDB. Bombay, 1996. P.378-389.

64. Gibson G.A., Vitter J.S., Wilkes J. Strategic directions in storage I/O issues in large-scale computing // ACM Computing Surveys. 1996. -Vol. 28, No. 4. -P. 779-793.

65. Graefe G. Encapsulation of Parallelism in the Volcano Query Processing Systems // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. -ACM Press, 1990.

66. Graefe G. Query evaluation techniques for large databases // ACM Computing Surveys. -1993.-Vol. 25, No. 2.

67. Graefe G. Volcano An Extensible and Parallel Query Evaluation System // IEEE Transactions on Knowledge and Data Engineering. -1994. -Vol. 6, No. h

68. Graefe G. Query evaluation techniques for large databases // ACM Computing Survey N.Y., 1993. Vol. 25. No. 2. P.73-170.

69. Graefe G. Query Evaluation Techniques for Large Databases // ACM Computing Surveys. -1993. -Vol. 25, No 2. -P. 73-169.

70. Graefe Goetz, Dewitt David J. The EXODUS Optimizer Generator. In Proceedings 1987 ACM SIG-MOD International Conference on Management of Data, San Francisco, 1987. P.387-394.

71. Graefe Goetz, McKenna William. The Volcano Optimizer Generator: Extensibility and Efficient Search. In Proceeding of the 12th International Conf. on Data Engineering, 1993. P.209-218.

72. Graefe G. The Cascades Framework for Query Optimization, Bulletin of the IEEE Technical Committee on Data Engineering, 18(3), September 1995, P. 19-29.

73. Gray J. Notes on Data Base Operating Systems // Operating Systems, An advanced Course.-Springer, 1978 (Lecture Notes in Computer Science; Vol. 60).

74. Gray J., Graefe G. The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb // SIGMOD Record. -1997. -Vol. 26, No. 4.

75. Hasan W. Optimization of SQL Queries for Parallel Machines. (Lecture notes in computer science, Vol. 1182). -Berlin, New York: Springer, 1996.

76. Hong W., Stonebraker M. Optimization of Parallel Query Execution Plans in XPRS // Distributed and Parallel Databases. -1993. -Vol. 1, No. 1.

77. Hsiao H. I., DeWitt D. J. A Performance Study of Three High Availability Data Replication Strategies// Distributed and Parallel Databases. -1993. -Vol. 1, No. 1.

78. Hwang H-Y., Yao-Tin Y. An Analytical Method for Estimating and Interpreting QueryTime // Proceedings of the 13th VLDB Conference. Brighton, 1987.

79. Ibaraki T., Kameda T. On the optimal nesting order for computing N-relational joins. //ACM Transactions on Database Systems. 1984. 9(3). P.482-502.

80. Jarke M., Koch J. Query optimization in database systems // ACM Computing Surveys. -1984.-Vol. 16, No. 2.

81. Kim W. Highly Available Systems for Database Applications // ACM Computing Surveys.-1984.-Vol. 16, No. 1.

82. King G. M., Dias D. M., Yu P. S. Cluster Architectures and S/390 Parallel Sysplex Scalability // IBM Systems Journal. -1997. -Vol. 36, No. 2.

83. Kotsis G. Interconnection Topologies for Parallel Processing Systems // PARS Mitteilungen. -1993.

84. Kronenberg N.P., Levy H.M., Strecker W.D. VAXclusters: A .Closely-Coupled Distributed System // ACM Transactions on Computer Systems. -1986. -Vol. 4, No. 2.

85. Lakshmi M.S., Yu P.S. Effectiveness of Parallel Joins // IEEE Transactions on Knowledge and Data Engineering. -1990. -Vol. 2, No. 4.

86. Lohman G.M., et al Query Processing in R* // Query Processing in Database Systems. -Springer, 1985.

87. Lorie R., et al. Adding Intra-transaction Parallelism to an Existing DBMS: Early Experience// Data Engineering Bulletin. -1989. Vol. 12, No. 1.

88. Lorie R.A., Young H.C. A Low Communication Sort Algorithm for a Parallel Database Machine // Proceedings of the Fifteenth International Conference onVery Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands. -Morgan Kaufmann, 1989.

89. Lu H., Shan M.-C., Tan K.-L. Optimization of Multi-Way Join Queries for Parallel Execution // 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings. -Morgan Kaufmann, 1991.

90. Matthias Jarke, Jürgen Koch. Query Optimization in Database Systems. Computing Surveys, Vol. 16, No. 2, June 1984.

91. Menon J. A Study of Sort Algorithms for Multiprocessor Database Machines // VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. -Morgan Kaufmann, 1986.

92. Method and system for query processing,United States Patent 6757670.

93. Michie D. 'Memo' Functions and Machine Learning, Nature, April 1968. No. 218, P. 1922.

94. Montgomery A.Y.,D'Souza D.J., Lee S.B. The Cost of Relational Algebraic Operations on Skewed Data: Estimates and Experiments // Information Processing 83,

95. Proceedings of the IFIP 9th World Computer Congress, Paris, France, September 19-23, 1983.-North-Holland: IF1P, 1983.

96. Nick J. M„ Moore B. B„ Chung J.-Y., Bowen N. S. S/390 Cluster Technology: Parallel Sysplex // IBM Systems Journal. -1997. -Vol. 36, No. 2.

97. Norman M. G., Zurek T., Thanisch P. Much Ado About Shared-Nothing // ACM SIGMOD Record. -1996. -Vol. 25, No. 3.

98. Oldehoeft R. R. Multithreaded Computer Systems // Proceedings Supercomputing'92, November 16-20, 1992, Minneapolis, MN, USA. -IEEE Computer Society, 1992.

99. Ozsu M.T., Valduriez P. Principles of Distributed Database System. Englewood Cliffs, NJ: Prentice-Hall, 1991.

100. Patterson D.A., Gibson G.A., Katz R.H. A Case for Redundant Arrays of Inexpensive Disks (RAID) // Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988. 1988.

101. Pfister G. Sizing Up Parallel Architectures // DataBase Programming & Design OnLine (http://www.dbpd.com). May 1998. -Vol. 11. No. 5.

102. Pirahesh Hamid, Hellerstein Joseph M., Hasan Waqar. Extensible/Rule Based Query Rewrite Optimization in Starburst. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, pages 39-48, San Diego, California, June 1992.

103. Pramanik S., Tout W.R. The NUMA with Clusters of Processors for Parallel Join // IEEE Transactions on Knowledge and Data Engineering. -1997. -Vol. 9, No. 4. -P. 653-666.

104. Query Processing in Parallel Relational Database Systems / edited by. Lu H., Ooi B.-C., Tan K.-L. -IEEE Computer Society Press, 1994.

105. Rahm E. A Framework for Workload Allocation in Distributed Transaction Processing Systems//Journal of Systems and Software. -1992. -Vol. 18.

106. Rahm E. Parallel Query Processing in Shared Disk Database Systems // ACM SIGMOD Record. -1993. -Vol. 22, No. 4.

107. Richardson J.P., Lu H., Mikkilineni K. Design and Evaluation of Parallel Pipelined Join Algorithms // Proceedings of the ACM S1GMD 1987 Annual Conference, San Francisco, California, May 27-29, 1987. -ACM Press, 1987.

108. Seiinger P.G., Astrahan M.M., Chamberlin D.D., Lorie R.A., Price T.G. Access Path Selection in a Relational Database Management System // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., May 30 June 1, 1979. New York, 1979.- C. 23-34.

109. Skillicorn D.B. A Taxonomy for Computer Architectures // IEEE Computer. -1988.-Vol. 21, No. 1.

110. Sokolinsky L.B. Design and Evaluation of Database Multiprocessor Architecture with High Data Availability// 12th International DEXA Workshop, Munich, Germany, 37 September, 2001, Proceedings. -IEEE Computer Society, 2001.

111. SQLBase. Advanced Topic Guide. 20-2119-9901 SQL designs. Gupta Inc. 2006

112. Sterling T., et all. BEOWULF: A Parallel Workstation for Scientific Computation // Proceedings of the 1995 International Conference on Parallel Processing, August 1418, 1995, Urbana-Champain, Illinois, USA. Volume I: Architecture. -CRC Press, 1995.

113. Stonebraker M., Katz R.H., Patterson D.A., Ousterhout J.K. The Design ofXPRS // Fourteenth International Conference on Very Large Data Bases, August 29 September 1, 1988, Los Angeles, California, USA, Proceedings. -Morgan Kaufmann, 1988.

114. Stonebraker M. Operating System Support for Database Management // Communications of the ACM. -1981. -Vol. 24, No. 7.

115. Stonebraker M. The case for shared nothing // Database Engineering Bulletin. -1986. -Vol. 9, No. 1.

116. Strickland J.P., Uhrowczik P.P., Watts V.L. IMS/VS: An Evolving System // IBM Systems Journal. -1982. -Vol. 21, No. 3.

117. The Benchmark Handbook for Database and Transaction Processing Systems, Second Edition. -Morgan-Kaufmann, 1993.

118. Valduriez P. Parallel Database Systems: Open Problems and New Issues // Distributed and Parallel Databases. -1993. -Vol. 1, No. 2.

119. Valduriez P., Gardarin G. Join and Semijoin Algorithms for a Multiprocessor Database Machine // ACM Transactions on Database Systems. -1984. -Vol. 9, No. 1.

120. Van Vleck T. H. , Clingen C. T. The Multics System Programming Process // Proceedings of the 3rd International Conference on Software Engineering, May 1012,1978, Atlanta, Georgia, USA. -IEEE Computer Society, 1978.

121. W. Hasan, D. Florescu, P. Valduriez Open Issues in Parallel Query Optimization // ACM SIGMOD Record. -1996. -Vol. 25, No. 3.

122. Williams M.H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques. IEEE Computer society, 1998.

123. Wong, Eugene, Youssefi, K., Decomposition A Strategy for Query Processing. ACM Transactions on Database Systems, 3 (September) 1976.

124. Xu Y., Dandamudi S.P. Performance Evaluation of a Two-Level Hierarchical Parallel Database System // Proceedings of the Int. Conf. Computers and Their Applications, Tempe, Arizona, 1997.

125. Yannis E. Ioannidis: Query Optimization.ACM Comput. Surv. 28(1): 121-123 (1996)

126. Zipf G.K. Human Behavior and the Principle of Least Effort: an Introduction to Human Ecology. -Cambridge, Mass.: Addison-Wesley, 1949.

127. Amol Deshpande, Zacchary Ives, Vijayshankar Raman Adaptive Query Processing // Foundations and Trends in Databases. -2007. -Vol.1, No. 1(2007), p. 1-140.