Введение
Глава 1. Анализ существующих методов построения оптимизаторов запросов 11
1.1. Процесс обработки запросов в СУБД 12
1.2. Анализ процесса оптимизации запросов 17
1.3. Обзор подходов к оптимизации запросов 20
1.3.1. Восходящий алгоритм System R 22
1.3.2. Восходящий расширяемый алгоритм Starburst 26
1.3.3. Нисходящий подход Exodus и Volcano 28
1.3.4. Нисходящий расширяемый подход Cascades 30
1.4. Обзор методов оценки стоимости операции соединения 32
1.4.1. Стоимостная модель Грэфа 32
1.4.2. Стоимостная модель Хэрриса 33
1.4.3. Обзор алгоритмов соединения Мишры и Эйчина 34
1.4.4. Стоимостная модель Шапиро 34
1.5. Выводы 35
Глава 2. Методы повышения эффективности нисходящей стратегии поиска 37
2.1. Анализ нисходящей стратегии поиска 38
2.1.1. Внутреннее представление пространства поиска 38
2.1.2. Алгоритм нисходящей стратегии поиска 41
2.1.3. Пример использования нисходящей стратегии поиска 45
2.1.4. Сравнение алгоритмов нисходящей и восходящей стратегий поиска..46
2.2. Методы поиска оптимального плана на основе нисходящей стратегии ...48
2.2.1. Анализ механизма отсечения групп 48
2.2.2. Метод увеличения стоимости мультивыражения 52
2.2.3. Метод генерации пространства поиска без декартовых произведений..54
2.3. Оценка эффективности разработанных методов поиска оптимального плана на основе нисходящей стратегии 64
2.3.1. Качественный анализ разработанного алгоритма нисходящей стратегии поиска 64
2.3.2. Оценка числа альтернативных деревьев поиска 67
2.3.3. Оценка числа мультивыражений в memo-структуре 73
2.3.4. Оценка преимуществ использования memo-структуры для представления пространства поиска 79
2.3.5. Количественный анализ разработанных методов поиска оптимального плана на основе нисходящей стратегии 81
2.4. Метод оценки стоимости операции соединения 83
2.4.1. В+ индекс и хеш-индекс 84
2.4.2. Соединение методом вложенных циклов 86
2.4.3. Соединение методом сортировки и слияния 89
2.5. Выводы 94
Глава 3. Разработка оптимизатора запросов с нисходящей стратегией поиска 95
3.1. Модель процесса оптимизации запросов 96
3.1.1. Модель логических операций 99
3.1.2. Модель физических операций 102
3.1.3. Модель правил генерации пространства поиска 106
3.1.4. Стоимостная модель 109
3.1.5. Стратегия поиска 111
3.2. Выбор архитектуры оптимизатора запросов 114
3.2.1. Компоненты оптимизатора запросов 114
3.2.2. Входные данные оптимизатора запросов 116
3.2.3. Выходные данные оптимизатора запросов 117
3.3. Разработка модуля поиска оптимального плана 118
3.3.1. Главный цикл оптимизации 120
3.3.2. Структура задач модуля поиска 121
3.3.3. Задачи модуля поиска 121
3.3.4. Применение правил 128
3.3.5. Пример работы модуля поиска 130
3.4. Разработка интерфейса взаимодействия пользователя с системой 133
3.5. Методика использования оптимизатора запросов 135
3.5.1. Назначение методики 135
3.5.2. Процедура оценки времени выполнения запроса 136
3.5.3. Метод оценки параметров стоимостной модели 137
3.5.4. Способы применения методики 138
3.6. Выводы 142
Глава 4. Использование разработанного оптимизатора запросов для анализа эффективности предложенных методов поиска оптимального плана и при разработке программных продуктов компании Сайбико ...143
4.1. Исследование эффективности предложенных методов поиска 144
4.1.1. Описание условий проведения исследований 144
4.1.2. Эффективность методов Ml и М2, реализующих механизм отсечения групп 146
4.1.3. Сравнение механизма отсечения групп и применения эвристик 148
4.1.4. Влияние числа соединяемых таблиц на размер пространства поиска. 149
4.2. Анализ адекватности получаемых результатов 150
4.2.1. Описание запросов теста ТРС-Н 150
4.2.2. Результаты оптимизации запросов с использованием предложенных методов поиска оптимального плана 152
4.3. Использование оптимизатора запросов при разработке СУБД для миникомпьютера Сайбико 156
4.3.1. Механизм использования оптимизатора в структуре СУБД 156
4.3.2. Оценка преимуществ от использования оптимизатора запросов 157
4.4. Использование разработанного оптимизатора и методики оценки времени выполнения запросов для анализа системы «Cybiko PDBS»... 159
4.4.1. Описание исследуемой системы 159
4.4.2. Анализ базового варианта системы 161
4.4.3. Усовершенствование системы 162
4.5. Выводы 164
Заключение 166
Литература 168
