Database access path selection: A two step approach

摘要

In this paper, we develop an efficient two-step approach to database access path selection. In the first step, we use index threshold values to identify those queries for which index lookup is clearly the less expensive access path. For these queries, there is no need to estimate block selectivity, resulting in saving in processing cost. In the second step, we present a measure of clustering effect and empirically relate this measure to block selectivity. This method of estimating block selectivity can be performed much more quickly than the O(km) or O(m) flops required by some of the other approaches and relaxes a previous assumption that clusters are linearly ordered. In addition, its use does not hinge on particular assumptions of data distributions. We test this approach with a corporate file obtained from the COMPUSTAT database. The results of the test indicate that the approach leads to sound access path selections and is superior to the random placement model in estimating block selectivity.