SQL - статьи




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


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

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

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




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