SQL - статьи




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


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

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

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




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