Database algorithm Simple Nested Loop Join

Question

Given Relation:

Sailors (sid: integer, sname: string, rating: integer, age: real)
Reserves (sid: integer, bid: integer, day: dates, rname: string)

Query

SELECT  *
FROM   Reserves R, Sailors S
WHERE  R.sid=S.sid

Assume:

M pages of R, pR tuples per page (i.e., number of tuples of R = M * pR) 
N pages of S, pS tuples per page (i.e., number of tuples of S = N * pS)

Cost is the number of I/Os (ignore the output cost)

Algorithm for the query

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

Cost

Scan of outer  +    for each tuple of outer, scan of inner relation.

Cost  =     M    +     pR * M * N  I/Os

I am confused with the final result for the cost. If we were to scan every tuple in R and then for each r, scan every tuple in S then wouldn't the final cost be R*S = M*pR*N*pS ? (R = M * pR , S = N * pS). I'm not sure why there is an addition symbol. Does I/O only account for pages? and not records?

Renzo · Accepted Answer · 2015-12-01 19:32:48Z

2

You are giving yourself the right answer:

Does I/O only account for pages? and not records?

The cost in these cases is calculated in numbers of disk accesses. An I/O operation transfers an entire page, not a record, from disk to main memory and vice-versa (this is exactly the meaning of a page: the minimum unit of transfer between the two memories).

So, since the Nested Loop algorithm reads the relation R only once, the first term is equal to the number of I/O operations to read it, which is equal to the number of its pages.

answered Dec 1, 2015 at 19:32

Renzo

27.6k5 gold badges54 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sam Over a year ago

If it read only pages, then shouldn't the cost be M*N (where M is the number of Pages for Reserves and N is the number of Pages for Sailors)

Renzo Over a year ago

No, since for each record of R (that is M * pR), the algorithm reads all the pages of S (that is, N). Note that the situation is asymmetric, so that the cost changes if you excange the role of R and S.

Collectives™ on Stack Overflow

Database algorithm Simple Nested Loop Join

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related