Conditional selectivity for statistics on query expressions
Authors:
Open Access
- 13 June 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 311-322
Abstract
Cardinality estimation during query optimization relies on simplifying assumptions that usually do not hold in practice. To diminish the impact of inaccurate estimates during optimization, statistics on query expressions (SITs) have been previously proposed. These statistics help directly model the distribution of tuples on query sub-plans. Past work in statistics on query expressions has exploited view matching technology to harness their benefits. In this paper we argue against such an approach as it overlooks significant opportunities for improvement in cardinality estimations. We then introduce a framework to reason with SITs based on the notion of conditional selectivity. We present a dynamic programming algorithm to efficiently find the most accurate selectivity estimation for given queries, and discuss how such an approach can be incorporated into existing optimizers with a small number of changes. Finally, we demonstrate experimentally that our technique results in superior cardinality estimations than previous approaches with very little overhead.Keywords
This publication has 15 references indexed in Scilit:
- Optimizing queries using materialized views2001
- STHoles2001
- Independence is good2001
- Optimal aggregation algorithms for middleware2001
- Selectivity estimation using probabilistic models2001
- Join synopses for approximate query answering1999
- Self-tuning histograms1999
- Fuzzy queries in multimedia database systems1998
- Accurate estimation of the number of tuples satisfying a condition1984
- Access path selection in a relational database management system1979