Conjunctive Queries with Comparisons.
Published in ACM Transactions on Database Systems (TODS), 2025
Invited as Best of SIGMOD 2022
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. The new algorithm is further extended to support annotated relations and aggregations over general semirings. While Boolean free-connex conjunctive queries with comparisons remain tractable, counting variants may not, answering an open question on the hardness of different semirings. 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. 2025. Conjunctive Queries with Comparisons. ACM Trans. Database Syst (TODS).
Supplemental Material
The experiment scripts have obtained the ACM Reproducibility 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 has been accepted by SIGMOD 2023. Thanks to Binyang for his hard work.