C-Store: Column-Oriented Data WarehousingJianlin Feng School of Software SUN YAT-SEN UNIVERSITY May 17, 2010C-Stores Father: Michael Stonebraker nA former Professor at Berkeley, nan Adjunct Professor at M.I.T. nACM Software System Award, 1988 qINGRES, developed by undergraduatesqPOSTGRES, Mariposa, C-StorenACM SIGMOD Innovation Award, 1994nNational Academy of Engineering , 1998C-Store: The Home Page http:/db.lcs.mit.edu/projects/cstore/nC-Store: A Column-Oriented DBMSndownload-Source codenoverview-Project descriptionnpapers-Publicationsnpeople-Who are we?nThe CStore project is a collaboration between MIT, Yale, Brandeis University. Brown University, and UMass Boston . nCommercialized C-Store: Vertica The Starting PointnC-Store: A Column Oriented DBMS nMike Stonebraker, Daniel Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth ONeil, Pat ONeil, Alex Rasin, Nga Tran and Stan Zdonik. nVLDB, pages 553-564, 2005. C-Store: the Column Store ProjectnRow Store or Column Store ?Record 1Record 2Column 1Column 2Record 3Column 3Relation or TablesExample of a RelationThe History: Relational ModelnCodd, E.F. (1970). “A Relational Model of Data for Large Shared Data Banks“. Communications of the ACM 13 (6): 377387.n Physical Data IndependenceqRow Store Vs. Column Store on the same Conceptual Model: RelationRow Store: Why? nOLTP (On-Line Transaction Processing)qATM, POS in supermarketsnCharacteristics of OLTP applications : qTransactions that involve small numbers of records (or tuples)qFrequent updates (including queries)qMany users qFast response timesnOLTP Needs Write-Optimized Row Store.qInsert and delete a record in one physical write.Row Store: Columns Stored TogetherRecord id = Page iRid = (i,N)Rid = (i,2)Rid = (i,1)Pointer to start of free spaceSLOT DIRECTORYN . . . 2 1201624N # slotsSlot ArrayDataCurrent DBMS Gold StandardCurrent DBMS Gold StandardnStore Columns in one record contiguously on disknUse B-tree indexingnUse small (e.g. 4K) disk blocksnAlign fields on byte or word boundariesnConventional (row-oriented) query optimizer and executor (technology from 1979)nAries-style transactionsFrom OLTP to OLAP and Data WarehousenOLAP (On-Line Analytical Processing, Codd, 1993)qFlexible Reporting for Business IntelligencenCharacteristics of OLAP applications : qTransactions that involve large numbers of recordsqFrequent Ad-hoc queries and Infrequent updates qA few decision making users qFast response timesnData warehouses are designed to facilitate reporting and analysis. qRead-MostlyOther Read-Mostly ApplicationsnCRM (Customer Relationship Management )qSiebel (Oracle) nCatalog Search in Electronic CommerceqAmazon.com qShopping.comColumn Store: Why?nThe Intuition: Only read relevant columnsqSay, Ad-hoc queries read 2 columns out of 20nColumn Store is not a new ideaqSybase IQ (early 90s, bitmap index)qAddamark (i.e., SenSage, for Event Log data warehouse)qMonetDB (Hyper-Pipelining Query Execution, CIDR05)C-Store Technical IdeasC-Store Technical IdeasnLogical Data Model: Relational ModelnColumn StorenOnly Materialized Views on Each Relation (perhaps many)nActive Data CompressionnColumn-Oriented Query Executor and OptimizernShared Nothing ArchitecturenReplication-Based Concurrency Control and RecoveryHow to Evaluate The C-Store PapernNone of the ideas in isolation merit publication nJudge the complete system by its (hopefully intelligent) choice ofqSmall collection of inter-related powerful ideasqThat together put performance in a new sandboxArchitecture of C-Store (Vertica) On a Single NodeC-Store code base version 0.2nhttp:/db.lcs.mit.edu/projects/cstore/cstore0.2. tar.gznruns on Linux x86 computers qTested on RedHat LinuxnThis code compiles on old versions BerkeleyDB and gcc. qBerkeleyDB.4.2nLZO version 1 (http:/www.oberhumer.com/opensource/lzo/)ReferencesnMike Stonebraker, Daniel Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth ONeil, Pat ONeil, Alex Rasin, Nga Tran and Stan Zdonik. C-Store: A Column Oriented DBMS VLDB, pages 553-564, 2005. nVERTICA DATABASE TECHNICAL OVERVIEW WHITE PAPER. http:/www.vertica.com/php/pdfgateway?file=Vertic aArchitectureWhitePaper.pdfnhttp:/www.sensage.com/English/Products/Event_ Data_Warehouse.html