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

Правин Сешарди (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-запросы, включающие представления, табличные выражения и подзапросы с агрегатными функциями. Такие запросы становятся все более важными в приложениях поддержки принятия решений (см., например, тестовый набор TPC­D [TPCD94]). Метод перезаписи с использованием магических множеств (см., например, [BMSU86, RLK86, BR91, MFPR90, SS94]) был предложен как эвристическое преобразование для оптимизации таких запросов, и этот метод может приводить к серьезным улучшениям эффективности выполнения запросов [MFPR90]. Может быть много возможных вариантов этой перезаписи даже для одиночного запроса, основанных на решениях относительно распространений связываний. Некоторые из этих вариантов могут в действительности ухудшить эффективность. До данной работы не был продемонстрирован алгоритм эффективного выбора варианта в оценочном стиле. В этой статье устраняется важная преграда к внедрению перезаписи на основе магических множеств в коммерческие базы данных.

В статье анализируются два подхода к решению данной проблемы. Первый подход основывается на моделировании перезаписи на основе магических множеств как методаМетод (от греч. — «способ»)— систематизированная совокупность шагов, действий, которые необходимо предпринять, чтобы решить определенную задачу или достичь определенной цели. В отличие от области знаний или исследований, является авторским, то есть созданным конкретной персоной или группой персон, научной или практической школой. В силу своей ограниченности рамками действия и результата, методы имеют тенденцию морально устаревать, преобразовываясь в другие методы, развиваясь в соответствии с временем, достижениями технической и научной мысли, потребностями общества. Совокупность однородных методов принято называть подходом. Развитие методов является естественным следствием развития научной мысли. соединения, и он реализован в системе баз данных DB2 C/S V2. ВторойВторой — второй по счёту альбом песен Владимира Высоцкого в исполнении Григория Лепса, записанный и вышедший в 2007 году подход представляет модель перезаписи на основе магических множеств, основанную на алгебраических преобразованиях. Оба подхода являются взаимнодополнительными и, взятые совместно, позволяют изучать соответствующие практические и теоретические вопросы.

Целью реализации является разработка алгоритма, в котором учитываются ограничения и требования полнофункциональной СУБД. Перезапись на основе магических множеств моделируется как специальный метод соединения, который может быть добавлен к любому существующему оценочному оптимизатору запросов. Выводятся оценочные формулы, позволяющие оптимизатору выбрать наилучший вариант перезаписи и определить, является ли он полезным. Исчерпывающий поиск среди всех вариантов сущетсвенно увеличивает сложность оптимизации запросов. Чтобы сохранить порядок сложности процесса оптимизации к пространству поиска применяются разумные ограничения. Изучение производительности на основе реализации в DB2 C/S V2 демонстрирует низкие дополнительные накладные расходы и стабильность алгоритма при выполнении основанного на стоимости выбора, что приводит к существенному сокращению времени выполнения запросов. Существенно то, что результаты показывают, что для перезаписи на основе магических множеств требуется оценочный алгоритм (эффективность алгоритмАлгоритм, от имени учёного аль-Хорезми (перс. [al-Khwrazm])— точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.ов, основанных на эвристиках, изменяется при изменении статистики данных и оценок стоимости), и что предложенный оценочный алгоритм работает правильно.

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

Сначала мы мотивируем проблему с использованием примера.

CREATECREATE— DDL оператор языка SQL используемый для создания объектов базы данных. Различные СУБД работают с различными объектами. VIEW DepAvgSal AS 
  (SELECT E.did, AVG(E.sal) AS avgsal FROM Emp E 
   GROUPBY E.did);

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

CREATE VIEW PartialResult AS 
  (SELECTSELECT ("селект") — оператор DML языка SQL, возвращающий набор данных (выборку) из базы данных, удовлетворяющих заданному условию. 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);

SELECT P.eid, P.sal FROM PartialResult P, LimitedDepAvgSal V 
WHERE P.did = V.did AND P.sal > V.avgsal

2. Мотивация

SQL-запрос на рис. 1 находит всех работающих в больших отделах молодых служащих, зарплата каждого из которых выше средней зарплаты отдела, в котором работает данный служащий. Запрос затрагивает реляционное представление DepAvgSal, которое порождает среднюю зарплату в каждом отделе, и включает соединение отношений Emp, Dept и DepAvgSal. В перезаписи на основе магических множеств используется тот факт, что среднюю отдельскую зарплату не требуется вычислять для каждого отдела; ее нужно вычислять только для больших отделов, в которых имеются молодые«Молодые»— советский художественный фильм по роману Александра Андреева «Рассудите нас, люди». служащиеСлужащие— социальная группа, включающая всех занятых по найму нефизическим трудом в промышленности (инженеры, бухгалтеры, секретари и т.д.), а также наемных работников в торговле и сфере услуг.. Если таких отделов немного, то, вероятно, желательно применить перезапись на основе магических множеств.¹ Переписанный запрос показан на рис. 2. Представление PartialResult представляет представляет частичное вычислениеВычисление — математическое преобразование, позволяющее преобразовывать входящий поток информации в выходной, с отличной от первого структурой. Если смотреть с точки зрения теории информации, вычисление — это получение из входных данных нового знания. в основном блоке запроса на стадии, когда таблицБогуслав Таблиц (словацк. Bohuslav Tablic (Tablicz); 6 сентября 1769, Ческе Брезово, Словакия — 21 января 1832, Костолне Моравце, Словакия) — чешско-словацкий писатель, священник, деятель возрождения словаков-лютеран, подобно тому как Бернолак является деятелем возрождения словаков-католиков. Таблиц учредил в Пресбурге «Общество чешско-словацкой литературы и языка» с целью издавать на понятном народу чешском языке простонародные и школьные книги. Учреждение этого общества было причиной если не процветания словацкой литературы, то появления в пресбургском лицее кафедры словацкого языка, для чего общество собрало большой капитал. Занять кафедру приглашен был Юрай Палкович. Общество скоро распалось, но кафедра продолжала существовать. Молодёжь имела возможность слушать историю своего народа на родном языке. В 1812 г. Таблиц был одним из основателей нового «Литературного общества Горных Городов» (Bergstdte), задававшегося прежней целью; результатом было открытие кафедры словацкого языка и в Банской Штьявнице. Это общество также скоро распалось. Таблиц писал очень много и по различным специальностям. Первое место занимают его «Poesie» (Вацов, 1806-1812). К ним приложены биографии известных словацких деятелей. Его «Sloventi verovci» (Вацов, 1805-1809) — отрывки из произведений древних словацких писателей, в то время почти уже позабытых. Перу Таблица принадлежит также много книг для народа, изданных двумя упомянутыми обществами.ы Emp и Dept уже соединены между собой, но к ним еще не присоединено представление DepAvgSal. На основе этой таблицы PartialResult создается не содержащее дубликатов представление Filter, порождающее множество всех отделов, для которых требуется вычислять среднюю зарплату. Далее это фильтрующее множество используется для ограничения вычислений в исходном представлении.² Представление модифицируется путем включения эквисоединения с фильтрующим множеством (тем самым, ограничивая вычисления в представлении отделами, представляющими интересИнтерес— первоначально средневековый коммерческий и правовой термин (лат.interesse), обозначавший «возмещение ущерба». Отсюда развились, во-первых, чисто юридическое понятие интереса (уже в XIV веке— то, что затрагивает правовые интересы лица), и, во-вторых, финансовое понятие интереса (в XVI веке, сначала в значении «проценты за ссуду», т.е. страховка за риск невозврата).). Наконец, в основном блоке запроса на рис. 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. АрхитектураАрхитектура (лат.architectura от др.-греч. — старший, главный и — строитель, плотник) — искусство проектировать и строить здания и другие сооружения (также их комплексы), создающие материально организованную среду, необходимую людям для их жизни и деятельности, в соответствии с назначением, современными техническими возможностями и эстетическими воззрениями общества. Сами здания и сооружения также называют архитектурой. оптимизации

2.2 Оценочное решение

В данной статье представляется оценочное решение проблемы выбора надлежащей SIPS. Мы реализовали свое решения в системе баз данных DB2 C/S V2 (основанной на системе Starburst [HCL+90]), в которой поддерживается перезапись на основе магических множеств как преобразование «запрос-в-запрос». Архитектура системы показана на рис. 3. Пользовательский запрос поступает прямо на вход оценочного оптимизатора, который решает, выполнять или нет перезапись на основе магических множеств. В то время когда оптимизатор анализирует пространство возможных порядков и методов соединений, он также исследует и пространство возможных вариантов для перезаписи на основе магических множеств. Если принимается решение о том, что никакая перезапись не требуется, оптимизатор генерирует план выполнения обычным образом и посылает его процессору выполнения. С другойДругой — центральная категория современной философии. Актуализация данного понятия связана с такими событиями, как антропологический и лингвистический поворот. Другой — это не Я, тот, кто противостоит мне, находится по ту сторону меня, моих ценностей, моего мировоззрения. И вместе с тем, Другой такой же как Я: он мыслит, чувствует, ходит и т. д. стороны, если оптимизатор решает, что магическая перезапись требуется, то он также выбирает одну конкретную SIPS для перезаписи, которая руководит применением преобразования на основе магических множеств. После того, как запрос перезаписывается, он снова оптимизируется для генерации плана выполнения. В обсуждавшемся выше решении Starburst [MP94] впервые предлагалась двухпроходная архитектураАрхитектура (лат.architectura от др.-греч. — старший, главный и др.-греч. — строитель, плотник) — искусство проектировать и строить здания и другие сооружения (также их комплексы), создающие материально организованную среду, необходимую людям для их жизни и деятельности, в соответствии с назначением, современными техническими возможностями и эстетическими воззрениями общества., и мы используем ту же идею, поскольку хотели бы избежать серьезных изменений в существующих компонентах системы. Альтернативный подход, который мы обсуждаем в разд. 7, состоит в реализации магической перезаписи с помощью алгебраических преобразований (вместо перезаписи «SQL-в-SQL»).

1 При наличии многих вариантов перезаписи на основе магических множеств наиболее практичным подходом в контексте РСУБД является перезапись на основе дополнительных магических множеств, используемая в этой статье.

2 В литературе фильтрующее множество и PartialResult называются «магическим» множеством и «дополнительным» магическим множеством соответственно.

Содержание Вперёд