Read-optimized databases, in depth

ABSTRACT

Recently, a number of papers have been published showing the benefits of column stores over row stores. However, the research comparing the two in an "apples-to-apples" way has left a number of unresolved questions. In this paper, we first discuss the factors that can affect the relative performance of each paradigm. Then, we choose points within each of the factors to study further. Our study examines five tables with various characteristics and different query workloads in order to obtain a greater understanding and quantification of the relative performance of column stores and row stores. We then add materialized views to the analysis and see how much they can help the performance of row stores. Finally, we examine the performance of hash join operations in column stores and row stores.

REFERENCES

• 1: https://www.cs.hut.fi/Opinnot/T-106.290/K2005/Ohjeet/Zipf.html. Accessed November 8, 2007.
• 2: http://db.lcs.mit.edu/projects/cstore/. Accessed November 8, 2007.
• 3: Daniel Abadi , Samuel Madden , Miguel Ferreira, Integrating compression and execution in column-oriented database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142548]
• 4: Daniel J. Abadi , Samuel R. Madden , Nabil Hachem, Column-stores vs. row-stores: how different are they really?, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376712]
• 5: Abadi, D. J., Myers, D. S., DeWitt, D. J., Madden, S. R. "Materialization Strategies in a Column-Oriented DBMS." In ICDE, 2007.
• 6: Anastassia Ailamaki , David J. Dewitt , Mark D. Hill, Architecture-conscious database systems, The University of Wisconsin - Madison, 2000
• 7: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , Marios Skounakis, Weaving Relations for Cache Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.169-180, September 11-14, 2001
• 8: Boncz, P., Zukowski, M., and Nes, N. "MonetDB/X100: Hyper-Pipelining Query Execution." In CIDR, 2005.
• 9: George P. Copeland , Setrag N. Khoshafian, A decomposition storage model, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.268-279, May 1985, Austin, Texas, United States
• 10: Halverson, A. J., Beckmann, J. L., Naughton, J. F., DeWitt, D. J. "A Comparison of C-Store and Row-Store in a Common Framework." Technical Report, University of Wisconsin-Madison, Department of Computer Sciences, T1666, 2006.
• 11: Richard A. Hankins , Jignesh M. Patel, Data morphing: an adaptive, cache-conscious storage technique, Proceedings of the 29th international conference on Very large data bases, p.417-428, September 09-12, 2003, Berlin, Germany
• 12: Stavros Harizopoulos , Velen Liang , Daniel J. Abadi , Samuel Madden, Performance tradeoffs in read-optimized databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: Allison L. Holloway , Vijayshankar Raman , Garret Swart , David J. DeWitt, How to barter bits for chronons: compression and bandwidth trade offs for database scans, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247525]
• 14: Huffman, D. "A Method for the Construction of Minimum-Redundancy Codes." In Proceedings of the I. R. E., pages 1098--1102, 1952.
• 15: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• 16: Raman, V., Swart, G. "Entropy Compression of Relations and Querying of Compressed Relations." In VLDB, 2006.
• 17: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• 18: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 19: T. P. P. Council. "TPC Benchmark H (Decision Support)," http://www.tpc.org/tpch/default.asp, August 2003.
• 20: "The Vertica Database Technical Overview White Paper." Vertica, 2007.
• 21: Marcin Zukowski , Sandor Heman , Niels Nes , Peter Boncz, Super-Scalar RAM-CPU Cache Compression, Proceedings of the 22nd International Conference on Data Engineering, p.59, April 03-07, 2006 [doi>10.1109/ICDE.2006.150]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Query processing
      H.2.m Miscellaneous
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance