Joins via Geometric Resolutions: Worst-case and Beyond

Summary: Introduce a geometric framework that formalizes index inference as “geometric resolution”, reducing join evaluation to a geometric problem and yielding an algorithm that achieves the fractional hypertree‑width bound. Also gives beyond‑worst‑case guarantees for B‑trees, multidimensional structures and multiple indices per table, and connects to logical resolution and backtracking-with-memoization perspectives. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1661
Venue: PODS
Year: 2015
Pagerank: 9.0746479e-05
Overall Rank: 2,298 | 84.04%
DOI: 10.1145/2745754.2745776

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
5,049	High-Performance Row Pattern Recognition Using Joins	2023	VLDB	5.7275467e-05
5,076	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	5.709895e-05
5,503	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4718854e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
6,640	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	4.9753538e-05
7,328	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7560344e-05
7,456	BSX : Subgraph Matching with Batch Backtracking Search	2025	SIGMOD	4.7205339e-05
8,350	LogiQL: a Declarative Language for Enterprise Applications	2015	PODS	4.5342845e-05
8,470	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.4993203e-05
10,336	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1905499e-05
10,493	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1905499e-05
10,639	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1905499e-05

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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
350	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00026368305
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
538	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020632609
1,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141
2,007	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8123766e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
6,294	Free Join: Unifying Worst-Case Optimal and Traditional Joins	2023	SIGMOD	5.1202075e-05
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05