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

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

ЛОКШИН Марк Викторович

РАЗРАБОТКА МЕТОДОВ РАСПАРАЛЛЕЛИВАНИЯ ЗАПРОСОВ В ГЕТЕРОГЕННЫХ СИСТЕМАХ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Воронеж - 2005

Работа выполнена в Воронежском государственном техническом университете

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

доктор технических наук, профессор Кравец Олег Яковлевич

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

доктор технических наук, профессор Погодаев Анатолий Кирьянович;

кандидат технических наук Дорофеев Александр Николаевич

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

Воронежский государственный университет

Зашита состоится 26 мая 2005 г. в 10 00 часов в конференц-зале на заседании диссертационного совета Д 212.037.01 Воронежского государственного технического университета по адресу: 394026, г. Воронеж, Московский просп., 14.

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

Автореферат разослан 26 апреля 2005 г.

Ученый секретарь диссертационного совета

Питолин В.М.

-у

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

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

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

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

Диссертационная работа выполнена в рамках научного направления Воронежского государственного технического университета - «Вычислительные системы и программно-аппаратные электротехнические комплексы».

Цель работы Целью работы является разработка методов распарапле-ливания 8<ЗЬ-запросов в гетерогенных архитектурах для повышения производительности распределенных СУБД.

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

1. Выполнить анализ современных архитектур СУБД и методов, применяемых в них для параллельного исполнения БС^Ь-запросов, обобщить анализ современного состояния исследований в области применения методов параллельной обработки запросов.

2 Разработать эффективные методы распараллеливания запросов в гетерогенных средах с доказательством их корректности.

3. Разработать алгоритмы и программные средства для распараллеливания 5С}Ь-запросов, обеспечить их совместимость с существующими СУБД.

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

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

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

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

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

• априорные оценки эффективности распараллеливания запросов, отличающиеся учетом особенностей исполнения запросов в гетерогенных системах с репликацией данных и позволяющие быстро оценить целесообразность применения созданного метода распараллеливания БС^Ь-запросов на этапе конфигурирования системы;

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

