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

Правин Сешарди (Praveen Seshadri, Univ. of Wisconsin, Madison)
Джозеф Хеллерстейн (Joseph M. Hellerstein, Univ. of California, Berkeley)
Хамид Пирамеш (Hamid Pirahesh, IBM Almaden Research Ctr.)
Клифф Леюнг (T. Y. Cliff Leung, IBM Santa Teresa Lab.)
Раджу Рамакришнан (Raghu Ramakrishnan, Univ. of Wisconsin, Madison)
Дивеш Сривастава (Divesh Srivastava, AT&T Research)
Питер Стюки (Peter J. Stuckey, Univ. of Melbourne)
С. Сударшан (S. Sudarshan, IIT, Bombay)
SIGMOD Conference 1996: 435-446

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

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

7.5 Θ-полусоединения и ограничительная магическая перезапись

При использовании магической перезаписи [BR91, MP94, SS94] запросы к базе данных оптимизируются путем определения дополнительных магических (или фильтрующих) отношений, которые используются как фильтры для ограничения вычислений при обработке запроса. Ограничительная магическая перезапись (Constraint Magic rewriting, CM-перезапись) [SS94] является наиболее общим методом магической перезаписи, и мы представляем порождаемое правило преобразования, в котором фиксируется ключевое интуитивное понимание CM-перезаписи для одного отношения. Повторяющееся применение этого правила преобразования к последовательности соединений производит действие, аналогичное CM-перезаписи одноблочного SQL-запроса. В заключение мы указываем эвристику для применения этого метода к SQL-запросам, которые адресуются не только к хранимым отношениям базы данных, но и к представляемым отношениям; эвристика моделирует поведение CM-перезаписи (с полными SIPS слева направо) на таких запросах.

Шаг CM-преобразования с использованием Θ-полусоединения: В следующем правиле преобразования фиксируется базовый шаг CM-перезаписи [SS94]:

где Θ₂ включает только атрибуты из attrs(F) attrs(E₁),⁶ и E₁’ и E₂’ определяются ниже:

Мы называем это преобразование шагом ограничительного магического преобразования (Constraint Magic Transformation, CMT). Шаг CMT может быть порожден из более простых правил преобразования; подробности представлены в [SSS95].

Шаг CMT и CM-перезапись: В выражениях, определяющих E₁’ и E₂’ в шаге CMT, фиксируется существо CM-перезаписи. Интуитивные соображения состоят в следующем. Предположим, что у нас имеется ограничивающее множество F для результата соединения отношений E₁ и E₂. При CM-перезаписи этого соединения «фильтрующее» отношение F (также называемое «магическим» отношением) сначала используется для ограничения вычисления E₁ кортежами, релевантными F. Затем ограниченный таким образом набор кортежей E₁ вместе с фильтрующим отношением F используется для ограничения вычисления E₂. Эта стратегия точно фиксируется в шаге CMT.

Более формально, эта связь может быть установлена следующим образом. Рассмотрим представление, определенное как

с фильтрующим отношением F и параметризуемым предикатом Θ₁ ∧ Θ₂, где Θ₂ включает только атрибуты из attrs(F) attrs(E₁). (Это то же самое, что и левая часть шага CMT.) Дополнительная ограничительная магическая перезапись (Supplementary Constraint Magic rewriting) сначала определяет показанное ниже дополнительное отношение S₁ (или PartialResult):^7*

где E₁’’ является результатом дополнительной ограничительной магической перезаписи E₁ с фильтрующим отношением F и параметризуемым предикатом Θ₂.⁸ Затем представление V заменяется представлением V’, определяемым ниже:

где E₂’’ является результатом дополнительной ограничительной магической перезаписи E₂ с фильтрующим отношением S₁ и параметризуемым предикатом Θ₁ ∧ Θ₃.

Отметим строгое соответствие между E₁’ (в CMT) и E₁’’ (в ограничительной магии), между правым операндом Θ-полусоединения в определении E₂’ (в CMT) и S₁ (в ограничительной магии) и между E₂’ и E₁’’. Основное различие между перезаписью ограничительной магией и шагом CMT на одиночном соединении состоит в том, что в CM-перезаписи используются Θ-соединения, а не Θ-полусоединения. Хотя окончательное выражение, в котором используется Θ-полусоединение, является более сложным, чем определение V’, генерируемое при CM-перезаписи, эта дополнительная сложность требуется для сохранения мультимножественной семантики.

CM-преобразование SQL-блока с использованием Θ-полусоединения: Алгебраическое выражение V, генерируемое путем преобразования SQL-запроса, состоящего из одиночного блока запроса, имеет вид:

