Расширяемая, управляемая правилами оптимизация путем перезаписи запросов в Starburst

2009 г.

Расширяемая, управляемая правилами оптимизация путем перезаписи запросов в Starburst

Хамид Пирамеш, Джозеф Хеллерстейн, Вакар Хасан

Перевод: Сергей Кузнецов

3.2 Гарантирование слияния подзапросов с квантором существования

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

Правило 7. E to F Quantifier Conversion (преобразование E-квантификатора в F-квантификатор)

В этом правиле (таб. 9) мы преобразуем подзапросы с квантором существования булевских сомножителей в табличные выражения путем изменения типа квантификатора над этим подзапросом с E на F. Заметим, что правило ADDKEYS гарантирует, что условие этого правила, в конце концов, будет удовлетворено для всех таких подзапросов. Как отмечалось выше, преобразование подзапроса в табличное выражение (и, следовательно, в ряд соединений) увеличивает число возможных порядков выполнения соединений. Это может также позволить выполнять дополнительные слияния, если подзапрос является еще одним блоком SELECT.

Таб. 9. Правило 7 – EtoF

Это правило является QGM-эквивалентом правила, корректность которого доказана в [Day87].⁵ Мы не доказываем здесь его корректность, но интуитивно ее можно увидеть путем рассмотрения случая с двумя квантификаторами. В качестве примера рассмотрим следующий запрос, выдающий информацию о заказах для изделий, которые произведены в определенных местоположениях и обрабатываются определенными рабочими центрами. Заметим, что у таблицы itp имеется ключ и, следовательно, в ней не содержатся дубликаты.

Пример 4.

SELECT * FROM itp
WHERE itp.itemn IN
 (SELECT itl.itemn FROM itl
  WHERE itl.wkcen = 'WK468' AND itl.locan = 'LOCA000IN');

Чтобы выполнить этот запрос, мы должны вывести в результат одну копию кортежа из itp в том и только в том случае, когда в результате подзапроса имеется, по крайней мере, один кортеж, удовлетворяющий соответствующему предикату. Если мы применим DISTPU для преобразования подзапроса в табличное выражение, а затем применим SELMERGE, мы получим запрос с единственной операцией SELECT:

SELECT DISTINCT itp.* FROM itp, itl
WHERE itp.itemn = itl.itemn
  AND itl.wkcen = 'WK468' AND itl.locan = 'LOCA000IN';

В преобразованном запросе мы выводим одну копию каждого кортежа из itp × itl, такого что удовлетворяются соответствующие предикаты (включая предикат «itp.itemn = itl.itemn», который ранее подразумевался конструкцией «IN»). Поскольку никакие столбцы из itl не участвуют в окончательной проекции, и дубликаты удаляются, производится тот же результат, что и у исходного запроса.

Приведенный пример взят из среды измерения производительности, разъяснявщейся в разд. 2. Результаты измерений производительности показаны в таб. 10. После перезаписи мы получаем 32-кратное уменьшение время ЦП и 14-кратное уменьшение общего времени.⁶. Во время преобразования правило DISTPU распознает, что в результате отсутствуют дубликаты. Затем правило EtoF преобразует подзапрос в табличное выражение, не добавляя к результату дополнительных ключей, поскольку уже установлено, что в результате нет дубликатов. После этого правило SELMERGE производит слияние табличного выражения, существенно повышая эффективность запроса.

Таб. 10. Перед перезаписью и после нее

