автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Метод поиска оптимального плана выполнения запросов к базам данных на основе нисходящей стратегии

ВВЕДЕНИЕ.

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

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

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

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

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

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

1.3.3. Нисходящий подход Exodus и Volcano.

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

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. Методы поиска оптимального плана на основе нисходящей стратегии.

2.2.1. Анализ механизма отсечения групп.

2.2.2. Метод увеличения стоимости мультивыражения.

2.2.3. Метод генерации пространства поиска без декартовых произведений.

2.3. Оценка эффективности разработанных методов поиска оптимального плана на основе нисходящей стратегии.

2.3.1. Качественный анализ разработанного алгоритма нисходящей стратегии поиска.

2.3.2. Оценка числа альтернативных деревьев поиска.

2.3.3. Оценка числа мультивыражений в шешо-структуре.

2.3.4. Оценка преимуществ использования memo-структуры для представления пространства поиска.

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. Эффективность методов Ml и М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. Использование разработанного оптимизатора и методики оценки времени выполнения запросов для анализа системы «Cybiko PDBS».

4.4.1. Описание исследуемой системы.

4.4.2. Анализ базового варианта системы.

4.4.3. Усовершенствование системы.

4.5. Выводы.

Актуальность темы. В настоящее время при разработке информационных систем широко используются системы управления базами данных (СУБД) на основе реляционной модели данных. Одной из составных частей этой модели являются методы оптимизации запросов, позволяющие анализировать множества альтернативных планов выполнения запросов и выбирать оптимальные планы их реализации.

Разработка эффективного оптимизатора запросов в составе СУБД остаётся одной из наиболее важных задач. Это позволяет существенно уменьшить время выполнения запросов в системах разных классов. Например, при принятии решений в системах организационного управления выполняются SQL-запросы, соединяющие несколько десятков таблиц. При этом существующие оптимизаторы в основном используют эвристические методы, что может приводить к выбору неоптимального плана выполнения запросов. Часто запросы выполняются часами. Другой класс систем, системы оперативной обработки информации, характеризуются большим числом клиентов и наличием дорогостоящей техники, обрабатывающий большой поток запросов. Уменьшение времени выполнения запросов для таких систем позволяет увеличить нагрузочную способность и сократить число единиц дорогостоящей техники.

Практика показывает, что подходы, используемые для оптимизации простых запросов в системах оперативной обработки информации, оказываются не столь эффективными для сложных аналитических запросов, выполняемых в системах организационного управления. Причиной этого является то, что восходящая стратегия оптимизации, разработанная более 15 лет назад для оптимизатора системы System R и не претерпевшая с тех пор значительных изменений, имеет один принципиальный недостаток, который ограничивает её применение для оптимизации сложных запросов: перед генерацией первого плана некоторой группы, оптимизируются все её дочерние группы. При этом нет возможности избежать генерации мультивыражений в группах, которые не являются частью оптимального плана, на основе информации, получаемой с верхнего уровня. В последние годы была предложена нисходящая стратегия оптимизации, позволяющая преодолеть недостаток восходящего подхода за счёт использования верхних и нижних границ стоимости для отсечения групп планов. Это делает её более перспективной для дальнейшего развития, однако в существующей реализации нисходящей стратегии оптимизации вероятность срабатывания механизма отсечения групп невелика, что обесценивает её преимущества. Поэтому разработка метода поиска оптимального плана, позволяющих использовать преимущества нисходящей стратегии и уменьшить время анализа пространства поиска за счёт сокращения числа рассматриваемых альтернативных планов, является актуальной задачей.

Цель работы. Целью работы является разработка новых методов поиска оптимального плана на основе нисходящей стратегии анализа альтернативных планов и использование полученных теоретических результатов при разработке оптимизатора запросов к СУБД.

В работе решены следующие задачи:

1) выполнен критический анализ существующих методов оптимизации выполнения запросов,

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

3) разработан оптимизатор запросов, реализующий предложенные методы нисходящей стратегии поиска,

4) проведён анализ эффективности предлагаемых методов поиска оптимального плана с помощью разработанного оптимизатора запросов,

5) выполнено исследование процесса обработки запросов в реальной вычислительной системе на этапе её реорганизации.

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

Предмет исследований. Предметом исследований настоящей работы являются процессы оптимизации запросов пользователей системами управления базами данных.

Научная новизна. В работе получены следующие новые научные результаты:

1) разработан новый метод поиска оптимального плана с использованием нисходящей стратегии анализа альтернативных планов, позволяющий уменьшить время поиска за счёт рационального выбора верхней и нижней границ стоимости выражений в шешо-структуре,

2) предложен метод генерации пространства поиска, который позволяет определить все логически эквивалентные мультивыражения, описывающие альтернативные планы выполнения запроса, и исключить все планы, содержащие декартовы произведения,

3) получены формулы для оценки вероятности отсечения планов, содержащих декартовы произведения,

4) выведены формулы для оценки числа альтернативных деревьев поиска и необходимых для их представления мультивыражений в шешо-структуре для различных типов деревьев поиска и топологий запросов,

