Column-oriented query processing for row stores

ABSTRACT

Column-oriented DBMSs have gained increasing interest due to their superior performance for analytical workloads. Prior efforts tried to determine the possibility of simulating the query processing techniques of column-oriented systems in row-oriented databases, in a hope to improve their performance, especially for OLAP and data warehousing applications. In this paper, we show that column-oriented query processing can significantly improve the performance of row-oriented DBMSs. We introduce new operators that take into account the unique characteristics of data obtained from indexes, and exploit new technologies such as flash SSDs and multi-core processors to boost the performance. We demonstrate our approach with an experimental study using a prototype built on a commercial row-oriented DBMS.

References

1. MySQL, http://http://www.mysql.com/.
2. TPC-H Benchmark, http://www.tpc.org/tpch.
3. D. J. Abadi, P. A. Boncz, and S. Harizopoulos. Column oriented Database Systems. PVLDB, 2(2):1664--1665, 2009.
4. D. J. Abadi, S. Madden, and M. Ferreira. Integrating Compression and Execution in Column-oriented Database Systems. In SIGMOD, 2006.
5. D. J. Abadi, S. R. Madden, and N. Hachem. Column-Stores vs. Row-Stores: How Different Are They Really? In SIGMOD, 2008.
6. P. A. Boncz and M. L. Kersten. MIL Primitives for Querying a Fragmented World. VLDB Journal, 8(2):101--119, 1999.
7. P. A. Boncz, M. Zukowski, and N. Nes. MonetDB/X100: Hyper-Pipelining Query Execution. In CIDR, 2005.
8. N. Bruno. Teaching an Old Elephant New Tricks. In CIDR, 2009.
9. M. Canim, G. A. Mihaila, B. Bhattacharjee, C. A. Lang, and K. A. Ross. Buffered Bloom Filters on Solid State Storage. In ADMS, 2010.
10. S. Chen. FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance. In SIGMOD, 2009.
11. B. Debnath, S. Sengupta, and J. Li. FlashStore: High Throughput Persistent Key-Value Store. In VLDB, 2010.
12. G. Graefe. Efficient Columnar Storage in B-trees. SIGMOD Record, 36(1):3--6, 2007.
13. A. Halverson, J. L. Beckmann, J. F. Naughton, and D. J. Dewitt. A Comparison of C-Store and Row-Store in a Common Framework. Technical Report TR1570, University of Wisconsin-Madison, 2006.
14. Y.-R. Kim, K.-Y. Whang, and I.-Y. Song. Page-Differential Logging: An Efficient and DBMS-Independent Approach for Storing Data into Flash Memory. In SIGMOD, 2010.
15. P.-Å. Larson, C. Clinciu, E. N. Hanson, A. Oks, S. L. Price, S. Rangarajan, A. Surna, and Q. Zhou. SQL Server Column Store Indexes. In SIGMOD, 2011.
16. C. Mohan, D. J. Haderle, Y. Wang, and J. M. Cheng. Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. In EDBT, 1990.
17. S. Nath and A. Kansal. FlashDB: Dynamic Self-Tuning Database for NAND Flash. In IPSN, 2007.
18. S. Padmanabhan, B. Bhattacharjee, T. Malkemus, L. Cranston, and M. Huras. Multi-Dimensional Clustering: A New Data Layout Scheme in DB2. In SIGMOD, 2003.
19. S. Padmanabhan, T. Malkemus, R. C. Agarwal, and A. Jhingran. Block Oriented Processing of Relational Database Operations in Modern Computer Architectures. In ICDE, 2001.
20. R. Ramamurthy, D. J. DeWitt, and Q. Su. A Case for Fractured Mirrors. In VLDB, 2002.
21. V. Raman, L. Qiao, W. Han, I. Narang, Y.-L. Chen, K.-H. Yang, and F.-L. Ling. Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding. In SIGMOD, 2007.
22. M. Stonebraker, D. J. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. O'Neil, P. O'Neil, A. Rasin, N. Tran, and S. Zdonik. C-Store: A Column-Oriented DBMS. In VLDB, 2005.
23. D. Tsirogiannis, S. Harizopoulos, M. A. Shah, J. L. Wiener, and G. Graefe. Query Processing Techniques for Solid State Drives. In SIGMOD, 2009.
24. J. Zhou and K. A. Ross. Buffering Database Operations for Enhanced Instruction Cache Performance. In SIGMOD, 2004.

Index Terms

• Hardware

  • Integrated circuits

    • Semiconductor memory

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)