A Black-Box Approach to Query Cardinality Estimation

Summary: Black-box method: no plans or data stats, groups queries by syntax and learns per-family cardinality distributions from high-dimensional feature vectors (attrs, ops, constants, funcs, aggregates). Accurate, space- and compute-frugal estimates for remote/federated settings (Open SkyQuery), greatly improving caching/scheduling. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 60
Venue: CIDR
Year: 2007
Pagerank: 9.0625592e-05
Overall Rank: 2,157 | 85.21%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Tanu Malik (Johns Hopkins University)
2. Randal Burns (Johns Hopkins University)
3. Nitesh Chawla (University of Notre Dame)

BibTeX Citation

@inproceedings{malik_cidr07,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '07},
        title = {{A Black-Box Approach to Query Cardinality Estimation}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Malik, Tanu and Burns, Randal and Chawla, Nitesh},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
465	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.0001803934
1,712	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.9492299e-05
1,815	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.6894541e-05
2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.9410226e-05
2,991	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.8880723e-05
3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	7.6785856e-05
4,617	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.604437e-05
4,900	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.4534715e-05
7,829	Robust Query Processing: Mission Possible	2020	VLDB	5.5360082e-05
7,967	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.5169373e-05
10,078	Request Window: an Approach to Improve Throughput of RDBMS-based Data Integration System by Utilizing Data Sharing Across Concurrent Distributed Queries	2007	VLDB	5.1603976e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
100	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034385207
182	Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases	1991	VLDB	0.00026367971
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
448	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00018292618
646	Adaptive Precision Setting for Cached Approximate Values	2001	SIGMOD	0.00015335457
664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015167825
1,195	Best-Effort Cache Synchronization with Source Cooperation	2002	SIGMOD	0.00011727947
7,994	SkyQuery: A Web Service Approach to Federate Databases	2003	CIDR	5.5096586e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
2	10,875	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB
3	5,516	Distributed Set-Expression Cardinality Estimation	2004	VLDB
4	2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
5	1,122	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB
6	6,543	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD
7	2,723	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB
8	1,468	Towards a Learning Optimizer for Shared Clouds	2019	VLDB
9	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
10	1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB