next up previous
Next: Use of an Index Up: Join Strategies Previous: Block-Oriented Iteration


  1. Suppose neither relation fits in main memory, and both are stored in sorted order on the join attributes. (E.g. both deposit and customer sorted by cname.)
  2. We can then perform a merge-join, computed like this:
  3. In the case where tuples of the relations are stored together physically in their sorted order, this algorithm allows us to compute the join by reading each block exactly once.

Osmar Zaiane
Sun Jul 26 17:45:14 PDT 1998