Магия сохраняет силу

Индерпал Сингх Мумик, Шелдон Финкельштейн, Хамид Пирамеш, Раджу Рамакришнан
Перевод: Сергей Кузнецов

Оригинал: 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. Введение

1.1. Starburst SQL (SBSQL)

2. Связь метода магических множеств с традиционными методами оптимизации

2.1. Проталкивание предикатов

2.2. Корреляция и декорреляция

2.3. Предыдущие работы

3. Определения

4. Расширенное преобразование методом магических множеств

4.1. Проталкивание условий с использованием магии

4.2. Преобразования методом магических множеств для нерекурсивных программ

4.3. Простые bcf-украшения

5. Набросок реализации расширенных магических множеств (EMS)

6. Производительность

6.1. Эксперимент 1

6.2. Эксперимент 2

6.3. Эксперимент 3

7. Заключение

8. Благодарности

Литература

Аннотация

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

1. Введение

«Магические множества» – это название алгоритма преобразования запросов ([BMSU86]) (а теперь класса алгоритмов – обобщенные магические множества (Generalized Magic-sets) в [BR87], магические шаблоны (Magic Templates) в [Ram88], магические условия в [MFPR90]) для обработки рекурсивных запросов, написанных на языке Datalog. Ранее эти алгоритмы не применялись в стандартных реляционных системах баз данных, и их значение для таких систем не было оценено.

В системах реляционных баз данных поддерживается ряд возможностей, находящихся за пределами средств Datalog, включая дубликаты (ведущие к мультимножествам), агрегирование и группировку. Мы расширили подход магических множеств (и язык Datalog) для обработки этих особенностей ([MPR90]), а также показали, что магические множества можно расширить для распространения условий, отличных от сравнения по равенству [MFPR90]. В данной статье эти результаты интегрируются, расширяются и применяются; наша цель состоит в том, чтобы показать, что магические множества обеспечивают надежный метод, который может быть с пользой применен в практических реляционных системах не только для рекурсивных запросов (например, ведомость материалов), но и для не рекурсивных запросов. Этот метод особенно важен для сложных запросов, таких как запросы в системах поддержки принятия решений.

Статья организована следующим образом. Мы представляем короткий подраздел, описывающий SBSQL – язык SQL системы Starburst, в котором поддерживается рекурсия, и приводим пример нелинейного запроса. В разд. 2 обосновывается практичность метода магических множеств путем описания его взаимосвязи с традиционными преобразованиями (такими как выдавливание предикатов) нерекурсивных сложных SQL-запросов. В разд. 3 определяются преобразование магических множеств и некоторые общепринятые родственные понятия. В разд. 4 описывается наше расширение преобразования магических множеств для реляционных систем баз данных, разрешающее сложности, которые возникают при объединении наших предыдущих результатов [MFPR90, MPR90] и их применении к SBSQL. Мы показываем, что можно избежать рекурсии, возникающей при преобразовании нерекурсивных запросов методом магических множеств, и что комбинирование фазы украшения (adornment phase) с преобразованием методом магических множеств позволяет распространять произвольные условия с использованием простого паттерна украшения. В разд. 5 содержится обзор реализации метода магических множеств в прототипе расширяемой реляционной системы баз данных Srarburst в IBM Almaden Research Center ([HFLP89]). В разд. 6 приводятся результаты измерения производительности показывающие, что применение метода магических множеств может повысить эффективность выполнения сложных нерекурсивных SQL-запросов по сравнению с применением традиционных методов, таких как корреляция и декорреляция. В разд. 7 содержится заключение.

1.1. Starburst SQL (SBSQL)

Язык SQL в Starburst (SBSQL) расширен с целью включения рекурсии, определяемых пользователями функций и абстрактных типов данных. В SBSQL поддерживается ряд операций над таблицами, включая SELECT, GROUPBY и UNION. Операция SELECT производит соединения и ограничения входных таблиц и выводит множество столбцов (выражений на столбцах) отобранных кортежей. Опытный пользователь Starburst (настройщик базы данных, Database Customizer) может определять новые операции (например, внешнее соединение) на таблицах, так что компонент перезаписи запросов в Starburst должен легко приспосабливаться к расширениям языка.

