[prev] 39 [next]

Block Nested Loop Join (cont)

Best-case scenario: bR ≤ N-2
  • read bR pages of relation R into buffers
  • while R is buffered, read bS pages of S
Cost   =   bR + bS

Typical-case scenario: bR > N-2

  • read ceil(bR/N-2) chunks of pages from R
  • for each chunk, read bS pages of S

Cost   =   bR + bS . ceil(bR/N-2)

Note: requires rR.rS checks of the join condition