Теперь мы можем сказать, почему подзапросы с кванторами существования булевских сомножителей под блоками блоками SELECT гарантированно сливаются. Рассмотрим какой-либо блок SELECT upper с булевским сомножителем – подзапросом SELECT (т.е. блоком SELECT, над которым определен E-квантификатор). По причине наличия правил EorAPDFR и DISTPDFR/TO мы можем предположить, что в подзапросе имеется body.distinct = PERMIT. Теперь мы хотим иметь возможность возбудить правило EtoF, но не можем это сделать, если upper.head.distinct = FALSE, upper.body.distinct = PRESERVE и для квантификатора между этими двумя блоками не соблюдается условие one-tuple-condition. В этом случае мы можем применить правило ADDKEYS, чтобы получить upper.head.distinct = TRUE, и тогда мы сможем применить правило EtoF. После его применения upper определяется над lower с использованием F-квантификатора, и lower.body.distinct != ENFORCE, так что удовлетворяются условия для возбуждения SELMERGE, и блок lower может быть слит с блоком upper.

Правило 8. INTERSECT to Exists

Это правило (таб. 11) преобразует операцию над множествами INTERSECT (которая может быть n-арной) к запросу с квантором существования, который может быть впоследствии преобразован (через EtoF и SELMERGE) к одиночному блоку SELECT. Обычно в РСУБД операция INTERSECT выполняется путем сортировки операндов с последующим их слиянием. Этот метод выполнения является разновидностью соединения сортировкой со слиянием. Мы переписываем операцию INTERSECT как соединение и поэтому можем использовать методы соединения, отличные от сортировки со слиянием. Это может повысить эффективность на много порядков, и поэтому такое преобразование запросов является необходимым.⁷

Таб. 11. Правило 8 – INT2EXIST

Напомним, что в SQL семантика операции INTERSECT заключается в том, что сначала в операндах удаляются дубликаты, и в результат попадает одна копия каждого кортежа, встречающегося во всех операндах. Это эквивалентно тому, что выбирается любой операнд, и в результат передается одна копия каждого его кортежа, встречающегося во всех других операндах. В данном правиле просто фиксируется эта эквивалентность – оно производит блок SELECT DISTINCT с одним F-квантификатором (произвольно выбранным операндом) и E-квантификаторами над всеми другими операндами, которые фильтруют кортежи источника F-квантификатора, не соответствующие всем другим источникам. Заметим, что для сопоставления кортежей в предикате подзапроса требуется большая конъюнкция – два кортежа соответствуют один другому, когда равны значения всех их столбцов.⁸

В качестве примера рассмотрим следующий запрос, который находит пересечение множества изделий, обрабатываемых служащим 1279, и множества изделий, которые запланированы для обработки в рабочем центе WK195 на дату 9773.

Пример 5.

 SELECT items FROM wor
 WHERE empno = 'EMPN1279'
INTERSECT
 SELECT itemn FROM itl
 WHERE entry.tirne = '9773' AND wkctr = 'WK195';

Правило перезаписи для пересечения преобразует запрос в подзапрос с квантором существования, который, в свою очередь, преобразуется в соединение путем применения правила EtoF и сливается путем применения правила SELMERGE. Запрос после перезаписи выглядит следующим образом:

SELECT DISTINCT itemn FROM itl, wor
WHERE empno = 'EMPN1279' AND entry time = '9773'
  AND wkctr = 'WK195' AND itl.itemn = wor.itemn;

Результата выполнения этого запроса с использованием перезаписи и без этого показаны в таб. 12.⁹ После преобразования к соединению оптимизатор планов учитывает возможность применения как метода соединения слиянием, так и метода вложенных циклов. По причине наличия индекса на столбце соединения itemn выбирается метод вложенных циклов, что намного повышает эффективность.¹⁰

Таб. 12. Пример 5, до и после перезаписи

4. Процессор правил

Для соответствия целям расширяемости проекта Sturburst было решено, что система правил является подходящей платформой, позволяющей легко добавлять к системе правила преобразований с последующим их переупорядочением и обновлением. Для наших целей не подходили существующие процессоры правил, и поэтому мы разработали собственную систему. Как будет ясно из дальнейшего обсуждения, нам требовались многочисленные возможности, недоступные в типичных системах правил (таких как OPS5 [BFKM85]). Процессор правил Query Rewrite проекта Sturburst обладает следующими особенностями:

