Базы данных 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]. Общая идея всех этих стратегий заключается в выполнении квазислучайных блужданий в пространстве поиска, начиная с исходного состояния и пытаясь достичь локального минимума низкой стоимости. Конечно, эти стратегии не гарантируют, что может быть достигнут глобальный минимум — наилучшее преобразование, так как во время блужданий посещается только малая часть пространства состояний. Тем не менее, они имеют практическую значимость, так как качество решения обычно улучшается с длительностью поиска.



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