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 language | English |
---|---|
Title of host publication | SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data |
Publisher | Association for Computing Machinery (ACM) |
Pages | 108-121 |
Number of pages | 14 |
ISBN (Print) | 9781450392495 |
DOIs | |
Publication status | Published - 11 Jun 2022 |
Event | ACM SIGMOD International Conference on Management of Data, SIGMOD 2022 - Virtual, Online, Philadelphia, United States Duration: 12 Jun 2022 → 17 Jun 2022 https://2022.sigmod.org/ https://dl.acm.org/doi/proceedings/10.1145/3514221 |
Publication series
Name | Proceedings of the ACM SIGMOD International Conference on Management of Data |
---|---|
ISSN (Print) | 0730-8078 |
Conference
Conference | ACM SIGMOD International Conference on Management of Data, SIGMOD 2022 |
---|---|
Country/Territory | United States |
City | Philadelphia |
Period | 12/06/22 → 17/06/22 |
Internet address |
Scopus Subject Areas
- Software
- Information Systems
User-Defined Keywords
- acyclic joins
- conjunctive query
- inequality joins