Определение 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

Здесь dlnfo является порождаемой таблицей, определяемой табличным выражением. Заголовок этой texp – dlnfo(Dno, Avgsal , Empcount), а тело – (SELECT Dno, AVG(Sal), COUNT(*) FROM emp GROUPBY Dno).

В этой статье для краткости мы используем некоторый вариант синтаксиса стандарта SQL. Мы записываем texp отдельно, как если бы определяли представление, так что (Q) из примера 1.1 записывается как:

(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), мы будем явно именовать атрибуты таблиц в разделе FROM, используя одно и то же имя в двух позициях, что является сокращенной записью предиката сравнения по равенству этих двух столбцов.

Поддержка табличных выражений позволяет нам писать Datalog-запросы. Заголовок и тело правила Datalog отображаются на заголовок и тело texp. Несколько правил Datalog с одинаковыми заголовками отображаются на одно texp с телом, которое объединяет (UNION) запросы, ассоциируемые с телами этих правил.

ПРИМЕР 1.2 (Нелинейный запрос): Рассмотрим систему с большим числом компонентов. Компоненты могут являться базовыми блоками, или для них может требоваться поддержка других компонентов. Пусть у каждого компонента имеется основное и вспомогательное средства поддержки. Если происходит отказ основного средства поддержки, его функции начинает выполнять вспомогательное средство поддержки. Компонент выходит из строя, если происходит отказ его основного и вспомогательного средств поддержки. Некоторые компоненты могут ломаться сами по себе, и нас интересует результирующий набор отказавших компонентов.

Пусть primary(C,P) и secondary(C,S) задают первичные (P) и вспомогательные (S) средства поддержки компонента C соответственно. Пусть broken(B) – множество компонентов, поломавшихся сами по себе. Множество отказавших компонентов fail(C) определяется следующей texp:

(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))

Здесь fail – это имя результирующей таблицы texp F. Выражение F является рекурсивным, поскольку внутри F имеется ссылка на fail. Эта рекурсия является нелинейной (поскольку в списке одного раздела FROM fail появляется дважды), и невозможно написать эквивалентный линейный запрос ([AC89]).

В этой статье мы будем иногда называть запросы на языке SBSQL программами.

2. Связь метода магических множеств с традиционными методами оптимизации

В этом разделе приводятся неформальное описание метода магических множеств и его связи с более традиционными методами преобразований, а также сравнение нашей работы с ранее полученными результатами. В разд. 3 преобразования методом магических множеств определяются формально.

2.1. Проталкивание предикатов

В практических реляционных системах баз данных предикаты выборки проталкиваются как можно ниже в дереве выполнения. Данные фильтруются таким образом, что неподходящие строки не распространяются; в некоторых случах предикаты применяются неявно через путь доступа, выбранный для извлечения данных. Рассмотрим следующий 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 (или фильтрации).

Предикат на Sal + Bonus можно было бы применить после выборки dept, но вместо этого «проталкивание предикатов» перемещает его ближе к доступу к данным. Поскольку вычисление таких предикатов обходится недорого, проталкивание предикатов (с возможно быстрейшим устранением ненужных строк) обычно явялется хорошей стратегией.

Эта идея получает дальнейшее развитие в операции полусоединения [BC8l, RBF+80]. Если отдел служащего не находится в Сан-Хосе, этот служащий не является релевантным (для приведенного выше запроса), так же, как если бы служащий был младшим программистом. Путем вычисления SJDno (номеров отделов, располагающихся в Сан-Хосе) система может использовать модифицированный вариант описанного выше плана выполнения, в котором служащие фильтруются (на основе emp.Dno IN SJDno) до соединения с таблицей dept. Как и при использовании индексов, вводится дополнительная операция (вычисление SJDno и соединение). Применение этой операции означает, что к таблице dept доступ должен производиться дважды: первый раз для вычисления SJDno, а второй – для доступа к соответствующим отделам.

В исходном плане сначала производился доступ к emp, а затем значение Dno передавалось к dept для обеспечения доступа к нужным отделам. Предикат полусоединения, ограничивающий служащих теми, у которых Dno IN SJDno, передается «сторонним образом» в противоположном направлении, от таблицы отделов. Использование информации, передаваемой сторонним образом, является подходом магических множеств – систематическим введением предикатов, основанных на информации, которая передается сторонним образом, так что эти предикаты могут использоваться для как можно более раннего отфильтровывания неуместных данных.

В отличие от стандартного преобразования проталкивания предикатов, магия для конкретного запроса может применяться многими разными способами в соответствии с выбранными «sips» (silde-ways mformatlon passing strategies, стратегиями передачи информации сторонним образом). Sips могут использоваться гибко: для каждого порядка соединений (порядка sips) мы можем выбрать произвольный набор таблиц для генерации связываний и выбрать любой поднабор связываний для проталкивания. Это приводит к обазованию магических предикатов, которые связываются с некоторыми столбцами (аналогично приведенному выше предикату полусоединения для SJDno). Имена, используемые для магических таблиц, показывают, как они создавались – у этих имен имеются верхние индексы, указывающие ограничения на атрибуты таблиц исходного запроса. Эти верхние индексы называются «украшениями» (adornment).

2.2. Корреляция и декорреляция

Несколько авторов изучало подзапросы SQL ([ISO89, ABC+76]) и описывали преобразования для миграции предикатов сквозь них [Kim82, GW87, Day87]. Корреляция, подобно магии, «проталкивает (push down) предикаты» в подзапросы. Обратное преобразование – декорреляция – «вытягивает (pull up) предикаты» из подзапросов. Одним из основных различий между магией и подобными другими методами является то, что магия применяется единообразно к иерархическим (древовидным) и рекурсивным запросам (а также к запросам с общими подвыражениями), а другие методы применяются только к иерархическим запросам.¹⁾ Сравнение эффективности этих методов приводится в разд. 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) выбирает старших программистов, которые получают зарплату, большую средней зарплаты своего отдела. Запрос написан так, что в нем имеется корреляция: для каждого служащего, являющегося старшим программистом, вычисляется средняя зарплата в его отделе, и выбирается служащий, зарплата которого больше вычисленного значения. Не обрабатывается ненужная информация, но средняя заплата отдела может вычисляться много раз (если в отделе работает несколько служащих).²⁾ Кроме того, доступ к el и e2 должен производиться в специальном порядке (сначала el, потом e2). Наконец, обработка e2 является скорее покортежной, чем ориентированной на множества, а именно ориентация на обработку множеств обеспечивает основное преимущество реляционной модели в отношении эффективности. Таким образом, корреляция сокращает преимущества реляционной модели касательно непроцедурности и ориентированности на множества и может приводить к избыточным вычислениям.

Запрос C можно преобразовать в декоррелированный запрос³⁾ D, в котором используется временная таблица dep-avgsal(Dno, Asal), определяемая внутри запроса:

(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)

В отличие от коррелированного запроса, декоррелированный запрос является ориентированным на множества (средние зарплаты вычисляются для всех отделов за одну операцию вместо того, чтобы вычислять среднее значение зарплаты для одного отдела за один раз, когда выбирается служащий этого отдела). Кроме того, новый запрос непроцедурный (два сканирования служащих могут меняться местами). План выполнения может предполагать доступ к таблице служащих по Dno, вычисление средней зарплаты для этого Dno с формированием кортежа таблицы dep_avgsal, и нахождение в каждом отделе всех старших программистов с зарплатой выше средней зарплаты отдела. Но у декорреляции имеется существенный недостаток: средняя зарплата определяется для всех отделов, независимо от того, работают ли в них старшие программисты. Если имеется много отделов, и только в некоторых из них имеются старшие программисты, то стоимость ненужных вычислений будет значительной.

