59.1. Обработка запросов как сложная оптимизационная задача#
59.1. Обработка запросов как сложная оптимизационная задача #
Среди всех операторов соединения наиболее сложным для обработки и оптимизации является оператор join. Количество возможных планов запроса растет экспоненциально с количеством соединений в запросе. Дополнительные усилия по оптимизации вызываются поддержкой различных методов соединения (например, вложенный цикл, соединение слиянием или по хешу в Tantor BE) для обработки отдельных соединений и разнообразием индексов (например, B-дерево, хеш, GiST и GIN в Tantor BE) в качестве путей доступа к отношениям.
Обычный оптимизатор запросов Tantor BE выполняет почти исчерпывающий поиск по пространству альтернативных стратегий. Этот алгоритм, впервые представлен в базе данных System R от IBM, создает почти оптимальный порядок соединения, но может занимать огромное количество времени и памяти, когда количество соединений в запросе становится большим. Это делает обычный оптимизатор запросов Tantor BE непригодным для запросов, объединяющих большое количество таблиц.
Институт автоматического управления Университета горного дела и технологии в Фрайберге, Германия, столкнулся с некоторыми проблемами, когда он хотел использовать Tantor BE в качестве основы для системы поддержки принятия решений на основе знаний для обслуживания электрической сети. СУБД должна была обрабатывать большие запросы с соединениями для машинного вывода знаний в системе на основе знаний. Количество соединений в этих запросах делало использование обычного оптимизатора запросов невозможным.
В следующем разделе мы описываем реализацию генетического алгоритма для решения проблемы определения порядка соединения в запросах, в которых присутствует большое количество соединений.