При наличии фильтрующего отношения F для V, обозначаемого V ⊳<_ψ F, к V ⊳<_ψ F можно применить следующую последовательность преобразований. Во-первых, определим наиболее мощное подмножество ψ, обозначаемое как ψ_n, которое можно протолкнуть через операцию группировки/агрегации. Если в исходном запросе не использовался раздел GROUPBY, то предикат ψ_n является таким же, как и ψ. Затем можно протолкнуть внутрь операции проецирования и операции группировки/агрегирования, получая

Наконец, можно многократно применить шаг CMT к выражению

как это описывается ниже. Сначала определим S_i, i ≥ 1 следующим образом:

Кроме того, пусть ψ_i, i < n обозначает наиболее мощное подмножество ψ_i+1, в котором используются только атрибуты F и S_i, а γ_i, i < n обозначает оставшуюся часть ψ_i+1. Первое применение шага CMT преобразует в , где и

Посмотрим теперь на S’_n-1: Θ-полусоединение можно протолкнуть через определение S’_n-1 точно в такой же манере, как выше. Таким образом, шаг CMT применяется для каждого S_i, n ≥ i ≥ 2. Заметим, что имеются два вхождения S’_n-1, т.е. это общее подвыражение двух выражений. Путем использования помеченных выражений мы можем избежать двойной оптимизации и вычисления выражений. Использование помеченных выражений является очень важным для избежания экспоненциального взрыва при спуске от S_n к S₁.

CM-преобразование SQL-запросов с представлениями: Мы начинаем с блока SQL-запроса и выполняем преобразование Θ-полусоединение, как это описывалось раньше. В этом блоке могут использоваться представляемые отношения, и после преобразования использования отношения R_i в блоке может иметься полусоединение вида или . Пусть E_i обозначает все выражение полусоединения, включающее R_i. Если R_i является представляемым отношением, можно рекурсивно создать специализированную версию R_i’, в которую протолкнуто полусоединение, путем использования преобразования Θ-полусоединения SQL-блока, определяющего R_i. Наконец, если весь предикат β_i можно протолкнуть в определение представления R_i, то E_i заменяется на R_i’, а иначе на R_i’ заменяется только R_i в E_i.

Обсуждавшаяся ранее для случая одиночного соединения связь между шагом CMT и ограничительной магической перезаписью также распространяется на случай соединений и запросов над несколькими представлениями.

Таким образом, мы показали, что для SQL-запросов эффект ограничительной магической перезаписи достигается как специальный случай преобразований Θ-полусоединений, в частности, путем использования шага CMT. При исследовании полного пространства эквивалентных выражений ограничительная магическая перезапись будет рассматриваться в качестве варианта, и в пространстве поиска будет выбрано наиболее дешевое выражение.

7.6 Обсуждение

В нескольких коммерческих системах баз данных используются идентификаторы кортежей (tid) как неявные атрибуты, позволяющие различить множественные вхождения кортежа. В этих системах выполняются преобразования SQL-запросов, которые могут влиять на мультимножественную семантику (например, замена вложенных подзапросов соединениями), и уникальные tid’ы используются, в случае потребности, для получения корректной семантики. Это делается следующим образом. Для отношений, перечисленных в разделе FROM, т.е. для тех отношений, которые вносят вклад в мультимножественную семантику, tid’ы выбираются вместе со всеми другими атрибутами, встречающимися в разделе SELECT, и в результирующем отношении производится удаление дубликатов. На заключительной фазе выполняется проецирование, устраняющее атрибуты-tid’ы, и получается желаемое мультимножественное отношение.

Этот подход обладает тем преимуществом использования соединений, а не Θ-полусоединений, что позволяется использовать большее число порядков соединения. Однако у него имеется несколько недостатков. Во-первых, его невозможно использовать в связи с группировкой/агрегированием. Во-вторых, оптимизатор должен отслеживать tid’ы при выполнении операций и производить удаление дубликатов. Наш подход использования операции Θ-полусоединения является более чистым, поскольку он может единообразно справляться как с SQL-запросами с мультимножественной семантикой, так и с запросами с множественной семантикой. Кроме того, наш запрос позволяет избежать расходов на явное удаление дубликатов и на поддержку tid’ов и работу с ними.

8. Родственные работы

