Базы данных Oracle - статьи
Методы поиска в пространстве состояний
Фундаментальный вопрос, связанный с преобразованиями, которые основаны на оценке стоимости, заключается в том, приведут ли эти преобразования к комбинаторно быстрому росту альтернатив, которые необходимо оценивать, и обеспечат ли они баланс между стоимостью оптимизации и стоимостью выполнения.
Источник многочисленных альтернатив — сами разнообразные преобразования, а также множество объектов (например, блоки запроса, таблицы, ребра соединений, предикаты и т.д.), к которым каждое преобразование может применяться. Если есть N объектов, к которым может применяться преобразование T, то применением T потенциально можно образовать 2N возможных альтернативных комбинаций. В общем случае, если есть M преобразований T1, T2, ..., TM, которые могут применяться к N объектам, то существует (1 + M)N возможных альтернативных комбинаций.
Например, для запроса Q1 нужно рассмотреть 4 альтернативы: без устранения вложенности, с устранением вложенности только первого подзапроса (QS1), с устранением вложенности только второго подзапроса (QS2) или с устранением вложенности обоих подзапросов. Мы обозначаем состояние как массив бит, где n-ый бит показывает, является ли n-ый объект (например, подзапрос) преобразованным (значение 1) или нет (значение 0). Например, состояние (0,1) говорит об устранении вложенности только второго подзапроса. Если есть M преобразований, применяемых к N объектам, состояние представляется матрицей из M×N бит.
Чтобы справиться с проблемой комбинаторно быстрого роста в случае перестановок соединения, было предложено использовать рандомизированные алгоритмы, такие как имитация отжига (Simulated Annealing), генетический поиск (Genetic Search), итерационное уточнение (Iterative Improvement), поиск с запретами (Tabu Search) [20], [21], [11]. Общая идея всех этих стратегий заключается в выполнении квазислучайных блужданий в пространстве поиска, начиная с исходного состояния и пытаясь достичь локального минимума низкой стоимости. Конечно, эти стратегии не гарантируют, что может быть достигнут глобальный минимум — наилучшее преобразование, так как во время блужданий посещается только малая часть пространства состояний. Тем не менее, они имеют практическую значимость, так как качество решения обычно улучшается с длительностью поиска.
Сложность преобразований, основанных на оценке стоимости, определяется количеством альтернативных комбинаций или пространством состояний, которое экспоненциально растет с количеством преобразуемых объектов. Если количество преобразуемых объектов мало, может стать осуществимой техника полного перебора преобразований с исчерпывающим поиском в пространстве состояний. Для ограничения потенциального роста времени оптимизации мы используем несколько различных методов перебора пространства состояний.
Исчерпывающий поиск (Exhaustive Search). При исчерпывающем поиске рассматриваются все возможные 2N состояний пространства состояний N объектов. Например, в запросе Q1 мы рассматриваем 4 состояния: (0,0), (0,1), (1,0) и (1,1). Этот поиск гарантирует нахождение наилучшего решения.
Итерационное уточнение (Iterative Improvement). Метод итерационного уточнения используется для сокращения пространства поиска. Главная идея этого метода состоит в том, что мы начинаем с некоторого исходного состояния и продвигаемся к следующему соседнему состоянию, используя некоторый метод, направленный на поиск локального минимума за счет постоянного выбора нисходящего направления движения; мы повторяем этот поиск локального минимума, начиная с другого исходного состояния в следующей итерации. Алгоритм останавливается, если новые состояния более не находятся, или было достигнуто некоторое условие завершения (например, максимальное количество состояний). Количество состояний, перебираемых этой техникой, лежит в пределах от N до 2N.
Линейный поиск (Linear Search). Основная идея этого метода поиска основана на подходе динамического программирования, в котором предполагается, что для запроса, состоящего из нескольких объектов, достаточно проанализировать на предмет преобразования только некоторый поднабор этих объектов, а затем расширить это дополнительными преобразованиями других объектов. Другими словами, если стоимость (1,0) меньше, чем стоимость (0,0), и стоимость (1,1) меньше, чем стоимость (1,0), то можно надежно предположить, что стоимость (1,1) — самая низкая для всевозможных преобразований, и, следовательно, нет необходимости оценивать стоимость (0,1). Как можно видеть, это может существенно сократить пространство поиска. Этот метод анализирует N + 1 состояний. Линейный поиск работает лучше всего, если преобразования различных элементов независимы одно от другого.
Двухпроходной поиск (Two-pass Search). Двухпроходный поиск — самый дешевый метод поиска, в котором анализируется 2 состояния. Сравниваем стоимость плана выполнения полностью непреобразованного запроса (т.е. состояние (0,0,...)) со стоимостью плана запроса, в котором преобразованы все объекты (т.е. состояние (1,1,...)).
Инфраструктура преобразований, основанных на оценке стоимости, автоматически решает, какой метод поиска следует использовать, основываясь на количестве объектов, которые преобразуются в блоке запроса, характеристиках преобразований и общей сложности запроса. Например, если в блоке запроса содержится небольшое число подзапросов, мы используем для устранения вложенности подзапросов исчерпывающий поиск, а если число подзапросов превышает некоторое фиксированное пороговое значение, мы используем линейный поиск. Если общее число элементов в запросе, подлежащих преобразованию (например, представлений с group-by, подзапросов, вложенность которых можно устранить) превышает некоторое пороговое значение, то мы используем для всех преобразований запроса двухпроходный поиск.