В подходе магических множеств объединяются достоинства методов корреляции и декорреляции, хотя и не бесплатно. После преобразования запроса 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_mag), определить, в каких отделах имеется хотя бы один из таких служащих (mag), вычислить среднюю зарплату только для этих отделов (mag_avgsal) и затем выбрать всех старших программистов (s_mag), которые получают зарплату выше средней зарплаты своего отдела. Порядок доступа может быть другим, как если бы запрос был декоррелированным, и операции являются ориентированными на множества. Более того, не затрагиваются нерелевантные данные, поскольку средняя зарплата вычисляется только для отделов, содержащих старших программистов. Однако эта магика становится возможной за счет вычисления дополнительных таблиц s_mag и mag.⁴⁾

Магический запрос S напоминает приведенный в разд. 2.1 пример с полусоединением. Информация об уместных связываниях (отделы, включающие старших программистов) передается «сторонним образом» от emp к mag_avgsal.

2.3. Предыдущие работы

Ким [Kim82] первым занялся изучением вопроса о том, когда квантифицированные подзапросы можно заменить соединениями (или антисоединениями). Гански и Вонг [GW87] и Дайал [Day87] проделали дополнительную работу как по устранению вложенных подзапросов⁵⁾, так и по повышению эффективности корреляционных запросов. В этих статьях демонстрируется, что корреляционные подзапросы могут быть очень неэффективны, поскольку они не ориентированы на множества. Авторы устраняют корреляцию путем введения дополнительных реляционных операций, включающих внешнее соединение [GW87] и обобщенное агрегирование [Day87]. Преобразования могут применяться к SQL-запросам, написанных специальным образом, когда пользователь либо проталкивает предикаты соединения из запроса в подзапрос, либо пишет предикат, ссылающийся на таблицы, и в позапросе, и в запросе. Эти предикаты, которые мы считаем сторонними предикатами, используются для генерации в запросе связываний.

В отличие от этого, в нашем методе EMS (Extended Magic Sets, расширенные магические множества) для обработки принимаются запросы без указываемой пользователями корреляции, и определяется, какие сторонние предикаты следует протолкнуть. Это является продвижением, поскольку пользователи могут упустить некоторые возможности проталкивания предикатов, а некоторые из них даже невозможно представить синтаксически.⁶⁾ Однако, если пользователи специфицируют корреляционные запросы, желательно преобразовать их в орентированные на множества. Для этой цели мы используем методы, аналогичные представленным в [GW87] и [Day87]. Поэтому мы рассматриваем работы Гански и Дайала как дополнение к нашей работе. В статье Гански иллюстрируется сложность перезаписи запросов, поскольку при этом устранется эффект некоторых предшествующих преобразований. Эта сложность является доводом в пользу нашего единообразного структурного подхода, при использовании которого мы систематически преобразовываем алгебраически общий класс запросов (включающий рекурсию).

---

¹⁾ В рекурсивных запросах может существовать и корреляция, но этот вопрос в данной статье не обсуждается [PF89]

²⁾ Можно было бы реализовывать корреляцию таким образом, что средние зарплаты по отделам сохраняются во временной таблице. Для этого нужны отдельные расходы.

³⁾ В этой статье программа, состоящая из выражений X1, …, Xn, называется программой X.

⁴⁾ Таблица s_mag используется более одного раза и потенциально должна сохраняться во временной таблице. Таблица же mag используется только один раз и может конвейеризоваться.

⁵⁾ Мы используем в Starburst такие правила устранения подзапросов (называемые правилами слияния) для удаления вложенности перед применением преобразований методом магических множеств.

⁶⁾ Например, пользователи не могут протолкнуть предикаты в представления.

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