{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:05Z","timestamp":1773481865746,"version":"3.50.1"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2023,6,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3604437.3604450","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T22:22:01Z","timestamp":1686262921000},"page":"54-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Conjunctive Queries with Comparisons"],"prefix":"10.1145","volume":"52","author":[{"given":"Qichen","family":"Wang","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"HKUST Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases: The Logical Level","author":"Abiteboul S.","unstructured":"S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases: The Logical Level . Addison-Wesley S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases: The Logical Level. Addison-Wesley"},{"key":"e_1_2_1_2_1","volume-title":"On acyclic conjunctive queries and constant delay enumeration. CSL\/EACSL, page 208--222","author":"Bagan G.","year":"2007","unstructured":"G. Bagan , A. Durand , and E. Grandjean . On acyclic conjunctive queries and constant delay enumeration. CSL\/EACSL, page 208--222 . Springer-Verlag , 2007 . G. Bagan, A. Durand, and E. Grandjean. On acyclic conjunctive queries and constant delay enumeration. CSL\/EACSL, page 208--222. Springer-Verlag, 2007."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840441"},{"key":"e_1_2_1_5_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms , Third Edition. The MIT Press , 3 rd edition, 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_7_1","volume-title":"WG, page 1--15","author":"Gottlob G.","year":"2005","unstructured":"G. Gottlob , M. Grohe , N. Musliu , M. Samer , and F. Scarcello . Hypertree decompositions: Structure, algorithms, and applications . In WG, page 1--15 . Springer-Verlag , 2005 . G. Gottlob, M. Grohe, N. Musliu, M. Samer, and F. Scarcello. Hypertree decompositions: Structure, algorithms, and applications. In WG, page 1--15. Springer-Verlag, 2005."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_10_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICDT","author":"Khamis M.","year":"2019","unstructured":"M. Khamis , H. Ngo , D. Olteanu , and D. Suciu . Boolean tensor decomposition for conjunctive queries with negation . In ICDT , volume 127 of LIPIcs , pages 21: 1 -- 21 :19. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik , 2019 . M. Khamis, H. Ngo, D. Olteanu, and D. Suciu. Boolean tensor decomposition for conjunctive queries with negation. In ICDT, volume 127 of LIPIcs, pages 21:1--21:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, 2019."},{"key":"e_1_2_1_11_1","volume-title":"ACM","author":"Khamis M.","year":"2017","unstructured":"M. Khamis , H. Q. Ngo , and D. Suciu . What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In PODS, page 429--444 . ACM , 2017 . M. Khamis, H. Q. Ngo, and D. Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In PODS, page 429--444. ACM, 2017."},{"key":"e_1_2_1_12_1","volume-title":"Functional aggregate queries with additive inequalities. ACM Transactions on Database Systems, 45(4), dec","author":"Khamis M. A.","year":"2020","unstructured":"M. A. Khamis , R. R. Curtin , B. Moseley , H. Q. Ngo , X. Nguyen , D. Olteanu , and M. Schleich . Functional aggregate queries with additive inequalities. ACM Transactions on Database Systems, 45(4), dec 2020 . M. A. Khamis, R. R. Curtin, B. Moseley, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. Functional aggregate queries with additive inequalities. ACM Transactions on Database Systems, 45(4), dec 2020."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9684-2"},{"key":"e_1_2_1_14_1","volume-title":"Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal of the ACM, 60(6), nov","author":"Marx D.","year":"2013","unstructured":"D. Marx . Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal of the ACM, 60(6), nov 2013 . D. Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal of the ACM, 60(6), nov 2013."},{"key":"e_1_2_1_15_1","volume-title":"ACM","author":"Ngo H. Q.","year":"2012","unstructured":"H. Q. Ngo , E. Porat , C. R\u00b4e , and A. Rudra . Worst-case optimal join algorithms: [extended abstract]. In PODS, page 37--48 . ACM , 2012 . H. Q. Ngo, E. Porat, C. R\u00b4e, and A. Rudra. Worst-case optimal join algorithms: [extended abstract]. In PODS, page 37--48. ACM, 2012."},{"key":"e_1_2_1_16_1","volume-title":"ACM","author":"Patrascu M.","year":"2010","unstructured":"M. Patrascu . Towards polynomial lower bounds for dynamic problems. In STOC, page 603--610 . ACM , 2010 . M. Patrascu. Towards polynomial lower bounds for dynamic problems. In STOC, page 603--610. ACM, 2010."},{"key":"e_1_2_1_17_1","first-page":"2599","volume-title":"VLDB","volume":"14","author":"Tziavelis N.","year":"2021","unstructured":"N. Tziavelis , W. Gatterbauer , and M. Riedewald . Beyond equi-joins: Ranking, enumeration and factorization . In VLDB , volume 14 , page 2599 -- 2612 . VLDB Endowment , 2021 . N. Tziavelis, W. Gatterbauer, and M. Riedewald. Beyond equi-joins: Ranking, enumeration and factorization. In VLDB, volume 14, page 2599--2612. VLDB Endowment, 2021."},{"key":"e_1_2_1_18_1","first-page":"108","volume-title":"SIGMOD","author":"Wang Q.","year":"2022","unstructured":"Q. Wang and K. Yi . Conjunctive queries with comparisons . In SIGMOD , pages 108 -- 121 . ACM, 2022 . Q. Wang and K. Yi. Conjunctive queries with comparisons. In SIGMOD, pages 108--121. ACM, 2022."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1848"},{"key":"e_1_2_1_20_1","volume-title":"VLDB Endowment","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis . Algorithms for acyclic database schemes. In VLDB, page 82--94 . VLDB Endowment , 1981 . M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, page 82--94. VLDB Endowment, 1981."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1979.762509"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604450","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604437.3604450","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:19Z","timestamp":1750178839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6,7]]}},"alternative-id":["10.1145\/3604437.3604450"],"URL":"https:\/\/doi.org\/10.1145\/3604437.3604450","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"2023-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}