Improving Join Reorderability with Compensation Operators

Summary: Proposes compensation operators to enable join reorderability for inner-joins, single-sided outer-joins, and/or antijoins. Overcomes non-associativity and enumeration gaps in prior work, enabling complete search of the join order space for this class and beating leading approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hdf6945804e0b8ba3
Venue: SIGMOD
Year: 2018
Pagerank: 4.9793485e-05
Overall Rank: 12,209 | 17.92%
DOI: 10.1145/3183713.3183731

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. TaiNing Wang (National University of Singapore)
2. Chee-Yong Chan (National University of Singapore)

BibTeX Citation

@inproceedings{wang_sigmod18,
        title = {{Improving Join Reorderability with Compensation Operators}},
        author = {Wang, TaiNing and Chan, Chee-Yong},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3183731},
        url = {https://dl.acm.org/doi/10.1145/3183713.3183731},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034124569
884	Dynamic Programming Strikes Back	2008	SIGMOD	0.00013267935
1,057	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD	0.00012231557
1,935	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB	9.3389342e-05
2,251	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7511987e-05
3,267	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.4764157e-05
3,699	Canonical Abstraction for Outerjoin Optimization	2004	SIGMOD	7.0865558e-05
4,464	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.5877622e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD
2	8,039	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
3	3,699	Canonical Abstraction for Outerjoin Optimization	2004	SIGMOD
4	3,982	Simplicity Done Right for Join Ordering	2021	CIDR
5	1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
6	3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
7	3,267	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD
8	1,935	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB
9	7,344	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD
10	1,057	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD