Abstract.
The decomposition storage model (DSM) vertically partitions all attributes of a table and has excellent I/O behavior when the number of attributes accessed by a query is small. It also has a better cache footprint than the standard storage model (NSM) used by most database systems. However, DSM incurs a high cost in reconstructing the original tuple from its partitions. We first revisit some of the performance problems associated with DSM and suggest a simple indexing strategy and compare different reconstruction algorithms. Then we propose a new mirroring scheme, termed fractured mirrors, using both NSM and DSM models. This scheme combines the best aspects of both models, along with the added benefit of mirroring to better serve an ad hoc query workload. A prototype system has been built using the Shore storage manager, and performance is evaluated using queries from the TPC-H workload.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
1. SybaseIQ White Paper (2001) www.sybase.com
2. TPCH Benchmark Specification (2001) www.tpc.org
3. Agrawal R, Somani A, Xu Y (2001) Storage and querying of e-commerce data. In: Apers PMJ, Atzeni P, Ceri S, Paraboschi S, Ramamohanroa K, Snodgrass RT (eds) Proceedings of the 27th internal conference on very large databases, Rome 11--14 September 2001. Morgan Kaufmann, San Francisco, pp 149--158
4. Ailamaki A, DeWitt DJ, Hill MD, Skounakis M (2001) Weaving relations for cache performance. In: Apers PMJ, Atzeni P, Ceri S, Paraboschi S, Ramamohanroa K, Snodgrass RT (eds) Proceedings of the 27th international conference on very large databases, Rome, 11--14 September 2001. Morgan Kaufmann, San Francisco, pp 169--180
5. Ailamaki A, DeWitt DJ, Hill MD, Wood DA (1999) DBMSs on a modern processor: where does time go? In: Atkinson MP, Orlowska ME, Valduriez P, Zdonik SB, Brodie ML (eds) Proceedings of the 25th international conference on very large databases, Edinburgh, 7--10 September 1999. Morgan Kaufmann, San Francisco, pp 266--277
6. Bitton D, Gray J (1988) Disk shadowing. In: Bancilhon F, DeWitt DJ (eds) Proceedings of the 14th international conference on very large data bases, Los Angeles, 29 August--1 September 1988. Morgan Kaufmann, San Francisco, pp 331--338
7. Blakeley JA, McKenna WJ, Graefe G (1993) Experiences building the open oodb query optimizer. In: Buneman P, Jajodia S (eds) Proceedings of the 1993 ACM SIGMOD international conference on management of data, Washington, DC, 26--28 May 1993. ACM Press, New York, pp 287--296
8. Boncz PA, Wilschut AN, Kersten ML (1998) Flattening an object algebra to provide performance. In: Proceedings of the 14th international conference on data engineering, 23--27 February 1998, Orlando. IEEE Computer Society, New York, pp 568--577
9. Carey MJ, DeWitt DJ, Franklin MJ, Hall NE, McAuliffe ML, Naughton JF, Schuh DT, Solomon MH, Tan CK, Tsatalos OG, White SJ, Zwilling MJ (1994) Shoring up persistent applications. In: Proceedings of the 1994 ACM SIGMOD international conference on management of data, Minneapolis, 24--27 May 1994, pp 383--394
10. Copeland GP, Alexander W, Boughter EE, Keller TW (1988) Data placement in bubba. In: Boral H, Larson P (eds) Proceedings of the 1988 ACM SIGMOD international conference on management of data, Chicago, 1--3 June 1988. ACM Press, New York, pp 99--108
11. Copeland GP, Khoshafian S (1985) A decomposition storage model. In: Navathe SB (ed) Proceedings of the 1985 ACM SIGMOD international conference on management of data, Austin, TX, 28--31 May 1985. ACM Press, New York, pp 268--279
12. Gray J, Graefe G (1997) The 5-minute rule revisited and other storage rules of thumb. ACM Sigmod Record 26(4):63--68
13. Ioannidis YE (1996) Query optimization. ACM Comput Surv 28(1):121--123
14. Keeton K, Patterson DA, He YQ, Raphael RC, Baker WE (1998) Performance characterization of a quad Pentium Pro SMP using OLTP workloads. In: Proceedings of the 25th annual international symposium on computer architecture, Barcelona, 27 June--1 July 1998. ACM/IEEE Computer Society, New York, pp 15--26
15. Khoshafian S, Copeland GP, Jagodis T, Boral H, Valduriez P (1987) A query processing strategy for the decomposed storage model. In: Proceedings of the 3rd international conference on data engineering, 3--5 February 1987, Los Angeles. IEEE Computer Society, New York, pp 636--643
16. Livny M, Khoshafian S, Boral H (1987) Multi-disk management algorithms. In: Proceedings of the 1987 ACM SIGMETRICS conference on measurement and modeling of computer systems, Alberta, Canada, 11--14 May 1987. ACM Press, New York, pp 69--77
17. O'Neil P, Quass D (1997) Improved query performance with variant indexes. In: Proceedings of the 1997 ACM SIGMOD international conference on management of data, Tucson, 13--15 May 1997. ACM Press, New York, pp 38--49
18. Orji CU, Solworth JA (1993) Doubly distorted mirrors. In: Buneman P, Jajodia S (eds) Proceedings of the 1993 ACM SIGMOD international conference on management of data, Washington, DC, 26--28 May 1993. ACM Press, New York, pp 307--316
19. Ramakrishnan R (1997) Database management systems. McGraw-Hill, New York
20. Severance DG, Lohman GM (1976) Differential files: their application to the maintenance of large databases. TODS 1(3):256--267
21. Solworth JA, Orji CU (1990) Write-only disk caches. In: Garcia-Molina H, Jagadish HV (eds) Proceedings of the 1990 ACM SIGMOD international conference on management of data, Atlantic City, 23--25 May 1990. ACM Press, New York, pp 123--132
22. Szalay AS, Kunszt PZ, Thakar A, Gray J, Slutz DR (2000) Designing and mining multi-terabyte astronomy archives: the sloan digital sky survey. In: Chen W, Naughton JF, Bernstein PA (eds) Proceedings of the 2000 ACM SIGMOD international conference on management of data, 16--18 May 2000, Dallas. ACM Press, New York, pp 451--462
23. Titman PJ (1974) An experimental database system using binary relations. In: Proceedings of the IFIP working conference on data base management, Corsica, France, 1--5 April 1974, pp 351--362
24. Todd S (1975) Prtv: an efficient implementation for large relational data bases. In: Proceedings of the international conference on very large data bases, 22--24 September 1975, Framingham, MA. ACM Press, New York, pp 554--556
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 3 September 2002, Accepted: 15 February 2003, Published online: 10 July 2003
Edited by P. Bernstein
Rights and permissions
About this article
Cite this article
Ramamurthy, R., DeWitt, D.J. & Su, Q. A case for fractured mirrors. VLDB 12, 89–101 (2003). https://doi.org/10.1007/s00778-003-0093-1
Issue Date:
DOI: https://doi.org/10.1007/s00778-003-0093-1