SYSTEM AND METHOD FOR PERFORMING I/O-EFFICIENT JOIN PROCESSING

I/O-efficient methods and apparatus are provided for the d-dimensional join problem in one, two, and three dimensions, and are also generalized for arbitrary higher dimensions. Let N be the total number of rectangles in the two sets to be joined, M the total amount of memory available, B the disk block size, and T the total number of pairs in the output of the join. Define n=N/B, m=M/B, and t=T/B. For one and two dimensions, I/O-optimal join methods are provided that run in O(nlog.sub.m n+t) I/O operations and have utility to temporal and spatial database systems. For dimensions d.gtoreq.3, methods are provided that run in O(nlog.sub.m.sup.(d-1) n+t) I/O operations, which is within a log.sub.m.sup.(d-2) n factor of the currently known lower bounds.