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

(D) join selection factor between $r(R)$ and $s(S)$ is less than 0.5.

it does not matter if 10 x 20 or 20 x 10 answer is still the same. If the jon selection factor is less that means we will fewer record in the result relation