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: h7a9a38629c802055
Venue: CIDR
Year: 2007
Pagerank: 8.9193253e-05
Overall Rank: 2,174 | 85.39%
DOI: -
PDF: Download (CC BY 2.5)

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
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035876108
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021166957
462	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.00017836105
1,605	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	0.00010095581
1,800	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.6082185e-05
2,237	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7738349e-05
2,844	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.9446987e-05
3,208	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	7.5355264e-05
4,690	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.4667478e-05
5,006	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3159614e-05
7,958	Robust Query Processing: Mission Possible	2020	VLDB	5.4164639e-05
8,137	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.391109e-05
10,295	Request Window: an Approach to Improve Throughput of RDBMS-based Data Integration System by Utilizing Data Sharing Across Concurrent Distributed Queries	2007	VLDB	5.0422244e-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
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034099838
186	Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases	1991	VLDB	0.00025938943
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.0002378554
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019822444
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017955913
644	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015209065
661	Adaptive Precision Setting for Cached Approximate Values	2001	SIGMOD	0.000150088
1,219	Best-Effort Cache Synchronization with Source Cooperation	2002	SIGMOD	0.00011478351
7,913	SkyQuery: A Web Service Approach to Federate Databases	2003	CIDR	5.4259499e-05
8,173	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3824152e-05

Semantically Similar Papers

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