Histogram techniques are used to efficiently estimate query result sizes in most of the modern-day database systems. In a recent work, we introduced a new histogram-like approximation strategy, called the Rectangular Attribute Cardinality Map (R-ACM), which approximates the density function within a given sector by a rectangular cell. In this paper, we introduce another histogram-like approximation strategy, called the Trapezoidal Attribute Cardinality Map (T-ACM) that approximates the density function within a given sector by a trapezoidal cell, where the slope of the trapezoid is obtained so as to fix the actual probability mass within the cell. We present numerous analytic and experimental results concerning the T-ACM demonstrating its superiority over the traditional equi-width and equi-depth histograms for query result size estimation. We hope that with the R-ACM introduced in [6], the T-ACM could become an invaluable tool for query optimization in the future database systems.

Additional Metadata
Conference 2000 International Database Engineering and Applications Symposium
Citation
Oommen, J, & Thiyagarajah, Murali (Murali). (2000). Query result size estimation using the Trapezoidal Attribute Cardinality Map. Proceedings of the International Database Engineering and Applications Symposium, IDEAS, 236–242.