Nested Loops Join

Hi,
This question is a easy one.

Given:
|R| = pages in R,

pR = tuples/page
|S| = pages in S

pS = tuples/page.

Our Loop is:
foreach tuple r in R do

	foreach tuple s in S do
		if ri = sj  then add <r, s> to result

I am trying to calculate the number of I/Os for this. The book that I am reading this from says that the cost of IO should be calculated as follows: ****(We will ignore output cost.)****

|R| + pR * |R|*|S|

This doesn't make too much sense to me and here is why..

I think the cost should be

The codes says for EVERY tuple in R retieve every tuple in S. So if we're reading one tuple at a time, |R|*pR will give us the total number of tuples in R. Similiarly pS*|S| will give us the total number of tuples in S.

So the total should be

|R|*pR*|S|*pS

If we're going to read R and S as pages into the memory then the cost should be like this.

|R| + |R|*|S|

|R|*|S| indicates the number of S pages need to be read. I am ignoring
the number of tuples per page since the "ri = sj then add <r, s> to result" is done in the memory and therefore does not require an IO. ((ri) is a tuple in the memory.)

Any idea on whether my method of thinking is correct or not?

Thanks in Advance Received on Mon Oct 09 2006 - 15:35:34 CDT