Histogram-Based Solutions to Diverse Database Estimation Problems.

Yannis E. Ioannidis, Viswanath Poosala: Histogram-Based Solutions to Diverse Database Estimation Problems. IEEE Data Eng. Bull. 18(3): 10-18(1995)
  author    = {Yannis E. Ioannidis and
               Viswanath Poosala},
  title     = {Histogram-Based Solutions to Diverse Database Estimation Problems},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {18},
  number    = {3},
  year      = {1995},
  pages     = {10-18},
  ee        = {db/journals/debu/IoannidisP95.html},
  bibsource = {DBLP,}


Many current database systems use some form of histograms to approximate the frequency distribution of values in the attributes of relations and based on them estimate some query result sizes and access plan costs. In this paper, we overview the line of research on histograms that we have followed at the Univ. of Wisconsin. Our goal has been to identify classes of histograms that combine three features in most realistic cases: (i) they produce estimates with small errors, (ii) they are inexpensive to construct, use, and maintain, and (iii) they can be used for many diverse estimation problems. Based on that goal, we present several results, which eventually point towards a class of histograms that are practical, close to optimal, and effective in estimating sizes of query results, frequency distributions of attribute values in query results, and even costs of accesses using secondary indices.

Copyright © 1995 by the author(s). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition:

Data Engineering Bulletin September 1995: Database Query Processing (Goetz Graefe, ed.)
( letter+figures , letter-figures , A4+figures , A4-figures , PDF+figures)


Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277 BibTeX
Yannis E. Ioannidis, Stavros Christodoulakis: Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. ACM Trans. Database Syst. 18(4): 709-748(1993) BibTeX
Yannis E. Ioannidis: Universality of Serial Histograms. VLDB 1993: 256-267 BibTeX
Yannis E. Ioannidis, Viswanath Poosala: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995: 233-244 BibTeX
Raj Jain, Imrich Chlamtac: The P² Algorithm for Dynamic Calculation of Quantiiles and Histograms Without Storing Observations. Commun. ACM 28(10): 1076-1085(1985) BibTeX
Robert Kooi: The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980
M. Muralikrishna, David J. DeWitt: Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988: 28-36 BibTeX
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276 BibTeX
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
Yun Wang: Experience from a Real Life Query Optimizer. SIGMOD Conference 1992: 286 BibTeX

Referenced by

  1. Joachim Kröger, Regina Illner, Steffen Rost, Andreas Heuer: Query Rewriting and Search in CROQUE. ADBIS 1999: 288-302
  2. Steve Olson, Richard Pledereder, Phil Shaw, David Yach: The Sybase Architecture for Extensible Data Management. IEEE Data Eng. Bull. 21(3): 12-24(1998)
  3. Narayanan Shivakumar, Hector Garcia-Molina, Chandra Chekuri: Filtering with Approximate Predicates. VLDB 1998: 263-274
  4. Navin Kabra, David J. DeWitt: Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998: 106-117
  5. Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Random Sampling for Histogram Construction: How much is enough? SIGMOD Conference 1998: 436-447
  6. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
  7. Viswanath Poosala, Yannis E. Ioannidis: Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing. VLDB 1996: 448-459
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
Bulletin of the IEEE Computer Society Technical Committee on Data Engineering: Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:56:14 2009