Abstract

In a database system, a method for determining a set of essential statistics. A set of potentially relevant, but unconstructed, statistics for a user query comprising a plurality of operators is compiled. A first value is assigned to the unconstructed statistics and a first projected query cost is computed for the query wherein the unconstructed statistics have the first value. A second value is assigned to the unconstructed statistics and a second projected query cost is computed for the query wherein the unconstructed statistics have the second value. The first and second projected query costs are compared and the determination of essential statistics is discontinued if the first and second projected query costs are equivalent. If the first and second projected query costs are not equivalent, an unconstructed statistic is selected to build and process is repeated until the first and second projected query costs are equivalent or all the unconstructed potentially relevant statistics have been constructed. Statistics which do not sufficiently impact a query plan may be added to a drop list for elimination.

Other References

• Choenni S., Blanken H., Chang T., "Index Selection in Relational Databases" , Proc. 5th IEEE ICCI 1993
• Chaundhuri, S., Motwani R., Narasayya V., "Random Sampling For Histogram Construction: How much is enough?" Proceedings of the ACM SIGMOD International Conference on Management of Data, 1988
• Chaundhuri S., Marasayya V., "An Efficient. Cost-Driven Index Selection Tool for Miscrosoft SQL Server." Proceedings of the 23rd VLDB Conference Athens, Greece, 1997
• Frank M., Omiecinski E., Navathe S., "Adaptive and Automated Index Selection in RDBMS", EDBT 92
• Finkelstein S., Schkolnick M., Tiberio P., "Physical Database Design for Relational Databases", ACM TODS, Mar. 1988
• Gibbons P.B., Matias Y., Poosala V., "Fast Incremental Maintenance of Approximate Histograms." Proceedings of the 23rd VLDB Conference, Athens, Greece, 1997, pp. 466-475
• Haas P.J., Naughton J.F., Seshadri S., Stokes L., "Sampling-Based Estimation of the Number of Distinct Values of an Attribute." Proceedings of the 21st VLDB Conference, pp. 311-322, 1995
• Ioannidis Y., Poosala V., "Balancing Histogram Optimality and Practicality for Query Result Size Estimation." Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 233-245, 1995
• Poosala V., Ioannidis Y., Haas P., Shekita E., "Improved Histograms for Selectivity Estimation of Range Predicates." Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 294-305, 1996
• Slutz, D., Massive Stochastic Testing of SQL, Proceedings of VLDB, 1998
• Poosala V., Ioannidis Y., "Selectivity Estimation Without the Attribute Value Independence Assumption" , Proceedings of the 23rd VLDB Conferenece, Athens, Greece, 1997, pp. 486-495
• Labio, W.J., Quass D., Adelberg B., "Physical Database Design for Data Warehouses" , Proc. of ICDE97
• Manku G.S., Rajagopalan S., Lindsay B., "Approximate Medians and other Quantiles in One Pass and with Limited Memory" . Proc of SIGMOD 1998, pp. 426-43