Week 09 Lecture (44)

Index Nested Loop Join

A problem with nested-loop join:

needs repeated scans of entire inner relation S

If there is an index on S, we can avoid such repeated scanning.

Consider Join[R.i=S.j](R,S):

for each tuple r in relation R {
    use index to select tuples
        from S where s.j = r.i
    for each selected tuple s from S {
        add (r,s) to result
}   }