How much does the following query costs in terms of operations when the attribute is a key or an attribute ?

SELECT Attribute
    WHERE Attribute = 50
      ORDER BY Attribute

We assume we have R(K,A,B,other) a relation with

  • Nrec(R)=100000,
  • 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.

I have an array giving me the following costs for heap organizations : enter image description here

My attempt :

I know that

SELECT Attribute
    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.

1 Answer 1


Not sure what your question is exactly, as the symbols you use seem a bit confusing, but the general idea I think is this:

Firstly, you have to visit all records in the heap to find those where Attribute = 50, so that would be, in pages, 100000 records times 100 bytes each divided by 1024 (page size) rounded up, which comes to 9766. This determines your I/O cost, which will be all you need to know for the query without ordering -- matching records can be returned to the client immediately.

The rest is impossible to evaluate without knowing the selectivity of your search criteria, that is, how many records match it. For the query with ORDER BY ultimately you will need to 1) store all matching records in memory, determining your memory cost, and 2) sort them, determining your CPU cost.


With Attribute uniformly distributed across 1000 distinct values we can estimate that the equality predicate will fetch on average 100000/1000 = 100 rows, each 100 bytes long, which will require 10000 bytes to store. CPU cost to sort them will be proportional to log₂(100 rows).

Note that some smarty-pants optimizer might notice that there's no need to order the result set by the value that's on the right hand side of the sole equality predicate and ignore the ORDER BY clause altogether.

  • Why would CPU cost to sort them will be proportional to log₂(100 rows), where does it comes from ? And why isn't it log<sub>10</sub>(10000 rows)=4 ? Which would explain why the size of the output page with the rows is 100*4 = 400 ? Commented Mar 4, 2017 at 16:12
  • Because you're sorting only the matching rows, no? And you're sorting rows not bytes. While log₂(n) might be a bit optimistic, we don't really know the sort algorithm used anyway.
    – mustaccio
    Commented Mar 4, 2017 at 16:26
  • Okay, so I don't understand why my teacher concluded that the size of Erec = 100 x 4 = 400 <1024. We would only need one page to order Erec. Commented Mar 4, 2017 at 16:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.