Практическая )начимость работы Практическая значимость работы заключается в создании специального программного обеспечения, обеспечивающего распараллеливание 8(3£.-запросов до начала их исполнения в гете-

рогенных СУБД, а также алгоритмов рационального выбора атрибута разделения отношений.

Реализаиия и внедрение результатов работы Теоретические и практические результаты работы реализованы в специальном программном комплексе исполнения аналитических запросов в рамках системы автоматизации предприятия. С его использованием разработана программа "Учет потребления электроэнергии абонентами юридическими лицами", которая внедрена в практическую деятельность ОГУП "Западные межрайонные электрические сети" (г. Елец) и зарегистрирована в Государственном фонде алгоритмов и программ.

Апробаиия работы Основные результаты работы докладывались и обсуждались на Международной научно-практической конференции «Единое информационное пространство» (Днепропетровск, 2003); IIX - X Международных открытых научных конференциях «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях» (Воронеж, 2003-2005); XI Всероссийской научно-методической конференции «Телематика'2004» (Санкт-Петербург, 2004); II Всероссийской научно-технической конференции «Вузовская наука - региону» (Вологда, 2004); VIII Международной научно-практической конференции «Актуальные проблемы информатики и информационных технологий» (Тамбов, 2004).

Публикации Основные результаты диссертации опубликованы в 11 научных работах, в том числе 5 без соавторов. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежит: в [7, 8] - основные принципы параллельного исполнения запросов в рассматриваемых системах, в [9] алгоритм быстрого нахождения точек разбиения отношений, в [6, И] - особенности проблемы параллельного исполнения запросов и способов организации взаимодействия при параллельном исполнении запросов в больших информационных системах, в работе в [10] -особенности реализации подсистемы высокоуровневого распараллеливания.

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

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

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

В первой главе проведен обзор существующих параллельных архитектур, способных поддерживать функционирование СУБД. Сделан вывод о перспективности разработки параллельных СУБД, ориентированных на работу в различных вариантах массово-параллельных систем (Massively Parallel Processing, МРР). Данные системы использую схему, согласно которой каж-

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

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

а1Я =

dAlOA

АВ A t a J,

(1)

' в'ов

где d, - степень параллелизма (например количество процессоров) конфигурации 4; dB - степень параллелизма конфигурации В; t0l - время, затраченное конфигурацией Л на выполнение теста Q\ i,m - время, затраченное конфигурацией В на выполнение теста Q.

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

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

На основе проведенного обзора сформулирована цель исследования и определены задачи для ее выполнения.

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

Предположим, что система состоит из N узлов, на которых установлены SQL сервера, причем мы допускаем наличие гетерогенной среды. В таком случае для обращения к подобной системе необходимо использовать под-

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

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

Рис. 1. Архитектура системы для параллельного исполнения запросов

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

Рис. 2. Укрупненный алгоритм работы препроцессора распараллеливания запросов

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

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

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

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

Теорема Рассмотрим запрос вида

SELECT * FROM R WHERE L,

где L - фиксированное логическое выражение, вычислимое для каждого кортежа из R.

Определим y,{R) - оператор группирования кортежей отношения, где /одна из функций агрегирования: SUM, A VG, MIN, MAX, COUNT.

Пусть л*ш|П = /„,,„ , ,(R), а а1шч =г,Т1м1„ JR), и выбраны и 1 произвольные точки х, из отрезка [дстщ дг,|Цч J, где i с [0 л], причем л„ = \mirl и х„ = х^. Пусть для всех точек х, выполнены следующее два условия: v<*,/6[i «и*/)[к_„л(]п[*,.,..г,]=о], V(*,/e[0 **,J

Тогда для параллельного исполнения запрос можно эквивалентно преобразовать к виду:

SELECT * PROM R WHERE L and (R.A >= хш„ and F.A<=,v,' ONION ALL

SELECT * FROM R WHERE L and (R.A > v, and Р.А^=.т, ) UNION ALL.. (3)

UNION ALL

SELECT * FROM R WHERE L and (R.A > .r„_, and R.A<=\mJV) UNION ALL SELECT * FROM R WHERE L and (R.A IS null)

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

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

Предположим, что в отношении R присутствует атрибут А, по которому мы будем проводить разделение. Согласно условию *т,„ и .vmx - минимальное и максимальное значение атрибута на всем отношении соответственно. Мы не накладываем никаких ограничений на отсутствие вхождения атрибута А в выражение L, более того, если в нем присутствуют явные ог-

раничения значений атрибута, то их целесообразно использовать в качестве значений *,„,„ или *mlx.

Представим запрос в виде

<rL(R), (4)

где сг - оператор выбора реляционной алгебры, применяемый к кортежам отношения R, удовлетворяющим некоторому заданному условию 1..

Замечая, ЧТО (RA>=xlmllandRA<=xms)or{RA = null) истинно для любых значений RA, преобразуем данное выражение к виду (RA >= .vmm andR А <= х,)or or(R А >- х„ , andR А <= vmax )or(RA = null). Согласно выбору .г, хотя бы один из операторов дизъюнкции принимает значение «истина», а значит и все выражение тождественно истине.

Из (4) получаем, обозначая Е, =(RA>= A,_,and R А <=А,) ,а Е = Е,ог огЕ„:

i ап.Цпие) (К) = / anJiCorlR Л-ш<//»(^) ■ (5)

Преобразуя (5), получаем

<* Lmd f.l(«)U ... U (Т LanJ в, (K)U СГ Land (R ,(/?) .

Путем анализа структуры программы, которой соответствует запрос аl and установлено, что SQL-запросы вида (3) при ограничениях (2)

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

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

Определено три семейства параметров В, Т и L для описания ресурсных затрат на обработку отношений, используемых в запросе:

• B{R)- количество блоков, необходимое для хранения всех кортежей отношения R.

• T(R) - количество кортежей в отношении R. Тогда количество кортежей, которые умещаются в пределах одного блока, выражается как

nR)fB{R).

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

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

При построении оценок для более сложных БОЬ-запросов необходимо использовать различные комбинации методов оценок, приведенных в табл. 1-

3.

Таблица 1

_Априорные оценки времени исполнения запросов на N узлах__

Тип запроса Оценка скорости исполнения

SELECT ^) + 2ЦЯ.В(Ю) + С1 N

GROUP N 2 Т(Я)

JOIN В(Л1)+ В(К2) + 2ЩЛ1, й(«1))+ ЦЯ2, В(Н2))} + О N

Таблица 2 Априорные оценки времени исполнения запросов на одном узле

Тип запроса Оценка скорости исполнения

SELECT В(Ю + ЦИ,В(Ю)

GROUP 2 Г(Л)

JOIN 1) + Я(Д2) + £(Я1, В( Д1)) + £(Й2, 2»

Таблица 3 Коэффициент ускорения согласно (1)

Тип запроса Оценка скорости исполнения

SELECT j (2N-l)L(R,B(R)) + NCl й(й) + 2ЛХ(Л,й(«))+Л'а

GROUP B(R) + IB(R) B(R) (2N 1 )L(R, V Л ( v + ^ 2 Г(Л) B(R)+ [B(R) B(R) Зй(Я) + 2ЩЯ, ' — • --) + Nil 2 T(R)

JOIN j (2.V - 1)(ДЛ1, B(R\)) + ¿(Л2,B(R2))) + NCI B(R\) + B(R2) + 2NL(Rl B( Я1)) + 2NL(R2, B(R2)) f Mi

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

Преимущества при реализации разработанного метода распараллеливания запросов заключаются в следующем:

• обеспечивается работа с гетерогенными СУБД с динамически изменяемым количеством узлов;

• достигается относительная простота реализации системы с параллельной обработкой запросов. Распараллеливание на уровне 8(}Ь-запросов не затрагивает реализацию операций нижнего уровня, применяемых при исполнении запроса. Фактически в системе применяется двойной процесс оптимизации - для параллельного исполнения запроса между

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

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

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

включено в статистическую информацию) и а, Введем функцию

,-а

плотности распределения кортежей p(c,d) = c/d, характеристическую функ-

\\,a<t<b

цию отрезка [а,Ь]: = { Л и кардинальное число отношения С .

[О, иначе

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

Разработан алгоритм численного решения уравнения (6) для быстрого нахождения точек разбиения значений атрибута (рис. 3). Увеличение скорости нахождения точек разбиения осуществляется за счет использования уже вычисленных на предыдущих итерациях алгоритма точек.

Рис. 3. Быстрый алгоритм поиска точек разделения отношений В качестве й, и Ь, здесь обозначены минимальные и максимальные значения атрибута на всем отношении соответственно.

С использованием быстрого алгоритма поиска точек разделения отношений разработано семейство алгоритмов распараллеливания запросов для различных SQL операций. Механизм динамического преобразования запроса в данных алгоритмах осуществляется за счет адаптивного выбора параметров, что, как показано в главе 4, обеспечивает субоптимальное время испол-

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

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

• Данные атрибуты разбиваются на четыре группы, согласно которым можно проводить разделение отношений (группа с меньшим номером является более предпочтительной):

1. Разделение операции соединения JOIN по атрибуту, который входит в инструкцию GROUP BY, и первому атрибуту в инструкции сортировки ORDER BY.

2. Разделение по атрибуту из GROUP BY.

3. Разделение по первому атрибуту инструкции сортировки ORDER BY (в том случае, если в запросе отсутствует инструкция группировки GROUP BY).

4. Разделение по атрибуту инструкции соединения JOIN, не входящему в инструкцию GROUP BY, или при условии отсутствия данной инструкции.

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

• Модифицируется исходный SQL-запрос, после чего исполняются получившиеся запросы.

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

поставлена задача разработки программных средств распараллеливания SQL-запросов.

В четвертой главе проведены экспериментальные исследования предложенного метода распараллеливания SQL-запросов и результаты практического внедрения.

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

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

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

Таблица 4

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

Кол-во Время Строк Проме- Дополни- Об- %от Коэф.

узлов на уз- в вы- жуточная тельные пла- щее исход- уско-

N ле борке выборка ны запроса время ного рения

1 135 10 0 0 135 100% 1

2 69 10 20 3 71 53% 0.951

4 35 10 40 3 37 27% 0.912

8 ^ 18 10 80 3 20 15% 0.844

16 10 10 160 3 12 9% 0.703

Содержимое табл. 4 отражает следующие величины:

• время на узле Г . максимум по времени, затраченному для исполнения запроса на каждом из узлов системы (г, - время на исполнение запроса для 1 -го узла);

• промежуточная выборка - общее количество кортежей в промежуточных выборках для всех N серверов системы;

• дополнительные планы запроса - количество планов запроса, которые были дополнительно построены и проанализированы при подготовке к выбору алгоритма для параллельного исполнения запроса;

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

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

• коэффициент ускорения рассчитан согласно формуле (1).

Данные табл. 4 позволяют сказать, что применение предложенного метода позволяет значительно сократить время исполнения запроса за счет малых временных затрат на его предварительное распараллеливание. Масштабируемость системы для исходного запроса и набора данных ограничивается 30-40 узлами, однако увеличение объема обрабатываемых данных позволяет увеличить масштабируемость системы.

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

•А—1_огйегкеу О—о_огс]егкеу —8-о_огйеп)а1е --о- А1д

Количество узлов в системе N

Рис. 4. Диаграмма зависимости времени исполнения запросов от количества узлов для тестовой базы данных (1 Гб)

Диаграмма на рис. 5 отражает время исполнения аналогичных запросов на тестовой базе, построенной с применением масштабирующего коэффициента 10 (соответствует базе данных размером около 10 Гб). Графики времени исполнения запроса, полученного на основе предлагаемого метода (с учетом времени работы алгоритма преобразования) и наилучшего варианта, полученного путем перебора всех возможных атрибутов разбиения на рис. 5, практически совпадают.

Количество узлов в системе N

Рис. 5. Диаграмма зависимости времени исполнения запросов от количества узлов для тестовой базы данных (10 Гб)

Из рис. 4 следует, что дальнейшее масштабирование системы не приводит к существенному уменьшению времени исполнения запроса, так как в этом случае большая часть времени будет уходить на подготовку запроса к параллельному исполнению, а не собственно на исполнение запроса. Согласно формуле (1) и рис. 5 можно утверждать, что для базы данных объемом 10 Гб число узлов системы может быть увеличено до 200 с сохранением коэффициента ускорения, близким к единице.

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

• распараллеливание всех запросов позволило уменьшить время исполнения;

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

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

Для других наборов данных, отличных от предлагаемых в тесте ТРС-Э, с использованием той же схемы отношений были получены аналогичные результаты. Атрибуты, при которых достигалась минимальная скорость исполнения запроса, оказывались различными, существенным образом зависящими от набора данных. Использование предлагаемых алгоритмов для преобразования запроса позволяло выводить время исполнение запроса на уровень наилучшего априорно неизвестного атрибута, без использования фиксированного разделения по атрибутам.

Разработанные методы распараллеливания использованы при реализации системы учета потребления и оплаты электроэнергии на предприятии ОГУП «Западные межрайонные электрические сети» (г. Елец). Структура информационной системы предприятия представлена на рис. 6.

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

Применение разработанного метода распараллеливания 8<ЗЬ-запросов на основе их предварительной модификации позволило ускорить выполнение аналитических запросов в информационной системе предприятия на 30 -90 % (по данным опытной эксплуатации, в зависимости от типа запроса). Разработана и зарегистрирована в Государственном фонде алгоритмов и программ программа «Учет потребления электроэнергии абонентами юридическими лицами», опирающаяся на данную технологию в подсистеме обработки аналитических запросов [10].

Рис. 6. Структура информационной системы предприятия:

- запросы оперативного учета (OLTP)

---аналиютеские запросы (OLAP)

репликация данных

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

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

2. Получены априорные оценки общего времени параллельного исполнения преобразованных SQL-запросов.

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

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

5. С использованием метода распараллеливания SQL-запросов создана программа для ОГУП «Западные межрайонные электрические сети» (г. Елец), входящая в состав системы автоматизации работы предприятия, обеспечивающая исполнение аналитических запросов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ:

1. Локшин М.В. Об одном методе параллельного выполнения запросов в распределенных СУБД // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: Сб. тр. -Воронеж: Изд-во «Научная книга», 2004. Вып. 9. - С. 360-361.

2. Локшин М.В. Эквивалентное преобразование БОЬ-запроса к запросу с диапазонами в условии фильтрации // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: Сб. тр. - Воронеж: Изд-во «Научная книга», 2005. Вып. 10. - С. 255-256.

3. Локшин М.В. Модификация деревьев разбора для параллельного исполнения запроса // Успехи современного естествознания. - 2004. №10. -

4. Локшин М.В. Обработка запросов к большим объемам данных в СУБД // Актуальные проблемы информатики и информационных технологий: Материалы Междунар. (VIII Тамбовской межвузовской) науч.-практ. конф. Тамбов: Изд-во ТГУ им. Державина, 2004. - С. 69.

5. Локшин М.В. Система для параллельного исполнения запросов к базам данных // Седьмая регион, молодежная науч. и инженерная выставка «Шаг в будущее. Центральная Россия»: Сб. тез. докл. Липецк: Липецкий гос. техн. ун-т, 2004. - С. 25-26.

6. Локшин М.В., Кравец О .Я. О некоторых принципах построения автоматизированных информационных систем с применением СУБД // Единое информационное пространство:Сб докл. Междунар. науч.-практ. конф. ИПК ИнКомЦентра УГХТУ, 2003. - С. 140-143.

7. Локшин М.В., Кравец. О.Я. Параллельное исполнение запросов в реляционных базах данных с использованием репликации // Информационные технологии моделирования и управления: Междунар. сб. науч. тр. - Воронеж: Изд-во «Научная книга», 2004. Вып. 17,-С. 75-80.

8. Локшин М.В., Кравец. О.Я. Построение систем для параллельной обработки запросов к СУБД // Телематика'2004: Труды XI Всерос. науч.-метод. конференции. -СПб: ИТМО, 2004. - С. 94-95.

9. Локшин М.В., Кравец. О.Я. Параллельное исполнение запросов в системах с репликацией данных // Вузовская наука - региону: Труды Второй Всерос. науч.-техн. конф. Вологда, 2004. - С. 484-486.

10.Локшин М.В., Струков И.А. Программа «Учет потребления электроэнергии абонентами юридическими лицами». - М.: ФАП ВНТИЦ, 2003. Per. №50200300423.

1 Шерепухин А.Н., Савинков Ю.А., Локшин М.В. Проблемы разработки больших информационных систем // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: Сб. тр. - Воронеж: Из-во «Научная книга», 2003. Вып. 8. - С. 120-121.

С. 70-71.

Подписано в печать 25.04.05. Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 90 экз. Заказ № т.

Воронежский государственный технический университет 394026 Воронеж, Московский просп., 14

Р - 8 3 9 6

РНБ Русский фонд

2006-4 5288

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

1. АНАЛИЗ СОВРЕМЕННЫХ МЕТОДОВ ОБРАБОТКИ SQL-ЗАПРОСОВ В СУБД.

1.1 Архитектуры параллельных систем.

1.2 Классификация архитектур параллельных систем баз данных.

1.3 Масштабируемость параллельных систем обработки данных.

1.4 Формы параллелизма. Параллельное исполнение операторов языка SQL

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

1.6 Основные понятия и обозначения реляционной алгебры.

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

ГЛАВА 2. ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ЗАПРОСОВ С ИСПОЛЬЗОВАНИЕМ ИЗБЫТОЧНОСТИ

ДАННЫХ.

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

2.2. Декомпозиция запроса с отображением его в древовидную структуру41 2.3 Доказательства эквивалентности преобразования запросов к запросам, допускающим параллельное исполнение.

2.4. Исследование возможности параллельного исполнения модифицированных запросов.

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

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

ГЛАВА 3. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ ЗАПРОСОВ ДЛЯ

ПАРАЛЛЕЛЬНОГО ИСПОЛНЕНИЯ.

3.1 Алгоритм для преобразования запросов с использованием условий фильтрации в инструкции WHERE.

3.2 Алгоритм для преобразования запроса с агрегирующими функциями и оператором группирования атрибутов.

3.3 Алгоритм преобразования запроса с использованием инструкции соединения таблиц JOIN.

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

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

3.6 Применение инструкции ORDER BY при параллельном исполнении запроса.

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

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

ЭФФЕКТИВНОСТИ МЕХАНИЗМА РАСПАРАЛЛЕЛИВАНИЯ ЗАПРОСОВ

4.1 Программная реализация распараллеливания 8(ЗЬ-запросов. Структура, особенности реализации, методика выбора алгоритма преобразования

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

4.3 Результаты экспериментального исследования распараллеливания запросов.

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

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

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

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

В настоящее время СУБД используются практически во всех сферах человеческой деятельности, связанных с хранением и переработкой информации. Прогресс, достигнутый в области технологий баз данных, в значительной мере базируется на реляционной модели, предложенной Э. Коддом [57] на рубеже 60-х - 70-х годов XX века. За свою тридцатилетнюю историю реляционные СУБД прошли путь от научно-исследовательских прототипов, наиболее значительными из которых являются System R [18, 43] и Ingres [91, 89], до коммерческих продуктов, способных хранить и обрабатывать терабайты информации. Однако научная и практическая деятельность человека выдвигает все новые масштабные задачи, требующие обработки сверхбольших баз данных.

Анализируя существующие методы работы с данными, можно прийти к выводу, что они не в полной мере отвечают всем предъявляемым к ним в настоящий момент требованиям. Об этом, в частности, свидетельствуют интенсивные научные исследования в области баз данных, проводимые в настоящее время в России и за рубежом [13, 73].

Возникновение сверхбольших баз данных связано с расширением видов и сфер применения СУБД. Примерами новых приложений баз данных являются электронная коммерция [72], электронные библиотеки [14, 63], геоинформационные системы [39], мультимедийные архивы [76], научные базы данных [48, 92].

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

Фактически, единственным известным на сегодняшний день эффективным решением проблемы хранения и обработки сверхбольших баз данных является использование параллельных систем баз данных [61, 47] с репликацией хранящейся информации, обеспечивающих параллельную обработку запросов на многопроцессорных вычислительных системах.

Интенсивные научные исследования в области параллельных СУБД были начаты в 80-х годах. В течение последних двух десятилетий параллельные системы баз данных проделали путь от научно-исследовательских прототипов к полнофункциональным коммерческим продуктам, поставляемым на рынок высокопроизводительных информационных систем. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести целый ряд продуктов - DB2 Parallel Edition [11], NonStop SQL [37] и NCR Teradata[21]. Однако стоимость такого специализированного программного обеспечения для данных систем сопоставима, а в некоторых случаях и выше стоимости аппаратной составляющей.

Подобные системы объединяют сотни процессоров и жестких дисков и способны обрабатывать базы данных в десятки терабайт. Тем не менее, в области параллельных систем баз данных до сих пор остается ряд направлений, требующих дополнительных научных исследований [97, 10]. Одно из них -дальнейшее развитие методов оптимизации запросов для исполнения в составе параллельных и распределенных систем баз данных. Кроме того, многими исследователями справедливо указывается на ограничения в масштабируемости большинства существующих параллельных баз данных из-за ограничений, присущих архитектуре систем, поддерживающих их работу [20]. При большом количестве процессоров в системах такого рода начинают возникать конфликты доступа к разделяемой памяти, что может привести к серьезной деградации общей производительности системы [95]. В соответствии с этим реальная масштабируемость так называемых SMP систем ограничивается 32 процессорами [98].

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

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

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

Диссертационная работа выполнена в рамках научного направления Воронежского государственного технического университета - «Вычислительные системы и программно-аппаратные электротехнические комплексы».

Цель работы:

Целью работы является разработка методов параллельного исполнения БОЬ-запросов в гетерогенных архитектурах для повышения производительности распределенных СУБД.

Задачи исследования:

Исходя из указанных целей исследования, его основными задачами являются:

1. Выполнить анализ современных архитектур СУБД и методов, применяемых в них для параллельного исполнения БС^Ь-запросов, обобщить анализ современного состояния исследований в области применения методов параллельной обработки запросов.

2. Разработать эффективные методы распараллеливания запросов в гетерогенных средах с доказательством их корректности.

3. Разработать алгоритмы и программные средства для параллельного исполнения БС)Ь-запросов, обеспечить их совместимость с существующими СУБД.

4. На основе полученных результатов реализовать систему для распараллеливания запросов и провести вычислительный эксперимент, используя разработанные методы и алгоритмы. Методы исследования:

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

Научная новизна работы:

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

• метод параллельного исполнения 8(^Ь-запросов, ориентированный на использование источников данных, не поддерживающих параллелизм в гетерогенных средах, отличительной особенностью которого является динамическое разделение отношений запроса на диапазоны обработки;

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

• априорные оценки эффективности распараллеливания запросов, отличающиеся учетом особенностей исполнения запросов в гетерогенных системах с репликацией данных, и позволяющие быстро оценить целесообразность применения созданного метода распараллеливания БС^Ь-запросов на этапе конфигурирования системы;

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

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

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

Реализация и внедрение результатов работы. Теоретические и практические результаты работы реализованы в специальном программном комплексе исполнения аналитических запросов в рамках системы автоматизации предприятия. С его использованием разработана программа "Учет потребления электроэнергии абонентами юридическими лицами", которая внедрена в практическую деятельность ОГУП "Западные межрайонные электрические сети" (г. Елец) и зарегистрирована в Государственном фонде алгоритмов и программ [31].

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

Основные результаты работы докладывались и обсуждались на Международной научно-практической конференции «Единое информационное пространство» (Днепропетровск, 2003); ИХ - X Международных открытых научных конференциях «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях» (Воронеж, 2003-2005); XI Всероссийской научно-методической конференции «Телема-тика'2004» (Санкт-Петербург, 2004); II Всероссийской научно-технической конференции «Вузовская наука - региону» (Вологда, 2004); VIII Международной научно-практической конференции «Актуальные проблемы информатики и информационных технологий» (Тамбов, 2004).

Публикации:

Основные результаты диссертации опубликованы в 11 научных работах. Список работ включен в список литературы.

Структура и объем работы:

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

Выводы к главе 4

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

В результате проведенного анализа времени исполнения запросов получены следующие выводы:

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

3. Получены априорные оценки общего времени параллельного исполнения преобразованных 8С)Ь-запросов.

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

5. Экспериментальное исследование разработанного метода для распараллеливания 8С>Ь-запросов подтвердило его эффективность на системах с различной конфигурацией.

6. С использованием метода распараллеливания БС^Ь-запросов создана программа для ОГУП «Западные межрайонные электрические сети» (г.

Елец), входящая в состав системы автоматизации работы предприятия, обеспечивающая исполнение аналитических запросов.

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

2. Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы.

4. М.: Издательский дом «Вильяме», 2000. -С. 384.

5. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. -СПб.: БХВ-Петербург, 2002. 608 с.

6. Волков В.В. Тесты ТРС // СУБД. -1995. -№2. -С. 70-78.

7. Вьейра P. SQL Server 2000. Программирование. Часть 1, изд. -М.: Бином, 2004. 736 с.

8. Вьейра P. SQL Server 2000. Программирование. Часть 2, изд. -М.: Бином, 2004. 808 с.

9. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. -М. «Вильяме», 2003. 1088 С.

10. Дейт К. Дж. Введение в системы баз данных. -М. Вильяме, 2000 — 846 с.

11. Зильбершатц А. Стоунбрейкер М, Ульман Д. Базы данных: достижения и перспективы на пороге 21-го столетия // СУБД. -1996. -№3. -С. 103117.

12. Игнатович Н. Семейство реляционных баз данных IBM DB2 // СУБД. -1997. -№2. -С. 5-17.

13. Кнут Д.Э. Искусство программирования, т. 3. Сортировка и поиск, 2-е изд. -М.: Издательский дом «Вильяме», 2000. -832 с.

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

15. Когаловский М.Р., Новиков Б.А. Электронные библиотеки новый класс информационных систем // Программирование. -2000. -№3. -С. 3-8.

16. Коннолли Т., Бегг К, Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и практика. М.: Вильяме, 2000. -1120 с.

17. Корнеев В.В. Архитектуры с распределенной разделяемой памятью // Открытые системы. -2001. -№3. -С. 15-23.

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

19. Кузнецов С Д. Развитие идей и приложений реляционной СУБД System R // Сб. Итоги науки и техники. Вычислительные науки. -Т.1. -М/.ВИНИТИ, 1989. -С. 3-75.

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

21. Кузьминский М. Архитектура S2MP свежий взгляд на cc-NUMA// Открытые системы. - 1997. № 2. -С. 14-21.

22. Лисянский К, Слободяников Д. СУБД Teradata для ОС UNIX // СУБД. -• 1997.-№5-6.-С. 25-46.

23. Локшин М.В. Модификация деревьев разбора для параллельного исполнения запроса. // Успехи современного естествознания. — 2004. №10. -С. 70-71.

24. Локшин М.В., Кравец О.Я. Построение систем для параллельной обработки запросов к СУБД. // Телематика'2004: Труды XI Всероссийской научно-методической конференции (7-10 июня 2004). -СПб:ИТМО.2004. -С. 94-95.

25. Мамаев Е. Шкарина Л., Microsoft SQL Server 2000 для профессионалов. -СПб: Питер2001. 1088 с.

26. Никитина Г. SQL Server и кластеры // СУБД. -1997. -№3. -С. 65-71.

27. Оззу Т., Валдуриз П. Распределенные и параллельные системы баз данных // СУБД. -1996. -№4. -С. 4-26.

28. Соколинский Л. Б. Методы организации параллельных систем баз данных на вычислительных системах с массовым параллелизмом. Диссертация доктора физико-матаематических наук. - Челябинск, 2003. - 247 с.

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

30. Хаманн Ф. Отказоустойчивая операционная система Tandem NonStop Kernel // Открытые системы. -1997. -№3. -С. 32-36.

31. Хендерсон К. Профессиональное руководство по Transact-SQL, изд. -СПб.: Издательство «Питер Пресс», 2005. -560 с.

32. Цветков В.Я. Геоинформационные системы и технологии. -М.: Финансы и статистика, 1998.

33. Чаудхари С. Методы оптимизации запросов в реляционных системах // СУБД. -1998. -№3. -С. 22-36.

34. Amza С., et al. ThreadMarks: Shared Memory Computing on Networks of Workstations // IEEE Computer. -1996. -Vol. 29, No. 2. -P. 18-28.

35. Astrakan M.M., et al. System R: Relational Approach to Database Management // ACM Transactions on Database Systems. -1976. -Vol. 1, No. 2. -P. 97-137.

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

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

38. Bernstein P.A., et al. The Asilomar Report on Database Research // ACM SIGMOD Record. -1998. -Vol. 27, No. 4. -P. 74-80.

39. Brobst S., Robertson O. Taming Data Giants // DBMS №2. -1997. -C. 3849.

40. Brown P., Stonebraker M. BigSur: A System For the Management of Earth Science Data // VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. -Morgan Kaufmann, 1995. -P. 720-728.

41. Bruno N., Chaudhuri S. Exploiting Statistics on Query Expressions for Optimization // Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 June 2, 2002. -ACM Press, 1989. -P. 98-109

42. Bruno N., Chaudhuri S., Gravano L. Top-k selection queries over relational databases: Mapping strategies and performance evaluation // TODS 27(2), 2002-P. 153-187.

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

44. Carter J., Wegman M. Universal classes of hash functions. Journal of Computer and System Sciences, 1979, № 18. -P. 143-154.

45. Chaudhuri S., Shim K. Including Group-by in Queiy Optimization // VLDB'94, Proceedings of 20th International Conference on Veiy Large Data

46. Bases, September 12-15, 1994, Santiago de Chile, Chile. -Morgan Kaufmann, 1994. -P. 354-366.

47. Chaudhuri S., Shim K. An Overview of Cost-based Optimization of Queries with Aggregates // Bulletin of the Technical Committee on Data Engineering. -1995,-Vol. 18, No. 3.-P. 3-9.

48. 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. -P. 416-428.

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

50. Codd E.F. A Relational Model of Data for Large Shared Data Banks // Communications of the ACM. -1970. -Vol. 13, No. 6. -P. 377-387.

51. Copeland G.P., Keller T. A Comparison Of High-Availability Media Recovery Techniques // Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 June 2, 1989. -ACM Press, 1989. -P. 98-109.

52. Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries

53. That Contain Nested Subqueries, Aggregates, and Quantifiers. // VLDB'87,

54. Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. -Morgan Kaufmann, 1987. -P. 197-208.

55. Fox E.A., Akscyn R.M., Furuta R.K., Leggett J.J. Digital libraries // Communications of the ACM. -1995. -Vol. 38, No. 4. -P. 22-28.

56. Garcia-Molina H., Labio W., Yang J. Fast Incremental Maintenance of Approximate Histograms I I VLDB'98, Proceedings of 24th International Conference on Very Large Data Bases, August 25-29, 1998, New York, USA. -Morgan Kaufmann, 1997. -P. 500-511.

57. Gibbons P. Matias Y. Poosala V. Fast Incremental Maintenance of Approximate Histograms // VLDB'97, Proceedings of 23th International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greese. -Morgan Kaufmann, 1993. -P. 466-475.

58. 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.-P. 102-111.

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

60. Ibaraki T. and Kameda. T. On the Optimal Nesting Order for Computing N-Relation Joins // ACM Transactions on Database Systems. -1984, -Vol. 9, No. 3. -P. 482-502.

61. Ioannidisy Y. Poosala V. Histogram-Based Solutions to Diverse Database Estimation Problems // Bulletin of the Technical Committee on Data Engineering. -1995, -Vol. 18, No. 3. -P. 10-18.

62. Kalakota R,, Whinston A. Readings in Electronic Commerce. -Addison-Wesley, 1997.

63. Kim W. On Optimizing an SQL-like Nested Query // ACM TODS, Vol. 9, No. 3, 1982.

64. Lu G. Multimedia Database Management System. -Artech House, 1999.

65. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Local Queries // Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. -ACM Press, 1986. -P. 84-95.

66. Neumann T., Moerkotte G.\ A Combined Framework for Grouping and Order Optimization. // VLDB'04, Proceedings of 30th International Conference on Very Large Data Bases, August 31-September 3, 2004, Toronto, Canada. -Morgan Kaufmann, 2004. -P. 960-971.

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

68. Palermo F. A Data Base Search Problem // J.T. Tou (ed.). Information System: COINS IV New York, N.Y.:Plenum Press, 1974.

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

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

71. Rosenthal A., Galindo-Legaria C. Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 2325, 1990. -ACM Press, 1990. -P. 291-299.

72. Shekhar S., Srivastava J., Dutta S.: A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. 457-467, VLDB 1988.

73. Sismanis Y., Roussopoulos.: The Complexity of Fully Materialized Coalesced Cubes. // VLDB'04, Proceedings of 30th International Conference on Very Large Data Bases, August 31-September 3, 2004, Toronto, Canada. -Morgan Kaufmann, 2004. -P. 540-551.

74. Stonebraker M. Retrospection on a Database System // ACM Transactions On Database Systems. -1980. -Vol. 5, No. 2. -P. 225-240.

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

76. Stonebraker M., et al. The Design and Implementation of INGRES // ACM Transactions On Database Systems. -1976. -Vol. 1, No. 3. -P. 189-222.

77. Stonebraker M., Frew J., Gardeis K., Meredith J. The Sequoia 2000 Benchmark // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. -ACM Press, 1993.-P. 2-11.

78. TCP Benchmark D Standard Specification Revision 2.1 http://www.tpc.org

79. Thakkar S. S., Sweiger M. Performance of an OLTP Application on Symmetry Multiprocessor System // Proc. of the 17th Annual Int. Symposium on Computer Architecture. Seattle, WA, June 1990. IEEE Computer Society Press, 1990.-P. 228-238.

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

81. Valduriez P. Parallel Database Systems: the Case for Shared-something // Proc. of the 9th Int. Conf. on Data Engineering, April 19-23, 1993, Vi-enna, Austria. IEEE Computer Society, 1993. - P. 460-465.

82. Yang H.Z., Larson P.A. Query Transformation for PSJ-queries // VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. -Morgan Kaufmann, 1987. -P. 245-254.

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