Правила произвольной сложности: Правилами в нашем процессоре являются пары функций, написанных на процедурном языке Си. Функция проверки условия выполняет произвольную проверку и выставляет флаг TRUE или FALSE. Если функция проверки условия устанавливает флаг TRUE, то для выполнения произвольного действия вызывается функция действия. Тот факт, что наши правила представляют собой Си-функции, является существенным – мы требуем, чтобы наши правила могли манипулировать QGM, который в Starburst представляется как сеть Си-структур. Хотя правила пишутся на языке Си, для эффективного выполнения они компилируются в машинный язык.
Средство работы с контекстом: Структура данных, передаваемая каждому вызову системы правил, включает указатель на информацию пользователя, которая, в свою очередь, передается в сами функции правил, где ее можно читать и модифицировать. Для наших целей в Query Rewrite мы используем этот указатель для сохранения текущего «контекста» в QGM (блока, квантификатора или предиката), и наши правила перезаписи пишутся с использованием ссылки на этот контекст. Это позволяет обеспечивать обсуждавшуются ранее локальность правил. К набору правил добавляются специальные правила для «продвижения» контекста, когда мы исчерпываем возможности модификации текущего контекста. Так что эти правила «обходят» граф QGM.¹¹
Классы правил и расширяемое разрешение конфликтов: Мы разделяем наш набор правил на классы, каждый из которых можно считать отдельным набором правил. Это обеспечивает ряд преимуществ. Во-первых, это позволяет нам группировать правила в осмысленные модули, обеспечивающие лучшее понимание действия правил. Во-вторых, поскольку правила являются произвольными Си-процедурами, правило может вызывать другой класс правил как подпрограмму. Это приводит к улучшенной модульности и понимаемости.
Наконец, для разных наборов правил могут иметься разные схемы разрешения конфликтов [MF78] для выбора следующего правила, подлежащего возбуждению. В настоящее время в Starburst поддерживаются две схемы: последовательная схема с циклическим обходом упорядоченного набора правил и приоритетная схема, в которой всегда возбуждается удовлетворяющее условию правило с наивысшим приоритетом. К системе могут быть легко добавлены новые схемы разрешения конфликтов.
Механизм классов правил поддерживает для правил некоторую необязательную структуру, обеспечивающую нам средство управления без потребности обращения к полностью процедурной системе. Рис. 2 показывает, что при наших взаимодействиях правил очень трудно явно представить порядок применения правил. Понятие продукционных правил избавляет нас от этого бремени. Однако, на самом деле, мы желаем применять некоторое управление порядком возбуждения правил. Например, мы хотим применять INT2EXIST до SELMERGE, чтобы гарантировать, что блок INTERSECT над блоком SELECT будет преобразован и слит в один блок SELECT. Мы обеспечиваем это упорядочивание путем тщательной организации своих классов правил.
Заметим, что в нашем процессоре поддерживается полный спектр возможностей управления – от управления, диктуемого данными, до полностью процедурного управления. Схема управления, полностью диктуемого данными, может моделироваться путем использования единственного класса правил, в котором схема управления рандомизирована, а полностью процедурная схема могла бы представлять собой набор правил из одного правила, которое один раз инициируется и выполняет произвольную процедуру или программу. В Query Rewrite мы используем процессор правил для нахождения баланса между этими крайностями – у нас имеется несколько классов правил, для некоторых из которых мы используем последовательную схему управления, а для других – приоритетную. В результирующей системе остается многое от организации процедурной программы, но имеются преимущества простой расширяемости и гибкого взаимодействия, присущие системе правил.
Гарантированное завершение: После рассмотрения заданного числа правил наш процессор правил завершит свое выполнение, независимо от того, остались или нет правила, пригодные для выполнения. Это число находится под контролем программиста правил. Заметим, что, поскольку выполнение может закончиться после проверки или исполнения любого правила, мы вынуждены делать каждое правило атомарным изменением, отображающим допустимый OGM в эквивалентный допустимый OGM. Это ограничение оказывается очень полезным, поскольку оно навязывает концептуальную чистоту каждого правила.
Элементы управления процессора правил: Пользователям Starburst может локально разрешаться или запрещаться определение правил «налету» без воздействия на других пользователей. Это позволяет разработчикам правил пользоваться удобствами парадигмы системы правил без влияния на одновременно работающих пользователей базы данных. Управляющие элементы также позволяют нам трассировать и толковать действия правил – полезный метод для отладки потенциально сложных взаимодействий между правилами.

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

