Conjunctive Queries with Comparisons

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationSIGMOD '22: Proceedings of the 2022 International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Pages108-121
Number of pages14
ISBN (Print)9781450392495
DOIs
Publication statusPublished - 11 Jun 2022
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2022 - Virtual, Online, Philadelphia, United States
Duration: 12 Jun 202217 Jun 2022
https://2022.sigmod.org/
https://dl.acm.org/doi/proceedings/10.1145/3514221

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Conference

ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2022
Country/TerritoryUnited States
CityPhiladelphia
Period12/06/2217/06/22
Internet address

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • acyclic joins
  • conjunctive query
  • inequality joins

Fingerprint

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

Cite this