1

How can I calculate the cost of the query, if there is a between condition?

Select *
From A 
Where A.id between 10 and 50

If Index not exists and there is only one condition:

  1. Search in B+ tree to find the first block that meets the condition (Binary search). Cost: log_2(b_A).
  2. Search in the following blocks that meets the condition. (Suppose half of the blocks meet the condition). Cost: b_A/2.

    • If the condition was Where A.id > 10, then the cost would be: log_2(b_A) + b_A/2

    • If the condition was Where A.id < 50, then the cost would be: log_2(b_A) + b_A/2

What is the correct way to calculate cost of 2 ranges of the same field?

1

If there is no index for A.id column, then database engine perform full table scan. So O(N) operations are performed.

If there is a B+tree index for A.id then database optimizer may choose it, if it is better than full table scan.

In a B+tree all the leaf nodes/records are linked; a node may have more than 2 elements. Because all the records/leaves are linked in order (asc|desc), to get matching value for given range, it is sufficient find the min record location then we can iterate sequentially till max value.

For a b-order B+ tree, finding a record requires O(logb⁡(N)). If there is a m matching elements for (10,50 ) range, if we assume DB engine follow the above said method, then it requires O(logb⁡(N))+O(m) operations to find matching rows.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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