Успех, которого мы добились с использованием своей системы правил, является необычным, и он объясняется как уникальными особенностями общего проекта системы, так и применением системы правил. Поскольку все наши правила перезаписи производят допустимые графы QGM, и покольку каждое индивидуальное правило не приводит к деградации эффективности запросов, в наихудшем случае преобразованный запрос сохранит эффективность исходного. На практике это случается только с простыми запросами, для которых не требуется оптимизация.

5. Заключение: процессор и правила

Мы построили расширяемую систему Query Rewrite для Starburst и показали, что она может на порядки повысить эффективность выполнения запросов. Раньше педлагались другие преобразования запросов ([Kim82, GW87, Day87, Anf89]), но в нашей работе многие из этих преобразований обобщаются, и это первая (насколько нам известно) реализация системы, в которой схемы преобразований органически включаются в полную СУБД. Мы потратили значительные усилия на разработку системы, направленную на решение проблем, которые стоят перед полными исследовательскими прототипами и промышленными РСУБД, особенно при обработке сложных запросов и запросов, ассоциированных со сложными объектами [LLPS91]. Возможности нашей системы Query Rewrite значительно превосходят возможности современных РСУБД, включая коммерческие системы.

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

Кажется логичным наше решение разработать процессор запросов. Мы столкнулись с несколькими часто упоминаемыми проблемами систем правил (недетерминированность результата, сложность понимания исполнения системы, слабая производительность и т.д.) и воспользовались врожденными преимуществами системы правил (простота расширяемости, отстраненность программиста правил от потока управления и т.д.). Расширяемость системы Query Rewrite является ключевой характеристикой системы – она позволяет добавлять новую функциональность как в язык запросов, так и в используемую технологию (например, более быструю и дешевую память), и также должна позволить оптимизаторам планов стать «умнее», чтобы избегать недостатков, которые можно обнаружить только после введения системы в производственный режим [Pir89, HCL+90]. Наша расширяемая система Query Rewrite направлена на решение всех этих проблем.

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

Как обычно, Джордж Лапис (George Lapis) оказал громадную помощь в реализационных деталях многих правил. Ян Ванг (Yun Wang) из группы DB2 и Жозефин Ченг (Josephine) из DBTI сильно способствовали нашему пониманию преобразований запросов в контексте производственных систем. Это привело к значительному совершенствованию полноты наших правил перезаписи. Могочисленные обсуждения с Шелдоном Финкельштейном (Sheldon Finkelstein) привели с улучшению концептуального представления QGM и правил. Мы получили существенную пользу от оптимизатора планов, компонента совершенствования запросов и среды времени выполнения Srarburst. Мы благодарны Брюсу Линдсею (Bruce Lindsay), Гаю Лохману (Guy Lohman), Джону МакФерсону (John McPherson), Мэвис Ли (Mavis Lee), Ханху Нгуену (Hanh Nguyen) и Киечи Оно (Kiyoshi Ono). Мы также благодарим Джона МакФерсона (John McPherson) и Адама Гласса (Adam Glass) за комментарии к ранней версии этой статьи.

Литература

