SQL - статьи




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


Сергей Кузнецов
24.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) выбрать из множества этих программ (найти в пространстве планов выполнения запроса) такую программу, выполнение которой было бы наиболее эффективным.




Содержание    Вперед