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

• Автор: Локшин, Марк Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Воронеж
• Количество страниц: 149 с. : ил.

ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

ГЛАВА 2. ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ЗАПРОСОВ С ИСПОЛЬЗОВАНИЕМ ИЗБЫТОЧНОСТИ ДАННЫХ.
2.1 Архитектура системы для параллельного исполнения запросов с
использованием избыточного представления информации
2.2. Декомпозиция запроса с отображением его в древовидную структуру
2.3 Доказательства эквивалентности преобразования запросов к запросам, допускающим параллельное исполнение
2.4. Исследование возможности параллельного исполнения модифицированных запросов
2.5. Априорные оценки времени исполнения запросов
Выводы к главе 2.
ГЛАВА 3. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ ЗАПРОСОВ ДЛЯ ПАРАЛЛЕЛЬНОГО ИСПОЛНЕНИЯ.
3.1 Алгоритм для преобразования запросов с использованием условий фильтрации в инструкции
3.2 Алгоритм для преобразования запроса с агрегирующими функциями и оператором группирования атрибутов.
3.3 Алгоритм преобразования запроса с использованием инструкции соединения таблиц I.
3.4 Алгоритмы для преобразования запросов с использованием ограничений на количество кортежей в инструкции .
3.5 Алгоритм для преобразования запроса с использованием подзапросов
3.6 Применение инструкции при параллельном исполнении
запроса
Выводы к главе 3.
ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕХАНИЗМА РАСПАРАЛЛЕЛИВАНИЯ ЗАПРОСОВ .
4.1 Программная реализация распараллеливания запросов. Структура, особенности реализации, методика выбора алгоритма преобразования
4.2 Проектирование информационной структуры базы данных для проведения тестирования.
4.3 Результаты экспериментального исследования распараллеливания
запросов
Выводы к главе 4
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Основные результаты работы докладывались и обсуждались на Международной научно-практической конференции «Единое информационное пространство» (Днепропетровск, ); ИХ - X Международных открытых научных конференциях «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях» (Воронеж, -); XI Всероссийской научно-методической конференции «Тслема-тика’» (Санкт-Петербург, ); II Всероссийской научно-технической конференции «Вузовская наука - региону» (Вологда, ); VIII Международной научно-практической конференции «Актуальные проблемы информатики и информационных технологий» (Тамбов, ). Основные результаты диссертации опубликованы в научных работах. Список работ включен в список литературы. Работа состоит из введения, четырех глав, заключения, списка литературы, включающего в себя 1 наименование и трех приложений. Основная часть работы изложена на 7 страницах, содержит таблицы и рисунка. АНАЛИЗ СОВРЕМЕННЫХ МЕТОДОВ ОБРАБОТКИ Б(? Данная глава посвящена анализу архитектур современных параллельных систем баз данных и общим вопросам выполнения 8(}Ь-запросов в данных системах. В пункте 1. В пункте 1. При рассмотрении данного вопроса за основу была взята классификация Стоунбрейкера. В пункте 1. Исследование данной величины позволяет оценивать эффективность параллельного исполнения того или иного решения. В пункте 1. СУБД. Особое внимание уделяется существующим алгоритмам параллельного исполнения операторов языка 8(}Ь. В пункте 1. В заключительной части главы даются четкие обозначения основных понятий реляционной алгебры, которые в дальнейшем используются в работе. В основе различных классов параллельных систем лежат структурные различия в компоновке различных функциональных элементов, основными из которых являются процессоры и оперативная память. SMP (Symmetric Multiprocessor) - симметричные мультипроцессорные системы (рис. NUMA (Non-Uniform Memory Architecture) - мультипроцессорные системы с неоднородным доступом к памяти (рис. МРР (Massively Parallel Processing) - массово-параллельные системы (рис. Кластеры - наборы полноценных компьютеров, объединенных в единую вычислительную систему. Памяп. Мд ЦПУ Памяп. Рис. SMP архитектуры состоят из небольшого числа процессоров, соединенных посредством шины или коммутатора с общей оперативной памятью. В таких системах время обращения к физически единой общей памяти одинаково для всех процессоров. Поэтому SMP системы относят к классу UMA (Uniform Memory Architecture) [). В силу этого количество процессоров в SMP системе редко превышает [,]. NUMA архитектуры характеризуются наличием физически распределенной оперативной памяти, разделяемой всеми процессорными модулями в качестве единого адресного пространства [, ]. При этом отдельный процессорный модуль может представлять собой SMP систему. Процессорные модули NUMA систем соединяются сетью. При этом для обеспечения унифицированного доступа к разделяемой памяти и синхронизации изменений в кэш-памяти процессоров в каждом процессорном модуле используется специальное устройство []. Системы с NUMA архитектурой могут включать в себя до процессорных модулей с общим числом процессоров до 8. Однако неоднородность доступа к разделяемой оперативной памяти ведет к тому, что при выборке данных из памяти чужого модуля мы будем наблюдать замедление от 0% до 0% в различных NUMA системах [], и эта цифра будет расти с увеличением числа процессорных модулей. В силу этого мы можем говорить только об ограниченной масштабируемости многопроцессорных систем с NUMA архитектурой. Следует заметить, что разница во времени доступа к локальной и удаленной кэш-памяти в различных NUMA системах составляет 0-% []. Поэтому производительность NUMA систем может существенным образом снижаться на приложениях, требующих частой синхронизации данных. В тоже время следует заметить, что различия в скорости доступа к различным участкам памяти в современных архитектурах становятся все менее заметными [8]. МРР архитектуры строятся как совокупность большого числа однородных процессорных модулей, соединенных высокоскоростной сетью [, , 8]. При этом каждый модуль имеет собственную оперативную память и, возможно, собственные диски. Подобные системы могут включать в себя сотни и тысячи процессорных устройств.