Conditional Selectivity for Statistics on Query Expressions

Summary: Frames SITs on query expressions with conditional selectivity, replacing view-matching to improve cardinality estimates. Proposes a DP algorithm to compute optimal conditional selectivities per query, enabling integration with minimal optimizer changes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hd6d06c18b771c424
Venue: SIGMOD
Year: 2004
Pagerank: 7.3726415e-05
Overall Rank: 3,361 | 77.42%
DOI: 10.1145/1007568.1007604

Incoming Non-self Citations Over Time

Authors

1. Nicolas Bruno (Microsoft)
2. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@inproceedings{bruno_sigmod04,
        title = {{Conditional Selectivity for Statistics on Query Expressions}},
        author = {Bruno, Nicolas and Chaudhuri, Surajit},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007604},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007604},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
956	Flexible Database Generators	2005	VLDB	0.0001286031
1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010177136
1,931	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3511556e-05
3,563	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2023194e-05
5,362	Can Large Language Models Predict Data Correlations from Column Names?	2023	VLDB	6.1592249e-05
5,475	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB	6.115573e-05
5,598	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0690976e-05
6,212	Efficient Detection of Empty-Result Queries	2006	VLDB	5.8469404e-05
8,295	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.3589408e-05
10,315	Fast Approximate Computation of Statistics on Views	2006	SIGMOD	5.0376863e-05
10,329	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.0322912e-05
11,298	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9769913e-05
12,798	Filtered Statistics	2009	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 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.0023943337
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679903
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047864281
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.0004772731
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034099838
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033884854
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003136296
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029618887
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023354266
273	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022498382
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022404363
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022112534
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019822444
413	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018686769
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017955913
553	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016518678
644	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015209065
700	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00014675903
867	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013376165
1,182	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011615497
1,743	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7342409e-05
3,134	Statistics on Views	2003	VLDB	7.6093829e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
2	9,640	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
3	3,134	Statistics on Views	2003	VLDB
4	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
5	2,975	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB
6	1,543	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB
7	3,208	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
8	644	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
9	7,603	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
10	1,931	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB