More Web Proxy on the site http://driver.im/

research-article

Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads

Authors:

Prashanth MenonAuthors Info & Claims

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Pages 583 - 598

https://doi.org/10.1145/2882903.2915231

Published: 14 June 2016 Publication History

Abstract

Data-intensive applications seek to obtain trill insights in real-time by analyzing a combination of historical data sets alongside recently collected data. This means that to support such hybrid workloads, database management systems (DBMSs) need to handle both fast ACID transactions and complex analytical queries on the same database. But the current trend is to use specialized systems that are optimized for only one of these workloads, and thus require an organization to maintain separate copies of the database. This adds additional cost to deploying a database application in terms of both storage and administration overhead.

To overcome this barrier, we present a hybrid DBMS architecture that efficiently supports varied workloads on the same database. Our approach differs from previous methods in that we use a single execution engine that is oblivious to the storage layout of data without sacrificing the performance benefits of the specialized systems. This obviates the need to maintain separate copies of the database in multiple independent systems. We also present a technique to continuously evolve the database's physical storage layout by analyzing the queries' access patterns and choosing the optimal layout for different segments of data within the same table. To evaluate this work, we implemented our architecture in an in-memory DBMS. Our results show that our approach delivers up to 3x higher throughput compared to static storage layouts across different workloads. We also demonstrate that our continuous adaptation mechanism allows the DBMS to achieve a near-optimal layout for an arbitrary workload without requiring any manual tuning.

References

[1]

Peloton Database Management System. http://pelotondb.org.

[2]

Linux perf framework. https://perf.wiki.kernel.org/index.php/Main_Page.

[3]

PostgreSQL Query Plan Cost. http://www.postgresql.org/docs/9.5/static/using-explain.html.

[4]

MemSQL. http://www.memsql.com, 2015.

[5]

MemSQL -- Columnstore. http://docs.memsql.com/4.0/concepts/columnstore/, 2015.

[6]

D. Abadi, D. Myers, D. DeWitt, and S. Madden. Materialization strategies in a column-oriented DBMS. In ICDE, 2007.

[7]

D. J. Abadi, S. R. Madden, and N. Hachem. Column-stores vs. row-stores: How different are they really? In SIGMOD, 2008.

Digital Library

[8]

S. Agrawal, V. Narasayya, and B. Yang. Integrating vertical and horizontal partitioning into automated physical database design. In SIGMOD, 2004.

Digital Library

[9]

A. Ailamaki, D. J. DeWitt, M. D. Hill, and M. Skounakis. Weaving relations for cache performance. In VLDB, 2001.

Digital Library

[10]

A. Ailamaki, D. J. DeWitt, and M. D. Hill. Data page layouts for relational databases on deep memory hierarchies. The VLDB Journal, 11 (3): 198--215, 2002.

Digital Library

[11]

I. Alagiannis, S. Idreos, and A. Ailamaki. H2O: A hands-free adaptive store. In SIGMOD, 2014.

Digital Library

[12]

J. Arulraj, A. Pavlo, and S. Dulloor. Let's talk about storage & recovery methods for non-volatile memory database systems. In SIGMOD, 2015.

Digital Library

[13]

D. Beaver, S. Kumar, H. C. Li, J. Sobel, P. Vajgel, and F. Inc. Finding a needle in haystack: Facebook's photo storage. In OSDI, 2010.

Digital Library

[14]

P. Boncz, S. Manegold, and M. L. Kersten. Database architecture optimized for the new bottleneck: Memory access. In VLDB, pages 54--65, 1999.

Digital Library

[15]

P. Boncz, M. Zukowski, and N. Nes. Monetdb/x100: Hyper-pipelining query execution. In CIDR, 2005.

[16]

N. Bruno and S. Chaudhuri. An online approach to physical design tuning. In ICDE, 2007.

[17]

G. P. Copeland and S. N. Khoshafian. A decomposition storage model. In SIGMOD, 1985.

Digital Library

[18]

D. Cornell and P. Yu. An effective approach to vertical partitioning for physical design of relational databases. In IEEE TSE, 1990.

Digital Library

[19]

N. de Bruijn. Asymptotic Methods in Analysis. Dover, 1981.

[20]

J. Dittrich and A. Jindal. Towards a one size fits all database architecture. In CIDR, pages 195--198, 2011.

[21]

G. Graefe. Volcano -- an extensible and parallel query evaluation system. In IEEE TKDE, volume 6, pages 120--135, Feb. 1994.

Digital Library

[22]

r, Plattner, Zeier, Cudre-Mauroux, and Madden}grund10M. Grund, J. Krüger, H. Plattner, A. Zeier, P. Cudre-Mauroux, and S. Madden. HYRISE: a main memory hybrid storage engine. In VLDB, pages 105--116, 2010.

Digital Library

[23]

R. A. Hankins and J. M. Patel. Data morphing: An adaptive, cache-conscious storage technique. In VLDB, 2003.

