Exact Cardinality Query Optimization with Bounded Execution Cost

Summary: ECQO with bounded probes uses exact cardinalities from probes to prune join plans via partial-relations bounds. Leverages dependencies and info-gain probe selection with cost bounds; non-intrusive atop SQL LIMIT, achieving 6×–69× speedups on join-order benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h38e589f1cb1e4066
Venue: SIGMOD
Year: 2019
Pagerank: 6.210331e-05
Overall Rank: 5,223 | 65.00%
DOI: 10.1145/3299869.3300087

Incoming Non-self Citations Over Time

Authors

1. Immanuel Trummer (Cornell University)

BibTeX Citation

@inproceedings{trummer_sigmod19,
        title = {{Exact Cardinality Query Optimization with Bounded Execution Cost}},
        author = {Trummer, Immanuel},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3300087},
        url = {https://dl.acm.org/doi/10.1145/3299869.3300087},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
983	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012677179
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011759683
3,655	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	7.1137504e-05
4,202	Kepler: Robust Learning for Faster Parametric Query Optimization	2023	SIGMOD	6.7258607e-05
5,044	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	6.2888728e-05
5,153	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.2375324e-05
6,402	A Unified Transferable Model for ML-Enhanced DBMS	2022	CIDR	5.7800842e-05
6,812	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6597129e-05
8,154	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.3732833e-05
8,225	Grep: A Graph Learning Based Database Partitioning System	2023	SIGMOD	5.3583852e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040739114
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031291457
285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022143946
381	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019497061
568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016221103
794	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.0001389694
824	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.0001360282
838	Proactive Re-Optimization	2005	SIGMOD	0.00013528646
1,080	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012114187
1,261	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011289724
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.2323722e-05
2,438	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4532693e-05
2,888	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.8895201e-05
3,361	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.3621595e-05
6,405	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB	5.7791099e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,075	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD
2	1,261	Sampling-Based Query Re-Optimization	2016	SIGMOD
3	3,226	Efficient and Provable Multi-Query Optimization	2017	PODS
4	10,220	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS
5	10,446	Coresets for Robust Query Optimization	2026	PODS
6	568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
7	381	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB
8	15	How Good Are Query Optimizers, Really?	2016	VLDB
9	7,619	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
10	3,361	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB