DBScholar

Back to papers

On the Propagation of Errors in the Size of Join Results

Summary: Formal framework for how errors in statistics propagate to join size estimates and optimizer plans. Analyzes general, extreme, and average-case propagation; derives guarantees for statistics-driven plans; outlines strategies to control error growth. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hbeeda4265fc3e3e2
Venue
SIGMOD
Year
1991
Pagerank
0.00034748721
Overall Rank
91 | 99.40%
DOI
10.1145/115790.115835

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ioannidis_sigmod91,
        title = {{On the Propagation of Errors in the Size of Join Results}},
        author = {Ioannidis, Yannis E. and Christodoulakis, Stavros},
        series = {{SIGMOD} '91},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/115790.115835},
        url = {https://dl.acm.org/doi/10.1145/115790.115835},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 82 citing papers.

Rank Citing Paper Year Venue Pagerank
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061067652
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
98 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034099838
149 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00028977821
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.0002378554
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023354266
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
284 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022205848
288 Optimization of Dynamic Query Evaluation Plans 1994 SIGMOD 0.00021964339
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021236408
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019446558
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019095982
471 Robust Query Processing through Progressive Optimization 2004 SIGMOD 0.00017744392
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016244162
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014749318
837 Proactive Re-Optimization 2005 SIGMOD 0.00013551072
1,058 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00012224038
1,084 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00012108365
1,135 Dremel: A Decade of Interactive SQL Analysis at Web Scale 2020 VLDB 0.00011886308
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011843746
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011147959
1,432 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 0.00010676754
1,509 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.00010436933
1,543 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010305662
1,588 Estimating Progress of Execution for SQL Queries 2004 SIGMOD 0.00010137374
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8614576e-05
1,743 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7342409e-05
1,931 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.3511556e-05
1,989 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.2469024e-05
2,002 FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021 VLDB 9.2076835e-05
2,162 DIFF: A Relational Interface for Large-Scale Data Explanation 2019 VLDB 8.9344773e-05
2,217 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.8151982e-05
2,320 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.6429103e-05
2,719 Partial Results in Database Systems 2014 SIGMOD 8.0942034e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9637452e-05
2,844 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9446987e-05
2,890 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9010819e-05
2,956 Scalable and Adaptive Online Joins 2014 VLDB 7.8100535e-05
3,103 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 7.6456038e-05
3,362 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.3719912e-05
3,527 Identifying Robust Plans through Plan Diagram Reduction 2008 VLDB 7.2283486e-05
3,552 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 7.2070901e-05
3,661 Scalable Computation of Acyclic Joins (Extended Abstract) 2006 PODS 7.1184935e-05
3,929 Big Metadata: When Metadata is Big Data 2021 VLDB 6.9159392e-05
3,969 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8874168e-05
4,069 Dynamically Optimizing Queries over Large Scale Data Platforms 2014 SIGMOD 6.8184364e-05
4,200 Adaptive Work Placement for Query Processing on Heterogeneous Computing Resources 2017 VLDB 6.7378729e-05
4,267 Buffer Pool Aware Query Optimization 2005 CIDR 6.6936093e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank Cited Paper Year Venue Pagerank
345 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.0002045459
397 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00019151375
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 143 Optimization of Nonrecursive Queries 1986 VLDB
2 1,514 Computing Joins Of Relations 1975 SIGMOD
3 1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB
4 4,882 Evaluation Of The Size Of A Query Expressed In Relational Algebra 1981 SIGMOD
5 7,496 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS
6 402 Worst-case Optimal Join Algorithms 2012 PODS
7 315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS
8 429 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS
9 2,138 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
10 1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD