Оптимизация потоков простых SQL-запросов

• Автор: Зверев, Дмитрий Львович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Санкт-Петербург
• Количество страниц: 169 с. : ил.

Глава 1. Современное состояние проблемы оптимизации ЗрЬ-запросов

1.1. Ход обработки запроса

1.2. Логическая оптимизация

1.3. Семантическая оптимизация

1.4. Построение возможных планов выполнения запроса и выбор оптимального из них

1.5. Выводы

Глава 2. Разработка метода оптимизации

2.1. Оптимизация потоков БСЖ-запросов

2.2. Критерии оптимизации

2.3. Выделение оптимизируемых классов задач и разработка метода оптимизации для них

2.3.1. Каскадные таблицы

2.3.2. Таблицы, зависимые только от одного уровня
2.3.3. Таблицы, имеющие зависимости более чем от одного столбца
2.3.4. Таблицы, имеющие фильтры и обратные зависимости
2.3.5.Таблицы смешанного типа
2.4. Сравнительный анализ предлагаемого метода оптимизации и существующих методов
2.5. Модель системы, реализующей предлагаемый метод оптимизации
2.6. Выводы
Глава 3. Оценка избыточности и времени выполнения при проведении оптимизации
3.1. Параметры, используемые для оценок
3.2. Оценка избыточности данных
3.2.1. Каскадные таблицы
3.2.2. Таблицы, зависимые только от одного уровня
3.3. Оценка времени обработки запросов сервером
3.3.1. Анализ способов доступа к данным
3.3.2. Анализ методов выполнения операции соединения и разработка оценки времени обработки запросов для них
3.3.2.1. Метод вложенных циклов
3.3.2.2. Метод хэш-соединения
3.3.2.3. Метод соединения слиянием
3.3.3. Особые случаи и разработка оценки времени обработки запросов для

3.3.3.1. Использование кластеров
3.3.3.2. Использование материализованных представлений
3.3.3.3. Использование битовых индексов соединения
3.4. Выводы
Глава 4. Разработка метода синтеза запросов
4.1. Этапы проведения синтеза
4.2. Выделение подпотоков запросов, подлежащих оптимизации
4.3. Преобразование множества простых запросов, составляющих выделенный
подпоток, к одному сложному
4.4. Проверка целесообразности преобразования
4.5. Выводы
Заключение
Литература
Приложение 1. Графики зависимостей числа операций ввода/вывода от различных
параметров и алгоритмов обработки, рассматриваемых в работе
Приложение 2. Вывод формулы числа возможных комбинаций при выполнении
операции соединения произвольного числа отношений
Приложение 3. Схема алгоритма проведения первого этаца синтеза
Приложение 4. Акты о внедрении и свидетельство о регистрации в отраслевом фонде алгоритмов и программ
Актуальность темы. В настоящее время для хранения и обработки данных активно используются реляционные базы данных. Размер баз данных, т.е. объем хранимых данных, может варьироваться в широком диапазоне - от килобайтов до терабайтов. Понятно, что чем больше размер отношений базы данных, тем больше уходит времени на поиск нужной информации, т.е. увеличивается время обработки запросов сервером. Кроме того, в последнее время базы данных используются для публикаций данных в интернет. В этом случае количество пользователей базы данных, которые обращаются к ней в данный момент времени, может значительно возрастать. В результате опять нее возрастает нагрузка на сервер. С одной стороны эту проблему пытаются решать увеличением производительности компьютеров, на которых находятся системы управления базами данных (СУБД). Однако, простого увеличения производительности компьютеров, конечно же, недостаточно; часто гораздо большего эффекта можно добиться с помощью изменения алгоритмов обработки БС^Ъ-запросов. Так, например, использование одноуровневых индексов взамен сканирования таблицы, позволяет добиться логарифмической зависимости скорости выполнения запроса от количества занимаемых страниц данных (при сканировании таблицы зависимость линейная). При использовании индексов в виде сбалансированных деревьев получаемый выигрыш еще больше. В то же время, повышение скорости работы внешней памяти дает лишь линейное увеличение производительности обработки запросов.
Таким образом, хотя работы по оптимизации БС)Ь-запросов ведутся уже не одно десятилетие, в настоящее время они вовсе не потеряли актуальности. Напротив, в связи с увеличением темпов роста объема информации и нагрузки на сервер баз данных, такие работы стали еще более актуальны.
Оптимизировать выполнение запросов можно по различным критериям - по скорости выполнения, по загрузке процессора, по объему используемой памяти и т.д. Обычно при оптимизации БС^Ь-запросов, главной целью является минимизация времени выполнения запроса, но поскольку при выполнении конкретного запроса самой дорогостоящей операцией является обращение к диску, то и параметром
Рис 2.4-а) Общий алгоритм обработки до оптимизации