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

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

Содержание
Введение

Глава 1 .Традиционная оптимизация мультизапросов

1.1 Введение

1.2. Оптимизация мультизапроса

1.2.1. Эвристический (Heuristic) алгоритм

1.2.2. Динамическое решение при многократной оптимизации запросов

1.3. Типовая архитектура системы, в которой применяется СУБД с оптимизатором запросов

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

1.5. Выводы

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

2.1. Введение
2.2. Независимая и совместная обработка запросов мультизапроса
2.3. Частный алгоритм формирования плана совместной обработки конъюнктивного мультизапроса
2.3.1. Время выполнения мультизапроса (2 запроса)
2.3.1.1. Неупорядоченые данные для мультизапроса (2 запроса)
2.3.1.2. Упорядоченые данные для мультизапроса (2 запроса)
2.3.2. Время выполнения мультизапроса (3 запроса)
2.3.2.1. Неупорядоченые данные для мультизапроса (3 запроса)
2.3.2.2. Упорядоченые данные для мультизапроса (3 запроса)
2.4. Общий алгоритм формирования плана совместной обработки конъюнктивного мультизапроса
2.5. Формирование плана совместной обработки конъюнктивного мультизапроса для мультизапроса (4 запроса)
2.6. Оценка времени выполнения мультизапроса
2.7. Выводы
Глава 3. Метод оптимизации многопроцессорной обработки мультизапросов
3.1. Введение
3.2. Степенная зависимость времени обработки элементарных запросов
3.2.1. Совместное выполнение запросов мультизапроса. СЗ
3.2.2. Несовместное выполнение запросов мультизапроса. СЗ
3.2.3. Сравнение совместной и несовместной обработки запросов. СЗ
3.3. Линейная зависимость времени обработки элементарных запросов
3.3.1. Совместное выполнение запросов мультизапроса. ЛЗ
3.3.2. Несовместное выполнение запросов мультизапроса. ЛЗ
3.3.3. Сравнение совместной и несовместной обработки запросов. ЛЗ
3.4. Выводы

Глава 4. Реализация плана выполнения мультизапроса в многопроцессорной базе данных
4.1. Введение
4.2. Оценка влияния числа процессоров на время выполнения мультизапроса
4.3. Совместная обработка запросов мультизапроса
4.3.1. Алгоритм
4.3.1.1. Минимальное время выполнения мультизапроса при степенном изменении параметра времени
4.3.1.2. Минимальное время выполнения мультизапроса при линейном изменении параметра времени
4.3.2. Алгоритм
4.3.2.1. Минимальное время выполнения мультизапроса при степенном изменении параметра времени
4.3.2.2. Минимальное время выполнения мультизапроса при линейном изменении
параметра времени
4.3.3. Алгоритм
4.3.3.1. Минимальное время выполнения мультизапроса при степенном изменении параметра времени
4.3.3.2. Минимальное время выполнения мультизапроса при линейном изменении параметра времени
4.4. Несовместная обработка запросов мультизапроса
4.4.1. Минимальное время выполнения мультизапроса для несовместной обработки запросов при степеном изменении параметра времени
4.4.2. Минимальное время выполнения мультизапроса для несовместной обработки запросов при линейном изменении параметра времени
4.5. Формирование оптимального плана выполнения мультизапроса
4.5.1. Формирование оптимального плана выполнения мультизапроса при степенном изменении параметра времени
4.5.2. Формирование оптимального плана выполнения мультизапроса при линейном изменении параметра времени
4.5. Выводы
Основные результаты работы
Литература

ililiKI EIEB1 ВЛИП
Введение
Проблеме оптимизации выполнения мультизапроса при обращении к базе данных посвящено большое число публикаций. В качестве критерия оптимизации мультизапросов обычно используют время выполнения запроса, при этом подразделяют время, затрачиваемое на работу с данными, находящимися в оперативной, буферной и внешней памяти. Дополнительными условиями являются объем памяти, число процессоров и др., которые часто задают в виде стоимостных ограничений.
Проблемами создания и оценки качества 003 занимались ряд российских и зарубежных исследователей: Григорьев Ю.А, Кузнецов С.Д, Amol Deshpande, Zacchary Ives, Vijayshankar Raman, Selinger P.G., Astrahan M.M., Chamberlin D.D. и др.
В данной работе в рамках базовой постановки оптимизации мы будем считать, что база данных целиком находится в основной памяти, что наиболее соответствует режимам функционования бортовых баз данных авиационных и космических систем.
Актуальность темы
Основным критерием при определении Плана реализации запроса является время выполнения мультизапроса, которое, вообще говоря, зависит от порядка выполнения элементарных запросов, его составляющих, и от времени проверки в строке и вероятности успеха в строке [36]. Время выполнения элементарного мультизапроса зависит от метода доступа к столбцу таблицы. Существуют два базовых метода: когда данные в столбцах не упорядочены и когда данные в столбцах упорядочены. Известным методом увеличения производительности является использование многопроцессорных бортовых ВС.

Время выполнения конъюнктивного мультизапроса при совместной обработке в соответствии с графом рис. 2.4 равно:
Тсовм = п(р (т4 + рт5 + р 2ХХ + р 2Т2 + Т3 + рт5 )).
Совместная обработка лучше независимой обработки, если справедливо неравенство (4). Числовые условия, когда совместная обработка лучше независимой приведены выше.
Таким образом, условия преимущества (обеспечение меньшего времени) совместной обработки конъюнктивного мультизапроса примера №2 по отношению к независимой обработке совпадают для упорядоченных и неупорядоченных данных.
2.4. Общий алгоритм формирования плана совместной обработки конъюнктивного мультизапроса
Алгоритм совместной обработки запросов конъюнктивного мультизапроса состоит в следующем: определяются подмножества совпадающих элементарных запросов, входящих в запросы конъюнктивного мультизапроса. Таких подмножеств может быть несколько, поэтому среди них выделяется одно по соответствующему критерию. Этому подмножеству соответствует элементарный запрос, который выполняется в первую очередь. Выделенный элементарный запрос удаляется из числа элементарных запросов мультизапроса.
Далее указанная процедура продолжается до тех пор, пока подмножество совпадающих элементарных запросов становится пустым.
В качестве критерия выделения подмножества (элементарного запроса) назовем следующие: номер элементарного запроса; число запросов, в которые входит элементарный запрос (глубина охвата); число элементарных запросов, образующих подмножество (ширина охвата).