Обработка запросов как сложная задача оптимизации

Среди всех реляционных операторов наиболее сложным для обработки и оптимизации является объединение. Количество возможных планов запросов растет экспоненциально с увеличением числа соединений в запросе. Дополнительные усилия по оптимизации связаны с поддержкой множества методов объединения (например, вложенный цикл, хэш-объединение, объединение в PostgreSQL) для обработки отдельных объединений и разнообразия индексов (например, B-tree, хэш, GiST и GIN в PostgreSQL) в качестве путей доступа к отношениям.

Обычный оптимизатор запросов PostgreSQL выполняет почти исчерпывающий поиск в пространстве альтернативных стратегий. Этот алгоритм, впервые появившийся в базе данных System R компании IBM, позволяет получить почти оптимальный порядок соединений, но при большом количестве соединений в запросе может занимать огромное количество времени и места в памяти. Это делает обычный оптимизатор запросов PostgreSQL непригодным для запросов, объединяющих большое количество таблиц.

Институт автоматического управления при Горно-технологическом университете во Фрайберге (Германия) столкнулся с некоторыми проблемами, когда захотел использовать PostgreSQL в качестве бэкенда для системы поддержки принятия решений на основе знаний для обслуживания электросетей. СУБД должна была обрабатывать большие запросы на объединение для машины вывода системы, основанной на знаниях. Количество соединений в этих запросах делало невозможным использование обычного оптимизатора запросов.

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