5) получены формулы для оценки стоимостей операций соединения таблиц базы данных методом вложенных циклов и методом сортировки и слияния, учитывающие наличие и тип индексов по столбцам соединения, а также объём доступной оперативной памяти;

Методы исследования. Исследования проводились на основе комплексного использования теории реляционных баз данных, теории множеств, теории вероятности, теории графов, комбинаторики и теории формальных языков.

Практическая ценность полученных результатов. В работе для практического использования полученных результатов разработан оптимизатор запросов, реализующий предложенные методы и алгоритмы нисходящей стратегии поиска. Оптимизатор позволяет задавать различные наборы логических и физических операторов, правил генерации и ограничений пространства поиска, анализировать эффективность использования индексов по различным атрибутам таблиц, прогнозировать время выполнения запросов к СУБД. Он может быть использован для исследования процесса обработки запросов в реальных вычислительных системах на этапах реорганизации и модернизации.

Внедрение результатов исследований. Разработанный оптимизатор запросов использован в качестве программного компонента при проектировании специальной системы управления базами данных для миникомпьюте-ра Сайбико, что позволило уменьшить время выполнения запросов в СУБД в среднем на 40%.

Разработанные методы, методика и оптимизатор запросов использованы в процессе исследования процесса обработки запросов в системе «Cybiko PDBS» на этапе её реорганизации с целью прогнозирования характеристик функционирования системы при добавлении к ней подсистемы поддержки принятия решений. Проанализированы планируемые запросы к СУБД, учитывающие сложный характер задач указанной подсистемы, и содержащие большое количество операторов соединения, агрегации и сортировки. В результате получены оценки времени выполнения этих запросов к СУБД. Для двух запросов получено время выполнения, превышающее установленный десятисекундный предел. Для устранения этих «узких мест» было предложено использовать индексы по столбцам соединения и сортировки. Анализ оптимизированного варианта системы показал, что время выполнения всех тестовых запросов не превышает установленные в требованиях к системе ограничения.

Публикации по теме работы. По материалам работы опубликовано 7 печатных работ.

Апробация работы. Материалы работы были изложены автором на следующих конференциях и семинарах:

1) Теоретическая конференция компании Сайбико, М., 2002.

2) НТС кафедры ИУ-5, МГТУ им. Н.Э. Баумана, М., 2003.

Структура диссертационной работы. В первой главе «Анализ существующих методов построения оптимизаторов запросов» приведено описание процесса обработки запросов в СУБД, выделены и проанализированы компоненты ядра СУБД, участвующие в обработке запросов пользователей. Выделены аспекты, определяющие процесс оптимизации запросов, приведена общая классификация подходов к оптимизации запросов, реализуемых в современных СУБД. Проведён анализ основных подходов к оптимизации запросов с точки зрения реализуемых стратегий поиска оптимального плана выполнения запроса. Проведён анализ существующих методов оценки стоимости операции соединения таблиц базы данных.

Во второй главе «Методы повышения эффективности нисходящей стратегии поиска» проведен анализ алгоритма нисходящей стратегии поиска, выполнено сравнение алгоритмов нисходящей и восходящей стратегий поиска. Разработаны новые методы поиска оптимального плана на основе нисходящей стратегии, позволяющие увеличить вероятность отсечения групп. Доказаны лемма и теорема, определяющие эффективный метод генерации пространства поиска с использованием нисходящей стратегии поиска. Получены формулы для оценки числа альтернативных деревьев поиска и необходимых для их представления мультивыражений в шешо-структуре для различных типов деревьев поиска и топологий запросов. На их основе проведена оценка предлагаемых методов поиска на основе нисходящей стратегии. Предложена стоимостная модель для операций соединения таблиц базы данных методом вложенных циклов и методом сортировки и слияния.

В третьей главе «Разработка оптимизатора запросов с нисходящей стратегией поиска» предложена формализованная модель процесса оптимизации запросов, на основе модели разработаны архитектура и логический проект оптимизатора запросов, реализующего предложенные методы нисходящей стратегии поиска, предложена методика использования оптимизатора запросов для прогнозирования времени выполнения запросов СУБД.

В четвертой главе «Использование разработанного оптимизатора запросов для анализа эффективности предложенных методов поиска оптимального плана и при разработке программных продуктов компании Сайби-ко» приведены результаты исследования эффективности предложенных методов поиска на основе нисходящей стратегии, описано использование оптимизатора запросов при разработке специальной СУБД для миникомпью-тера Сайбико, а также рассмотрены результаты исследований системы «Cybiko PDBS» с помощью разработанного оптимизатора запросов.

4.5. ВЫВОДЫ

1) Проведены практические исследования эффективности предложенных в работе методов поиска оптимального плана на основе нисходящей стратегии анализа альтернативных планов, показавшее эффективность предложенных методов и подтвердившее полученные теоретические результаты.

2) Проведено сравнение эффективности механизма отсечения групп и метода применения эвристик, используемого восходящими оптимизаторами, показавшее, что механизм отсечения групп гарантирует получение оптимального результата и в некоторых случаях является более эффективным.

