Efficient Scheduling of Page Access in Join Processing

Simple item page
dc.contributor.authorC Y Chanen_US
dc.contributor.authorB C Ooien_US
dc.date.accessioned2004-10-21T14:28:52Zen_US
dc.date.accessioned2017-01-23T07:00:38Z
dc.date.available2004-10-21T14:28:52Zen_US
dc.date.available2017-01-23T07:00:38Z
dc.date.issued1995-04-01T00:00:00Zen_US
dc.description.abstractThis 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.en_US
dc.format.extent284438 bytesen_US
dc.format.extent333206 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.format.mimetypeapplication/postscripten_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1387en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTRC4/95en_US
dc.titleEfficient Scheduling of Page Access in Join Processingen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
report.ps
Size:
325.4 KB
Format:
Postscript Files
Description:
Download
Thumbnail Image
Name:
report.pdf
Size:
277.77 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.52 KB
Format:
Plain Text
Description:
Download
Collections
Technical Reports