[ABC+76] M. Astrahan, M. Blasgen, D. Chamberlin, K. Eswaran, J. Gray, P. Griffiths, W. King, R. Lorie, P. McJones, J. Mehl, G. Putzolu, I. Traiger, B. Wade, and V. Watson. System R: Relational Approach to Database Management. ACM Transactions on Database Systems, 1(2):97–137, June 1976.

[Anf89] Ole Jirgen Anfindsen. A Study of Access Path Selection in DB2. Technical report, Norwegian Telecommunications Administration and University of Oslo, Norway, October 1989.

[BFKM85] L. Brownston, R. Farrell, E. Kant, and N. Martin. Programming Expert Systems in OPS5. Addison-Wesley Publishing Co., 1985.

[BTA90] Jose Blakeley, Craig Thompson, and Abdallah Alashqur. Strawman reference model for object query language. In First OODB Standardization Workshop, X3/SPARC/DBSSG/OODBTG, Atlantic City, New Jersey, May 1990.

[Day87] Umeshwar Dayal. Of Nests and Trees: A Unified Approach to Processing Queries that Contain Nested Subqueries, Aggregates, and Quantifiers. In Proc. 13^th International Conference on Very Large Data Bases, pages 197–208, Brighton, September 1987.

[GW87] Richard A. Ganski and Harry K. T. Wong. Optimization of Nested SQL Queries Revisited. In Proc. ACM SIGMOD International Conference on Management of Data, pages 23–33, San Francisco, May 1987.

[HCL+90] L.M. Haas, W. Chang, G.M. Lohman, J. McPherson, P.F. Wilms, G. Lapis, B. Lindsay, H. Pirahesh, M. Carey, and E. Shekita. Starburst Mid-Flight: As the Dust Clears. IEEE Transactions on Knowledge and Data Engineering, pages 143–160, March 1990.

[HH91] Joseph M. Hellerstein and Meichun Hsu. Determinism in Partially Ordered Production Systems. Research Report RJ 8089, IBM Almaden Research Center, March 1991.

[HP88] Waqar Hasan and Hamid Pirahesh. Query Rewrite Optimization in Starburst. Research Report RJ 6367 ,IBM Almaden Research Center, August 1988.

[HSS88] T. Haerder, H. Schoning, and A. Sikeler. Parallelism in Processing Queries on Complex Object. In Proc. International Symposium on Databases in Parallel and Distributed Systems, Austin, December 1988.

[ISO91] ISO ANSI. Database Language SQL ISO/IEC 9075:1992, 1991.

[Kim82] W. Kim. On Optimizing an SQL-like Nested Query. ACM Transactions on Database Systems, 7(3), September 1982.

[LLOW91] Chares Lamb, Gordon Landis, Jack Orenstein, and Dan Weinreb. The Objectstore Database System. Communications of the ACM, October 1991.

[LLPS91] Guy Lohman, Bruce Lindsay, Hamid Pirahesh, and Bernhard Schiefer. Extensions to Starburst: Objects, Types, Functions, and Rules. Communications of the ACM, October 1991.

[Loo86] Chris Loosley. Measuring IBM Database 2 Release 2 - The Benchmark Game. InfoDB, 1(2), 1986.

[MF78] J. McDermott and C. Forgy. Production System Conflict Resolution Strategies. In D.A. Waterman and Fredrick Hayes-Roth, editors, Pattern Directed Inference Systems, pages 177–199. Academic Press, 1978.

[MFPR90a] Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, and Raghu Ramakrishnan. Magic is Relevant. In Proc. SIGMOD 90 [Pro90], pages 247–258. Имеется перевод на русский язык С.Кузнецова: Индерпал Сингх Мумик, Шелдон Финкельштейн, Хамид Пирамеш, Раджу Рамакришнан. Магия сохраняет силу.

[MFPR90b] Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, and Raghu Ramakrishnan. Magic Conditions. In Proc. 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 314–330, Nashville, March 1990.

