2009 г.
Оценочная оптимизация для магии: алгебра и реализация
Правин Сешарди (Praveen Seshadri, Univ. of Wisconsin, Madison)
Джозеф Хеллерстейн (Joseph M. Hellerstein, Univ. of California, Berkeley)
Хамид Пирамеш (Hamid Pirahesh, IBM Almaden Research Ctr.)
Клифф Леюнг (T. Y. Cliff Leung, IBM Santa Teresa Lab.)
Раджу Рамакришнан (Raghu Ramakrishnan, Univ. of Wisconsin, Madison)
Дивеш Сривастава (Divesh Srivastava, AT&T Research)
Питер Стюки (Peter J. Stuckey, Univ. of Melbourne)
С. Сударшан (S. Sudarshan, IIT, Bombay)
SIGMOD Conference 1996: 435-446
Перевод: Сергей Кузнецов
Содержание
- 1. Введение
- 2. Мотивация
- 2.1 Альтернативы перезаписи
- 2.2 Оценочное решение
- 3. Магические множества и оптимизация соединений
- 3.1 Букварь по оптимизации соединений
- 3.2 Упорядочение соединений и SIPS
- 3.3 Перезапись на основе магических множеств как метод соединения
- 3.4 Ограничение пространства поиска
- 4. Оценка стоимости и мощности
- 4.1 Оценивание FilterCostRk
- 4.2 Пространственная сложность оптимизации
- 4.3 Как исчезает сложность?
- 5. Реализация в DB2 C/S V2
- 5.1 Осуществимость
- 5.2 Эффективность
- 5.3 Практический опыт
- 6. Измерение производительности
- 6.1 Экспериментальная методология
- 6.2 Сравниваемые алгоритмы
- 6.3 Общие результаты
- 6.4 Фиксированные варианты SIPS
- 6.5 Результаты времени компиляции
- 6.6 Вариации экспериментов
- 7. Алгебра
- 7.1 Нотация
- 7.2 Правила преобразований для Θ-полусоединения
- 7.3 Оценочная модель для Θ-полусоединения
- 7.4 Применение правил эквивалентности Θ-полусоединения
- 7.5 Θ-полусоединения и ограничительная магическая перезапись
- 7.6 Обсуждение
- 8. Родственные работы
- 9. Заключение
- Acknowledgements
- References
Аннотация
Перезапись с использованием магических множеств является хорошо известной оптимизационной эвристикой для сложных запросов принятия решений. Даже для простого запроса может иметься много вариантов этой перезаписи, сильно различающихся по эффективности выполнения. Мы предлагаем основанные на стоимости методы для выбора эффективного варианта из многих альтернатив.
Нашим первым вкладом является практическая схема моделирования перезаписи с использованием магических множеств как специального метода соединений, который можно добавить к любому оценочному оптимизатору. Мы выводим оценочные формулы, позволяющие оптимизатору выбрать наилучший вариант перезаписи и решить, полезен ли он. Порядок сложности процесса оптимизации сохраняется путем ограничения пространства поиска разумным образом. Мы реализовали этот метод в системе баз данных IBM DB2 C/S V2. Наши измерения производительности показывают, что оценочный метод оптимизации с использованием магических множеств работает хорошо, и что без его использования могли бы быть приняты некоторые ложные решения.
Вторым вкладом является формальная алгебраическая модель перезаписи с использованием магических множеств, основанная на расширении мультимножественной реляционной алгебры. Мы вводим мультимножественную операцию Θ-полусоединения и получаем правила эквивалентности, включающие эту операцию. Мы демонстрируем, что перезапись с использованием магических множеств для не рекурсивных SQL-запросов можно моделировать как последовательную композицию этих правил эквивалентности.
1. Введение
В современных системах реляционных баз данных обрабатываются сложные SQL-запросы, включающие представления, табличные выражения и подзапросы с агрегатными функциями. Такие запросы становятся все более важными в приложениях поддержки принятия решений (см., например, тестовый набор TPCD [TPCD94]). Метод перезаписи с использованием магических множеств (см., например, [BMSU86, RLK86, BR91, MFPR90, SS94]) был предложен как эвристическое преобразование для оптимизации таких запросов, и этот метод может приводить к серьезным улучшениям эффективности выполнения запросов [MFPR90]. Может быть много возможных вариантов этой перезаписи даже для одиночного запроса, основанных на решениях относительно распространений связываний. Некоторые из этих вариантов могут в действительности ухудшить эффективность. До данной работы не был продемонстрирован алгоритм эффективного выбора варианта в оценочном стиле. В этой статье устраняется важная преграда к внедрению перезаписи на основе магических множеств в коммерческие базы данных.
В статье анализируются два подхода к решению данной проблемы. Первый подход основывается на моделировании перезаписи на основе магических множеств как метода соединения, и он реализован в системе баз данных DB2 C/S V2. Второй подход представляет модель перезаписи на основе магических множеств, основанную на алгебраических преобразованиях. Оба подхода являются взаимнодополнительными и, взятые совместно, позволяют изучать соответствующие практические и теоретические вопросы.
Целью реализации является разработка алгоритма, в котором учитываются ограничения и требования полнофункциональной СУБД. Перезапись на основе магических множеств моделируется как специальный метод соединения, который может быть добавлен к любому существующему оценочному оптимизатору запросов. Выводятся оценочные формулы, позволяющие оптимизатору выбрать наилучший вариант перезаписи и определить, является ли он полезным. Исчерпывающий поиск среди всех вариантов сущетсвенно увеличивает сложность оптимизации запросов. Чтобы сохранить порядок сложности процесса оптимизации к пространству поиска применяются разумные ограничения. Изучение производительности на основе реализации в DB2 C/S V2 демонстрирует низкие дополнительные накладные расходы и стабильность алгоритма при выполнении основанного на стоимости выбора, что приводит к существенному сокращению времени выполнения запросов. Существенно то, что результаты показывают, что для перезаписи на основе магических множеств требуется оценочный алгоритм (эффективность алгоритмов, основанных на эвристиках, изменяется при изменении статистики данных и оценок стоимости), и что предложенный оценочный алгоритм работает правильно.
Алгебраический подход к перезаписи на основе магических множеств базируется на правилах эквивалентности на мультимножественной реляционной алгебре, затрагивающих операцию Θ-полусоединения. Алгебраический подход позволяет правильно определять пространство поиска и может использоваться в оптимизаторе, основанном на правилах (возможно, совместно с эвристиками для ограничения пространства поиска). Мы представляем характерный набор правил эквивалентности и показываем, как эти правила моделируют перезапись на основе магических множеств для не рекурсивных SQL-запросов.
Сначала мы мотивируем проблему с использованием примера.
View Definition
CREATE VIEW DepAvgSal AS
(SELECT E.did, AVG(E.sal) AS avgsal FROM Emp E
GROUPBY E.did);
Main Query Block
SELECT E.eid, E.sal FROM Emp E, Dept D, DepAvgSal V
WHERE E.did = D.did AND E.did = V.did AND E.age < 30
AND D.budget > 100,000 AND E.sal > V.avgsal
Рис. 1. Исходный запрос
View Definitions
CREATE VIEW PartialResult AS
(SELECT E.eid, E.sal, E.did FROM Emp E, Dept D
WHERE E.did = D.did AND E.age < 30
AND D.budget > 100,000)
CREATE VIEW Filter AS
(SELECT DISTINCT P.did FROM PartialResult P );
CREATE VIEW LimitedDepAvgSal AS
(SELECT F.did, AVG(E.sal) as avgsal FROM Filter F, Emp E
WHERE E.did = F.did
GROUPBY F.did);
Main Query Block
SELECT P.eid, P.sal FROM PartialResult P, LimitedDepAvgSal V
WHERE P.did = V.did AND P.sal > V.avgsal
Рис. 2. Перезапись на основе магических множеств
2. Мотивация
SQL-запрос на рис. 1 находит всех работающих в больших отделах молодых служащих, зарплата каждого из которых выше средней зарплаты отдела, в котором работает данный служащий. Запрос затрагивает реляционное представление DepAvgSal, которое порождает среднюю зарплату в каждом отделе, и включает соединение отношений Emp, Dept и DepAvgSal. В перезаписи на основе магических множеств используется тот факт, что среднюю отдельскую зарплату не требуется вычислять для каждого отдела; ее нужно вычислять только для больших отделов, в которых имеются молодые служащие. Если таких отделов немного, то, вероятно, желательно применить перезапись на основе магических множеств.1 Переписанный запрос показан на рис. 2. Представление PartialResult представляет представляет частичное вычисление в основном блоке запроса на стадии, когда таблицы Emp и Dept уже соединены между собой, но к ним еще не присоединено представление DepAvgSal. На основе этой таблицы PartialResult создается не содержащее дубликатов представление Filter, порождающее множество всех отделов, для которых требуется вычислять среднюю зарплату. Далее это фильтрующее множество используется для ограничения вычислений в исходном представлении.2 Представление модифицируется путем включения эквисоединения с фильтрующим множеством (тем самым, ограничивая вычисления в представлении отделами, представляющими интерес). Наконец, в основном блоке запроса на рис. 2 модифицированное представление соединяется с таблицей PartialResult для формирования окончательного результата.
2.1 Альтернативы перезаписи
В приведенном перезаписанном запросе фильтрующее множество содержит все большие отделы, в которых работают молодые сотрудники. Это фильтрующее множество является наиболее ограничительным из всех возможных. Можно использовать менее ограничительное фильтрующее множество. Фильтрующее множество может содержать все большие отделы или все отделы с молодыми сотрудниками. В каждом из этих случаев перезаписанные запросы будут отличаться от запроса, представленного на рис. 2, но они будут иметь похожую общую структуру и будут производить одни и те же результаты. В то время как эти варианты могут приводить к большему числу вычислений внутри представления, они могут быть дешевле в целом (поскольку будут более дешево вычисляться таблицы PartialResult или Filter). В общем случае имеется много способов создания фильтрующего множества, каждый из которых соответствует некоторому подмножеству множества таблиц, указанных в разделе FROM табличного выражения представления PartialResult. Если все отделы являются большими и включают молодых служащих, перезаписанные запросы не обеспечат никаких преимуществ перед исходным запросом, и их выполнение может даже оказаться более дорогостоящим. Наконец, если имеется несколько атрибутов соединения, то требуется принять решение о том, все ли атрибуты соединения будут вносить вклад в фильтрующее множество, или же будут использоваться только некоторые атрибуты. Однако в подавляющем большинстве запросов имеется в точности один атрибут соединения, так что обычно этот аспект не является важным.
Конкретная комбинация результатов выбора по отношению к вычислению фильтрующего множества называется «стратегией сторонней передачи информации» («sideways information passing strategy, SIPS), названный так по той причине, что фильтрующее множество передает атрибуты соединения в определение представления «сторонним образом». Одна из SIPS приводит к наилучшему плану выполнения запроса. Однако это зависит от таблиц и предикатов, участвующих в запросе, и характеристик среды выполнения. В настоящее время отсутствует какое-либо практическое решение для выбора SIPS в оценочном стиле. Вместо этого, существующие системы, выполняющие перезапись на основе магических множеств, придерживаются одного из двух подходов:
- Использовать перезапись на основе магических множеств с SIPS по умолчанию (обычно «слева-направо» и разрешать пользователю указывать другие SIPS или блокировать перезапись на основе магических множеств. Этот подход используется в CORAL [RSSS94].
- Одновременно оптимизировать запрос с перезаписью на основе магических множеств и без нее и выбирать самый дешевый план. Для перезаписи на основе магических множеств выбирать SIPS на основе некоторой эвристики. Этот подход используется в Starburst [MP94]. Выбираемая SIPS «соответствует» порядку соединений, который происходит из оптимизации исходного запроса без магической перезаписи. Для этой эвристики не было представлено никакого оценочного обоснования, нет и никакой гарантии, что выбирается хороший план. На самом деле, как мы покажем в разд. 6, эта эвристика может приводить к плохому выбору. Однако, поскольку исходный запрос также независимо оптимизируется, можно гарантировать, что перезапись на основе магических множеств не приведет к ухудшению производительности.
Рис. 3. Архитектура оптимизации
2.2 Оценочное решение
В данной статье представляется оценочное решение проблемы выбора надлежащей SIPS. Мы реализовали свое решения в системе баз данных DB2 C/S V2 (основанной на системе Starburst [HCL+90]), в которой поддерживается перезапись на основе магических множеств как преобразование «запрос-в-запрос». Архитектура системы показана на рис. 3. Пользовательский запрос поступает прямо на вход оценочного оптимизатора, который решает, выполнять или нет перезапись на основе магических множеств. В то время когда оптимизатор анализирует пространство возможных порядков и методов соединений, он также исследует и пространство возможных вариантов для перезаписи на основе магических множеств. Если принимается решение о том, что никакая перезапись не требуется, оптимизатор генерирует план выполнения обычным образом и посылает его процессору выполнения. С другой стороны, если оптимизатор решает, что магическая перезапись требуется, то он также выбирает одну конкретную SIPS для перезаписи, которая руководит применением преобразования на основе магических множеств. После того, как запрос перезаписывается, он снова оптимизируется для генерации плана выполнения. В обсуждавшемся выше решении Starburst [MP94] впервые предлагалась двухпроходная архитектура, и мы используем ту же идею, поскольку хотели бы избежать серьезных изменений в существующих компонентах системы. Альтернативный подход, который мы обсуждаем в разд. 7, состоит в реализации магической перезаписи с помощью алгебраических преобразований (вместо перезаписи «SQL-в-SQL»).
1 При наличии многих вариантов перезаписи на основе магических множеств наиболее практичным подходом в контексте РСУБД является перезапись на основе дополнительных магических множеств, используемая в этой статье.
2 В литературе фильтрующее множество и PartialResult называются «магическим» множеством и «дополнительным» магическим множеством соответственно.
Содержание Вперёд