Processor scheduling for multiprocessor joins
- 7 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A family of practical algorithms is presented to schedule join execution in a shared-memory multiprocessor environment. The algorithms are based on page connectivity graphs and determine when to read each data page into memory and how to schedule page joins on the available processors. The goal is to overlap page reads with parallel join execution in such a way that both the number of processors and total duration of join processing time are minimized. Upper and lower bounds are derived on the number of processors required to complete join execution in optimal time. A description is given of a general strategy for generating read schedules that it is conjectured can be processed in minimal time (over all read schedules on any number of processors) and a family of practical algorithms utilizing an arbitrary number of lookahead steps to approximate this general strategy.Keywords
This publication has 4 references indexed in Scilit:
- Scheduling of page fetches in join operations using B/sub c/-treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Join indicesACM Transactions on Database Systems, 1987
- Use of graph-theoretic models for optimal relational database accesses to perform joinACM Transactions on Database Systems, 1985
- Parallel algorithms for the execution of relational database operationsACM Transactions on Database Systems, 1983