Conjunctive Queries with Comparisons

Summary: Conjunctive queries with inter-relational comparisons; predicate pushdown is weak here. Introduces a new algorithm for short and long comparisons, with an acyclic condition yielding linear-time evaluation; implemented on Spark and achieves order-of-magnitude speedups over SparkSQL on graph-pattern and analytical workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6346
Venue: SIGMOD
Year: 2022
Pagerank: 6.6223692e-05
Overall Rank: 4,575 | 68.62%
DOI: 10.1145/3514221.3517830

Incoming Non-self Citations Over Time

Authors

1. Qichen Wang (Hong Kong University of Science and Technology)
2. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{wang_sigmod22,
        title = {{Conjunctive Queries with Comparisons}},
        author = {Wang, Qichen and Yi, Ke},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517830},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517830},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,622	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.2465862e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
6,444	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	5.8774519e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
8,686	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	5.3849387e-05
9,184	Complex Event Recognition meets Hierarchical Conjunctive Queries	2024	PODS	5.3058708e-05
9,693	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.2351259e-05
9,720	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.2319816e-05
10,154	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	5.093636e-05
10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	5.093636e-05
10,762	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	5.093636e-05
11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	5.093636e-05
11,338	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
24	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00054865648
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
2,266	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.8391372e-05
2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.5358494e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,182	The Space-Time Complexity of Sum-Product Queries	2026	PODS
2	295	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD
3	10,002	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB
4	8,235	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD
5	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
6	11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD
7	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
8	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
9	954	Parallel Evaluation of Conjunctive Queries	2011	PODS
10	7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD