Conjunctive Queries with Comparisons

Qichen Wang*, Ke Yi*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review


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 patterns and analytical queries.
Original languageEnglish
Pages (from-to)54–62
Number of pages9
JournalSIGMOD Record
Issue number1
Publication statusPublished - Mar 2023

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • acyclic joins
  • conjunctive query
  • inequality joins


Dive into the research topics of 'Conjunctive Queries with Comparisons'. Together they form a unique fingerprint.

Cite this