Abstract
The rate of increase in hard disk storage capacity continues to outpace the rate of decrease in hard disk seek time. This trend implies that the value of a seek is increasing exponentially relative to the value of storage.
With this trend in mind, we introduce the partitioned exponential file (PE file) which is a generic storage manager that can be customized for many different types of data (e.g., numerical, spatial, or temporal). The PE file is intended for use in environments with intense update loads and concurrent, analytic queries. Such an environment may be found, for example, in long-running scientific applications which can produce petabytes of data. For example, the proposed Large Synoptic Survey Telescope [36] will produce 50–100 petabytes of observational, scientific data over its multi-year lifetime. This database will never be taken off-line, so bursty update loads of tens of terabytes per day must be handled concurrently with data analysis. In the PE file, data are organized as a series of on-disk sorts with a careful, global organization. Because the PE file relies heavily on sequential I/O, only a fraction of a disk seek is required for a typical record insertion or retrieval.
In addition to describing the PE file, we also detail a set of benchmarking experiments for T1SM, which is a PE file customized for use with multi-attribute data records ordered on a single numerical attribute. In our benchmarking, we implement and test many competing data organizations that can be used to index and store such data, such as the B+-Tree, the LSM-Tree, the Buffer Tree, the Stepped Merge Method, and the Y-Tree. As expected, no organization is the best over all benchmarks, but our experiments show that T1SM is the best choice in many situations, suggesting that it is the best overall. Specifically, T1SM performs exceptionally well in the case of a heavy query workload that must be handled concurrently with an intense insertion stream. Our experiments show that T1SM (and its close cousin, the T2SM storage manager for spatial data) can handle very heavy mixed workloads of this type, and still maintain acceptably small query latencies.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Communications of the ACM 31, 1116–1127 (1988)
Agarwal, P.K., Arge, L., Procopiuc, O., Vitter, J.S.: A framework for index bulk loading and dynamization. In: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001) pp. 115–127. Crete, Greece (2001)
Arge, L.: The buffer tree: A new technique for optimal I/O-algorithms (extended abstract). In: Algorithms and Data Structures, 4th International Workshop (WADS 1995) pp. 334–345. Kingston, Ontario, Canada (1995)
Arge, L., Hinrichs, K., Vahrenhold, J., Vitter, J.S.: Efficient bulk operations on dynamic R-trees. Algorithm Engineering and Experimentation, International Workshop (ALE-NEX 1999), Baltimore, MD, USA. January 15–16, pp. 328–348 (1999)
Bentley, J.L.: Decomposable searching problems. Information Processing Letters 8(5), 244–251 (1979)
Bercken, Jochen Van den, Seeger, B., Widmayer, P.: A generic approach to bulk loading multidimensional index structures. In: Proceedings of 23rd International Conference on Very Large Data Bases (VLDB 1997) pp. 406–415. Athens, Greece, (1997)
Chen, P.M., Lee, E.L., Gibson, G.A., Katz, R.H., Patterson, D.A.: RAID: High-performance, reliable secondary storage. ACM Computing Surveys 26(2), 145–185 (1994)
Comer, D.: The ubiquitous B-Tree. ACM Computing Surveys 11(2), 121–137 (1979)
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms, MIT Press, Massachusetts (1992)
Fagin, R., Nievergelt, J., Pippenger, N., Strong, H.R.: Extendible hashing—A fast access method for dynamic files. ACM Transactions on Database Systems 4(3), 315–344 (1979)
Garcia, Y.J., Lopez, M.A., Leutenegger, S.T.: On optimal node splitting for R-trees. In: Proceedings of the 24th International Conference on Very Large Data Bases (VLDB 1998) pp. 334–344. New York City, New York, USA (1998)
Gray, J., Shenoy, P.J.: Rules of thumb in data engineering. In: Proceedings of the 16th International Conference on Data Engineering (ICDE 2000) pp. 3–12. vol. 3 San Diego, CA, USA.
Growchowski, E.G.: Emerging Trends in Data Storage on Magnetic Hard Disk Drives. Datatech (1998)
Guttman, A.: R-Trees: A dynamic index structure for spatial searching. In: Proceedings of 1984 SIGMOD Conference (SIGMOD 1984) pp. 47–57. Boston, Massachusetts (1984)
Hellerstein, J.M., Naughton, J.F., Pfeffer, A.: Generalized search trees for database systems. In: Proceedings of 21th International Conference on Very Large Data Bases (VLDB'95) pp. 562–573, Zurich, Switzerland (1995)
Jagadish, H.V., Narayan, P.P.S., Seshadri, S., Sudarshan, S., Kanneganti, R.: Incremental organization for data recording and warehousing. In: Proceedings of 23rd International Conference on Very Large Data Bases (VLDB 1997) pp. 16–25. Athens, Greece (1997)
Jermaine, C., Datta, A., Omiecinski, E.: A novel index supporting high volume data warehouse insertion. In: Proceedings of 25th International Conference on Very Large Data Bases (VLDB 1999) pp. 235–246. Edinburgh, Scotland, UK (1999)
Jermaine, C., Omiecinski, E., Yee, W.G.: Maintaining a Large Spatial Index with T2SM. In: Proceedings of the Ninth ACM International Symposium on Advances in Geographic Information Systems (ACM-GIS 2001). Atlanta, GA, USA. (2001)
Kamel, I., Faloutss, C.: Hilbert R-tree: An improved R-tree using fractals. In: Proceedings of the 20th International Conference on Very Large Data Bases pp. 500–509. Santiago de Chile, Chile (VLDB 1994) (1994)
Knuth, D.E.: The art of computer programming, Vol. III: Sorting and Searching. Addison-Wesley, Reading, MA (1973)
Leutenegger, S.T., Edgington, J.M., Lopez, M.A.: STR: A simple and efficient algorithm for R-tree packing. In: Proceedings of the Thirteenth International Conference on Data Engineering (ICDE 1997) pp. 497–506. Birmingham, UK (1997)
Litwin, W., Hashing, L.: A new tool for file and table addressing. In: Proceedings of the Sixth International Conference on Very Large Data Bases pp. 212–223. Montreal, Quebec, Canada (VLDB 1980) (1980)
Lomet, D.B.: a simple bounded disorder file organization with good performance. ACM Transactions on Database Systems 13(4), 525–551 (1988)
Lomet, D., Salzberg, B.: Access methods for multiversion data. In: Proceedings of the 1989 ACM SIGMOD Conference on the Management of Data (SIGMOD 1989) pp. 315–323. Portland, Oregon, (1989)
Muth, P., O'Neil, P.E., Pick, A., Weikum, G.: Design, implementation, and performance of the lham log-structured history data access method. In: Proceedings of 24rd International Conference on Very Large Data Bases (VLDB 1998) pp. 452–463. New York City, New York, USA (1998)
Neefe, J.M., Roselli, D.S., Costello, A.M., Wang, R.Y., Anderson, T.E.: Improving the performance of log-structured file systems with adaptive methods. In: Proceedings of the Sixteenth ACM Symposium on Operating System Principles (SOSP 1997) pp. 238–251. St Malo, France (1997)
O'Neil, J.E., O'Neil, P.E., Weikum, G.: The LRU-K page replacement algorithm for database disk buffering. In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD 1993) pp. 297–306. Washington, DC (1993)
O'Neil, P.E.: The SB-tree: An index-sequential structure for high-performance sequential access. Acta Informatica 29(3), 241–265 (1992)
O'Neil, P.E., Cheng, E., Gawlick, D., O'Neil, E.J.: The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33(4), 351–385 (1996)
Overmars, M.H.: The design of dynamic data structures. Springer-Verlag, LNCS p. 156 (1983)
Park, J.S., Sridhar, V.: Probabilistic model and optimal reorganization of B+-Tree with physical clustering. IEEE Transactions on Knowledge and Data Engineering 9(5), 826–832 (1997)
Pollari-Malmi, K., Soisalon-Soininen, E., Ylönen, T.: Concurrency control in B-Trees with batch updates. IEEE Transactions on Knowledge and Data Engineering 8(6), 975–984 (1996)
Rosenblum, M., Ousterhout, J.K.: The design and Implementation of a log-structured file system. ACM Transactions on Computer Systems 10(1), 26–52 (1992)
Seeger, B., Kriegel, H.-P.: The Buddy-Tree: an efficient and robust access method for spatial data base systems. In: Proceedings of the 16th International Conference on Very Large Data Bases (VLDB 1990) pp. 590–601. Brisbane, Queensland, Australia (1990)
Tao, Y., Papadias, D.: Adaptive Index Structures. In: Proceedings of 28th International Conference on Very Large Data Bases (VLDB 2002) pp. 418–429. Hong Kong, China (2002)
Tyson, A., The LSST Collaboration: Large synoptic survey telescope: Overview. In: Proceeedings of SPIE; International Society of Optical Engineering 4836, pp. 10–20 (2002)
Zou, C., Salzberg, B.: On-line reorganization of sparsely-populated B+trees. In: Proceedings of the 1996 ACM S1GMOD International Conference on Management of Data (SIGMOD 1996) pp. 115–124. Montreal, Quebec, Canada (1996)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jermaine, C., Omiecinski, E. & Yee, W.G. The partitioned exponential file for database storage management. The VLDB Journal 16, 417–437 (2007). https://doi.org/10.1007/s00778-005-0171-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-005-0171-7