Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs

Summary: Proposes a generic top-down join enumeration for hypergraphs that handles multi-way predicates and outer joins, overcoming prior work limited to binary inner joins. Uses branch-and-bound pruning to preserve optimality with large compile-time gains, remaining competitive with bottom-up approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10857
Venue: VLDB
Year: 2013
Pagerank: 8.8196821e-05
Overall Rank: 2,275 | 84.40%
DOI: 10.14778/2556549.2556565

Incoming Non-self Citations Over Time

Authors

1. Pit Fender (University of Mannheim)
2. Guido Moerkotte (University of Mannheim)

BibTeX Citation

@article{fender_vldb13,
        title = {{Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs}},
        author = {Fender, Pit and Moerkotte, Guido},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {1822--1833},
        doi = {10.14778/2556549.2556565},
        url = {https://doi.org/10.14778/2556549.2556565},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
3,903	Keep It Simple: Testing Databases via Differential Query Plans	2024	SIGMOD	7.0304586e-05
4,916	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	6.4474058e-05
6,340	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.9071133e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.6041473e-05
11,160	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	5.093636e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.093636e-05
11,909	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
1,013	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012652549
1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011259156
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.91063e-05
3,263	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.584572e-05
3,538	A Combined Framework for Grouping and Order Optimization	2004	VLDB	7.3287689e-05
4,418	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.7137462e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
2	5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
3	10,622	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB
4	1,013	Dynamic Programming Strikes Back	2008	SIGMOD
5	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB
7	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
8	7,550	Processing Top-k Join Queries	2010	VLDB
9	3,263	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD
10	1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD