How much does the following query costs in terms of operations when the attribute is a key or an attribute ?
SELECT Attribute FROM R WHERE Attribute = 50 ORDER BY Attribute
We assume we have R(K,A,B,other) a relation with
- Lr=100 byte
- K, a key in [1;100000]
- A with integer values uniformly distributed in the range (1,1000)
R is stored with heap organization with data unsorted with both respect to K and A, in pages of size Dpag=1024 bytes each.
My attempt :
I know that
SELECT Attribute FROM R WHERE Attribute = 50
Is an equality search. As far as there can be several records with this attribute, with an attribute search it costs Npage(R). Yet with the Key search I've been told to follow the given array (without understanding why...)...
But I don't know what does
ORDER BY induces
Tips from my teacher
1. Attribute search
It should be the same costs for the attribute search as far as
RC = Csearch + Cwrite + Csort + Cread
Yet I merely understand this equation...
2. key search
"we need to estimate the number of bytes to store Erec" said he. where Erec = Nrec(R)/Lr= 100000/100 = 100. (I think there is a mistake here as far as first 100000/100 = 1000 and second it shouldn't have been Lr as the denominator but the number of files that actually have the attribute we are looking for => 100000/1000 = 100)
Furthermore, the size of Erec = 100 x 4 = 400 <1024. We would only need one page to order Erec. (Yet, I don't understand why is it multiplied by 4.)
This question comes more or less from a book written by Dario Colazzo and some others from Pisa University Relational DBMS Internals available in the link.