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.3760492e-05
Overall Rank: 3,361 | 77.41%
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
955	Flexible Database Generators	2005	VLDB	0.00012866364
1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010180835
1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3546057e-05
3,562	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2046519e-05
5,357	Can Large Language Models Predict Data Correlations from Column Names?	2023	VLDB	6.1619918e-05
5,470	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB	6.1182634e-05
5,597	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0718206e-05
6,208	Efficient Detection of Empty-Result Queries	2006	VLDB	5.8497045e-05
8,289	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.3614788e-05
10,308	Fast Approximate Computation of Statistics on Views	2006	SIGMOD	5.0400722e-05
10,322	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.0346745e-05
11,290	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9793485e-05
12,792	Filtered Statistics	2009	SIGMOD	4.9793485e-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.0023947656
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
273	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022504729
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.0002211981
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019829769
412	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018694414
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017962189
553	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.0001652591
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001520859
701	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00014680907
866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013381261
1,183	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011616705
1,741	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7382372e-05
3,133	Statistics on Views	2003	VLDB	7.6127492e-05

Semantically Similar Papers

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