[prev] 9 [next]

Block Nested Loop Join (cont)

Best-case scenario: bR ≤ N-2
  • read bR pages of relation R into buffers
  • while whole 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: always requires rR.rS checks of the join condition