MEMS storage devices are new non-volatile secondary storages that have outstanding advantages over magnetic disks. MEMS storage devices, however, are much different from magnetic disks in the structure and access characteristics in the following ways. They have thousands of heads called probe tips and provide the following two major access facilities: (1) flexibility: freely selecting a set of probe tips for accessing data, (2) parallelism: simultaneously reading and writing data with the set of probe tips selected. Due to these characteristics, it is nontrivial to find data placements that fully utilize the capability of MEMS storage devices. In this paper, we propose a simple logical model called the Region-Sector (RS) model that abstracts major characteristics affecting data retrieval performance, such as flexibility and parallelism, from the physical MEMS storage model. We also suggest heuristic data placement strategies based on the RS model. To show the usability of the RS model, we derive new data placements for relational data and two-dimensional spatial data by using these strategies. Experimental results show that the proposed data placements improve the data retrieval performance by up to 4.7times for relational data and by up to 18.7times for two-dimensional spatial data of approximately 320Mbytes compared with those of existing data placements. Further, these improvements are expected to be more marked as the database size grows.
, @cite_0 @cite_2 proposed methods for placing data on the MEMS storage device based on data access patterns of applications. , @cite_2 places relational data on the MEMS storage device such that projection queries are performed efficiently. , @cite_0 places two-dimensional spatial data such that spatial range queries are performed efficiently. These data placements identify that data access patterns of such applications are inherently two-dimensional, and then, place data so as to take advantage of parallelism and flexibility of the MEMS storage device. We explain each data placement in more detail for comparing them with our methods in Section ,6.
@cite_0 @cite_2
2086545850 2072618081
Due to the large difference between seek time and transfer time in current disk technology, it is advantageous to perform large I O using a single sequential access rather than multiple small random I O accesses. However, prior optimal cost and data placement approaches for processing range queries over two-dimensional datasets do not consider this property. In particular, these techniques do not consider the issue of sequential data placement when multiple I O blocks need to be retrieved from a single device. In this paper, we reevaluate the optimal cost of range queries by declustering two-dimensional datasets over multiple devices, and prove that, in general, it is impossible to achieve the new optimal cost. This is because disks cannot facilitate two-dimensional sequential access which is required by the new optimal cost. Then we revisit the existing data allocation schemes under the new optimal cost, and show that none of them can achieve the new optimal cost. Fortunately, MEMS-based storage is being developed to reduce I O cost. We first show that the two-dimensional sequential access requirement can not be satisfied by simply modeling MEMS-based storage as conventional disks. Then we propose a new placement scheme that exploits the physical properties of MEMS-based storage to solve this problem. Our theoretical analysis and experimental results show that the new scheme achieves almost optimal I O costs. Due to recent advances in semiconductor manufacturing, the gap between main memory and disks is constantly increasing. This leads to a significant performance bottleneck for Relational Database Management Systems. Recent advances in nanotechnology have led to the invention of MicroElectroMechanical Systems (MEMS) based storage technology to replace disks. In this paper, we exploit the physical characteristics of MEMS-based storage devices to develop a placement scheme for relational data that enables retrieval in both row-wise and column-wise manner. We develop algorithms for different relational operations based on this data layout. Our experimental results and analysis demonstrate that this data layout not only improves I O utilization, but results in better cache performance for a variety of different relational operations.