Перезапись с использованием магических множеств исходно использовалась в области обработки рекурсивных запросов в дедуктивных базах данных [BMSU86, RLK86]. Влияние различных вариантов выбора SIPS обсуждалось в [BR91], и идея использования аппроксимаций магического множества исследовалась в [Sag90, SS88]. Следует заметить, что в данной статье мы имеем дело с нерекурсивными SQL-запросами, поддерживаемыми во всех коммерческих реляционных системах баз данных. Ранее было показано, что магические множества применимы к нерекурсивным SQL-запросам [MFPR90], и соответствующий метод был реализован в системе баз данных Starburst [MP94].

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

При исследовании полусоединений в распределенных базах данных (см., например, [BGW+81, LMH+85]) предполагалось, что отношения являются простыми хранимыми отношениями, и поэтому было легко вычислить стоимость выполнения полусоединений. Кроме того, обычно не рассматривались аспекты, подобные выбору SIPS, поскольку предполагалось, что стоимость коммуникаций перевешивает стоимость локальной обработки (и, следовательно, всегда выбирались наиболее ограничительные полусоединения). Вместо этого оптимизация сосредотачивалась на корректном порядке вычисления полусоединений [BGW+81]. С другой стороны, в проекте System R* [LMH+85] предполагалось, что стоимость локальной обработки перевешивает стоимость коммуникаций; вследствие этого, в процессе оптимизации полусоединения не рассматривались.

В литературе, посвященной неоднородным базам данных, пока еще не рассматривались такие вопросы, как сложные запросы над удаленными представлениями. Однако такие вопросы становятся все более важными, и результаты нашей работы следует применять и в этой области.

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

В данной статье изложены два основных результата. Во-первых, предложено практическое решение для интеграции алгоритма перезаписи на основе магических множеств в каркас оценочной оптимизации. Это решение гарантирует, что перезапись применяется эффективно и только в тех случаях, когда это полезно. Реализация данного метода оптимизации в DB2 C/S V2 демонстрирует реализуемость предложенного решения. Кроме того, результаты измерения производительности подтверждают то заявление, что магическая перезапись может быть эффективно оптимизирована в оценочном стиле для широкого диапазона запросов без существенного увеличения накладных расходов на оптимизацию. Второй результат состоит в формализации этих идей путем введения мультимножественной алгебраической операции Θ-полусоединения. Представлен характерный набор алгебраических эквивалентностей, затрагивающих эту операций, которые могут использоваться для моделирования магической перезаписи. Алгебраическая характеристика отчетливо определяет полное пространство вариантов вычисления. Далее, правила преобразований могут быть использованы в основанном на правилах оптимизаторе для оптимизации сложных запросов в оценочной манере. Хотя эти результаты получены в двух независимых исследованиях, они являются, по существу, взаимодополняющими. Взятые вместе, они затрагивают теорию и практику применения оптимизации на основе перезаписи магических множеств в оценочном стиле.

Acknowledgements

Praveen, Joey, Raghu, Hamid and Cliff acknowledge the contributions of John McPherson, Guy Lohman, Beau Shekita, Dave Simmen, Lori Strain, Monica Urata, and Surendra Verma at IBM Almaden, Navin Kabra and Jignesh Patel at University of Wisconsin, and Inderpal Mumick for the original magic rewriting code. Divesh, Peter and Sudarshan would like to thank Brian Hart for discussions that lead them to start thinking of how Constraint Magic rewriting might be implemented using generalizations of semijoins, Bill McKenna for discussions regarding cost­based algebraic optimizers and feedback on the paper, and Tim Griffin for discussions about bag operators.

Praveen Seshadri was supported by an IBM Graduate Student Fellowship. Raghu Ramakrishnan was supported by a David and Lucile Packard Foundation Fellowship in Science and Engineering, a Presidential Young Investigator Award, with matching grants from Digital Equipment Corporation, Tandem and Xerox, and NSF grant IRI­9011563. Joseph Hellerstein was supported by NSF grant IRI­9157357.

References

[BGW+81] P. A. Bernstein, N. Goodman, E. Wong, C. L. Reeve and J. B. Rothnie. Query processing in a system for distributed databases (SDD­1) ACM Transactions on Database Systems, 6(4):602--625, 1981.

[BMSU86] F. Bancilhon, D. Maier, Y. Sagiv and J. D. Ullman. Magic sets and other strange ways to execute logic programs. In Proceedings of the ACM Symposium on Principles of Database Systems, 1--15, 1986.

[BR91] C. Beeri and R. Ramakrishnan. On the power of Magic. Journal of Logic Programming, 10(3&4):255--300, 1991.

[Blo70] B. H. Bloom. Space/time trade­offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970.

[CG85] S. Ceri and G. Gottlob. Translating SQL into relational algebra: Optimization, semantics,and equivalence of SQL queries. IEEE Transactions on Software Engineering, 11(4):324--345, 1985.

