[prev] 45 [next]

Index Nested Loop Join (cont)

This method requires:
  • one scan of R relation (bR)
    • only one buffer needed, since we use R tuple-at-a-time
  • for each tuple in R (rR), one index lookup on S
    • cost depends on type of index and number of results
    • best case is when each R.i matches few S tuples
Cost   =   bR + rR.SelS    (SelS is the cost of performing a select on S).

Typical SelS  =  1-2 (hashing) .. bq (unclustered index)

Trade-off:   rR.SelS  vs  bR.bS,   where   bR ≪ rR and SelS ≪ bS