Re: Nested Loops Join

accpactec_at_hotmail.com wrote:
> 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

It seems you are forgetting that the system checks if a tuple that you want to retrieve is still in the buffer, in which case there is no I/O.

• Jan Hidders