Аннотация
Перезапись с использованием магических множеств является хорошо известной оптимизационной эвристикой для сложных запросов принятия решений. Даже для простого запроса может иметься много вариантов этой перезаписи, сильно различающихся по эффективности выполнения. Мы предлагаем основанные на стоимости методы для выбора эффективного варианта из многих альтернатив.
Нашим первым вкладом является практическая схема моделирования перезаписи с использованием магических множеств как специального метода соединений, который можно добавить к любому оценочному оптимизатору. Мы выводим оценочные формулы, позволяющие оптимизатору выбрать наилучший вариант перезаписи и решить, полезен ли он. Порядок сложности процесса оптимизации сохраняется путем ограничения пространства поиска разумным образом. Мы реализовали этот метод в системе баз данных IBM DB2 C/S V2. Наши измерения производительности показывают, что оценочный метод оптимизации с использованием магических множеств работает хорошо, и что без его использования могли бы быть приняты некоторые ложные решения.
Вторым вкладом является формальная алгебраическая модель перезаписи с использованием магических множеств, основанная на расширении мультимножественной реляционной алгебры. Мы вводим мультимножественную операцию ?-полусоединения и получаем правила эквивалентности, включающие эту операцию. Мы демонстрируем, что перезапись с использованием магических множеств для не рекурсивных SQL-запросов можно моделировать как последовательную композицию этих правил эквивалентности.
