Оптимизация запросов: вечнозеленая область

Сергей Кузнецов
24.04.2003
Открытые системы, #04/2003

Оптимизаторы запросов — наиболее хитроумные, наиболее сложные и наиболее интересные компоненты СУБД. Историю этого направления принято отсчитывать с середины 70-х годов, хотя наверняка исследования проводились и раньше. Пионерские работы, в которых были получены фундаментальные результаты, относящиеся к оптимизации запросов, были выполнены в рамках проектов System R корпорации IBM [1, 2] и Ingres университета Беркли [3]. В System R были заложены основы техники оптимизации запросов на основе оценок стоимости плана выполнения запроса [4]. В университетском проекте Ingres, фактически использовались методы, которые позже стали называть семантической оптимизацией запросов.

В маленькой редакторской заметке невозможно привести обзор подходов к оптимизации запросов в SQL-ориентированных СУБД. Могу порекомендовать собственный обзор [5] (достаточно старый, но остающийся актуальным) и существенно более новый обзор Чаудхари [6]. Здесь же мне бы хотелось отметить некоторые вехи в истории развития методов оптимизации, которые имеют непосредственное отношение к статье Маркла, Лохмана и Рамана.

Начнем с формулировки проблемы оптимизации SQL-запросов. (Трудно сказать, насколько тесно эта проблема и имеющиеся методы ее решения связаны со спецификой языка SQL; как показывает текущий опыт, многие аспекты оптимизации перекладываются, например, на совсем иной язык запросов Xquery.) Язык SQL декларативен. В формулировках SQL-запросов указывается, какими свойствами должны обладать данные, которые хочет получить пользователь, но ничего не говорится о том, как система должна реально выполнить запрос. Проблема в том, чтобы по декларативной формулировке запроса найти — или построить — программу (в мире SQL такую программу принято называть планом выполнения запроса), которая выполнялась бы максимально эффективно и выдавала бы результаты, соответствующие указанным в запросе свойствам. Более точно, основная трудность состоит в том, что нужно уметь (1) построить все возможные программы, результаты которых соответствуют указанным свойствам, и (2) выбрать из множества этих программ (найти в пространстве планов выполнения запроса) такую программу, выполнение которой было бы наиболее эффективным.

Обе части проблемы нетривиальны. Прежде всего, необходимо обнаружить все корректные планы выполнения запроса или, по крайней мере, не упустить какой-либо план, который является наиболее эффективным. Далее, для облегчения решения второй части проблемы требуется предельно сократить пространство корректных планов, оставив только те планы, которые претендуют на максимальную эффективность. Обе эти задачи являются не полностью формализуемыми, поскольку отсутствуют точные математические критерии выбора. Обычно решение задач опирается на эвристические алгоритмы; обсудим некоторые из них.

Предположим теперь, что первая часть проблемы каким-то образом решена. Теперь требуется решить вторую — и более ответственную — часть проблемы: найти в пространстве планов выполнения запроса единственный план, в соответствии с которым запрос будет реально выполнен (часто эту часть проблемы называют проблемой физической оптимизации). Здесь уже требуются формальные критерии отбора. Патрицией Селинджер и ее коллегами [4] был предложен подход, в котором таким критерием являлась оценочная стоимость выполнения запроса по данному плану. Основным компонентом оцениваемой стоимости являлось число обменов с устройствами внешней памяти, которые потребуются при выполнении плана запроса. В действительности, именно этот подход продолжает использоваться в подавляющем большинстве SQL-ориентированных СУБД.

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

