Оценочная оптимизация для магии алгебра и реализация

       

Родственные работы


Перезапись с использованием магических множеств исходно использовалась в области обработки рекурсивных запросов в дедуктивных базах данных [BMSU86, RLK86]. Влияние различных вариантов выбора SIPS обсуждалось в [BR91], и идея использования аппроксимаций магического множества исследовалась в [Sag90, SS88]. Следует заметить, что в данной статье мы имеем дело с нерекурсивными SQL-запросами, поддерживаемыми во всех коммерческих реляционных системах баз данных. Ранее было показано, что магические множества применимы к нерекурсивным SQL-запросам [MFPR90], и соответствующий метод был реализован в системе баз данных Starburst [MP94].

Методы оценочной оптимизации, аналогичные методу магических множеств, могут также применяться к сложным SQL-запросам, включающим корреляцию (с использованием магического преобразования декорреляции [SPL96]) и дорогостоящие функции [Hel95].

При исследовании полусоединений в распределенных базах данных (см., например, [BGW+81, LMH+85]) предполагалось, что отношения являются простыми хранимыми отношениями, и поэтому было легко вычислить стоимость выполнения полусоединений. Кроме того, обычно не рассматривались аспекты, подобные выбору SIPS, поскольку предполагалось, что стоимость коммуникаций перевешивает стоимость локальной обработки (и, следовательно, всегда выбирались наиболее ограничительные полусоединения). Вместо этого оптимизация сосредотачивалась на корректном порядке вычисления полусоединений [BGW+81]. С другой стороны, в проекте System R* [LMH+85] предполагалось, что стоимость локальной обработки перевешивает стоимость коммуникаций; вследствие этого, в процессе оптимизации полусоединения не рассматривались.

В литературе, посвященной неоднородным базам данных, пока еще не рассматривались такие вопросы, как сложные запросы над удаленными представлениями. Однако такие вопросы становятся все более важными, и результаты нашей работы следует применять и в этой области.



Содержание раздела