Re: Nested Loops Join

Jan Hidders wrote:
> 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

The cost formul for NL is:

Cost = Cost(Access outer table) + Cardinality(Outer table)*Cost(access inner table)

In OP terminology:

Cardinality(Outer table) = |R|*pR
Cost(access inner table) = |S|

In other words you have to scan |S| pages in order to get matching tuple. This is done for every *tuple* in outer set. Received on Tue Oct 10 2006 - 02:02:19 CEST