GATE CSE 2014 | Set 2 | Question: 30

Question

Consider a join (relation algebra) between relations $r(R)$ and $s(S)$ using the nested loop method. There are $3$ buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming $\text{size}(r(R))<\text{size}(s(S)),$ the join will have fewer number of disk block accesses if

• A. relation $r(R)$ is in the outer loop.
• B. relation $s(S)$ is in the outer loop.
• C. join selection factor between $r(R)$ and $s(S)$ is more than $0.5$.
• D. join selection factor between $r(R)$ and $s(S)$ is less than $0.5$.

Comments

@ayushsomani

The total number of seeks will be ($b_r+n_r$) - Wikipedia Link Because -

Lets assume we have two memory blocks available in the main memory, now seek time is the time taken to move the read/write head of the disk to the position from where a block is to be read and written to the main memory from the disk.

Now all the blocks of a relation are contiguously stored in the disk so if you seek to a certain block of a relation, then you don't need further seeks to access the subsequent blocks as all are contiguous.

Coming to nested loop join, For every tuple in R all the tuples of S has to be scanned.

So as said earlier we have two blocks(B1,B2 (Suppose)) available in main memory, then first seek to a block of R and transfer it to B1.So number of seeks = 1

Now for the first tuple of R in B1 seek to a block of S and bring the block to B2. number of seeks = 1+1=2.Then compare the $1^{st}$ tuple of R with the first tuple of S. 

Next we have to compare $1^{st}$ tuple of R with second tuple of S, so transfer the same block again (assuming the second tuple of S is in that block only) in B2 (This is the disadvantage of nested loop join.Check Block Nested Loop Join) .But now no more seek is required, in-fact for comparing the $1^{st}$ tuple of R with all the other tuples of S , we don't need anymore seeks as all blocks are contiguous and can be accessed directly.

After we are done comparing all records of S to the first record of R .We have to compare second record of R with all the records of S .No seek needed as 2nd tuple of R already present in B1.But now the read/write head of disk is at last block of S,hence a seek is needed to move it to the first block of S. Thus number of seeks=2+1=3.

Thus we can see we need a seek for every tuple of R and we also need a seek if we have to access a block of R, like here if we are done comparing all the records of R in B1 , a seek is needed to move the read/write head to next block of R as now it is at the last block of S.  

Therefore total no. of seeks needed= $n_r+b_r$

---

yes these are part of query optimisation

and yes, they are in syllabus

optimisations in DBMS are as important as

Reducing time complexity in Algorithms

---

What does "Block Access" refer to?

"Block transfer" or "Block seek"?

If I assume "Block transfer", then they should give :

     1) number of records (for both $r$ and $s$)

     2) number of blocks (for both $r$ and $s$)

As the answer changes depending on values taken.

 

If I assume "Block seek", then the answer is "Option A" without a doubt.

 

Note : If r is taken for outer loop then :

1) Number of block transfers = $(n_r ×b_s) + b_r$

2) Number of seeks = $n_r + b_r$

Also, I am pretty sure, this question was framed using "Database System Concepts 7e - Chapter 15.5.1" by Abraham, Korth.

Or more precisely, 6th edition - Chapter 12.5.1 (same example in both editions)

Answer 1

In joining A and B using nested loop method, with A in outer loop two factors are involved.

1. No. of  blocks containing all rows in A should be fetched.
2. No. of rows of A times no. of blocks containing all rows of B.

(in worst case all rows of B are matched with all rows of A).

In above ques, $|R|<|S|$

(i) will be less when number of rows in outer table is less, since less no. of rows will take less no. of blocks

(ii) if we keep $R$ in outer loop, no. of rows in $R$ are less and no. of blocks in $S$ are more

If we keep $S$ in outer loop, no of rows in $S$ are more and no. of blocks in $R$ are less.

In (ii) block accesses will be multiplication and will come same in both cases.

So, (i) will determine no of block accesses

So, answer is A.

Comments

This is true for Block nested loop join. But I don't think this is always true for Nested loop join.
Consider the following example -

If we assume Block transfer time is $1$ ms & Seek time is $30$ ms on an avg, then in the above example, smaller relation in outer loop takes more time.

---

For understanding this Believe you will not find better source than this one,

Carnegie Mellon University

For Nested Loop Join : M(disk block access for outer block) + m(no. of tuples in outer block)*N(number of blocks in inner Loop)

Have a Look

