3

I have been learning Query Optimization from "Fundamentals of Database Systems by Elmasri and Navathe (6th edition)" and I am having trouble understanding on how some variables are being derived in the equation.

Textbook mentions a line where :

The number of levels (x) of each multilevel index (primary, secondary, or
clustering) is needed for cost functions that estimate the number of block 
accesses that occur during query execution. In some cost functions the  
number of first-level index blocks (bI1) is needed.

and the formula given for Secondary Index(B+ trees) is :

 Cost(C) = x+s;(on equality, =) and 
 Cost(C) = x + (bI1/2) + r/2 
 (for conditions <,<=,>,>=)
 where r = number of records (tuples)

My first question is, What does x actually refer to?

Because if you have a block containing the information which is available for identifying the root node of a secondary Index (B+ trees) in this case..why is there a need to take into number of levels as number of levels on first-level index is understandable as on might have to find all possible first level internal nodes to identify the position of the leaf node containing the data pointer.

My Second Question is regarding the join operation formulas, where

A and B are domain-compatible attributes of R and S, respectively. Assume
that R has bR blocks and that S has bS blocks:

■ J1—Nested-loop join. Suppose that we use R for the outer loop; then we get
the following cost function to estimate the number of block accesses for   
this
method, assuming three memory buffers.We assume that the blocking factor
for the resulting file is bfrRS and that the join selectivity is known:

        CJ1 = bR + (bR * bS) + (( js * |R| * |S|)/bfrRS)
The last part of the formula is the cost of writing the resulting file to disk.
This cost formula can be modified to take into account different numbers of
memory buffers, as presented in Section 19.3.2. If nB main memory buffers
are available to perform the join, the cost formula becomes:

     CJ1 = bR + ( ⎡bR/(nB – 2)⎤ * bS) + ((js * |R| * |S|)/bfrRS)


■ J2—Single-loop join (using an access structure to retrieve the matching
record(s)). If an index exists for the join attribute B of S with index levels xB,
we can retrieve each record s in R and then use the index to retrieve all the
matching records t from S that satisfy t[B] = s[A]. The cost depends on the
type of index. For a secondary index where sB is the selection cardinality for
the join attribute B of S,21 we get:

     CJ2a = bR + (|R| * (xB + 1 + sB)) + (( js * |R| * |S|)/bfrRS)

For a clustering index where sB is the selection cardinality of B, we get

     CJ2b = bR + (|R| * (xB + (sB/bfrB))) + (( js * |R| * |S|)/bfrRS)

Taking the above formulas and the assumptions,

On basis of my understanding, If there are three memory buffers, why is the initial term br in the nested join loop being given when each time the comparison is being made with a tuple in the second buffer .... why read all the br values again for the join operation being performed with relation s which is what happens to be going on in the second memory buffer mentioned in the textbook?

lets suppose if there are six blocks of relation R and there are five memory buffers, wont it be better to take the tuples of R from the first buffer, perform the join operation in the second with tuples of S and save the resulting tuples in the third memory buffer in case of Single- loop Join ? because the cost would be then increased because the buffer cannot accommodate the whole relation itself and you might need to load unnecessary data multiple times?

Pardon me if my basic understanding of things is flawed to begin with.

Your Answer

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

Browse other questions tagged or ask your own question.