[MPR90] Inderpal Singh Mumick, Hamid Pirahesh, and Raghu Ramakrishnan. The Magic of Duplicates and Aggregates. In Proc. 16th International Conference on Very Large Data Bases, Brisbane, August 1990.

[O'N89] P. O'Neil. Revisiting DBMS Benchmarks. Datamation, pages 47–54, September 15, 1989.

[Pir89] Hamid Pirahesh. Early Experience with Rule-Based Query Rewrite Optimization. In G. Graefe, editor, Workshop on Database Query Optimization, CSE Technical Report 89-005. Oregon Graduate Center, May 1989.

[Pro90] Proc. ACM-SIGMOD International Conference on Management of Data, Atlantic City, May 1990.

[Ras90] Louiqa Raschid. Maintaining Consistency in a Stratified Production System Program. In Proc. AAAI National Conference on Artificial Intelligence, 1990.

[RGL90] Arnon Rosenthal and Cesar Galindo-Legaria. Query graphs, implementing trees, and freely-reorderable outerjoins. In Proc. SIGMOD 90 [Pro90].

[SAC+79] Patricia G. Selinger, M. Astrahan, D. Chamberlin, Raymond Lorie, and T. Price. Access Path Selection in a Relational Database Management System. In Proc. ACM-SIGMOD International Conference on Management of Data, Boston, June 1979. Имеется перевод на русский язык С.Кузнецова: П. Селинджер, М. Астрахан, Д. Чемберлин, Р. Лури, Т. Прайс. Выбор пути доступа в реляционной системе управления базами данных.

[SJGP90] M. Stonebraker, A. Jhingran, Jeffrey Goh, and Spyros Potamianos. On rules, procedures, caching and views in data base systems. In Proc. SIGMOD 90 [Pro90].

[SWK76] M.R. Stonebraker, E. Wong, and P. Kreps. The design and implementation of ingres. ACM Transactions on Database Systems, 1(3):189–222, September 1976.

[TOB89] C. Turbyfill, C. Orji, and Dina Bitton. AS3AP – A Comparative Relational Database Benchmark. In Proc. IEEE Compcon Spring '89, February 1989.

[ZH90] Yuli Zhou and Meichun Hsu. A Theory for Rule Triggering Systems. In Francois Bancilhon, Costantino Thanos, and Dennis Tsichritzis, editors, Proc. International Conference on Extending Data Base Technology, Advances in Database Technology - EDBT '90. Lecture Notes in Computer Science, Volume 416, Venice, March 1990. Springer-Verlag.

⁵⁾ Точное правило выглядит следующим образом: Semijoin(R, S; J) = Delta-project(R, S; J); R.*). Здесь мы немного обобщаем правило, отделяя случай, в котором удовлетворяется условие one-tuple-condition.

⁶⁾ И эту оптимизацию не могут произвести многие СУБД, включая коммерческие.

⁷⁾ В Starburst существует аналогичное правило (EXC2NEXIST) для преобразования операциии EXCEPT в подзапрос с отрицанием квантора существования, который впоследствии может участовать в слиянии.

⁸⁾ Это можно упростить путем включения в конъюнкцияю только ключевых столбцов таблиц.

⁹⁾ Для этого эксперимента мы использовали исходную тестовую базу данных, а не масштабированную в 10 раз.

¹⁰⁾ В DB2 не поддерживается INTERSECT. В данном эксперименте мы вместо этой операции использовали операцию UNION, которая выполняется на основе очень похожей стратегии. Очевидно, что для UNION число результирующих кортежей отличается; однако, поскольку в нашем эксперименте это число было небольшим, ошибка в стоимости является незначительной. В действительности, в DB2 выбиралась более подходящая стратегия выполнения UNION, чем упомянутая нами ранее, и поэтому числовые данные об эффективности исходного запроса являются заниженными.

¹¹⁾ Выбор обхода также является расширяемым. В настоящее время мы поддерживаем как обход графа в глубину, так и обход в ширину.

Назад Содержание