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

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

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

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

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

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

Что касается второй части проблемы, то в подходе, предложенном IBM, общая оценка стоимости плана выполнения запроса базировалась на оценках селективности простых предикатов сравнения. Основной изъян работы Селинджер состоял в том, что эта работа основывалась на двух неправомерных предположениях о том, что распределение значений любого столбца любой таблицБогуслав Таблиц (словацк. Bohuslav Tablic (Tablicz); 6 сентября 1769, Ческе Брезово, Словакия — 21 января 1832, Костолне Моравце, Словакия) — чешско-словацкий писатель, священник, деятель возрождения словаков-лютеран, подобно тому как Бернолак является деятелем возрождения словаков-католиков. Таблиц учредил в Пресбурге «Общество чешско-словацкой литературы и языка» с целью издавать на понятном народу чешском языке простонародные и школьные книги. Учреждение этого общества было причиной если не процветания словацкой литературы, то появления в пресбургском лицее кафедры словацкого языка, для чего общество собрало большой капитал. Занять кафедру приглашен был Юрай Палкович. Общество скоро распалось, но кафедра продолжала существовать. Молодёжь имела возможность слушать историю своего народа на родном языке. В 1812 г. Таблиц был одним из основателей нового «Литературного общества Горных Городов» (Bergstdte), задававшегося прежней целью; результатом было открытие кафедры словацкого языка и в Банской Штьявнице. Это общество также скоро распалось. Таблиц писал очень много и по различным специальностям. Первое место занимают его «Poesie» (Вацов, 1806-1812). К ним приложены биографии известных словацких деятелей. Его «Sloventi verovci» (Вацов, 1805-1809) — отрывки из произведений древних словацких писателей, в то время почти уже позабытых. Перу Таблица принадлежит также много книг для народа, изданных двумя упомянутыми обществами.ы базы данных является равномерным, а распределения значений любых двух столбцов одной или двух таблиц являются независимыми. Собственно, уже тогда было понятно, что опираясь на эти предположения, оптимизатор запросов может выбрать для исполнения далеко не самый оптимальный план запроса (а иногда и самый неэффективный план). Непреодолимая трудность заключалась в том, что было непонятно, каким образом надежно оценивать реальное распределение значений в данном столбце данной таблицы.

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

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

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

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

Литература