Estimating block selectivities for physical database design

Access path deployment is a critical issue in physical database design. Access paths typically include a clustered index as the primary access path and a set of secondary indexes as auxiliary access paths. To deploy the right access paths requires an effective algorithm and accurate estimation of the parameters used by the algorithm. One parameter central to any index-selection algorithm is the block selectivity of a query. Existing methods for estimating block selectivities are limited by restrictive assumptions. Furthermore, most existing methods produce estimates useful for aiding the selection of secondary indexes only. Little research has been done in the area of estimating block selectivities for supporting the selection of the clustered index. The paper presents a set of methods that do not depend on any specific assumption, produce accurate estimates, and can be used to aid in selecting the clustered index as well as secondary indexes