Корреляция и декорреляция
Несколько авторов изучало подзапросы 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.
Литература
[A+85] Anon et al. A Measure of Transaction Processing Power. Datamation, April 1985.
[ABC+76] M. Astrahan et al. System R: Relational approach to database management. ACM TODS, 1(2), June 1976.
[AC89] F. Afrati and S. Cosmadakis. Expressiveness of Restricted Recursive Queries. In STOC 1989.
[Agr87] R. Agrawal. Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. In Data Engineering 1987.
[BC81] P. Bernstein and D. Chiu. Using Semijoins to Solve Relational Queries. JACM, 28(1):25--40, 1981.
[BMSU86] F. Bancilhon, D. Maier, Y. Sagiv, and J. Ullman. Magic Sets and other Strange Ways to Implement Logic Programs. In PODS 1986.
[BR86] F. Bancilhon and R. Ramakrishnan. An Amateur's Introduction to Recursive Query Processing Strategies. In SIGMOD 1986.
[BR87] C. Beeri and R. Ramakrishnan. On the Power of Magic. In PODS 1987.
[Day87] U. Dayal. Of Nests and Trees: A Unified Approach to Processing Queries that Contain Nested Subqueries, Aggregates, and Quantifiers. In VLDB 1987.
[DB88] IBM. IBM Database 2 Performance Monitor Report Reference, December 1988. Number: IBM SH206858.
[GW87] R. Ganski and H. Wong. Optimization of Nested SQL Queries Revisited. In SIGMOD 1987.
[HFLP89] L. Haas, J. Freytag, G. Lohman, and H. Pirahesh. Extensible Query Processing in Starburst. In SIGMOD 1989.
[HN84] L. Henschen and S. Naqvi. On Compiling Queries in Recursive FirstOrder Databases. JACM, 31(1):47--85, January 1984.
[HP88] W. Hasan and H. Pirahesh. Query Rewrite Optimization in Starburst. IBM Research report, RJ 6367 (62349), August 1988.
[ISO89] ISO ANSI. ISOANSI Working Draft: Database Language SQL2 and SQL3; X3H2; ISO/IEC JTC1/SC21/WG3, 1989.
[Kim82] W. Kim. On Optimizing an SQLlike Nested Query. TODS, 7(3), Sep 1982.
[Loh88] G. Lohman. Grammarlike Functional Rules for Representing Query Optimization Alternatives. In SIGMOD 1988.
[Loo86] C. Loosley. Measuring IBM Database 2 Release 2 The Benchmark Game. InfoDB, 1(2), 1986.
[MFPR90] I. Mumick, S. Finkelstein, H. Pirahesh, and R. Ramakrishnan. Magic Conditions. In PODS 1990.
[MHWC90] C. Mohan, D. Haderle, Y. Wang, and J. Cheng. Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. In EDBT 1990.
[MPR90] I. Mumick, H. Pirahesh, and R. Ramakrishnan. The Magic of Duplicates and Aggregates. In VLDB 1990.
[NRSU89] J. Naughton, R. Ramakrishnan, Y. Sagiv, and J. Ullman. Arity Reduction Through Factoring. In VLDB 1989.
[O'N89] P. O'Neil. Revisiting DBMS Benchmarks. Datamation, Sep 1989.
[PF89] H. Pirahesh and S. Finkelstein. Semantics of the Query Graph Model. IBM Internal Report, 1989
[Pir89] H. Pirahesh. Early experience with rulebased query rewrite optimization. In Optimization workshop, SIGMOD 1989.
[Ram88] R. Ramakrishnan. Magic Templates: A Spellbinding Approach to Logic Programs. In ICLP 1988.
[RBF+80] J. Rothnie Jr. et al. Introduction to a System for Distributed Databases (SDD1). TODS, 5(1):1--17, March 1980.
[SAC + 79] P. Selinger et al. Access Path Selection in a Relational Database Management System. In SIGMOD 1979.
[TG84] J. Teng and R. Gumaer. Managing IBM Database 2 Buffers to Maximize Performance. IBM System Journal, 23(2), 1984.
[TOB89] C. Turbyfill, C. Orji, and D. Bitton. AS3AP A Comparative Relational Database Benchmark. In IEEE Compcon 1989.
[TPC89] TPC benchmark group. TPC Benchmark, A Draft 6PR Proposed Standard, 1989. Available from ITOM International Co., PO Box 1450, Los Altos, CA 94023.
Набросок реализации расширенных магических множеств (EMS)
Мы реализуем EMS в Starburst. У нас имеется псевдокод, и C-код, выполняющий преобразования в простых случаях. В этом разделе мы приводим набросок своей реализации.
EMS является частью фазы перезаписи запросов в оптимизаторе Starburst. Перезаписи выполняются (продукционной) системой, основанной на правилах, в которой каждое преобразование запроса кодируется в виде правила перезаписи [HP88]. Процессор прямого построения цепочек обходит граф запроса (обычно) в глубину, применяя правила перезаписи. EMS применяется к элементам графа, представляющим табличные выражения, к одному табличному выражению за раз. Многочисленные возбуждения правила EMS по мере обхода графа совокупно производят преобразованный запрос.
В системе правил Starburst, кроме правила магических множеств, имеется ряд других правил перезаписи. Правила проталкивания предикатов определяют, какие предикаты и в какой форме выталкиваются из табличных выражений в таблицы, на которые в них имеются ссылки. После этого правило EMS размещает предикаты в правильных местах (как магические множества).
Способ применения магических множеств к таблице может зависеть от операции в табличном выражении. Например, магия не может быть применена к такой операции как GROUPBY (к плохим операциям), а к такой операции как SELECT – применима (к хорошим операциям).
Когда производится магическая обработка табличного выражения для таблицы t, предыдущая обработка обеспечивает украшение заголовка t, наличие магической таблицы mt для t и (для хороших операций) то, что mt является опорной и присоединенной к телу табличного выражения. Кроме того, должен быть известен порядок SIPS внутри табличного выражения.
В течение магической обработки t все предикаты в табличном выражении проталкиваются в каждую таблицу r, на которую имеются ссылки из табличного выражения (с использованием правил проталкивания предикатов). Для каждой r определяется украшение α, и создается табличное выражение для rα с телом, идентичным телу табличного выражения для r.
Для rα на основе его использования в t формируется магическое множество m_rα и, если r является хорошей, оно делается опорным и добавляется к табличному выражению для rα.
Магическая обработка производится для каждого табличного выражения, проходимого при обходе графа запроса. Мы избегаем повторной обработки табличного выражения, за исключением плохих табличных выражений при особых условиях. Для нашего алгоритма EMS справедлива следующая теорема (в предположении, что сначала мы избавляемся ото всех циклов в запросе Q, состоящем исключительно из плохих таблиц).
Теорема 5.1 Для любого графа запроса Q алгоритм EMS завершается, и EMS(Q) эквивалентен Q при применении стратегии выполнения Starburst.
Украшения и магические преобразования объединяются в однофазный алгоритм (разд. 4.3). По большей части используется простое bcf-украшение, хотя для плохих операций требуются специальные улучшенные украшения. Алгоритм EMS является расширяемым по отношению к (1) новым операциям в табличных выражениях и (2) стратегии обхода (в глубину, в ширину, снизу-вверх и т.д.).
Определения
Преобразование методом магических множеств: Алгоритм магических множеств перезаписывает запрос таким образом, что при вычислении с фиксированной точкой преобразованного запроса не генерируются нерелевантные кортежи. Идея состоит в том, чтобы вычислить набор дополнительных таблиц, которые содержат связывания, используемые для ограничения таблицы. Затем табличные выражения в запросе модифицируются путем соединения дополнительных таблиц, которые действуют как фильтры и препятствуют генерации нерелевантных кортежей. Однако на первом шаге мы производим украшенный (adorned) запрос, в котором таблицы украшаются аннотациями, показывающими, какие аргументы связываются с константами, какие ограничиваются условиями, и какие являются свободными в табличном выражении с данной таблицей. Для каждой таблицы мы имеем украшенную версию, соответствующую всем использованиям этой таблицы с применением паттерна связывания, который описывается данным украшением. Разные украшенные версии, по существу, трактуются как разные таблицы (возможно, по-разному разрешаемые). Например, pbf и pfb трактуются как разные таблицы (имена таблиц). Украшение (adornment) для некоторой n-арной таблицы определяется как строка из символов b, c и f. Позиции аргументов, которые трактуются как свободные (те, на которых нет предикатов), обозначаются как f, а позиции, которые связываются с конечным множеством данных значений (предикатами сравнения на равенство) обозначаются как b. Позиции аргументов, которые ограничены в цели некоторым предикатом, отличным от предиката сравнения на равенство, обозначаются как c.
В преобразованиях методом магических множеств из [BMSU86, BR87] распространяются связывания (предикаты сравнения на равенство) в Datalog с использованием украшений b и f. Условия игнорируются. В [MPR90] преобразования методом магических множеств расширяются для распространение связываний в программах с дубликатами и агрегированием. Расширение для работы с условиями ([MFPR90]) нуждается в адаптации для работы в присутствии дубликатов, и мы представляем эту идею в разд. 4.1.
В следующем определении мы игнорируем украшения и условия.
Алгоритм магических множеств можно понимать как двухшаговое преобразование, в котором мы сначала получаем украшенный запрос Pad, а затем применяем следующее преобразование:
Мы создаем новый запрос Pmq. Изначально этот запрос пуст.
Для каждой таблицы p из Pad создается новая таблица без дубликатов m_p. Ее арность равна числу связанных аргументов p.
Для каждого табличного выражения в Pad к Pmq добавляется модифицированная версия. Если у табличного выражения r имеется заголовок, скажем, p(t) (t – это сокращение для всех атрибутов p), то модифицированная версия получается путем присоединения к телу таблицы m_p(
Заметим, что с каждой таблицей в Pad ассоциируется магическая таблица. Если генерируется несколько табличных выражений с одним и тем же заголовком, они заменяются одним табличным выражением, в теле которого содержится объединение соответствующих тел.
Интуитивно преобразование методом магических множеств включает добавление в каждом операторе SQL магических таблиц в раздел FROM и предикатов сравнения по равенству в раздел WHERE.
ПРИМЕР 3.1 (Преобразование методом магических множеств): Рассмотрим запрос D из примера 2.1. Нам требуется вычислить среднюю зарплату в отделах в представлении dep_avgsal в том и только в том случае, когда в отделе имеется старший программист, поскольку в противном случае средняя зарплата не релевантна.
При применении метода магических множеств эта оптимизация достигается путем определения магической таблицы (M3) и перезаписи D1 и D2 как M1 и M2.
(Ml): SELECT Ename FROM emp, dep_avgsalbf
WHERE Job = 'Sr Programmer' AND Sal > Asal AND emp.Dno = dep_avgsalbf.Dno
(M2): dep_avgsalbf(Dno, Asal) AS (SELECT DUO, AVG(Sa1) FROM m_dep_avgsalbf, emp WHERE m_dep_avgsalbf.Dno = emp.Dno GROUPBY Dno)
(M3): m_dep_avgsalbf(Dno) AS (SELECT DISTINCT Dno FROM emp WHERE Job = 'Sr Programmer')
Здесь m_dep_avgsalbf является магической таблицей для представления dep_avgsalbf, выдающей уместные отделы, для которых требуется вычислять представление. Верхний индекс bf показывает, что представление dep_avgsalbf всегда будет вычисляться с использованием первого аргумента, связанного с набром кортежей, а второй аргумент является свободным.
Вспомогательные магические множества: В магическом запросе примера 3.1 предикат Job = 'Sr Programmer' повторяется в операторах M1 и M3. В программе S из примера 2.1 результат выборки сохранялся в s_mag и использовался как общее подвыражение при вычислении Sl и S3. Таблицы, подобные в s_mag, называются дополнительными магическими множествами. Программа D преобразуется в программу S с использованием дополнительных преобразований методом магических множеств ([BR87]). Мы используем дополнительные магические множества в разд. 6, потому что использование общих подвыражений существенно влияет на эффективность. Для простоты объяснений в других разделах мы используем просто магические множества.
SIPS: Sideways Information Passing Strategy определяет решение о том, как передавать информацию сторонним образом в теле табличного выражения при его вычислении. Передаваемая информация поступает из предикатов табличного выражения. SIPS определяется формально в [BR87, MFPR90].
SIPS может быть полной (в том смысле, что все подходящие предикаты используются настолько рано, насколько это возможно) или частичной. Полная SIPS может определяться путем упорядочения таблиц в разделе FROM.
Мы называем этот порядок порядком SIPS.
При преобразованиях методом магических множеств информация передается сторонним образом между соединяемыми таблицами в соответствии с заданным порядком SIPS. В этой статье мы предполагаем, что таблицы перечисляются в разделе FROM в порядке SIPS.
Графы зависимости: Графы зависимости широко используются для распознавания рекурсии. В табличном выражении таблицы в теле (в разделе FROM) используются для определения таблицы в заголовке. Если в некотором табличном выражении таблица q определяет таблицу r, мы обозначаем это как q → r, что называется дугой зависимости. Мы определяем →→ как транзитивное замыкание →. Запрос является рекурсивным в том и только в том случае, когда в графе зависимостей имеются циклы, т.е. если существует таблица q, такая что (q →→ q). Все таблицы в сильно связанном компоненте (strongly connected component, sсс) графа зависимости называются взаимно рекурсивными.
Предыдущие работы
Ким [Kim82] первым занялся изучением вопроса о том, когда квантифицированные подзапросы можно заменить соединениями (или антисоединениями). Гански и Вонг [GW87] и Дайал [Day87] проделали дополнительную работу как по устранению вложенных подзапросов, так и по повышению эффективности корреляционных запросов. В этих статьях демонстрируется, что корреляционные подзапросы могут быть очень неэффективны, поскольку они не ориентированы на множества. Авторы устраняют корреляцию путем введения дополнительных реляционных операций, включающих внешнее соединение [GW87] и обобщенное агрегирование [Day87]. Преобразования могут применяться к SQL-запросам, написанных специальным образом, когда пользователь либо проталкивает предикаты соединения из запроса в подзапрос, либо пишет предикат, ссылающийся на таблицы, и в позапросе, и в запросе. Эти предикаты, которые мы считаем сторонними предикатами, используются для генерации в запросе связываний.
В отличие от этого, в нашем методе EMS (Extended Magic Sets, расширенные магические множества) для обработки принимаются запросы без указываемой пользователями корреляции, и определяется, какие сторонние предикаты следует протолкнуть. Это является продвижением, поскольку пользователи могут упустить некоторые возможности проталкивания предикатов, а некоторые из них даже невозможно представить синтаксически. Однако, если пользователи специфицируют корреляционные запросы, желательно преобразовать их в орентированные на множества. Для этой цели мы используем методы, аналогичные представленным в [GW87] и [Day87]. Поэтому мы рассматриваем работы Гански и Дайала как дополнение к нашей работе. В статье Гански иллюстрируется сложность перезаписи запросов, поскольку при этом устранется эффект некоторых предшествующих преобразований. Эта сложность является доводом в пользу нашего единообразного структурного подхода, при использовании которого мы систематически преобразовываем алгебраически общий класс запросов (включающий рекурсию).
1) В рекурсивных запросах может существовать и корреляция, но этот вопрос в данной статье не обсуждается [PF89]
2) Можно было бы реализовывать корреляцию таким образом, что средние зарплаты по отделам сохраняются во временной таблице. Для этого нужны отдельные расходы.
3) В этой статье программа, состоящая из выражений X1, …, Xn, называется программой X.
4) Таблица s_mag используется более одного раза и потенциально должна сохраняться во временной таблице. Таблица же mag используется только один раз и может конвейеризоваться.
5) Мы используем в Starburst такие правила устранения подзапросов (называемые правилами слияния) для удаления вложенности перед применением преобразований методом магических множеств.
6) Например, пользователи не могут протолкнуть предикаты в представления.
Преобразования методом магических множеств для нерекурсивных программ
Хорошо известно, что у преобразований методом магических множеств имеется нежелательное свойство слияния сильно связанных компонентов. В результате нерекурсивная программа может стать рекурсивной.
ПРИМЕР 4.2 (Рекурсия из-за магии): В программе P
(Pl): SELECT A, B FROM r(A,C), q(C,B) WHERE A = 10
(P2): r(A,C) AS (SELECT A, C FROM q(A, D), t(D, C))
(P3): q(E,F) AS (SELECT E, F FROM s(E, F))
q используется дважды, в (Pl) и (P2), в обоих местах с украшением bf. Для qbf имеются связывания из rbf (Pl) и из m_rbf (P2). Поэтому магическим множеством является объединение. Магический запрос выглядит следующим образом:
(Ml): SELECT A, B FROM rbf(A,C), qbf(C,B) WHERE A = 10
(M2): rbf(A,C) AS (SELECT A, C
FROM m_rbf(A), qbf(A,D), t(D,C))
(M3): qbf(E,F) AS (SELECT E, F FROM m_qbf(E), s(E,F))
(M4): m_rbf (l0)
(M5): m_qbf(A) AS (5a) ((SELECT C FROM rbf(A,C) WHERE A = 10) UNION DISTINCT (5b) (SELECT A FROM m_rbf(A)))
Запрос (M) является рекурсивным, поскольку в его графе зависимостей имеется цикл qbf→(M2)rbf→(5a)m_qbf→(M3)qbf.
Во многих существующих СУБД рекурсия не поддерживается. Если в результате преобразований методом магических множеств будут производиться рекурсивные запросы, то применимость расширенных преобразований будет серьезно ограничена.
Рассмотрим пример 4.2. Таблица qbf является рекурсивной, но эта рекурсия введена заново через магическую таблицу m_qbf (как это и должно быть для любой рекурсии, вводимой путем магических преобразований). Кортеж m_qbf (10) вычисляется в (5b) и приводит к кортежам в qbf через (M3). На их основе генерируются кортежи для rbf через (M2). На основе кортежей из rbf генерируются новые кортежи в m_qbf (5a) и, следовательно, в qbf . Но появление новых кортежей в qbf не может возбудить тело (M2) для генерации новых кортежей в rbf. Таким образом, эта рекурсия «сама себя не подкармливает» и заканчивается после первого цикла.
Поэтому данную программу можно переписать без рекурсии.
Можно избежать введения рекурсии в магической программе, если не распознавать общих подвыражений. Если относиться к двум использованиям q в программе P как к двум разным таблицам q1 и q2, то преобразование методом магических множеств не приведет к появлению рекурсии, в чем можно убедиться, произведя преобразование методом магических множеств для программы P’, которая получается из P с использованием q1 и q2, определяемых в соответствии с P2.
Уточним интуитивные размышления, на которых основан приведенный пример.
Утверждение 4.1 Пусть M является запросом, полученным путем магического преобразования заданного запроса P в соответствии с набором полных SIPS. Тогда: (A) Если P является запросом с древовидной структурой, и (B) если P является направленным ациклическим графом (DAG), то в M будет иметься ограниченная рекурсия, которую можно избежать, не образуя общих подвыражений.
Производительность
В этом разделе мы представляем результаты измерения производительности, которые иллюстрируют ускорение с помощью EMS выполнения сложных запросов (таких как запросы поддержки принятия решений), состоящих из нескольких блоков запросов. Выполнение таких запросов нередко занимает несколько часов (и даже дней). Преобразование запросов может повысить производительность на несколько порядков.
Для исчерпывающей оценки производительности требуется определение тестовой базы данных и набора запросов для особой рабочей нагрузки. Мы концентрируемся на рабочей нагрузке из сложных запросов (с несколькими предикатами, соединениями, агрегацией и подзапросами), а не на транзакционной рабочей нагрузке с относительно простыми запросами. Хотя транзакционные тестовые наборы предложены [A+ 85, TPC89], рабочие нагрузки со сложными запросами все еще находятся на предварительной стадии ([TOB89, O'N89]). Чтобы измерить влияние на производительность преобразований методом магических множеств, мы используем масштабированную (в десять раз) версию тестовой базы DB2, описанной в [Loo86].
Преобразования методом магических множеств изучались в контексте рекурсивных запросов, и полезность магических множеств для рекурсивных запросов разъясняется в [BR86, BR87]. В этом разделе мы изучаем нерекурсивные запросы.
Наши измерения производительности выполнялись на реляционной СУБД IBM DB2 V2R2 с использованием средства мониторинга производительности DB2PM [DB88] для определения общего времени (общего времени, занимаемого у системы для выполнения запроса) и времени ввода/вывода (времени занятости устройств ввода/вывода). Мы измеряли эффективность выполнения каждого запроса до и после применения преобразований методом магических множеств. Оба представления запроса проходили процесс компиляции запроса, включая оценочную оптимизацию. Числовые показатели производительности для нескольких запросов, полученные при наших измерениях, описываются ниже.
Тестовая база данных DB2 основывается на приложении отслеживания и управления запасами.
У рабочих центров, представленных таблицей wkc, имеются месторасположения (locatn). Изделия (itm) обработываются в месторасположениях внутри рабочих центров, и эта взаимосвязь фиксируется в таблице itl. Для каждого изделия может иметься несколько заказов (itp). Некоторые физические характеристики базы данных показаны в таб. 1.
Таб. 1. Тестовая база данных
Проталкивание предикатов и ориентированные на множества вычисления являются двумя ключевыми факторами оптимизации и выполнения запросов. Преобразование методом магических множеств обеспечивает оба эти преимущества. Хорошо известно проталкивание локальных предикатов, таких как (Job = 'Sr Programmer') в запросе D1 примера 2.1. Мы концентируемся на проталкивании предиктов соединения, которые передают информацию сторонним образом (SIPS-предикаты), такие как (emp.Dno = dep_avgsal.Dno) в запросе D1 примера 2.1.
Вычисления, ориентированные на множества, являются желательными, поскольку обычно приводят к повышению эффективности по сравнению с эквивалентными пофрагментными или покортежными вычислениями. Проталкивание предикатов соединения (или SIPS) путем использования корреляции фрагментирует вычисления, приводя к вычислению подзапроса для каждого переданного значения. В результате мы можем потерять преимущество последовательного упреждающего чтения ([TG84]), поскольку в каждом фрагменте вычислений не производится доступ к достаточному числу страниц, чтобы воспользоваться полным преимуществом упреждающего чтения для амортизации расходов ввода/вывода для большого числа страниц. Неэффективность может также возникать при доступе к данным через некластеризованные индексы.
Если вычисления не фрагментированны, мы извлекаем из такого индекса TID’ы требуемых кортежей, сортируем результаты по идентификаторам страниц и затем производим ввод/вывод ([MHWC90]). Следовательно, даже нужные страницы считываются только один раз. При фрагментированной обработке одна и та же страница может считываться много раз, по одному разу для каждого фрагмента, в котором требуется кортеж в данной странице.
Далее, для каждого фрагмента имеется некоторая фиксированная стоимость, связанная с такими операциями, как открытие и закрытие сканирования и инициализация сортировки (например, инициализация деревьев выборки при сортировке повторной выборкой). При обработке, ориентированной на множества, эти фиксированные расходы тратятся только один раз. При использовании корреляции эти фиксированные расходы тратятся по разу на каждое вычисление подзапроса. Поэтому, как мы увидим в разд. 6.3, преобразования запросов, приводящие к обработке, не ориентированной на множества, могут существенно ухудшить эффективность.
Оценка эффективности метода магических множеств основывается на двух обсуждавшихся выше ключевых факторах: проталкивание предикатов (или сторонняя передача информации) и ориентированная на множества обработка. Влияние проталкивания предикатов зависит от влияния связывания на план запроса (или части запроса). Например, преобразование методом магических множеств может обеспечить связывание для столбца, так что индекс на этом столбце становится эффективным путем доступа. Влияние обработки, ориентированной на множества, зависит от мощности связывающего множества (с дубликатами и без дубликатов). Чем больше мощность, тем сильнее преимущество использования ориентированной на множества передачи информации. Имеются многочисленные запросы, для которых важны оба фактора. Сейчас мы представим некоторые из многих запросов, использованных в наших экспериментах.
Простые bcf-украшения
В преобразованиях методом магических множеств, рассматриваемых в [BMSU86, BR87, MFPR90], предполагается, что на вход поступает уже украшенная программа. Поэтому в преобразовании требуются две фазы. На первой фазе программа украшается, а на второй – магически преобразуется. В этом подразделе мы представляем однофазный алгоритм, совместно выполняющий украшение и магическое преобразование, и показываем, как это может помочь для сокращения сложности украшений.
Мы видим, что украшения обеспечивают три функции:
Функция 1: Украшение α на таблице t является абстракцией для ограничения таблицы t в точке ее использования. Эта абстракция α, а не реальное ограничение, используется для принятия решения о том, как будет вычисляться табличное выражение для tα.
Функция 2: tα вычисляется идентичным образом для всех ограничений, абстрагируемых украшением α (одни и те же SIPS, порядок SIPS, порядок соединений и украшения для таблиц, на которые имеются ссылки в табличном выражении t). Следовательно, если абстракция не является хорошей, то для некоторых ограничений tα будет разрешаться не оптимально. Украшение должно быть правильным ([MFPR90]) в том смысле, что оно должно позволять производить выбор оптимального вычисления всех ограничений (внутри класса ограничений, которые пытает фиксировать паттерн украшения), генерирующих это украшение.
Функция 3: Украшения указывают, когда в двух использованиях t может разделяться одна и та же копия t как общее подвыражение. Основанием для того требования, чтобы в использованиях имелось одно и то же украшение, является то, что тогда магические множества генерируются на основе этих использований с одними и теми же аргументами, что позволяет применять объединения.
В паттерне bcf-украшения, введенном в [MFPR90], c-украшение используется только для независимых условий. Условие на атрибуте X называется независимым, если оно может быть выражено без ссылки на какой-либо свободный (f) атрибут. Таким образом, условие X > 10 является независимым.
Условие X > Y независимо, если атрибут Y является связанным, в противном случае это условие зависимо. Алгоритм украшения и следующий за ним GMT из [MFPR90] работают в предположении, что проталкиваются только независимые условия, и что из заданных условий не выводятся какие-либо новые. В [MFPR90] также говорится, что при использовании двухфазного алгоритма невозможно вылавливать и проталкивать зависимые и более общие типы условий на основе паттерна bcf-украшения. Для проталкивания таких условий требуются более сильные паттерны.
В своем однофазном алгоритме мы генерируем магические множества для таблицы t по мере генерации ее украшений, до украшения тела табличного выражения, определяющего t. Далее, когда мы определяем SIPS в табличном выражении tα и украшаем таблицы, на которые в нем имеются ссылки, мы знаем реальные условия на tα (поскольку можем посмотреть на магическое множество). Эти реальные условия используются для обеспечения лучшего выбора способа вычисления табличного выражения.
Определим паттерн простого bcf-украшения аналогично bcf-паттерну из [MFPR90] (обсуждавшегося в разд. 4.1) за исключением того, что украшение c на атрибуте теперь представляет любой тип условия на этом атрибуте, а не только независимое условие.
Теперь мы объясним, каким образом возможность генерации магических множеств при украшении табличного выражения для t обеспечивает поддержку паттерном простого bcf-украшения всех трех упомянутых выше функций украшений, при том, что украшение c представляет произвольное условие.
В следующей лемме мы используем определение опорных (grounding) таблиц из [MFPR90]. При заданном условии p на порождаемой таблице t набор таблиц раздела FROM табличного выражения для t, содержащих все атрибуты, на которые имеются ссылки из p, называется опорным набором. Например, в операторе P2 примера 4.1 s является опорной таблицей для ограничения X > 10.
Лемма 4.1 Пусть p1 и p2 – два ограничения на одних и тех же атрибутах порождаемой таблицы t.
Тогда, если множество G является опорным для p1, то G является опорным множеством и для p2.
Используя Лемму 4.1, мы покажем, что однофазный алгоритм с простыми bcf-украшениями выполняет все функции, которые должны выполнять украшения.
Функция 1: Если реальные ограничения на таблице доступны во время украшения ее тела, то для функции 1 украшения больше не требуются. В результате абстракция, которую они представляют, не является важной.
Функция 2: Функция 2 обеспечивается паттерном простых bcf-украшений для класса произвольных ограничений; это следует из Леммы 4.1 и основного преобразования методом магических множеств [MFPR90]. Проиллюстрируем это на примере.
ПРИМЕР 4.3 (Простое bcf-украшение):
(P1): SELECT X,Y,Z FROM t(X,Y,Z) WHERE X > 10 AND Y > 10
(P2): SELECT X,Y,Z FROM t(X,Y,Z) WHERE X > Y
(P13): t(X,Y,Z) AS (SELECT DISTINCT X,Y,Z FROM q1(X), q2(Y), u(X,Z))
Для обоих запросов P1 и P2 генерируется украшение tccf. По Лемме 4.1 {q1,q2} является опорным множеством для любого ограничения над двумя первыми аргументами t. Таблицы q1 и q2 должны украшаться по-разному для двух использований tccf, а u должно украшаться как ubf для обоих использований. Если бы мы украшали программу без конструирования магических множеств и без использования информации, за исключением украшения ccf на t, то мы не смогли бы произвести желаемое украшение. Однако с использованием своего однофазного алгоритма мы получаем:
(M1): SELECT X, Y, Z FROM tccf(X,Y,Z) WHERE X > 10 AND Y > 10
(M2): SELECT X, Y, Z FROM tccf(X,Y,Z) WHERE X > Y
(M3): tccf (X,Y,Z) AS SELECT DISTINCT X, Y, Z FROM m_tccf (X,Y), ubf (X,Z))
(M4): m_tccf(X,Y) AS ((SELECT X, Y FROM q1c(X), q2c(Y) WHERE X > 10 AND Y > 10) UNION DISTINCT (SELECT X, Y FROM q1f(X), q2c(Y) WHERE X > Y ))
Отметим разные украшения для q1 в двух операторах SELECT в (M4) и украшение b в (M3), появившиеся по причине наличия магических множеств.
Вообще говоря, для c-украшенной таблицы t GMT переводит опорные таблицы tα в дополнительную таблицу. Для любых двух ограничений r1 и r2, генерирующих одно и то же bcf-украшение α на t, опорные таблицы q являются одними и теми же (Лемма 4.1). Таблица q будет копироваться в две таблицы – в (M1) вместе с r1 и в (M2) вместе с r2. Если эти ограничения обладают полностью различной природой, то в (M1) и (M2) для таблиц q могли бы выбираться разные украшения и разные порядки SIPS. Однако в исходном texp для tα в дополнительные магические множества выглядят как генерирующие связывания для всех украшений b или c, независимо от природы ограничений. Поскольку мы не различаем типы связывания при принятии решения о вычислении табличного выражения, вычисление tα будет оптимальным для обоих ограничений.
Функция 3: Паттерн простых bcf-украшений выполняет функцию 3. Если при двух использованиях таблицы в условиях применяются одни и те же аргументы, то и у их опорных магических множеств будут одни и те же аргументы.
7) В разд. 4.3 мы покажим, как можно объединить эти два шага.
8) В запросе с древовидной структурой отсутствуют общие подвыражения.
9) В DAG могут иметься общие подвыражения, но отсутствует рекурсия.
10) Как отмечалось в подразделе 4.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).
Проталкивание условий с использованием магии
В основном преобразовании на основе магических множеств, как оно представлено в [MFPR90], не сохраняется семантика дубликатов. Рассмотрим простой пример.
ПРИМЕР 4.1 Рассмотрим следующую программу P, где p1 и p2 – произвольные встроенные предикаты (условия), а u, v, s и w – EDB-отношения. (EDB – extensional database.)
(Pl): r(X,Z) AS ((SELECT X, Z
FROM tcf(X,Y), u(Y,Z) WHERE p1(X)) UNION ALL (SELECT X, Z
FROM tcf(X,Y), v(Y,Z) WHERE p2(X)))
(P2): tcf(X,Z) AS (SELECT X, Z FROM s(X,Y), w(Y,Z))
Пусть s = [(1,2),(1,2)], w = [(2,3)], u = [(3,4)] и v = [(3,4)]. Пусть p1(1) и p2(1) есть true. Тогда в соответствии с семантикой дубликатов программа P определяет r как мультимножество [(1,4),(1,4),(1,4),(1,4)].
GMT преобразует определение P2 в следующее:
(M2): tcf(X,Z) AS (SELECT X, Z FROM m(X,Y), w(Y,Z))
(M3): m(X,Y) AS ((SELECT X, Y FROM s(X,Y) WHERE p1(X)) UNION DISTINCT (SELECT X, Y FROM s(X,Y) WHERE p2(X)))
Для завершения процесса создания магической программы Pl копируется в Ml. В представлении m имеется одна копия кортежа (1,2), и, следовательно, в представлении r будут иметься две копии кортежа (1,4). В результате программы P и M не эквивалентны по отношению к дубликатам. Определение m с использованием UNION ALL нам не помогает, потому что тогда в m будут иметься четыре копии (1,2), и в r будут иметься восемь копий (1,4).
Кстати, если бы либо r, либо t были DISTINCT, GMT сохранял бы семантику запроса.
GMT конструирует специальные магические множества (m), называемые дополнительными магическими множествами, для каждого раздела SELECT путем комбинирования магического множества (p1(X)) с таблицей из раздела FROM. Для сохранения семантики дубликатов требуется удаление накладываемых кортежей (значений X, общих для p1 и p2), в то время как оставшиеся в таблицах дубликаты копируются из раздела(ов) FROM. Такая операция невозможна, если никогда не конструируются магические таблицы, как в случае GMT.
Простое решение состоит в явном конструировании магических таблиц путем следующей перезаписи M2 и M3:
(E2): tcf(X,Z) AS (SELECT X, Z
FROM m(X), s(X,Y), w(Y,Z))
(E3): m(X) AS ((SELECT X FROM s(X,Y) WHERE p1(X)) UNION DISTINCT (SELECT X FROM s(X,Y) WHERE p2(X)))
Здесь m – это магическое множество. Операция UNION DISTINCT удаляет дубликаты после объединения. В приведенной конструкции повторяются некоторые соединения, такие как соединение с s. В реализации Starburst у нас имеется решение, позволяющее использовать дополнительное преобразование; из-за недостатка места мы опускаем описание.
Расширенное преобразование методом магических множеств
Преобразования методом магических множеств, определенные в разд. 3, применимы к реляционным системам с дубликатами и агрегацией. В этом определении заимствуются результаты из [MPR90], где определяется семантика дубликатов и агрегации в присутствии рекурсии, и использование агрегации ограничивается классом монотонных (monotonic) и магических стратифицируемых (magical stratified) программ, замкнутых относительно преобразований методом магических множеств.
Долгое время преобразования методом магических множеств считались полезными только для распространения связываний (предикатов сравнения по равенству). В нашей недавней статье [MFPR90] затрагивалось расширение метода для распространения условий (предикатов сравнения не по равенству) в программах Datalog с использованием основного преобразования на основе магических множеств (ground magic-sets transformation, GMT). В разд. 4.1 мы расширяем GMT для работы в присутствии дубликатов.
Далее мы обсуждаем, каким образом метод магических множеств может быть полезен в чисто нерекурсивных системах (разд. 4.2), и представляем однофазный алгоритм для украшения и магического преобразования запроса, которые дают нам возможность проталкивания произвольных условий с использованием только украшений b, c и f (разд. 4.3).
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 программами.
Связь метода магических множеств с традиционными методами оптимизации
В этом разделе приводятся неформальное описание метода магических множеств и его связи с более традиционными методами преобразований, а также сравнение нашей работы с ранее полученными результатами. В разд. 3 преобразования методом магических множеств определяются формально.
это название алгоритма преобразования запросов
«Магические множества» – это название алгоритма преобразования запросов ([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 содержится заключение.
В этой статье мы показали,
В этой статье мы показали, что преобразование методом магических множеств можно расширить для работы с конструкциями SQL. Мы привели набросок реализации Extended Magicsets как части компонента перезаписи прототипа реляционной системы баз данных, а также представили исследование эффективности, в котором подход магических множеств сопоставляется с подходами корреляции и декорреляции. Многие существенные результаты были лишь упомянуты или вовсе опущены, включая аспекты улучшенных украшений, простых украшений и детали реализации.
Как мы полагаем, эта статья демонстрирует, что метод магических множеств (ранее служивший средством только для Datalog и логического программирования) следует рассматривать как практическое расширение существующих методов оптимизации путем перезаписи. Магия действительно «уместна» для систем реляционных баз данных; это общий метод (применимый как к рекурсивным, так и к не рекурсивным запросам) введения предикатов, которые как можно ранее отфильтровывают доступ к ненужным строкам таблиц. Ограниченные варианты этого метода долгие годы используются в системах баз данных.
Мы не предлагаем использовать преобразования методом магических множеств всякий раз, когда они возможны. Скорее, магия является ценной альтернативной, кажущейся более стабильной, чем методы корреляции и декорреляции, предметом выбора, который должен оцениваться стоимостным оптимизатором [SAC + 79, Loh88]. Магия особенно полезна для запросов (таких как запросы поддержки принятия решений), включающих большое число соединений, сложные вложения блоков запросов или рекурсию. Такие запросы могут быть невыполнимыми без применения магических множеств.
В литературе предлагался ряд специальных методов оптимизации. Некоторые из них можно считать альтернативами магических множеств, в которых делаются попытки использования специальных свойств некоторых запросов, таких как линейные запросы на ациклических данных (например, HenschenNaqvi [HN84], Counting [BMSU86]) или специальные операции для выражения ограниченного (и важного) класса запросов, таких как транзитивное замыкание (например, операция alpha [Agr87]).
При наличии возможности их применения, эти методы иногда оказываются лучше преобразования магических множеств. Однако пример 1.2 иллюстрирует полезные запросы, не выразимые с использованием линейной рекурсии. Важность метода магических множеств состоит в том, что он применим ко всем (расширенным) SQL-запросам и обеспечивает общий каркас оптимизации с хорошей и стабильной эффективностью. Имеются также методы, в которых подход магических множеств развивается и совершенствуется для некоторых классов запросов (например, факторизация [NRSU89]). Эти методы дополняют подход магических множеств путем распознавания специальных свойств программ и соответствующей оптимизации преобразованных программ.
Хотя мы реализуем магию как расширение компонента оптимизации путем перезаписи прототипа расширяемой системы реляционных баз данных Starburst, остается много практических вопросов. Одной из трудных открытых проблем является интеграция оптимизации путем перезаписи с оценочной оптимизацией. Для оценочной оптимизации может требоваться время, экспоненциально зависящее от числа соединяемых таблиц. Преобразования, подобные магическим множествам, могут привести к экспоненциально большому числу альтернативных запросов, для каждого из которых требуется оценочная оптимизация, более сложная, чем для исходного запроса. Очевидно, что между многими преобразованиями запросов имеется структурная связь, но мы недостаточно хорошо понимаем эту проблему, чтобы перевести ее на управляемый уровень с применением алгебраических методов или инженерных эвристик.
