Zheng LUO (UCLA):  Generating Join Trees for Yannakakis Algorithm

ISG seminar on March 6, Friday, 1 – 2 pm, DBH 3011

Title: Generating Join Trees for Yannakakis Algorithm

Abstract:
Most research on query optimization has centered on binary join algorithms like hash join and sort-merge join. However, recent years have seen growing interest in theoretically optimal algorithms, notably Yannakakis algorithm. These algorithms require new optimization techniques, as they rely on join trees where each node represents a relation, very different from the operator trees for binary joins.
Our recent theoretical work proposes three approaches to constructing join trees for Alpha-acyclic queries:
(1) an algorithm to enumerate all join trees, which forms the basis of a cost-based optimizer;
(2) a 1-shot approach to construct a unique shallowest join tree for any Berge-acyclic query, thus enabling parallel execution of large join queries;
(3) a simple algorithm that converts any connected left-deep linear plan of a Gamma-acyclic query into a join tree, allowing reuse of existing optimizers developed for binary joins.
In this talk, we will also discuss how the theoretical results can turbocharge query processing in modern database systems.

Bio:
Zheng LUO is a Ph.D. student at the University of California, Los Angeles (UCLA), advised by Prof. Remy WANG.
His research interests are twofold, spanning from theory to systems.
(1) His current work centers on the theoretical aspects of query optimization in relational databases by examining the algorithms and data structures that improve the efficiency of query processing;
(2) He is also exploring ways to put theory into practice by implementing theoretical results and integrating them into systems.