Framework for scheduling partition-based joins

Abstract

This paper presents a framework for scheduling partition-based joins. Partition-based joins are commonly used in databases, be it relation-al,temporal or spatial databases. Under a partition-based algorithm,the data are organized into partitions. During the join process, a partition in one relation only needs to join with some, but not all, partitions of the other relation. Depending on the orders in which partitions are processed, the number of I/Os incurred varies. We propose a three-phase scheduling framework to minimize the number I/Os incurred. From the framework, a large number of scheduling strategies can be derived. We also demonstrate the effectiveness of the framework on an application - temporal intersection join in temporal databases.