Conjunctive Queries with Comparisons.
Published in ACM SIGMOD International Conference on Management of Data (SIGMOD), 2022
Selected as ACM SIGMOD Best Paper Honorable Mention
Abstract
Conjunctive queries with predicates in the form of comparisons that span multiple relations have regained interest recently, due to their relevance in OLAP queries, spatiotemporal databases, and machine learning over relational data. The standard technique, predicate pushdown, has limited efficacy on such comparisons. A technique by Willard can be used to process short comparisons that are adjacent in the join tree in time linear in the input size plus output size. In this paper, we describe a new algorithm for evaluating conjunctive queries with both short and long comparisons, and identify an acyclic condition under which linear time can be achieved. We have also implemented the new algorithm on top of Spark, and our experimental results demonstrate order-of-magnitude speedups over SparkSQL on a variety of graph pattern and analytical queries.
Citation
Qichen Wang and Ke Yi. “Conjunctive Queries with Comparisons.” ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2022.
Supplemental Material
The experiment scripts have obtained the ACM Reprodicibility certification! You can reproduce the experiment results and all figures by using our experiment scripts! Thanks to Binyang Dai for his work to pass the test.
Our demo system for CQC is accepted by SIGMOD 2023. Thanks to Binyang for his hard work.