Digital Library

[24]

S. Harizopoulos, V. Liang, D. J. Abadi, and S. Madden. Performance tradeoffs in read-optimized databases. In VLDB, pages 487--498, 2006.

Digital Library

[25]

S. Idreos, M. L. Kersten, and S. Manegold. Database cracking. In CIDR, 2007.

[26]

S. Idreos, M. L. Kersten, and S. Manegold. Self-organizing tuple reconstruction in column-stores. In SIGMOD, 2009.

Digital Library

[27]

A. K. Jain. Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 2010.

Digital Library

[28]

A. Jindal and J. Dittrich. Relax and let the database do the partitioning online. In Enabling Real-Time Business Intelligence, Lecture Notes in Business Information Processing, 2012.

[29]

A. Kemper and T. Neumann. HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. In ICDE, pages 195--206, 2011.

Digital Library

[30]

P.-A. Larson, S. Blanas, C. Diaconu, C. Freedman, J. M. Patel, and M. Zwilling. High-performance concurrency control mechanisms for main-memory databases. In VLDB, 2011.

Digital Library

[31]

r, and Grund}lee13J. Lee, M. Muehle, N. May, F. Faerber, V. Sikka, H. Plattner, J. Krüger, and M. Grund. High-performance transaction processing in SAP HANA. IEEE Data Eng. Bull., 36 (2): 28--33, 2013.

[32]

N. Malviya, A. Weisberg, S. Madden, and M. Stonebraker. Rethinking main memory OLTP recovery. In ICDE, 2014.

[33]

S. Manegold, P. A. Boncz, and M. L. Kersten. Optimizing database architecture for the new bottleneck: Memory access. VLDB Journal, 2000.

Digital Library

[34]

MemSQL. How MemSQL Works. http://docs.memsql.com/4.1/intro/.

[35]

C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM TODS, 17 (1): 94--162, 1992. ISSN 0362--5915.

Digital Library

[36]

S. B. Navathe and M. Ra. Vertical partitioning for database design: A graphical algorithm. In SIGMOD, 1989.

Digital Library

[37]

T. Neumann. Efficiently compiling efficient query plans for modern hardware. Proc. VLDB Endow., 4 (9): 539--550, June 2011.

Digital Library

[38]

T. Neumann, T. Mühlbauer, and A. Kemper. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. In SIGMOD, 2015.

Digital Library

[39]

Oracle. Oracle database in-memory option to accelerate analytics, data warehousing, reporting and OLTP. http://www.oracle.com/us/corporate/press/2020717, 2013.

[40]

M. Pezzini, D. Feinberg, N. Rayner, and R. Edjlali. Hybrid Transaction/Analytical Processing Will Foster Opportunities for Dramatic Business Innovation. https://www.gartner.com/doc/2657815/, 2014.

[41]

H. Plattner. A common database approach for OLTP and OLAP using an in-memory column database. In SIGMOD, 2009.

Digital Library

[42]

R. Ramamurthy, D. J. DeWitt, and Q. Su. A case for fractured mirrors. In Proceedings of the 28th International Conference on Very Large Data Bases, VLDB '02, pages 430--441, 2002.

Digital Library

[43]

V. Raman, G. Swart, L. Qiao, F. Reiss, V. Dialani, D. Kossmann, I. Narang, and R. Sidle. Constant-time query processing. In ICDE, 2008.

Digital Library

[44]

V. Raman, G. Attaluri, R. Barber, N. Chainani, D. Kalmuk, V. KulandaiSamy, J. Leenstra, S. Lightstone, S. Liu, G. M. Lohman, T. Malkemus, R. Mueller, I. Pandis, B. Schiefer, D. Sharpe, R. Sidle, A. Storm, and L. Zhang. DB2 with BLU acceleration: So much more than just a column store. In VLDB, volume 6, pages 1080--1091, 2013.

Digital Library

[45]

A. Rosenberg. Improving query performance in data warehouses. Business Intelligence Journal, 11, Jan. 2006.

[46]

D. Schwalb, M. Faust, J. Wust, M. Grund, and H. Plattner. Efficient transaction processing for Hyrise in mixed workload environments. In IMDM, 2014.

[47]

V. Sikka, F. Farber, W. Lehner, S. K. Cha, T. Peh, and C. Bornhövd. Efficient transaction processing in SAP HANA database: The end of a column store myth. In SIGMOD, pages 731--742, 2012.

Digital Library

[48]

V. Sikka, F. Farber, A. Goel, and W. Lehner. SAP HANA: The evolution from a modern main-memory data platform to an enterprise application platform. In VLDB, 2013.

Digital Library

[49]

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. VLDB, pages 553--564, 2005.

Digital Library

[50]

A. H. Watson, T. J. Mccabe, and D. R. Wallace. Structured testing: A software testing methodology using the cyclomatic complexity metric. In U.S. Department of Commerce/National Institute of Standards and Technology, 1996.

[51]

M. Zukowski and P. A. Boncz. Vectorwise: Beyond column stores. In IEEE Data Engineering Bulletin, 2012.

Cited By

Yi PLiang LZhang DChen YZhu JLiu XTang KChen JLin HQiu LZhou J(2024)KGFabric: A Scalable Knowledge Graph Warehouse for Enterprise Data InterconnectionProceedings of the VLDB Endowment10.14778/3685800.368581017:12(3841-3854)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.14778/3685800.3685810
Schmidt TDurner DLeis VNeumann T(2024)Two Birds With One Stone: Designing a Hybrid Cloud Storage Engine for HTAPProceedings of the VLDB Endowment10.14778/3681954.368200117:11(3290-3303)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682001
Zhang YYang SHu HYang CCai PZhou X(2024)SuccinctKV: a CPU-efficient LSM-tree Based KV Store with Scan-based CompactionACM Transactions on Architecture and Code Optimization10.1145/369587321:4(1-26)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3695873
Show More Cited By

Index Terms

Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
  2. Information storage systems
    1. Record storage systems
      1. Relational storage
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Column-stores vs. row-stores: how different are they really?
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

There has been a significant amount of excitement and recent work on column-oriented database systems ("column-stores"). These database systems have been shown to perform more than an order of magnitude better than traditional row-oriented database ...
Modern Column Stores for Big Data Processing
Big Data Analytics
Abstract
The advent of MapReduce/Hadoop and NoSQL databases undermined the primacy of SQL relational databases for data processing. Pioneering work by researchers on MonetDB and C-Store opened up the world of column stores that retain the SQL model but use ...
Column-oriented query processing for row stores
DOLAP '11: Proceedings of the ACM 14th international workshop on Data Warehousing and OLAP

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

June 2016

2300 pages

ISBN:9781450335317

DOI:10.1145/2882903

General Chairs:
Fatma Özcan
IBM Research, USA
,
Georgia Koutrika
HP Labs, USA
,
Program Chair:
Sam Madden
Massachusetts Institute of Technology, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

U.S. National Science Foundation
Intel Science and Technology Center for Big Data

Conference

SIGMOD/PODS'16

Sponsor:

SIGMOD

SIGMOD/PODS'16: International Conference on Management of Data

June 26 - July 1, 2016

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
1,116
Total Downloads

Downloads (Last 12 months)99
Downloads (Last 6 weeks)7

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yi PLiang LZhang DChen YZhu JLiu XTang KChen JLin HQiu LZhou J(2024)KGFabric: A Scalable Knowledge Graph Warehouse for Enterprise Data InterconnectionProceedings of the VLDB Endowment10.14778/3685800.368581017:12(3841-3854)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.14778/3685800.3685810
Schmidt TDurner DLeis VNeumann T(2024)Two Birds With One Stone: Designing a Hybrid Cloud Storage Engine for HTAPProceedings of the VLDB Endowment10.14778/3681954.368200117:11(3290-3303)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682001
Zhang YYang SHu HYang CCai PZhou X(2024)SuccinctKV: a CPU-efficient LSM-tree Based KV Store with Scan-based CompactionACM Transactions on Architecture and Code Optimization10.1145/369587321:4(1-26)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3695873
Liu PZhong KLi CChen HSerra ESpezzano F(2024)Demonstrating PARS: A Decision Support System for Developing Vertical Partitioning PlansProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679224(5249-5253)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679224
Zhang CLi GZhang JZhang XFeng J(2024)HTAP Databases: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338969336:11(6410-6429)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3389693
Papon TMun JKaratsenidis KRoozkhosh SHoornaert DSanaullah ADrepper UMancuso RAthanassoulis M(2024)Effortless Locality on Data Systems Using Relational FabricIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338682736:12(7410-7422)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3386827
Zhang QSong HZhou KWei JXiao C(2024)A prefetching indexing scheme for in-memory database systemsFuture Generation Computer Systems10.1016/j.future.2024.03.012156(179-190)Online publication date: Jul-2024
https://doi.org/10.1016/j.future.2024.03.012
Liu PLi CChen H(2024)Enhancing Storage Efficiency and Performance: A Survey of Data Partitioning TechniquesJournal of Computer Science and Technology10.1007/s11390-024-3538-139:2(346-368)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11390-024-3538-1
Song HZhou WCui HPeng XLi F(2024)A survey on hybrid transactional and analytical processingThe VLDB Journal10.1007/s00778-024-00858-933:5(1485-1515)Online publication date: 4-Jun-2024
https://doi.org/10.1007/s00778-024-00858-9
Cheng AWaudby JFirth HCrooks NStoica I(2023)Mammoths are Slow: The Overlooked Transactions of Graph DataProceedings of the VLDB Endowment10.14778/3636218.363624117:4(904-911)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.14778/3636218.3636241
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents