Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The join relational operation is one of the most expensive among database operations. In this study, we consider the problem of scheduling page accesses in join processing. This raises two interesting problems: 1) determining a page access sequence that uses the minimum number of buffer pages without any page reaccesses, and 2) determining a page access sequence that minimizes the number of page reaccesses for a given buffer size. We use a graph model to represent the pages from the relations that contain tuples to be joined, and present new heuristics for the two problems based on the sort-merge join and the simple TID algorithm. Our experimental results show that the new heuristics perform well.

REFERENCES

• 1: M. W. Blasgen and K. P. Eswaran. Storage and access in relational data bases. IBM Systems Journal, vol. 16, no. 4, pp. 363-377, 1977.
• 2: C. Y. Chan and B. C. Ooi. Efficient scheduling of page access in join processing. Unpublished manuscript, http://www.comp.nus.edu.sg/-ooibc/papers/j oin.ps, Apr. 1995.
• 3: Chee Yong Chan , Beng Chin Ooi, Efficient Scheduling of Page Access in Index-Based Join Processing, IEEE Transactions on Knowledge and Data Engineering, v.9 n.6, p.1005-1011, November 1997 [doi>10.1109/69.649322]
• 4: F. Fotouhi , S. Pramanik, Optimal Secondary Storage Access Sequence for Performing Relational Join, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.318-328, September 1989 [doi>10.1109/69.87978]
• 5: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 6: A. Lim and W. C. Oon. Page access sequencing in join processing. To be published.
• 7: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 8: Edward R. Omiecinski, Heuristics for Join Processing Using Nonclustered Indexes, IEEE Transactions on Software Engineering, v.15 n.1, p.18-25, January 1989 [doi>10.1109/32.21722]
• 9: Sakti Pramanik , David Ittner, Use of graph-theoretic models for optimal relational database accesses to perform join, ACM Transactions on Database Systems (TODS), v.10 n.1, p.57-74, March 1985 [doi>10.1145/3148.3325]
• 10: R. Ramakrishnan. Database Management Systems. WCB/McGraw-HiI1, 1997.
• 11: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 12: Mechthild Stoer , Frank Wagner, A simple min-cut algorithm, Journal of the ACM (JACM), v.44 n.4, p.585-591, July 1997 [doi>10.1145/263867.263872]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory

Keywords:
graph models, heuristics, join processing, page access scheduling