How does one estimate the access cost for the below query given that the data is sorted according to a non-key attribute, that the data is not uniformly distributed across all possible values of said attribute and that we must use a linear scan?



Given the following:

  • Total #tuples = 525 employees
  • Block size = 500 bytes
  • Tuple size = 50 bytes
  • #DNO = 20, {1,...,20}, and is not a key attribute

Assuming Uniform

By assuming that the data was uniformly distributed, I've calculated the cost the following way:

The blocking factor will be 10, hence the number of block files will be 53. However, we have to assume that the data is uniformly distributed and we cannot have partial blocks. Therefore each DNO will require 3 blocks. So accessing all records for a given DNO will have a cost of 3, and a probability of accessing a random DNO, $x$ is just 1/20. Therefore, the total access cost is given by

$$ E(C) = \sum_{x=1}^{20} \frac{1}{20} 3x $$

Assuming the below distribution

Here my thoughts are to split the data into 3 main clusters and perform a similar calculation to above, but I'm confused about a couple of things. For example, in cluster 1, each bucket would have probability 20/525 when looking at the whole dataset, but if looking at the cluster only, then each element would of course now have a probability of 20/200. The problem is that when calculating the number of tuples per record I set the total number of tuples to 200 which gives me the required 2 records per tuple for the whole cluster, but would it then be appropriate to use the first probability? If not, would it then be appropriate to use the second probability when adding the costs of the first cluster to the costs of the second cluster? i.e.

$$ E(C_1) = \sum_{x=1}^{20} \frac{20}{525} 2x $$


$$ E(C_1) = \sum_{x=1}^{10} \frac{1}{10} 2x $$

And how would you factor $C_1$ into $C_2$'s calculation?

Attribute Tuples Distribution



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.