This paper shows how to uplift wco join algorithms so as to incorporate such filtering natively, improving efficiency and demonstrates the superiority of this approach by extending the Ring -- a compact index that provides wco resolution of BGPs within almost no extra space on top of the graph -- so as to handle property graphs using new techniques while retaining compactness.
Abstract
Worst-case-optimal (wco) join algorithms have demonstrated their power -- in both theory and practice -- to efficiently solve complex Basic Graph Patterns (BGPs). Modern graph query languages, such as SPARQL and GQL, have BGPs at their core, but also have a wide range of other features, including filters (aka.\ selections). Such conditions are typically handled via pre- or post-filtering, before or after processing the BGPs. In this paper we show how to uplift wco join algorithms so as to incorporate such filtering natively, improving efficiency. We demonstrate the superiority of this approach by extending the \textit{Ring} -- a compact index that provides wco resolution of BGPs within almost no extra space on top of the graph -- so as to handle property graphs using our new techniques while retaining compactness. We implement this extension and experimentally show that it outperforms various baseline systems.
This tutorial revisits Yannakakis algorithm (YA) as a central example of how database theory can guide practical query processing. Yannakakis algorithm gives an instance-optimal guarantee for evaluating acyclic joins, and its core ideas, including join trees, semijoin reduction, and information passing, have influenced decades of work in query evaluation. Recent studies have renewed interest in the Yannakakis algorithm by demonstrating that its structure-aware principles can be applied to modern database systems, yielding practical methods for robust SQL analytics. This tutorial introduces the foundations of the Yannakakis algorithm and acyclic query processing, surveys recent advances in theory and systems, and discusses how these ideas extend to query optimization and general queries beyond the multi-way joins. The goal is to give the audience both a clear conceptual understanding of Yannakakis algorithm and a broad view of its growing role in modern data management.
Paraschos Koutris, Stijn Vansummeren, Qichen Wang et al.· Proceedings of the VLDB Endo...· 0 citations
It is proved that Minimal-to-Maximal Conversion Search is in fact not output-polynomial and the lower bound construction motivates a more detailed analysis of how certain heuristic choices in the algorithm design affect the running time.
Worst-case optimal join (WCOJ) algorithms have attracted significant interest in both academia and industry due to their strong asymptotic performance guarantees. However, their integration into mature relational database management systems (RDBMSs) remains severely limited. Unlike prior theoretical surveys, this study analyzes the practical considerations for WCOJ adoption across three core query engine layers: interpretation, optimization, and execution, before extending to distributed environments. The findings indicate that the primary bottlenecks delaying widespread adoption are architectural rather than algorithmic. Specifically, WCOJ integration necessitates a fundamental shift in the optimization layer toward hybrid planning and new objective functions based on intersection costs. Furthermore, at the execution layer, the unpredictable pointer-chasing inherent to hierarchical index traversals creates severe hardware inefficiencies. By synthesizing ongoing research efforts, this survey provides a structured roadmap of engineering trade-offs to guide practitioners in successfully integrating WCOJs into conventional database architectures.
Ayoub Berdai, Kawtar Younsi Dahbi, D. Chiadmi et al.· International Journal of Adv...· 0 citations
Prescriptive analytics workloads often require solving package queries over data that changes continuously. A package query (PQ) returns a multiset of tuples satisfying global constraints and optimizing a given objective, a natural formulation of constrained optimization within a database. When each attribute in the query has a clear "better" direction, e.g., lower cost and higher performance, most candidate tuples are irrelevant: they are strictly worse than others on every dimension and can never appear in an optimal solution. Yet, keeping solutions current as data evolves remains challenging: re-solving from scratch is slow, warm-starting helps only modestly, and solver preprocessing achieves only limited data reduction. We demonstrate SKYPQ, a system that employs a novel, dominance-based data reduction method for such package queries under updates. The key idea is to maintain a
K-skyband index
, a small, correctness-preserving subset of candidates, and apply a
resolve checker
to skip re-optimization when updates cannot affect the optimal package. The index can be shared by multiple PQs. Via an interactive interface, participants visualize the candidate space collapsing to the K-skyband, solve PQs over the reduced space with exact results, explore what-if scenarios, and observe the system efficiently handling batch updates. Participants experience firsthand how K-skyband reduction provides both speed and correctness for constrained optimization over evolving data.
Vasileios Vittis, A. Abouzied, Peter J. Haas et al.· Proceedings of the VLDB Endo...· 0 citations
This paper shows how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice, and demonstrates the potential of parallelism when applied to the bounded tree search phase of FPT algorithms.
F. Dehne, A. Rau-Chaplin, U. Stege et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