3) Проведено исследование влияния числа соединяемых в запросе таблиц на размеры пространства поиска, показавшее, что эффект от использования различных методов ограничения пространства поиска практически не зависит от числа соединяемых таблиц.

4) Проведён анализ адекватности оценок времени выполнения запросов, получаемых с помощью разработанного оптимизатора, на основе тестов ТРС-Н, показавший, что погрешность предлагаемого метода для тестовых запросов составляет не более 30-35%.

5) Приведены результаты использования разработанного оптимизатора запросов при разработке СУБД для миникомпьютера Сайбико, позволившее уменьшить время выполнения запросов в СУБД в среднем на 40%.

6) Проведёно исследование процесса обработки запросов в системе Cybiko PDBS на этапе её реорганизации с целью прогнозирования характеристик функционирования системы при добавлении к ней подсистемы поддержки принятия решений.

7) Выявлены запросы, время реакции на которые превышает установленные пределы, и предложены методы устранения этих «узких мест», основанные на использовании индексов по столбцам соединения и сортировки.

8) Использование разработанного оптимизатора запросов в проектно-конструкторской деятельности компании Сайбико позволило сократить затраты на проведение опытно-конструкторских работ и уменьшить проектные риски на стадии реализации проектов при разработке собственной СУБД и подсистемы поддержки принятия решений системы Cybiko PDBS.

166

ЗАКЛЮЧЕНИЕ

В качестве основных результатов работы определены следующие положения:

1. Предложен новый метод поиска оптимального плана с использованием нисходящей стратегии анализа альтернативных планов, позволяющий уменьшить время поиска за счёт рационального выбора верхней и нижней границ стоимости мультивыражений в анализируемых группах отношений.

2. Разработан метод генерации пространства поиска, который позволяет определить все логически эквивалентные мультивыражения, описывающие альтернативные планы выполнения запроса, и исключить все планы, содержащие декартовы произведения.

3. Выведены формулы для оценки числа альтернативных деревьев поиска и необходимых для их представления мультивыражений для различных типов деревьев поиска и топологий запросов. На их основе получены формулы для оценки вероятности отсечения планов, содержащих декартовы произведения.

4. Получены формулы для оценки стоимости операций соединения таблиц базы данных методом вложенных циклов и методом сортировки и слияния, учитывающие наличие и тип индексов по столбцам соединения, а также объём доступной оперативной памяти.

5. На основе предложенных методов поиска оптимального плана разработан оптимизатор запросов, позволяющий задавать различные логические и физические операторы, правила генерации и ограничения пространства поиска, а также анализировать эффективность использования индексов по различным атрибутам таблиц и прогнозировать время выполнения запросов СУБД.

6. С помощью разработанного оптимизатора запросов выполнен анализ эффективности предложенных методов поиска оптимального плана, который показал, что метод отсечения групп гарантирует получение оптимального результата и в ряде случаев имеет преимущества по сравнению с эвристическими методами ограничения пространства поиска.

7. Разработанный оптимизатор запросов использован в качестве программного компонента при проектировании специальной системы управления базами данных для миникомпьютера Сайбико, что позволило уменьшить время выполнения запросов в СУБД в среднем на 40%.

8. Проведено исследование процесса обработки запросов в системе Cybiko PDBS на этапе её реорганизации с целью прогнозирования характеристик функционирования системы при добавлении к ней подсистемы поддержки принятия решений. Выявлены запросы, время выполнения которых превышает установленные пределы, и предложены методы устранения «узких мест», основанные на использовании индексов по столбцам соединения и сортировки.

168

1. Бобровски С. ORACLE 8: Архитектура. - М.: Лори, 1997. - 210 с.

2. Боггс У., Боггс М. UML и Rational Rose. М.: Лори, 2000. - 580 с.

3. Гребенников Н.А., Постников В.М. Разработка метода и модели оценки времени выполнения запросов пользователей серверами современных СУБД // Информатика и системы управления (Благовещенск). 2002. -№2(4). - С. 12-24.

4. Джексон Г. Проектирование реляционных баз данных для использования с микроЭВМ. М.: Мир, 1991.-252 с.

5. Дрибас В. Реляционные модели баз данных. Минск: Изд-во БГУ, 1982. -192 с.

6. Дэйт К. Дж. Введение в системы баз данных. Киев: Диалектика, 1998. -784 с.

7. Зиндер Е. Критерий выбора современной СУБД как объекта инвестиций для развития предприятия // СУБД (М.). 1995. - № 1. - С. 36-48.

8. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. -М.: Мир, 1978.-844 с.

9. Корн Г., Корн Т. Справочник по математике. — М.: Наука, 1984. — 615 с.

10. Кузнецов С.Д. Введение в СУБД: Часть 1 // СУБД (М.). 1995. - №1. - С. 50-56.

11. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД // Программирование (М.). 1989. - №6. - С. 46-59.

12. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД // Итоги науки и техники. Вычислительные науки. — М., 1989 -С. 76-90.

13. Кузнецов С.Д. Развитие идей и приложений реляционной СУБД System R // Итоги науки и техники. Вычислительные науки. М., 1989 -С. 53-75.14