Выбор плана выполнения SQL-запроса в современной реляционной СУБД производится путем оптимизации его стоимости. Чем меньше стоимость, тем меньше время выполнения запроса. Стоимость вычисляется на основе сложной математической модели, основанной на многих допущениях и параметрах. Допущения выполняются не всегда. Таким образом, если требуется, чтобы запрос выполнялся с заданным временем ответа, необходимо:

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

Обеспечение условий для выбора одного из таких планов выполнения и составляет задачу настройки реляционной системы баз данных. Часть средств настройки компонент системы баз данных являются автоматическими, составляя основу для построения самонастраиваемых систем баз данных. Часть средств требует участия администратора системы. Разница между ними весьма условна — развитие способов настройки с участием администратора системы может способствовать совершенствованию средств автоматической настройки, и наоборот. Так, в 2003 году в статье [2] Волкер Маркл были описаны поправки (Adjustments) для оценок стоимости, используемые самонастраиваемым оптимизатором LEO в DB2. Идея поправок была использована Вольфганом Брейтлингом при разработке нового метода настройки для СУБД Oracle с участием администратора системы на основе обратной связи по мощности выборки (Cardinality Feedback). В 2008 году на основе опыта использования этого метода в СУБД Oracle был реализован механизм автоматического уточнения мощности выборки [7], схожий с механизмом поправок оптимизатора LEO.

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

1. Самонастраиваемые системы баз данных. Современные СУБД содержат развитую систему средств автоматической настройки своих компонент и структур. Их активная разработка началась после получения в 1997 году первых технических результатов реализации проекта AutoAdmin [1] исследовательского центра Microsoft. Система средств автоматической настройки содержит инфраструктуру (framework), реализация которой может различаться (“What-if” интерфейс в MSSQL [1], LEO интерфейс в DB2 [2], Tuning Pack в Oracle [7]). Существующие средства автоматической настройки позволяют:
   • Производить выработку рекомендаций для построения индексов и материализованных представлений по известной рабочей нагрузке [1] [3]
   • Производить отбор и воспроизведение рабочей нагрузки [1] [5]
   • Автоматически информировать о проблемах производительности [1]
   • Производить автоматическое управление статистикой [1] [6] [4]
   • Использовать самонастраиваемые гистограммы [1] [2] [7]
   Эти средства позволяют решить множество частных задач обеспечения адекватности оценок стоимости — обновлять устаревшую статистику, учитывать зависимость предикатов, использовать гистограммы для скошенных распределений значений. Однако пока что не существует подхода к исправлению всех модельных ошибок вне зависимости от их источника.
2. Преобразования запросов. Запрос может быть подвергнут преобразованиям, улучшающим его декларативность. Это позволяет оптимизатору рассмотреть в процессе оптимизации дополнительные способы выполнения. Преобразования с точки зрения реляционной алгебры можно разделить на эквивалентные и неэквивалентные. Эквивалентные преобразования могут выполняться на фазе логической оптимизации запроса. В современных оптимизаторах насчитывается более десяти [8] различных видов преобразований, и их количество по мере выхода новых версий увеличивается. Тем не менее, одних эквивалентных преобразований может быть недостаточно для получения плана выполнения, реализующего требуемое время ответа.

Требуемую информацию на языке SQL можно описать разными способами (выражениями). Некоторые из этих выражений будут неэквивалентны друг другу. Изменяя способ записи требуемой информации, можно способствовать рассмотрению новых планов выполнения. Неэквивалентные преобразования на сегодняшний день не могут быть выполнены автоматически.

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

Во второй части доклада рассматривается один из путей совершенствования настройки компонент системы с участием администратора, используя новую модель стоимости на основе свойств О-большое асимптотик.

В 2006 году Борис Новиков предложил производить настройку с участием администратора системы локальным методом [10]. Для его совершенствования было предложено [13] использовать в процессе настройки новую модель стоимости. На практике сложность настройки на основе существующих методов состоит в том, что:

