Optimizing Recursive Queries

Prof. Dan Suciu University of Washington Monday, September 26, 2022 @ 4:15 pm Room BC 410 Hosted by: Prof. Christoph Koch

Abstract

Modern data analytics requires iteration, yet relational database engines are mostly optimized for non-recursive queries. SQL supports only a limited form of recursion. A better formalism for recursive queries is datalog, which has some elegant properties (recursion always terminates), and lead to the development of two powerful optimizations techniques: semi-naive evaluation, and magic set rewriting. But standard datalog is restricted to monotone queries over sets and does not support aggregates, which has limited its adoption.

In this talk I will describe a new approach to recursive queries and their optimization. First, we extend datalog to semirings, while preserving some of the elegant properties of datalog, and also supporting aggregates naturally. Then, I will describe a simple, yet very powerful optimization rule, called the FGH rule, that rewrites a recursive program into a different recursive program. The rule captures many optimizations discussed in the literature, such as magic set optimization, the PreM rule, and semi-naive evaluation, and as well as new semantics optimizations. Our implementation of the FGH rule is based on the egg term rewriting engine, and the Rosette program synthesizer.

Joint work with: Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler

Bio

Dan Suciu is a Microsoft Endowed Professor in Computer Science and Engineering at the University of Washington. Suciu is conducting research in data management, on topics such as query optimization, probabilistic data, data pricing, parallel data processing, data security. He is a co-author of two books Data on the Web: from Relations to Semistructured Data and XML, 1999, and Probabilistic Databases, 2011. He received the ACM SIGMOD Codd Innovation Award, received several best paper awards and test of time awards, and is a Fellow of the ACM. Suciu is currently an associate editor for the Journal of the ACM. Suciu’s PhD students Gerome Miklau, Christopher Re and Paris Koutris received the ACM SIGMOD Best Dissertation Award in 2006, 2010, and 2016 respectively, and Nilesh Dalvi was a runner up in 2008.