Also Notice the fact that there are 3 buffers given , so infact if it was not mentioned that its a natural join, then we could have done a block nested join which will take even less time.

@ਜਗਮੀ,  @KartikGawande @Chhotu, in this lecture professor says "We want the outer loop to be one with smaller number of pages, and not the one with smaller number of tuples" i dont understand the meaning but just thought it would be nice to put it.

 

---

Is this in gate syllabus 2027

Answer 2

We just have to think which table would be in outer loop.
To minimize block accesses, we have to put that table outside having less records coz for each outer record one block access inside will be required

so answer is A

https://gateoverflow.in/3847/gate2005-it-82a

 

Answer 3

Nested loop join Algo: https://en.wikipedia.org/wiki/Nested_loop_join

No. of block transfers, N(B) = $n_r*b_s+b_r$ ; when R is in outer loop and S is in inner loop

Where, $n_r$ are number of tuples in relation R.

$b_s$ and $b_r$ are number of blocks in relation S and R respectively.

size(r(R))<size(s(S)) blocks occupied by R are less ($b_r<b_s$). Also, ($n_r<n_s$). As, less no of blocks acquire less no. of rows. 

For minimizing N(B), product term must be minimum and it will be minimum when R is in the outer loop.

For Example: let $b_r=10 , b_s=20; n_r=50, n_s=100$ since size(r(R))<size(s(S))

1. when R is in the Outer loop: N(B) = $n_r*b_s+b_r$ = 50*20+10 = 1010.

2. when S is in the outer loop: N(B) = $n_s*b_r+b_s$ = 100*10+20 = 1020.

So, relation R should be in outer loop.

Option(A).

Answer 4

for each tuple r in R:
    for each tuple s in S:
        if r.a = s.b:
            output (r, s)
this is nested loop method and

let assume r is 5 disk blocks and s is 10 disk blocks

if r is outer relation then for each block access the inner block should be accessed i.e r*s for inner loop and r for outer relation which is r+r*s which is 5+5*10=55

similarly if we swap then the block accesses becomes 10+10*5=60

so r(R) is at outer loop

OPTION A IS THE RIGHT ANSWER

i hope this is helpful for you

Comments

Great Explanation !!

Answer 5

The answer is option $\left ( A\right )$

But there is a misconception in the explanations given so far which I am rectifying here.

I take the example given in Database System Concepts, 5th Edition, Silberschatz Et.al

Number of records of customer: $n_{customer_{}} = 10,000$

Number of blocks of customer: $b_{customer_{}} = 400$ 

Number of records of depositor: $n_{depositor_{}} = 5,000 $

Number of blocks of depositor: $b_{depositor_{}} = 100$ 

Consider the Formula for number of Block Transfer $\left ( n_{r}\times b_{s} \right )+b_{r}$ , Where $r$ is outer relation and $s$ is the inner relation.

Now consider $r\Rightarrow depositor$ and $s\Rightarrow customer$ (That is $depositor$ is the smaller and considered as outer relation)

By substituting values $\left ( 5000\times 400 \right )+100 = 20,00,100$

Now consider $r\Rightarrow customer$ and $s\Rightarrow depositor$ (That is $customer$ is the larger and considered as outer relation)

By substituting values $\left ( 10000\times 100 \right )+400 = 10,00,400$

So by observing this example, it is obvious that even if we consider the outer table to be smaller, the number of block transfer seems to be higher than considering the outer table to be larger.

But if you observe the question carefully, they are asking about Block Access (in particular Block Seek) rather than asking Block Transfer.

So the Number of Block Seek is $n_{r}+b_{r}$ and this is minimized only when outer relation $r$ is smaller.

Form the above example 

$r\Rightarrow depositor :$ $n_{r}+b_{r} = 5000+100 = 5,100$

$r\Rightarrow customer :$ $n_{r}+b_{r} = 10000+400 = 10,400$

$\therefore$ Option $\left ( A\right )$

 

Answer 6

The join between r(R) and s(S) which is using nested loop will be as follows,
For each tuple r in R do
    For each tuple s in S do
        If r and s satisfy the join condition then output the tuple 

The above algorithm involves (nr*bs+br ) block transfer and (nr+br ) seeks.
where,
br → no. of blocks in R
bs → no. of blocks in S
nr → no. of tuples in R
To have less block accesses in nr should be less and in question it is given that size(r(R)) < size(s(S)).
To have fewer no. of disk block accesses the relation r(R) should be in outer loop.