Binary Matching Operators (cont.)

• Nested Loops Join

  • Simplest
  • Does not work well for large inputs
  • Several improvement options are mentioned
  • Index nested loops
  • Need a mechanism to keep track of which inner elements made matches

Previous slide

Next slide

Back to first slide

View graphic version

Improvements:

1. Terminate scanning after the 1st match

2. Scan inner input once for each page of outer input

3. Fill all but K pages of memory with outer input, put scanned inner input in the K pages of memory

4. Scan inner input alternatingly forwards and backwards

Index nested loops:

Replace scans with index retrievals

May want to have indices for popular join attributes