 |
|
|
 |
|
2009 г.
Магия сохраняет силуИндерпал Сингх Мумик, Шелдон Финкельштейн Оригинал: Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan. Magic is Relevant. Proceedings of the 1990 ACM SIGMOD international conference on Management of data.
Любая достаточно развитая технология Содержание
АннотацияМы определяем преобразование магических множеств для традиционных реляционных систем (с дубликатами, агрегацией и группировкой), а также для реляционных систем, расширенных рекурсией. Мы сравниваем перезапись на основе магических множеств с традиционными методами оптимизации для нерекурсивных запросов и используем эксперименты с производительностью для доказательства того, что преобразование на основе магических множеств часто является более подходящим методом оптимизации.1. Введение«Магические множества» – это название алгоритма преобразования запросов ([BMSU86]) (а теперь класса алгоритмов – обобщенные магические множества (Generalized Magic-sets) в [BR87], магические шаблоны (Magic Templates) в [Ram88], магические условия в [MFPR90]) для обработки рекурсивных запросов, написанных на языке Datalog. Ранее эти алгоритмы не применялись в стандартных реляционных системах баз данных, и их значение для таких систем не было оценено. В системах реляционных баз данных поддерживается ряд возможностей, находящихся за пределами средств Datalog, включая дубликаты (ведущие к мультимножествам), агрегирование Статья организована следующим образом. Мы представляем короткий подраздел, описывающий SBSQL – язык SQL системы 1.1. Starburst SQL (SBSQL)Язык SQL в Starburst (SBSQL) расширен с целью включения рекурсии, определяемых пользователями функций и абстрактных типов данных. В SBSQL поддерживается ряд операций над таблицами, включая Определение 1.1. Табличные выражения: Табличное выражение (table expression, texp) в SBSQL – это выражение, определяющее именованную порождаемую таблицу, которую можно использовать в запросе вместо базовой таблицы. Texp состоит из заголовка и тела. Заголовок texp специфицирует результирующую таблицу (имя, имена атрибутов). Телом texp в SBSQL является запрос, задающий способ формирования результирующей таблицы. ПРИМЕР 1.1 (Табличное выражение): (Q): SELECT Eno, Sal, Avgsal, Empcount
FROM emp, dlnfo(Dno, Avgsal, Empcount) AS
(SELECT Dno, AVG(Sal), COUNT(*)
FROM emp GROUPBY Dno)
WHERE Job = 'SI Programmer' AND
emp.Dno = dlnfo.Dno
Здесь В этой статье для краткости мы используем некоторый вариант синтаксиса стандарта SQL. Мы записываем texp отдельно, как если бы определяли представление, так что (Q) из примера
(Tl): SELECT Eno, Sal, Avgsal, Empcount
FROM emp(Eno, Sal, Dno, Job),
dlnfo(Dno, Avgsal, Empcount)
WHERE Job = '31 Programmer'
(T2): dlnfo(Dno, Avgsal, Empcount) AS
(SELECT Dno, AVG(Sal),COUNT(*)
FROM emp GROUPBY Dno)
Иногда, как в случае (T1), мы будем явно именовать атрибуты таблиц в разделе Поддержка табличных выражений позволяет нам писать Datalog-запросы. Заголовок и тело правила Datalog отображаются на заголовок и тело texp. Несколько правил Datalog с одинаковыми заголовками отображаются на одно texp с телом, которое объединяет ( ПРИМЕР 1.2 (Нелинейный запрос): Рассмотрим систему с большим числом компонентов. Компонент Пусть
(F): fail(C) AS
((SELECT * FROM broken)
UNION DISTINCT
(SELECT p.C
FROM primary p, secondary s, fall fl, fall f2
WHERE fl.C = p.P AND f2.C = s.S AND
p.C = s.C))
Здесь В этой статье мы будем иногда называть запросы на языке SBSQL программами. 2. Связь метода магических множеств с традиционными методами оптимизацииВ этом разделе приводятся неформальное описание метода магических множеств и его связи с более традиционными методами преобразований, а также сравнение нашей работы с ранее полученными результатами. В разд. 3 преобразования методом магических множеств определяются формально.2.1. Проталкивание предикатовВ практических реляционных системах баз данных предикаты выборки проталкиваются как можно ниже в дереве выполнения. Данные Данные (калька от лат.data) — это представление фактов и идей в формализованном виде, пригодном для передачи и обработки в некотором информационном процессе. фильтруются таким образом, что неподходящие строки не распространяются; в некоторых случах предикаты применяются неявно через путь доступа, выбранный для извлечения данных. Рассмотрим следующий SQL-запрос над базовыми таблицами emp(Eno, Ename, Sal, Bonus, Job, Dno, EkldsN) и dept(Dno, Mgrno, Location):
(Q): SELECT Ename,Mgrno FROM emp, dept
WHERE Job = 'Sr Programmer' AND
Sal + Bonus > 50000 AND
emp.Dno = dept.Dno AND
Location = “San Jose" AND
P(emp,dept)
Здесь P – это некоторый сложный подзапрос. СистемаСистема (от др.-греч. — «сочетание»)— множество взаимосвязанных элементов, обособленное от среды и взаимодействующее с ней, как целое. могла бы использовать индекс на Job для доступа только к старшим программистам с немедленным применением предиката на Sal + Bonus, производить доступ к dept с использованием индекса на столбце Dno и немедленным применением предиката на Location, и в заключение выполнять подзапрос P. Использование индексов часто обеспечивает хорошее соотношение «стоимость/эффективность», несмотря на то, что это можно считать дополнительным соединением (с использованием индекса). Индексный доступ может устранять извлечение многих неподходящих строк (и, следовательно, многих нетребуемых страниц данных). Как только мы получаем строку emp, можно передать вниз по дереву emp.Dno, и предикат на Dno можно использовать для доступа к dept (или фильтрации).
Предикат на Эта идея получает дальнейшее развитие В исходном плане сначала производился доступ к В отличие от стандартного преобразования проталкивания предикатов, магия для конкретного запроса может применяться многими разными способами в соответствии с выбранными «sips» (silde-ways mformatlon passing strategies, стратегиями передачи информации сторонним образом). Sips могут использоваться гибко: для каждого порядка соединений (порядка sips) мы можем выбрать произвольный набор таблиц для генерации связываний и выбрать любой поднабор связываний для проталкивания. Это приводит к обазованию магических предикатов, которые связываются с некоторыми столбцами (аналогично приведенному выше предикату полусоединения для 2.2. Корреляция и декорреляцияНесколько авторов изучало подзапросы SQL ([ISO89, ABC+76]) и описывали преобразования для миграции предикатов сквозь них [Kim82, GW87, Day87]. Корреляция, подобно магии, «проталкивает (push down) предикаты» в подзапросы. Обратное преобразование – декорреляция – «вытягивает (pull up) предикаты» из подзапросов. Одним из основных различий между магией и подобными другими методаМетод (от греч. — «способ»)— систематизированная совокупность шагов, действий, которые необходимо предпринять, чтобы решить определенную задачу или достичь определенной цели. В отличие от области знаний или исследований, является авторским, то есть созданным конкретной персоной или группой персон, научной или практической школой. В силу своей ограниченности рамками действия и результата, методы имеют тенденцию морально устаревать, преобразовываясь в другие методы, развиваясь в соответствии с временем, достижениями технической и научной мысли, потребностями общества. Совокупность однородных методов принято называть подходом. Развитие методов является естественным следствием развития научной мысли.ми является то, что магия применяется единообразно к иерархическим (древовидным) и рекурсивным запросам (а также к запросам с общими подвыражениями), а другие методыМетод (от греч. — «способ»)— систематизированная совокупность шагов, действий, которые необходимо предпринять, чтобы решить определенную задачу или достичь определенной цели. В отличие от области знаний или исследований, является авторским, то есть созданным конкретной персоной или группой персон, научной или практической школой. В силу своей ограниченности рамками действия и результата, методы имеют тенденцию морально устаревать, преобразовываясь в другие методы, развиваясь в соответствии с временем, достижениями технической и научной мысли, потребностями общества. Совокупность однородных методов принято называть подходом. Развитие методов является естественным следствием развития научной мысли. применяются только к иерархическим запросам.1) Сравнение эффективности этих методов приводится в разд. 6.
ПРИМЕР 2.1 (Корреляция, декорреляция и магия):
(C): SELECT Ename FROM emp el
WHERE Job = 'Sr Programmer' AND
Sal > (SELECT AVG(e2.Sal) FROM emp e2
WHERE e2.Dno = el.Dno)
Запрос (C) выбирает старших программистов, которые получают зарплату, большую средней зарплаты своего отдела. Запрос написан так, что в нем имеется корреляция: для каждого служащего, являющегося старшим программистом, вычисляется средняя зарплата в его отделе, и выбирается служащий, зарплата которого больше вычисленного значения. Не обрабатывается ненужная информация, но средняя заплата отдела может вычисляться много раз (если в отделе работает несколько служащих).2) Кроме того, доступ к Запрос C можно преобразовать в декоррелированный запрос3) D, в котором используется временная таблица
(Dl): SELECT Ename FROM emp, dep_avgsal
WHERE Job = 'Sr Programmer' AND Sal > Asal
AND emp.Dno = dep_avgsal.Dno
(D2): dep_avgsal(Dno, Asal) AS
(SELECT Dno, AVG(Sa1) FROM emp
GROUPBY Dno)
В отличие от коррелированного запроса, декоррелированный запрос является ориентированным на множества (средние зарплаты вычисляются для всех отделов за одну операцию вместо того, чтобы вычислять среднее значение В подходе магических множеств объединяются достоинства методов корреляции и декорреляции, хотя и не бесплатно. После преобразования запроса C методом магических множеств мы получим следующий магический запрос S:
(Sl): SELECT Ename FROM s_mag, mag_avgsal
WHERE Sal > Asal AND
s_mag.Dno = mag_avgsal.Dno
(S2): mag_avgsal(Dno, Asal) AS
(SELECT Dno, AVG(Sa1) FROM mag, emp
WHERE mag.Dno = emp.Dno GROUPBY Dno)
(S3): mag(Dno) AS
(SELECT DISTINCT Dno FROM s_mag)
(S4): s_mag(Ename, Dno, Sal) AS
(SELECT Ename, Dno, Sal FROM emp
WHERE Job = 'Sr Programmer')
Один из возможных планов выполнения S состоит в том, чтобы выбрать служащих, являющихся старшими программистами ( Магический запрос S напоминает приведенный в разд. 2.1 пример с полусоединением. Информация об уместных связываниях (отделы, включающие старших программистов) передается «сторонним образом» от 2.3. Предыдущие работыКим [Kim82] первым занялся изучением вопроса о том, когда квантифицированные подзапросы можно заменить соединениями (или антисоединениями). Гански и Вонг [GW87] и Дайал [Day87] проделали дополнительную работу как по устранению вложенных подзапросов5), так и по повышению эффективности корреляционных запросов. В этих статьях демонстрируется, что корреляционные подзапросы могут быть очень неэффективны, поскольку они не ориентированы на множества. Авторы устраняют корреляцию путем введения дополнительных реляционных операций, включающих внешнее соединение [GW87] и обобщенное агрегирование [Day87]. Преобразования могут применяться к SQL-запросам, написанных специальным образом, когда пользовательПользователь— лицо или организация, которое использует действующую систему для выполнения конкретной функции. либо проталкивает предикаты соединения из запроса в подзапрос, либо пишет предикат, ссылающийся на таблицы, и в позапросе, и в запросе. Эти предикаты, которые мы считаем сторонними предикатами, используются для генерации в запросе связываний.
В отличие от этого, в нашем методе EMS (Extended Magic Sets, расширенные магические множества) для обработки принимаются запросы без указываемой пользователями корреляции, и определяется, какие сторонние предикаты следует протолкнуть. Это является продвижением, поскольку пользователи могут упустить некоторые возможности проталкивания предикатов, а некоторые из них даже невозможно 1) В рекурсивных запросах может существовать и корреляция, но этот вопрос в данной статье не обсуждается [PF89] 2) Можно было бы реализовывать корреляцию таким образом, что средние зарплаты по отделам сохраняются во временной таблице. Для этого нужны отдельные расходы. 3) В этой статье программа, состоящая из выражений X1, …, Xn, называется программой X. 4) Таблица 5) Мы используем в Starburst такие правила устранения подзапросов (называемые правилами слияния) для удаления вложенности перед применением преобразований методом магических множеств. 6) Например, пользователи не могут протолкнуть предикаты в представления.
|
| ellspacing="0" cellpadding="0" border=0> | ||||||||||||
|
||||||||||||
