• physical arrangement of tuples
  • sorting   (search strategy)
  • hashing   (static, dynamic, n-dimensional)
• additional indexing information
  • index files   (primary, secondary, trees)
  • signatures   (superimposed, disjoint)

Our analyses assume: 1 input buffer available for each relation.

If more buffers are available, most methods benefit.