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.