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.2327836e-05
Overall Rank: 5,199 | 65.05%
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
982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012714044
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
3,645	UDO: Universal Database Optimization using Reinforcement Learning	2021	VLDB	7.1397796e-05
4,202	Kepler: Robust Learning for Faster Parametric Query Optimization	2023	SIGMOD	6.7374091e-05
5,022	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	6.3100988e-05
5,126	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.261175e-05
6,416	A Unified Transferable Model for ML-Enhanced DBMS	2022	CIDR	5.7920805e-05
6,791	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6811782e-05
8,131	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.3936608e-05
8,202	Grep: A Graph Learning Based Database Partitioning System	2023	SIGMOD	5.378708e-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.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019444411
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016245271
796	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00013938011
827	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013632674
836	Proactive Re-Optimization	2005	SIGMOD	0.00013557047
1,077	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012154948
1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011310561
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.250242e-05
2,433	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4766785e-05
2,891	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.9021718e-05
3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.3719456e-05
6,393	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB	5.8002013e-05

Semantically Similar Papers

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