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: h5499855f9e141158
Venue: VLDB
Year: 2023
Pagerank: 5.5202266e-05
Overall Rank: 7,394 | 50.44%
DOI: 10.14778/3611479.3611489
PDF: Download (CC BY-NC-ND 4.0)

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 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,991	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.0845476e-05
10,476	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.9605343e-05
10,924	Worst-Case Optimal BGPs on Temporal Graphs	2026	VLDB	4.9605343e-05
11,243	AJOSC: Adaptive Join Order Selection for Continuous Queries	2025	SIGMOD	4.9605343e-05
11,856	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	4.9605343e-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.0023948467
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
34	The Design Of Postgres	1986	SIGMOD	0.00049063803
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040739114
142	Neo: A Learned Query Optimizer	2019	VLDB	0.00029114937
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024929198
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
355	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00020146245
411	QTune: A Query-Aware Database Tuning System with Deep Reinforcement Learning	2019	VLDB	0.0001874043
467	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00017740891
522	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016893112
848	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013463236
1,238	DB-BERT: A Database Tuning Tool that "Reads the Manual"	2022	SIGMOD	0.00011375179
1,294	An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems	2021	VLDB	0.00011129451
1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010090639
1,609	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	0.0001007196
3,655	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	7.1137504e-05
4,817	Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling	2021	VLDB	6.388743e-05
4,990	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD	6.3120056e-05
8,253	Demonstrating UDO: A Unified Approach for Optimizing Transaction Code, Physical Design, and System Parameters via Reinforcement Learning	2021	SIGMOD	5.353686e-05
8,556	GRainDB: A Relational-core Graph-Relational DBMS	2022	CIDR	5.3017563e-05
8,872	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.2459616e-05
11,856	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	4.9605343e-05

Semantically Similar Papers

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