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: 5680
Venue: SIGMOD
Year: 2019
Pagerank: 6.3507372e-05
Overall Rank: 5,137 | 64.76%
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
1,122	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.0001209124
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
3,926	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	7.0128068e-05
4,470	Kepler: Robust Learning for Faster Parametric Query Optimization	2023	SIGMOD	6.6817353e-05
5,010	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	6.4023732e-05
5,011	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.4020848e-05
6,357	A Unified Transferable Model for ML-Enhanced DBMS	2022	CIDR	5.9020843e-05
7,193	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6770249e-05
7,967	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.5169373e-05
8,042	Grep: A Graph Learning Based Database Partitioning System	2023	SIGMOD	5.5015896e-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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019410042
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013846487
829	Proactive Re-Optimization	2005	SIGMOD	0.00013769838
1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012401532
1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011457194
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.3517129e-05
2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.6225576e-05
2,944	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.9335187e-05
3,426	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.4218997e-05
6,316	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB	5.9151861e-05

Semantically Similar Papers

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