В этой статье мы показали,
В этой статье мы показали, что преобразование методом магических множеств можно расширить для работы с конструкциями SQL. Мы привели набросок реализации Extended Magicsets как части компонента перезаписи прототипа реляционной системы баз данных, а также представили исследование эффективности, в котором подход магических множеств сопоставляется с подходами корреляции и декорреляции. Многие существенные результаты были лишь упомянуты или вовсе опущены, включая аспекты улучшенных украшений, простых украшений и детали реализации.
Как мы полагаем, эта статья демонстрирует, что метод магических множеств (ранее служивший средством только для Datalog и логического программирования) следует рассматривать как практическое расширение существующих методов оптимизации путем перезаписи. Магия действительно «уместна» для систем реляционных баз данных; это общий метод (применимый как к рекурсивным, так и к не рекурсивным запросам) введения предикатов, которые как можно ранее отфильтровывают доступ к ненужным строкам таблиц. Ограниченные варианты этого метода долгие годы используются в системах баз данных.
Мы не предлагаем использовать преобразования методом магических множеств всякий раз, когда они возможны. Скорее, магия является ценной альтернативной, кажущейся более стабильной, чем методы корреляции и декорреляции, предметом выбора, который должен оцениваться стоимостным оптимизатором [SAC + 79, Loh88]. Магия особенно полезна для запросов (таких как запросы поддержки принятия решений), включающих большое число соединений, сложные вложения блоков запросов или рекурсию. Такие запросы могут быть невыполнимыми без применения магических множеств.
В литературе предлагался ряд специальных методов оптимизации. Некоторые из них можно считать альтернативами магических множеств, в которых делаются попытки использования специальных свойств некоторых запросов, таких как линейные запросы на ациклических данных (например, HenschenNaqvi [HN84], Counting [BMSU86]) или специальные операции для выражения ограниченного (и важного) класса запросов, таких как транзитивное замыкание (например, операция alpha [Agr87]).
При наличии возможности их применения, эти методы иногда оказываются лучше преобразования магических множеств. Однако пример 1.2 иллюстрирует полезные запросы, не выразимые с использованием линейной рекурсии. Важность метода магических множеств состоит в том, что он применим ко всем (расширенным) SQL-запросам и обеспечивает общий каркас оптимизации с хорошей и стабильной эффективностью. Имеются также методы, в которых подход магических множеств развивается и совершенствуется для некоторых классов запросов (например, факторизация [NRSU89]). Эти методы дополняют подход магических множеств путем распознавания специальных свойств программ и соответствующей оптимизации преобразованных программ.
Хотя мы реализуем магию как расширение компонента оптимизации путем перезаписи прототипа расширяемой системы реляционных баз данных Starburst, остается много практических вопросов. Одной из трудных открытых проблем является интеграция оптимизации путем перезаписи с оценочной оптимизацией. Для оценочной оптимизации может требоваться время, экспоненциально зависящее от числа соединяемых таблиц. Преобразования, подобные магическим множествам, могут привести к экспоненциально большому числу альтернативных запросов, для каждого из которых требуется оценочная оптимизация, более сложная, чем для исходного запроса. Очевидно, что между многими преобразованиями запросов имеется структурная связь, но мы недостаточно хорошо понимаем эту проблему, чтобы перевести ее на управляемый уровень с применением алгебраических методов или инженерных эвристик.
