Query optimization in tertiary storage based systems using a generalized storage model

With the growing demand for storage space from storage hungry database applications, designers will have to look at a hierarchical storage based systems. Such a system will consist of primary, secondary and tertiary storage devices. Currently tertiary storage is regarded as being external to the system. In this work we look at the situation where tertiary storage is part of an information system thus creating a data warehouse system where applications are no longer constrained by storage limitations.; In this work we are interested in modeling a complex storage system and the placement of data on it. Then we use the model to estimate the I/O related cost of the joint operation, in a hierarchical storage system environment. We propose a model for a generic storage system. The model can be used in a variety of ways: as a measuring tool to measure the cost of database operations, to measure a systems efficiency, to measure a systems reliability, etc.; as a advising tool that will advise designers on the best arrangement of devices and data placements to suit their needs; as a learning tool that learns from the users and their needs and thus adapts to better serve those needs.; In this work, the model is used to create a hierarchical storage system and measure the cost of several joint algorithms. We consider the nested loop and hybrid hash algorithms. Both these algorithms are modified to improve their performance with respect to I/O operations. We then add more capabilities (or intelligence) to each of the devices and study the gain in terms of the reduction in I/O cost. Finally, we look at methods to place fragments of a relation on the storage system such that the I/O time given a joint algorithm is under the specified acceptable time. We propose three placement algorithms aimed at reducing I/O cost. We also study the problem of placing one relation with respect to another.; We feel that the database and data warehouse community will benefit from this work in the following manner. The proposed model will provide designers the tool to design, analyze and implement an hierarchical storage system. one that integrates tertiary memory systems and conventional information systems to produce a data warehouse system. Using the model, designers will be able to use available devices to create a system that best suits their needs.