Heuristic algorithms for I/O scheduling for efficient retrieval of large objects from tertiary storage

ABSTRACT

Multimedia data service applications of today are to efficiently deal with possibly massive amount of large objects (LOBs). The storage capacity of the traditional disk-based DBMS is certainly limited to support such applications. As such, it is necessary for the DBMS to employ the tertiary storage devices, which perform often with long latency and yet can provide huge amount of storage capacity at the relatively low cost. In this paper, we investigate the tertiary I/O scheduling algorithms for efficient retrieval of the LOBs that are stored in the tertiary storage device with multiple platters. Taking into consideration the performance characteristics of the tertiary storage devices and LOB retrieval, we propose a set of tertiary I/O scheduling algorithms each of which employs different heuristic for scheduling, reducing the latency involved in tertiary I/O for retrieving LOBs. The performance of the proposed algorithms is evaluated through the detailed simulation experiments.

REFERENCES

• 1: Michael J. Carey , Laura M. Haas , Miron Livny, Tapes hold data, too: challenges of tuples on tertiary store, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.413-417, May 25-28, 1993, Washington, D.C., United States
• 2: A. L. Chervenak , D. A. Patterson , R. H. Katz, Storage systems for movies-on-demand video servers, Proceedings of the 14th IEEE Symposium on Mass Storage Systems, p.246, September 11-14, 1995
• 3: Stavros Christodoulakis , Peter Triantafillou , Fenia Zioga, Principles of Optimally Placing Data in Tertiary Storage Libraries, Proceedings of the 23rd International Conference on Very Large Data Bases, p.236-245, August 25-29, 1997
• 4: Scheduling and Data Replication to Improve Tape Jukebox Performance, Proceedings of the 15th International Conference on Data Engineering, p.532, March 23-26, 1999
• 5: Bruce K. Hillyer , Avi Silberschatz, Random I/O scheduling in online tertiary storage systems, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.195-204, June 04-06, 1996, Montreal, Quebec, Canada
• 6: Theodore Johnson , Ethan L. Miller, Performance Measurements of Tertiary Storage Devices, Proceedings of the 24rd International Conference on Very Large Data Bases, p.50-61, August 24-27, 1998
• 7: M. G. Kienzle , A. Dan , D. Sitaram , W. Tetzlaff, Using tertiary storage in video-on-demand servers, Proceedings of the 40th IEEE Computer Society International Conference, p.225, March 05-09, 1995
• 8: J. Kohl, C. Staelin, and M. Stonebraker. Highlight: Using a log-structured file system for tertiary storage management. Proc. Winter USENIX, pages 435-447, 1993.
• 9: Tape-Disk Join Strategies under Disk Contention, Proceedings of the 15th International Conference on Data Engineering, p.552, March 23-26, 1999
• 10: CORPORATE Microsoft Press, Microsoft ODBC 3.0 software development kit and programmer's reference, Microsoft Press, Redmond, WA, 1997
• 11: Jussi Myllymaki , Miron Livny, Disk-tape joins: synchronizing disk and tape access, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.279-290, May 15-19, 1995, Ottawa, Ontario, Canada
• 12: Jussi Myllymaki , Miron Livny, Relational Joins for Data on Tertiary Storage, Proceedings of the Thirteenth International Conference on Data Engineering, p.159-168, April 07-11, 1997
• 13: HweeHwa Pang, Tertiary storage in multimedia systems: staging or direct access?, Multimedia Systems, v.5 n.6, p.386-399, Dec. 1997 [doi>10.1007/s005300050070 ]
• 14: Improving the Access Time Performance of Serpentine Tape Drives, Proceedings of the 15th International Conference on Data Engineering, p.542, March 23-26, 1999
• 15: S. Sarawagi, Database systems for efficient access to tertiary memory, Proceedings of the 14th IEEE Symposium on Mass Storage Systems, p.120, September 11-14, 1995
• 16: Sunita Sarawagi, Query Processing in Tertiary Memory Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.585-596, September 11-15, 1995
• 17: Sunita Sarawagi , Michael Stonebraker, Reordering Query Execution in Tertiary Memory Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.156-167, September 03-06, 1996
• 18: A. Shoshani , L. M. Bernardo , H. Nordberg , D. Rotem , A. Sim, Multidimensional Indexing and Query Coordination for Tertiary Storage Management, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.214, July 28-30, 1999
• 19: Michael Stonebraker, Managing persistent objects in a multi-level store, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.2-11, May 29-31, 1991, Denver, Colorado, United States
• 20: Jie-Bing Yu , David J. DeWitt, Query Pre-Execution and Batching in Paradise: A Two-Pronged Approach to the Efficient Processing of Queries on Tape-Resident Raster Images, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.64-78, August 11-13, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

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

General Terms:
Algorithms, Design, Theory