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

• Автор: Гребенников, Николай Андреевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 183 с. : ил.

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

ГЛАВА 1. Анализ существующих методов построения оптимизаторов запросов.

1.1. Процесс обработки запросов в СУБД.

1.2. Анализ процесса оптимизации запросов

1.3. Обзор подходов к оптимизации запросов.

1.3.1. Восходящий алгоритм

1.3.2. Восходящий расширяемый алгоритм .

1.3.3. Нисходящий подход x и V

1.3.4. Нисходящий расширяемый подход

1.4. Обзор методов оценки стоимости операции соединения

1.4.1. Стоимостная модель Грэфа
1.4.2. Стоимостная модель Хэрриса
1.4.3. Обзор алгоритмов соединения Мишры и Эйчина
1.4.4. Стоимостная модель Шапиро.
1.5. Выводы
ГЛАВА 2. Методы повышения эффективности нисходящей стратегии поиска.
2.1. Анализ нисходящей стратегии поиска
2.1.1. Внутреннее представление пространства поиска
2.1.2. Алгоритм нисходящей стратегии поиска
2.1.3. Пример использования нисходящей стратегии поиска
2.1.4. Сравнение алгоритмов нисходящей и восходящей стратегий поиска
2.2. Методы поиска оптимального плана на основе нисходящей стратеги и. 4
2.2.1. Анализ механизма отсечения групп
2.2.2. Метод увеличения стоимости мультивыражения
2.2.3. Метод генерации пространства поиска без декартовых произведений
2.3. Оценка эффективности разработанных методов поиска оптимального плана на основе нисходящей стратегии
2.3.1. Качественный анализ разработанного алгоритма нисходящей стратегии поиска.
2.3.2. Оценка числа альтернативных деревьев поиска
2.3.3. Оценка числа мультивыражений в шешоструктурс
2.3.4. Оценка преимуществ использования тсшоструктуры для представления пространства поиска
2.3.5. Количественный анализ разработанных методов поиска оптимального плана на основе нисходящей стратегии
2.4. Метод оценки стоимости операции соединения.
2.4.1. В индекс и хешиндекс.
2.4.2. Соединение методом вложенных циклов
2.4.3. Соединение методом сортировки и слияния
2.5. Выводы.
ГЛАВА 3. Разработка оптимизатора запросов с нисходящей стратегией поиска
3.1. Модель процесса оптимизации запросов.
3.1.1. Модель логических операций.
3.1.2. Модель физических операций
3.1.3. Модель правил генерации пространства поиска.
3.1.4. Стоимостная модель
3.1.5. Стратегия поиска
3.2. Выбор архитектуры оптимизатора запросов.
3.2.1. Компоненты оптимизатора запросов
3.2.2. Входные данные оптимизатора запросов
3.2.3. Выходные данные оптимизатора запросов.
3.3. Разработка модуля поиска оптимального плана.
3.3.1. Главный цикл оптимизации
3.3.2. Структура задач модуля поиска.
3.3.3. Задачи модуля поиска
3.3.4. Применение правил.
3.3.5. Пример работы модуля поиска.
3.4. Разработка интерфейса взаимодействия пользователя с системой
3.5. Методика использования оптимизатора запросов
3.5.1. Назначение методики.
3.5.2. Процедура оценки времени выполнения запроса.
3.5.3. Метод оценки параметров стоимостной модели
3.5.4. Способы применения методики.
3.6. Выводы
ГЛАВА 4. Использование разработанного оптимизатора запросов для анализа эффективности предложенных методов поиска оптимального плана и при разработке программных продуктов компании Сайбико
4.1. Исследование эффективности предложенных методов поиска
4.1.1. Описание условий проведения исследований
4.1.2. Эффективность методов и М2, реализующих механизм отсечения групп
4.1.3. Сравнение механизма отсечения групп и применения эвристик.
4.1.4. Влияние числа соединяемых таблиц на размер пространства поиска.
4.2. Анализ адекватности получаемых результатов
4.2.1. Описание запросов теста ТРСН.
4.2.2. Результаты оптимизации запросов с использованием предложенных методов поиска оптимального плана.
4.3. Использование оптимизатора запросов при разработке СУБД для миникомпьютера Сайбико
4.3.1. Механизм использования оптимизатора в структуре СУБД
4.3.2. Оценка преимуществ от использования оптимизатора запросов.
4.4. Использование разработанного оптимизатора и методики оценки времени выполнения запросов для анализа системы i .
4.4.1. Описание исследуемой системы
4.4.2. Анализ базового варианта системы
4.4.3. Усовершенствование системы
4.5. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Это процесс извлечения данных из базы данных, соответствующих требованиям пользователя. Процесс обработки запросов серверами современных СУБД представлен на рис. Рис. Процесс начинается с разбора поступившего запроса представленного на высокоуровневом языке формирования запросов, например, и преобразования его в дерево запроса, состоящего из операций реляционной алгебры. Затем оптимизатор запросов трансформирует это дерево запроса в план выполнения запроса. И, наконец, модуль выполнения запроса исполняет план выполнения, после чего результаты возвращаются пользователю. В обработке запроса участвуют компоненты ядра СУБД, представленные на рис. Работа модулей разбора запроса, выбора стратегии обработки запроса оптимизатора и выполнения запроса рассмотрена ниже. Процессор языка определения данных, обрабатывающий выражения типа I, и , а также модуль поддержки многопользовательского режима в дальнейшем не рассматриваются. Рис. Этап 1. Лексический и синтаксический анализ текста запроса. Этап 2. Логическая оптимизация запроса. Этап 3. Получение набора альтернативных планов выполнения запроса. Этап 4. Выбор оптимального плана из набора альтернативных планов. Этап 5. Формирование выполняемого представления оптимального плана. Этап 6. Физическое выполнение представления оптимального плана. На этапе 1 выполняется модуль разбора запроса, работа которого представлена на рис. На первом этапе запрос, заданный на языке запросов, подвергается лексическому и синтаксическому анализу. При этом формируется его внутреннее представление, отражающее структуру запроса и содержащее информацию, которая характеризует объекты базы данных, упомянутые в запросе отношения, поля и константы. Информация о хранимых в базе данных объектах выбирается из каталогов базы данных. Текстовая строка запроса
Модуль разбора запроса
Синтаксический анализатор запросов
Препроцессор 1. Рис. На этапах со второго по четвртый выполняется модуль выбора стратегии обработки запроса, работа которого представлена на рис. На втором этапе запрос во внутреннем представлении подвергается логической оптимизации. Могут применяться различные преобразования, улучшающие начальное представление запроса. Среди преобразований могут быть эквивалентные, после проведения которых получается внутреннее представление, семантически эквивалентное начальному например, приведение запроса к некоторой канонической форме. Преобразования могут быть и таким, что получаемое представление не является семантически эквивалентным начальному, но гарантируется, что результат выполнения преобразованного запроса совпадает с результатом запроса в начальной форме при соблюдении ограничений целостности, существующих в базе данных. Рис. Третий этап обработки запроса состоит в построении на основе информации, которой располагает оптимизатор, набора альтернативных процедурных планов выполнения данного запроса в соответствии с его внутрением представлением, полученным на втором этапе. Четвртый этап состоит в выборе оптимального плана из набора альтернативных планов выполнения данного запроса. Для каждого плана, построенного на предыдущем этапе, оценивается предполагаемая стоимость выполнения запроса. Из полученных альтернативных планов выбирается наиболее дешевый, при этом его внутреннее представление соответствует обрабатываемому запросу. На пятом и шестом этапы выполняется модуль выполнения запроса, работа которого представлена на рис. Модуль выполнения запроса
И
Трансляция физического плана . Дисковая
Оперативная
Рис. На пятом этапе по внутреннему представлению оптимального плана выполнения запроса формируется выполняемое представление плана. Это представление может быть программой в машинных кодах, если система ориентирована на компиляцию запросов в машинные коды, или может быть машиннонезависимым, если система ориентирована на интерпретацию запросов. На шестом этапе происходит реальное выполнение запроса по сформированному плану. Это может быть либо выполнение соответствующей подпрограммы, либо вызов интерпретатора с передачей ему управления для интерпретации выполняемого плана.