Заметной в этом направлении была работа [7], в которой, в частности, было показано, что всегда имеет смысл преобразовывать формулировку запроса к такому виду, чтобы ограничения индивидуальных таблиц производились до их соединения (predicate push down). Очень важную роль в истории логической оптимизации запросов сыграла серия статей, начало которой положил Вон Ким [8]. В них было показано, как можно преобразовать SQL-запросы, в разделе FROM которых присутствуют подзапросы, в запросы с соединениями. Важность этих результатов в том, что: (1) SQL стимулирует использование запросов с вложенными подзапросами; (2) в большинстве оптимизаторов запросов для реализации таких запросов используется некоторая фиксированная стратегия генерации планов (в основном, вложенные циклы); (3) альтернативные формулировки запросов с соединениями допускают порождения большего числа планов, среди которых могут находиться наиболее эффективные. Другими словами, этот подход позволяет разумным образом расширить пространство поиска оптимальных планов выполнения запросов.

Что касается второй части проблемы, то в подходе, предложенном IBM, общая оценка стоимости плана выполнения запроса базировалась на оценках селективности простых предикатов сравнения. Основной изъян работы Селинджер состоял в том, что эта работа основывалась на двух неправомерных предположениях о том, что распределение значений любого столбца любой таблицы базы данных является равномерным, а распределения значений любых двух столбцов одной или двух таблиц являются независимыми. Собственно, уже тогда было понятно, что опираясь на эти предположения, оптимизатор запросов может выбрать для исполнения далеко не самый оптимальный план запроса (а иногда и самый неэффективный план). Непреодолимая трудность заключалась в том, что было непонятно, каким образом надежно оценивать реальное распределение значений в данном столбце данной таблицы.

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

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

Теперь, что касается самонастраивающихся оптимизаторов запросов. Эта идея (как и большинство идей вообще) не нова. В конце 70-х — начале 80-х годов много писалось о так называемой «глобальной» оптимизации запросов, под которой, главным образом, понимался механизм автоматического поддержания набора индексов, обеспечивающих возможность оптимального выполнения запросов данной рабочей нагрузки СУБД. В то время результаты исследований не нашли практического применения. В конце 90-х к этой идее обратились исследователи корпораций Microsoft и Oracle (см., в частности, [6]).

Статья, представляемая вниманию читателей, имеет несколько иное направление. Это не столько самонастраиваемая, сколько адаптивная оптимизация, поскольку во время выполнения запроса собираются реальные (а не статистические) данные о состоянии базы данных, которые могут быть использованы как для оптимизации последующих запросов, так и для повторной оптимизации текущего запроса. Замечу, что Гай Лохман относится к старожилам лаборатории IBM Almaden Research Center; он начинал работать еще во время проекта System R. Мне было очень интересно читать и редактировать эту статью, чего и вам желаю.

Литература

1. С. Кузнецов. Развитие идей и приложений реляционной СУБД System R. http://www.citforum.ru/database/articles/art_27_1.shtml
2. Воссоединение SQL в 1995 г.: люди, проекты, политика. Под редакцией Пола МакДжонса, в переводе С. Кузнецова. http://www.citforum.ru/database/digest/sql1.shtml
3. Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held. The Design and Implementation of INGRES. TODS 1 (3), 1976.
4. Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. Access Path Selection in a Relational Database Management System. SIGMOD Conference, 1979.
5. С. Кузнецов. Методы оптимизации выполнения запросов в реляционных СУБД. http://www.citforum.ru/database/articles/ art_26.shtml
6. С. Чаудхари. Методы оптимизации запросов в реляционных системах. // СУБД, № 3, 1998.
7. M. Jarke, J. Koch. Query Optimization in Database Systems. ACM Comput. Surv., 1984, 16, No. 2.
8. W. On Optimizing an SQL-Like Nested Query. ACM Trans. Database Syst., 1982, 7, No. 3.
9. R.A. Ganski, H.K.T. Wong. Optimization of Nested SQL Queries Revisited. Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., 1987 May. New York.
10. U. Dayal. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, 1987 Sept..
11. G. Piatetski-Shapiro, C. Connel. Accurate Estimation of the Number of Tuples Satisfying a Condition. ACM SIGMOD Record. 1984, 19, No. 2.
12. M. Lee, J. Freytag, G. Lohman. Implementing an Interpreter for Functional Rules in a Query Optimizers. Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., 1988 Aug.-Sept.