Введение
Глава 1. Традиционная оптимизация мультизапросов 8
1.1 Введение 8
1.2. Оптимизация мультизапроса 9
1.2.1. Эвристический (Heuristic) алгоритм 10
1.2.2. Динамическое решение при многократной оптимизации запросов 11
1.3. Типовая архитектура системы, в которой применяется СУБД с оптимизатором запросов 13
1.4. Постановка задачи 17
1.5. Выводы 24
Глава 2. Оптимизация однопроцессорной обработки мультизапросов 25
2.1. Введение 25
2.2. Независимая и совместная обработка запросов мультизапроса 25
2.3. Частный алгоритм формирования плана совместной обработки конъюнктивного мультизапроса 26
2.3.1. Время выполнения мультизапроса (2 запроса) 26
2.3.1.1. Неупорядоченые данные для мультизапроса (2 запроса) 27
2.3.1.2. Упорядоченые данные для мультизапроса (2 запроса) 29
2.3.2. Время выполнения мультизапроса (3 запроса) 31
2.3.2.1. Неупорядоченые данные для мультизапроса (3 запроса) 31
2.3.2.2. Упорядоченые данные для мультизапроса (3 запроса) 34
2.4. Общий алгоритм формирования плана совместной обработки конъюнктивного мультизапроса 35
2.5. Формирование плана совместной обработки конъюнктивного мультизапроса для мультизапроса (4 запроса) 37
2.6. Оценка времени выполнения мультизапроса 42
2.7. Выводы 45
Глава 3. Метод оптимизации многопроцессорной обработки мультизапросов 46
3.1. Введение 46
3.2. Степенная зависимость времени обработки элементарных запросов 47
3.2.1. Совместное выполнение запросов мультизапроса. СЗ 47
3.2.2. Несовместное выполнение запросов мультизапроса . СЗ 54
3.2.3. Сравнение совместной и несовместной обработки запросов. СЗ 61
3.3. Линейная зависимость времени обработки элементарных запросов 67
3.3.1. Совместное выполнение запросов мультизапроса. ЛЗ 67
3.3.2. Несовместное выполнение запросов мультизапроса. ЛЗ 72
3.3.3. Сравнение совместной и несовместной обработки запросов. ЛЗ 77
3.4. Выводы 88
Глава 4. Реализация плана выполнения мультизапроса в многопроцессорной базе данных . 89
4.1. Введение 89
4.2. Оценка влияния числа процессоров на время выполнения мультизапроса. 89
4.3. Совместная обработка запросов мультизапроса 90
4.3.1. Алгоритм 1 91
4.3.1.1. Минимальное время выполнения мультизапроса при степенном изменении параметра времени 94
4.3.1.2. Минимальное время выполнения мультизапроса при линейном изменении параметра времени 98
4.3.2. Алгоритм 2 103
4.3.2.1. Минимальное время выполнения мультизапроса при степенном изменении параметра времени 105
4.3.2.2. Минимальное время выполнения мультизапроса при линейном изменении параметра времени 109
4.3.3. Алгоритм 3 114
4.3.3.1. Минимальное время выполнения мультизапроса при степенном изменении параметра времени 116
4.3.3.2. Минимальное время выполнения мультизапроса при линейном изменении параметра времени 120
4.4. Несовместная обработка запросов мультизапроса 125
4.4.1. Минимальное время выполнения мультизапроса для несовместной обработки запросов при степеном изменении параметра времени 125
4.4.2. Минимальное время выполнения мультизапроса для несовместной обработки запросов при линейном изменении параметра времени 129
4.5. Формирование оптимального плана выполнения мультизапроса 134
4.5.1. Формирование оптимального плана выполнения мультизапроса при степенном изменении параметра времени 134
4.5.2. Формирование оптимального плана выполнения мультизапроса при линейном изменении параметра времени 137
4.5. Выводы 141
Основные результаты работы 142
Литература 143