[DGK82] U. Dayal, N. Goodman, and R. H. Katz. An extended relational algebra with control over duplicate elimination. In Proceedings of the ACM Symposium on Principles of Database Systems, 1982.

[EN94] R. Elmasri and S. B. Navathe. Fundamentals of database systems. Benjamin/Cummings Publishers, 2nd edition, 1994.

[GHK92] S. Ganguly, W. Hasan and R. Krishnamurthy. Query optimization for parallel execution. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1992.

[GM93] G. Graefe and W. J. McKenna. The Volcano optimizer generator: Extensibility and efficient search. In Proceedings of the IEEE International Conference on Data Engineering, 1993.

[HCL+90] L. 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 Transactionson Knowledgeand Data Engineering, March 1990.

[Hel95] J. M. Hellerstein. Optimization and execution techniques for queries with expensive methods Ph.D. Thesis, University of Wisconsin, August 1995.

[IK84] T. Ibaraki and T. Kameda. Optimal nesting for computing N­relational joins. In ACM Transactions on Database Systems, 9(3):482--502, 1984.

[INSS92] Y. Ioannidis, R. Ng, K. Shim and T. K. Sellis. Parametric query optimization. In Proceedings of the International Conference on Very Large Databases (VLDB), 103--114, 1992.

[KBZ86] R. Krishnamurthy, H. Boral, and C. Zaniolo. Optimization of nonrecursive queries. In Proceedings of the International Conference on Very Large Databases (VLDB), 128--137, 1986.

[Klu82] A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. Journal of the ACM, 29(3):699--717, 1982.

[LMH+85] G. M. Lohman, C. Mohan, L. M. Haas, D. Daniels, B. G. Lindsay, P. G. Selinger and P. F. Wilms. Query processing in R*. In Query Processing in Database Systems, (W. Kim, D. S. Reiner, and D. S. Batory, eds.), Springer­Verlag, 30--47, 1985.

[LNSS93] R. J. Lipton, J. F. Naughton, D. A. Schneider and S. Seshadri. Efficient sampling strategies for relational database operations. Theoretical Computer Science, 116:195--226, 1993.

[MFPR90] I. S. Mumick, S. Finkelstein, H. Pirahesh, and R. Ramakrishnan. Magic is relevant. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1990.

[MP94] I. S. Mumick and H. Pirahesh. Implementation of magic­sets in a relational database system. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1994.

[RLK86] J. Rohmer, R. Lescoeur,and J. M. Kerisit. The Alexander method: A technique for the processing of recursive axioms in deductive databases. In New Generation Computing, 4(3):273--285, 1986.

[RSSS94] R. Ramakrishnan, D. Srivastava, S. Sudarshan and P. Seshadri. The CORAL deductive system. The VLDB Journal, Special Issue on Prototypes of Deductive Database Systems, 1994.

[SAC+79] P. G. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price. Access path selection in a relational database management system. In Proceedings of ACM SIGMOD International Conferenceon Managementof Data, 23--34, 1979.

[Sag90] Y. Sagiv. Is there anything better than magic? In Proceedings of the North American Conference on Logic Programming, 235--254, 1990.

[SPL96] P. Seshadri, H. Pirahesh,and T. Y. C. Leung. Decorrelating complex queries. In Proceedings of the Twelfth International Conference on Data Engineering, 1996.

[SS88] S. Sippu and E. Soisalon­Soinen. An optimization strategy for recursive queries in logic databases. In Proceedings of the Fourth International Conference on Data Engineering, 1988.

[SS94] P. J. Stuckey and S. Sudarshan. Compiling query constraints. In Proceedingsof the ACM Symposiumon Principles of Database Systems, 1994.

[SSS95] D. Srivastava, P. J. Stuckey and S. Sudarshan. The magic of theta­semijoins. AT&T Bell Laboratories Technical Report, 1995.

[TPCD94] TPC benchmark group. TPC­D Draft, December 1994. Information Paradigm. Suite 7, 115 North Wahsatch Avenue, Colorado Springs, CO 80903.

[Yao77] S. B. Yao. Approximating the number of accesses in database organizations. Communications of the ACM, 20(4):260--261, 1977.

---

6 Заметим, что это условие применимости может всегда удовлетворяться путем выбора в качестве Θ₂ предиката true.

7 В предположении, что E₁ выбирается в качестве первого отношения в порядке сторонней передачи информации.

8 В действительности, при CM-перезаписи используется проекция F на уместные атрибуты, но для простоты изложения мы используем само отношение F. Проекция может быть введена после выполнения шага CMT.

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