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.3493132e-05
Overall Rank: 3,371 | 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
958	Flexible Database Generators	2005	VLDB	0.00012834376
1,583	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010148362
1,935	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3407959e-05
3,555	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.1877332e-05
5,377	Can Large Language Models Predict Data Correlations from Column Names?	2023	VLDB	6.1396287e-05
5,490	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB	6.0970166e-05
5,611	StatAdvisor: Recommending Statistical Views	2009	VLDB	6.0498181e-05
6,224	Efficient Detection of Empty-Result Queries	2006	VLDB	5.828372e-05
8,310	Relational Support for Flexible Schema Scenarios	2008	VLDB	5.3412209e-05
10,343	Fast Approximate Computation of Statistics on Views	2006	SIGMOD	5.0210286e-05
10,355	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.0156513e-05
11,353	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9605343e-05
12,841	Filtered Statistics	2009	SIGMOD	4.9605343e-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.0023948467
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010688884
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047770864
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034050614
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031291457
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
275	Extensible Query Processing in Starburst	1989	SIGMOD	0.000224395
277	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002235043
287	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022060616
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
413	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018638335
457	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017915659
556	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016470022
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015166402
701	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.0001464136
868	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013336675
1,186	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011581468
1,754	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7111856e-05
3,142	Statistics on Views	2003	VLDB	7.5858292e-05

Semantically Similar Papers

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