ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning

Summary: Adaptive query engine for worst-case optimal joins that searches attribute-order space (not relation order) via episodic trials and reinforcement learning to balance exploration vs. exploitation. Novel data structure reuses processed input to avoid redundant work and converge quickly to near-optimal orders under skew/correlation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13311
Venue: VLDB
Year: 2023
Pagerank: 5.514996e-05
Overall Rank: 7,978 | 45.27%
DOI: 10.14778/3611479.3611489

Incoming Non-self Citations Over Time

Authors

1. Junxiong Wang (Cornell University)
2. Immanuel Trummer (Cornell University)
3. Ahmet Kara (University of Zurich)
4. Dan Olteanu (University of Zurich)

BibTeX Citation

@article{wang_vldb23,
        title = {{ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning}},
        author = {Wang, Junxiong and Trummer, Immanuel and Kara, Ahmet and Olteanu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {11},
        pages = {2805--2817},
        doi = {10.14778/3611479.3611489},
        url = {https://doi.org/10.14778/3611479.3611489},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,182	The Space-Time Complexity of Sum-Product Queries	2026	PODS	5.093636e-05
10,749	AJOSC: Adaptive Join Order Selection for Continuous Queries	2025	SIGMOD	5.093636e-05
10,765	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.093636e-05
11,497	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
34	The Design Of Postgres	1986	SIGMOD	0.00049302774
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
154	Neo: A Learned Query Optimizer	2019	VLDB	0.00028726181
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
378	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00019638121
490	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.000175757
498	QTune: A Query-Aware Database Tuning System with Deep Reinforcement Learning	2019	VLDB	0.00017440583
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
860	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013560445
1,337	DB-BERT: A Database Tuning Tool that "Reads the Manual"	2022	SIGMOD	0.00011117488
1,344	An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems	2021	VLDB	0.00011094717
1,712	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.9492299e-05
1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.875587e-05
3,926	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	7.0128068e-05
5,000	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	6.4069917e-05
5,091	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD	6.3669569e-05
8,068	Demonstrating UDO: A Unified Approach for Optimizing Transaction Code, Physical Design, and System Parameters via Reinforcement Learning	2021	SIGMOD	5.4941082e-05
8,376	GRainDB: A Relational-core Graph-Relational DBMS	2022	CIDR	5.4389021e-05
8,698	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.3830073e-05
11,497	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,488	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD
2	11,160	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD
3	7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
4	1,815	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB
5	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
6	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
7	6,593	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB
8	1,712	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD
9	6,735	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB
10	11,497	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB