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

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

:

Проблема повышения производительности систем управления базами данных (СУБД) в настоящее время продолжает оставаться актуальной. Увеличение количества пользователей, работающих с базой данных и возрастание объемов обрабатываемой информации, требует соответствующего повышения быстродействия баз данных для обеспечения приемлемого времени реакции на пользовательский запрос [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. С использованием метода распараллеливания БС^Ь-запросов создана программа для ОГУП «Западные межрайонные электрические сети» (г.

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