Home -> Usenet -> comp.databases.theory -> Nested Loops Join

Nested Loops Join

From: <accpactec_at_hotmail.com>
Date: 9 Oct 2006 13:35:34 -0700
Message-ID: <1160426134.776941.46880_at_b28g2000cwb.googlegroups.com> 





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 - 22:35:34 CEST












Original text of this message