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?
SELECT * FROM EMPLOYEE WHERE DNO = X
Context
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 $$
or
$$ E(C_1) = \sum_{x=1}^{10} \frac{1}{10} 2x $$
And how would you factor $C_1$ into $C_2$'s calculation?
