×

System and method for performing I/O-efficient join processing

  • US 6,282,533 B1
  • Filed: 09/30/1998
  • Issued: 08/28/2001
  • Est. Priority Date: 09/30/1998
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for performing a d-dimensional join between a first set and a second set of hyper-rectangles, at least one of said first set and said second set being stored in secondary memory, comprising the steps of:

  • dividing the d-dimensional join into k d-dimensional join strips and a (d−

    1)-and-a-half dimensional join;

    classifying hyper-rectangles within said strips as large if they are contained in more than a single strip and small if they are contained within said single strip;

    partitioning each large hyper-rectangle into one center piece and two end pieces;

    recursively computing intersections between a first type from said first set and a second type from said second set, wherein each of said first type and said second type is one selected from a group consisting of said end pieces and said small hyper-rectangles;

    computing intersections between center pieces from said first set and second set and with said small hyper-rectangles from said first set and said second set by partitioning said (d−

    1)-and-a-half dimensional join along d−

    1 dimensions and by processing through said steps of dividing, classifying, partitioning and recursively computing intersections for each of said d-2 dimensions; and

    reporting to the secondary memory all computed intersections.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×