Index Nested Loop Join

• If we have an index on S that is on the field we are joining on, it can be very fast to look up matches of $r_i$ in S.

$$\begin{array}{rl}\text{for each record }{r}_i\text{ in }R:& \\ \text{for each record }{s}_j\text{ in }S\text{ where }\theta (r_i,s_j)\text{==true}:& \text{yield }<r_i,s_j>\end{array}$$

COST = $[R]+|R|\times \text{(cost to look up matching records in }S)$