• по мере развития структура данных и запросы усложняются, что увеличивает как количество операций плана выполнения, так и количество параметров, на них влияющих;
• объемы хранимых данных постоянно увеличиваются, так что недостаточно просто достичь требуемого времени выполнения. Необходимо исследовать динамику поведения системы и убедиться, что время выполнения будет соответствовать требованиям, как минимум, в ближайшей перспективе;
• средства автоматической настройки не учитывают требований пользователей к времени ответа. Они лишь позволяют улучшить эффективность выполнения, если в результате работы автоматических средств удалось получить рекомендации по изменению параметров. Иногда такой настройки бывает недостаточно для удовлетворения требований к времени ответа, и требуется участие администратора системы;
• настройка с участием администратора системы в настоящее время производится с использованием различных переборных схем, что с ростом количества параметров настройки становится чрезмерно трудоемко и затратно.

Таким образом, один из путей совершенствования процесса настройки запросов состоит в сокращении переборных схем за счет использования новой модели стоимости, внешней по отношению к стоимостному оптимизатору. В отличие от существующих, предлагаемая модель строится на основе статистики выполнения запроса, используя известные О-большое асимптотические оценки стоимости выполнения операций. На основе новой модели становится возможным:

• определять новые критерии ранжирования операций плана выполнения;
• определять параметрические модели.

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

Адекватность новой модели основывается на гипотезе о стабильности поведения системы: если модель адекватна на границе области изменения параметров, то она адекватна всюду внутри области изменения параметров. Проведенные эксперименты [14] показали, что в некоторых случаях можно надеяться на справедливость этой гипотезы. Параметрические модели позволяют экстраполировать результаты тестовых испытаний на основе имеющихся данных на прогнозируемые объемы данных, используя гипотезу стабильности поведения системы, выполняя проверку только при максимальном значении параметров, а не на всей границе области изменения параметров.

Слайды к докладу в формате PDF: borchuk20101028.pdf

Литература:

1. Chaudhuri, S. Self-Tuning Database Systems: A Decade of Progress / Surajit Chaudhuri, Vivek Narasayya // Proceedings of the Second International Conference on Automatic Computing, p.326-327, June 13-16, 2005
2. Markl, V. LEO: An autonomic query optimizer for DB2 / V. Markl, G. M. Lohman, V. Raman // IBM Systems Journal, v.42 n.1, p.98-106, January 2003 Имеется перевод на русский язык: LEO: самонастраивающийся оптимизатор запросов для DB2 (перевод Сергей Кузнецов) http://citforum.ru/database/articles/leo.shtml
3. Zilio, S. DB2 Design Advisor: Integrated Automatic Physical Database Design / Zilio et al. // In Proceedings of the VLDB, Toronto, Canada, 2004
4. Aboulnaga, A. Automated statistics collection in DB2 UDB / Aboulnaga et al. // Proceedings of the Thirtieth international conference on Very large data bases, Volume 30, p. 1158 – 1169, Toronto, Canada, 2004
5. Belknap, P. Oracle real application testing / Belknap et al. // Proceedings of the 1st international workshop on Testing database systems, Vancouver, Canada, 2008
6. Chakkappen, S.Efficient and scalable statistics gathering for large databases in Oracle 11g // Proceedings of the 2008 ACM SIGMOD international conference on Management of data table of contents, p. 1053-1064, Vancouver, Canada, 2008
7. Lee, A. Closing the query processing loop in Oracle 11g / Allison W.Lee, Mohamed Zait // In Proceedings of the VLDB Endowment, 2008
8. Rafi, A. Cost-Based Query Transformation in Oracle / Rafi Ahmed, Allison Lee, Andrew Witkowski, Dinesh Das, Hong Su, Mohamed Zait, Thierry Cruanes // Proceedings of the 32nd international conference on Very large data base, 2006, pp. 1026 — 1036
9. Breitling, W. Tuning by Cardinality Feedback // http://www.centrexcc.com/Tuning%20by%20Cardinality%20Feedback.ppt.pdf
10. Новиков Б.А., Домбровская Г.Р. Настройка приложений баз данных. Спб: БХВ-Петербург, 2006.
11. Ривкин М.Н. Коммерческие СУБД: революция или эволюция? // Открытые системы. 2009. №2.
12. Конноли Т. И др. Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд. М.: Издательский дом “Вильямс”, 2000.
13. Борчук Л.Е. Совершенствование процесса настройки запросов пользователей на основе асимптотических оценок затрат ресурсов // Информационные технологии. 2008. №6. С. 6-11.
14. Борчук Л.Е., Кузьмин А.А. Оценка времени выполнения запроса в реляционной СУБД на основе асимптотических моделей затрат ресурсов // Наукоемкие технологии. 2008. №4. С. 61-64.