Efficient Scheduling of Page Access in Join Processing
No Thumbnail Available
Date
1995-04-01T00:00:00Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper examines the issue of scheduling page access in join processing. Two related problems are addressed:
<OL>
<LI>the determination of an optimal page access sequence such that the join can be computed without any page reaccesses using the minimum number of buffer pages,and</LI>
<LI>the determination of an optimal page access sequence such that the join can be computed with the minimum number of page reaccesses given a limited number of buffer pages.</LI>
</OL>
The first problem is believed to be NP-hard while the second problem has been shown to be NP-complete. Efficient heuristics for both problems can optimize buffer utilization as well as disk I/O cost. By modeling a page access sequence as a concatenation of segments, we derived two desirable properties of a \PAS, which serve as the basis of our new heuristics for solving both problems.
<BR>
An experimental performance comparison of the new heuristics with existing heuristics show that the new heuristics perform better than existing heuristics for the first problem, and also perform better for the second problem provided that the number of available buffer pages is not much less than the optimal buffer size.