MAD Skills: New Analysis Practices for Big Data

1 . MAD Skills: New Analysis Practices for Big Data Jeffrey Cohen Brian Dolan Mark Dunlap Greenplum Fox Audience Network Evergreen Technologies Joseph M. Hellerstein Caleb Welton U.C. Berkeley Greenplum ABSTRACT into groups. This was the topic of significant academic re- As massive data acquisition and storage becomes increas- search and industrial development throughout the 1990’s. ingly affordable, a wide variety of enterprises are employing Traditionally, a carefully designed EDW is considered to statisticians to engage in sophisticated data analysis. In this have a central role in good IT practice. The design and paper we highlight the emerging practice of Magnetic, Ag- evolution of a comprehensive EDW schema serves as the ile, Deep (MAD) data analysis as a radical departure from rallying point for disciplined data integration within a large traditional Enterprise Data Warehouses and Business Intel- enterprise, rationalizing the outputs and representations of ligence. We present our design philosophy, techniques and all business processes. The resulting database serves as the experience providing MAD analytics for one of the world’s repository of record for critical business functions. In addi- largest advertising networks at Fox Audience Network, us- tion, the database server storing the EDW has traditionally ing the Greenplum parallel database system. We describe been a major computational asset, serving as the central, database design methodologies that support the agile work- scalable engine for key enterprise analytics. The concep- ing style of analysts in these settings. We present data- tual and computational centrality of the EDW makes it a parallel algorithms for sophisticated statistical techniques, mission-critical, expensive resource, used for serving data- with a focus on density methods. Finally, we reflect on intensive reports targeted at executive decision-makers. It is database system features that enable agile design and flexi- traditionally controlled by a dedicated IT staff that not only ble algorithm development using both SQL and MapReduce maintains the system, but jealously controls access to ensure interfaces over a variety of storage mechanisms. that executives can rely on a high quality of service. [13] While this orthodox EDW approach continues today in many settings, a number of factors are pushing towards a 1. INTRODUCTION very different philosophy for large-scale data management in If you are looking for a career where your services will be the enterprise. First, storage is now so cheap that small sub- in high demand, you should find something where you provide groups within an enterprise can develop an isolated database a scarce, complementary service to something that is getting of astonishing scale within their discretionary budget. The ubiquitous and cheap. So what’s getting ubiquitous and cheap? world’s largest data warehouse from just over a decade ago Data. And what is complementary to data? Analysis. can be stored on less than 20 commodity disks priced at – Prof. Hal Varian, UC Berkeley, Chief Economist at Google [5] under $100 today. A department can pay for 1-2 orders of magnitude more storage than that without coordinating mad (adj.): an adjective used to enhance a noun. with management. Meanwhile, the number of massive-scale 1- dude, you got skills. data sources in an enterprise has grown remarkably: mas- 2- dude, you got mad skills. sive databases arise today even from single sources like click- – UrbanDictionary.com [12] streams, software logs, email and discussion forum archives, etc. Finally, the value of data analysis has entered com- Standard business practices for large-scale data analysis cen- mon culture, with numerous companies showing how sophis- ter on the notion of an “Enterprise Data Warehouse” (EDW) ticated data analysis leads to cost savings and even direct that is queried by “Business Intelligence” (BI) software. BI revenue. The end result of these opportunities is a grassroots tools produce reports and interactive interfaces that summa- move to collect and leverage data in multiple organizational rize data via basic aggregation functions (e.g., counts and units. While this has many benefits in fostering efficiency averages) over various hierarchical breakdowns of the data and data-driven culture [15], it adds to the force of data de- centralization that data warehousing is supposed to combat. In this changed climate of widespread, large-scale data Permission to copy without fee all or part of this material is granted provided collection, there is a premium on what we dub MAD anal- that the copies are not made or distributed for direct commercial advantage, ysis skills. The acronym arises from three aspects of this the VLDB copyright notice and the title of the publication and its date appear, environment that differ from EDW orthodoxy: and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, to post on servers • Magnetic: Traditional EDW approaches “repel” new or to redistribute to lists, requires a fee and/or special permission from the data sources, discouraging their incorporation until publisher, ACM. VLDB ‘09, August 24-28, 2009, Lyon, France they are carefully cleansed and integrated. Given the Copyright 2009 VLDB Endowment, ACM 000-0-00000-000-0/00/00. ubiquity of data in modern organizations, a data ware- 

2 . house can keep pace today only by being “magnetic”: toward more fluid integration or consolidation of tradition- attracting all the data sources that crop up within an ally diverse tools including traditional relational databases, organization regardless of data quality niceties. column stores, ETL tools, and distributed file systems. • Agile: Data Warehousing orthodoxy is based on long- range, careful design and planning. Given growing numbers of data sources and increasingly sophisticated 2. BACKGROUND: IF YOU’RE NOT MAD and mission-critical data analyses, a modern warehouse Data analytics is not a new area. In this section we de- must instead allow analysts to easily ingest, digest, scribe standard practice and related work in Business Intel- produce and adapt data at a rapid pace. This requires ligence and large-scale data analysis, to set the context for a database whose physical and logical contents can be our MAD approach. in continuous rapid evolution. • Deep: Modern data analyses involve increasingly so- 2.1 OLAP and Data Cubes phisticated statistical methods that go well beyond the Data Cubes and On-Line Analytic Processing (OLAP) rollups and drilldowns of traditional BI. Moreover, an- were popularized in the 1990’s, leading to intense commer- alysts often need to see both the forest and the trees in cial development and significant academic research. The running these algorithms – they want to study enor- SQL CUBE BY extension translated the basic idea of OLAP mous datasets without resorting to samples and ex- into a relational setting [8]. BI tools package these sum- tracts. The modern data warehouse should serve both maries into fairly intuitive “cross-tabs” visualizations. By as a deep data repository and as a sophisticated algo- grouping on few dimensions, the analyst sees a coarse “roll- rithmic runtime engine. up” bar-chart; by grouping on more dimensions they “drill As noted by Varian, there is a growing premium on an- down” into finer grained detail. Statisticians use the phrase alysts with MAD skills in data analysis. These are often descriptive statistics for this kind of analysis, and tradition- highly trained statisticians, who may have strong software ally apply the approach to the results of an experimental skills but would typically rather focus on deep data analy- study. This functionality is useful for gaining intuition about sis than database management. They need to be comple- a process underlying the experiment. For example, by de- mented by MAD approaches to data warehouse design and scribing the clickstream at a website one can get better inu- database system infrastructure. These goals raise interest- ition about underlying properties of the user population. ing challenges that are different than the traditional focus By contrast, inferential or inductive statistics try to di- in the data warehousing research and industry. rectly capture the underlying properties of the population. This includes fitting models and parameters to data and 1.1 Contributions computing likelihood functions. Inferential statistics require In this paper, we describe techniques and experiences we more computation than the simple summaries provided by have developed in our development of MAD analytics for Fox OLAP, but provide more probabilistic power that can be Audience Network, using a large installation of the Green- used for tasks like prediction (e.g., “which users would be plum Database system. We discuss our database design likely to click on this new ad?”), causality analysis (“what methodology that focuses on enabling an agile yet organized features of a page result in user revisits?”), and distribu- approach to data analysis (Section 4). We present a number tional comparison (e.g., “how do the buying patterns of of data-parallel statistical algorithms developed for this set- truck owners differ from sedan owners?”) Inferential ap- ting, which focus on modeling and comparing the densities of proaches are also more robust to outliers and other par- distributions. These include specific methods like Ordinary ticulars of a given dataset. While OLAP and Data Cubes Least Squares, Conjugate Gradiant, and Mann-Whitney U remain useful for intuition, the use of inferential statistics Testing, as well as general purpose techniques like matrix has become an imperative in many important automated multiplication and Bootstrapping (Section 5). Finally, we or semi-automated business processes today, including ad reflect on critical database system features that enable agile placement, website optimization, and customer relationship design and flexible algorithm development, including high- management. performance data ingress/egress, heterogeneous storage fa- cilities, and flexible programming via both extensible SQL 2.2 Databases and Statistical Packages and MapReduce interfaces to a single system (Section 6). BI tools provide fairly limited statistical functionality. It Underlying our discussion are challenges to a number of is therefore standard practice in many organizations to ex- points of conventional wisdom. In designing and analyzing tract portions of a database into desktop software packages: data warehouses, we advocate the theme “Model Less, It- statistical package like SAS, Matlab or R, spreadsheets like erate More”. This challenges data warehousing orthodoxy, Excel, or custom code written in languages like Java. and argues for a shift in the locus of power from DBAs to- There are various problems with this approach. First, ward analysts. We describe the need for unified systems copying out a large database extract is often much less effi- that embrace and integrate a wide variety of data-intensive cient than pushing computation to the data; it is easy to get programming styles, since analysts come from many walks orders of magnitude performance gains by running code in of life. This involves moving beyond religious debates about the database. Second, most stat packages require their data the advantages of SQL over MapReduce, or R over Java, to to fit in RAM. For large datasets, this means sampling the focus on evolving a single parallel dataflow engine that can database to form an extract, which loses detail. In modern support a diversity of programming styles, to tackle sub- settings like advertising placement, microtargeting requires stantive statistical analytics. Finally, we argue that many an understanding of even small subpopulations. Samples data sources and storage formats can and should be knit- and synopses can lose the “long tail” in a data set, and that ted together by the parallel dataflow engine. This points is increasingly where the competition for effectiveness lies. 

3 . A better approach is to tightly integrate statistical com- SQL code [16] are also relevant. The interested reader is also putation with a massively parallel database. Unfortunately, referred to new research systems on scientific data manage- many current statistical packages do not provide parallel im- ment [21] and scalability for R [25]. The idea of “dataspaces” plementations of any kind. Those statistical libraries that is related to our MAD philosophy as well, with a focus on have been parallelized, e.g., via ScaLAPACK [2], rely on data integration [6]. MPI-based message-passing protocols across processors, and do not integrate naturally with the dataflow parallelism of 3. FOX AUDIENCE NETWORK popular data-intensive solutions. Fox Audience Network serves ads across several Fox online publishers, including MySpace.com, IGN.com and Scout.com. 2.3 MapReduce and Parallel Programming With a reach of over one hundred and fifty million users, it While BI and EDW methodologies were being packaged is one of the world’s largest ad networks. for enterprise settings, the MapReduce programming model The FAN Data Warehouse today is implemented via the popularized by Google has captured the attention of many Greenplum Database system running on 42 nodes: 40 for developers. Google’s very visible successes in ad placement query processing, and two master nodes (one for failover). and text processing – and their public embrace of statisti- The query processing nodes are Sun X4500 (“Thumper”) cal machine learning – has driven this phenomenon forward machines, configured with 2 dual-core Opteron processors, quickly. A recent paper on implementing machine learning 48 500-GB drives, and 16 GB of RAM. The FAN EDW algorithms in MapReduce [3] highlighted a number of stan- currently holds over 200 terabytes of unique production data dard techniques that can be computed in a data-parallel that is then mirrored for failover. It is growing rapidly: fashion via summations. The Apache Mahout project is every day the FAN data warehouse ingests four to seven an effort to implement these techniques in the open-source billion rows of ad server logs amounting to approximately Hadoop MapReduce engine. The observation of that pa- five terabytes. The major impression fact table stretches per applies equally well to SQL, but the technical-social back to October of 2007, creating a single table of over 1.5 phenomenon surrounding MapReduce is important: it has trillion rows. FAN’s Customer Relationship Management caused a number of statistically-minded researchers and de- (CRM) solution also provides millions of rows of advertiser velopers to focus on Big Data and data-parallel program- and campaign dimension data every day. Additionally there ming, rather than on multiprocessing via MPI. This spirit is extensive data on each of over 150 million users. The FAN of data-parallel programming informs the design of our algo- EDW is the sole repository where all three data sources are rithms in Section 5 as well. But programming style is only integrated for use by research or reporting teams. one aspect of a MAD approach to managing the process of The EDW is expected to support very disparate users, analytics, as we describe in Section 4. from sales account managers to research scientists. These users’ needs are very different, and a variety of reporting and 2.4 Data Mining and Analytics in the Database statistical software tools are leveraged against the warehouse There is a significant literature on parallel data mining al- every day. The MicroStrategy BI tool has been implemented gorithms; see for example the collection by Zaki and Ho [24]. directly against the warehouse to service Sales, Marketing The most common data mining techniques – clustering, clas- and most other basic reporting needs. Research scientists sification, association rules – concern themselves with what also have direct command-line access to the same warehouse. we might call pointwise decisions. Classifiers and clustering Thus, the query ecosystem is very dynamic. assign individual points to cohorts (class labels or cluster No set of pre-defined aggregates could possibly cover every IDs); association rules form combinatorial collections of in- question. For example, it is easy to imagine questions that dividual points at the output. Though these problems are combine both advertiser and user variables. At FAN, this non-trivial, the field of statistical modeling covers quite a bit typically means hitting the fact tables directly. For instance, more ground in addition. For example, a common technique one question that is easy for a salesperson to pose is: How in advertising analysis is A/B testing, which takes response many female WWF enthusiasts under the age of 30 visited rates of a subpopulation and a control group, and compares the Toyota community over the last four days and saw a their statistical densities on various metrics. medium rectangle? (A “medium rectangle” is a standard- Standard data mining methods in commercial databases sized web ad.) The goal is to provide answers within minutes are useful but quite targeted: they correspond to only a to such ad hoc questions, and it is not acceptable to refuse small number of the hundreds of statistical libraries that to answer questions that were not precomputed. would ship with a stat package like R, SAS, or Matlab. This example is satisfied by a simple SQL query, but the Moreover, they are typically “black box” implementations, follow-up question in such scenarios is invariably a compar- whose code is compiled into an engine plugin. By contrast, ative one: How are these people similar to those that visited statistical package like R or Matlab are flexible programming Nissan? At this stage we begin to engage in open-ended environments, with library routines that can be modified multi-dimensional statistical analysis requiring more sophis- and extended by analysts. MAD analysis requires similar ticated methods. At FAN, R is a popular choice for research programming abilities to be brought to Big Data scenar- and the RODBC package is often used to interface directly ios, via extensible SQL and/or MapReduce. Black-box data with the warehouse. When these questions can be reduced mining routines can sometimes be useful in that context, to fewer than 5 million records, the data is often exported but only in a modest fraction of cases. and analyzed in R. The cases where it cannot be reduced In addition to our work, there are other interesting efforts form a main impetus for this research paper. to do significant scientific computation in SQL documented In addition to the data warehouse, the machine learning in the literature, most notably in the Sloan Digital Sky Sur- team at FAN also makes use of several large Hadoop clusters. vey [22]. The management of experiments [14] and complex That team employs dozens of algorithms for classification, 

4 .supervised and unsupervised learning, neural network and and responding to their concerns improves the overall health natural language processing. These are not techniques tra- of the warehouse. ditionally addressed by an RDBMS, and the implementation Ultimately, the analysts produce new data products that in Hadoop results in large data migration efforts for specific are valuable to the enterprise. They are not just consumers, single-purpose studies. The availability of machine learning but producers of enterprise data. This requires the ware- methods directly within the warehouse would offer a signifi- house to be prepared to “productionalize” the data gener- cant savings in time, training, and system management, and ated by the analysts into standard business reporting tools. is one of the goals of the work described here. It is also useful, when possible, to leverage a single par- allel computing platform, and push as much functionality 4. MAD DATABASE DESIGN as possible into it. This lowers the cost of operations, and eases the evolution of software from analyst experiments to Traditional Data Warehouse philosophy revolves around a production code that affects operational behavior. For ex- disciplined approach to modeling information and processes ample, the lifecycle of an ad placement algorithm might start in an enterprise. In the words of warehousing advocate Bill in a speculative analytic task, and end as a customer fac- Inmon, it is an “architected environment” [13]. This view ing feature. If it is a data-driven feature, it is best to have of warehousing is at odds with the magnetism and agility that entire lifecycle focused in a single development environ- desired in many new analysis settings, as we describe below. ment on the full enterprise dataset. In this respect we agree 4.1 New Requirements with a central tenet of Data Warehouse orthodoxy: there is As data savvy people, analysts introduce a new set of re- tangible benefit to getting an organization’s data into one quirements to a database environment. They have a deep repository. We differ on how to achieve that goal in a useful understanding of the enterprise data and tend to be early and sophisticated manner. adopters of new data sources. In the same way that sys- In sum, a healthy business should not assume an archi- tems engineers always want the latest-and-greatest hardware tected data warehouse, but rather an evolving structure that technologies, analysts are always hungry for new sources iterates through a continuing cycle of change: of data. When new data-generating business processes are 1. The business performs analytics to identify areas of launched, analysts demand the new data immediately. potential improvement. These desires for speed and breadth of data raise ten- 2. The business either reacts to or ignores this analysis. sions with Data Warehousing orthodoxy. Inmon describes 3. A reaction results in new or different business practices the traditional view: – perhaps new processes or operational systems – that There is no point in bringing data ... into the typically generate new data sets. data warehouse environment without integrating 4. Analysts incorporate new data sets into their models. it. If the data arrives at the data warehouse in an 5. The business again asks itself “How can we improve?” unintegrated state, it cannot be used to support A healthy, competitive business will look to increase the a corporate view of data. And a corporate view pace of this cycle. The MAD approach we describe next is of data is one of the essences of the architected a design pattern for keeping up with that increasing pace. environment. [13] Unfortunately, the challenge of perfectly integrating a new 4.2 Getting More MAD data source into an “architected” warehouse is often sub- The central philosophy in MAD data modeling is to get stantial, and can hold up access to data for months – or in the organization’s data into the warehouse as soon as possi- many cases, forever. The architectural view introduces fric- ble. Secondary to that goal, the cleaning and integration of tion into analytics, repels data sources from the warehouse, the data should be staged intelligently. and as a result produces shallow incomplete warehouses. It To turn these themes into practice, we advocate the three- is the opposite of the MAD ideal. layer approach. A Staging schema should be used when Given the growing sophistication of analysts and the grow- loading raw fact tables or logs. Only engineers and some ing value of analytics, we take the view that it is much more analysts are permitted to manipulate data in this schema. important to provide agility to analysts than to aspire to The Production Data Warehouse schema holds the aggre- an elusive ideal of full integration. In fact, analysts serve as gates that serve most users. More sophisticated users com- key data magnets in an organization, scouting for interest- fortable in a large-scale SQL environment are given access ing data that should be part of the corporate big picture. to this schema. A separate Reporting schema is maintained They can also act as an early warning system for data qual- to hold specialized, static aggregates that support reporting ity issues. For the privilege of being the first to see the tools and casual users. It should be tuned to provide rapid data, they are more tolerant of dirty data, and will act to access to modest amounts of data. apply pressure on operational data producers upstream of These three layers are not physically separated. Users the warehouse to rectify the data before it arrives. Analysts with the correct permissions are able to cross-join between typically have much higher standards for the data than a layers and schemas. In the FAN model, the Staging schema typical business unit working with BI tools. They are un- holds raw action logs. Analysts are given access to these daunted by big, flat fact tables that hold complete data sets, logs for research purposes and to encourage a laboratory scorning samples and aggregates, which can both mask er- approach to data analysis. Questions that start at the event rors and lose important features in the tails of distributions. log level often become broader in scope, allowing custom Hence it is our experience that a good relationship with aggregates. Communication between the researchers and the analytics team is an excellent preventative measure for the DBAs uncovers common questions and often results in data management issues later on. Feeding their appetites aggregates that were originally personalized for an analyst 

5 .being promoted into the production schema. ated using operators called “functionals” acting upon func- The Production schema provides quick answers to com- tions. This is the realm of functional analysis. Methods like mon questions that are not yet so common as to need re- t−tests or likelihood ratios are functionals. A/B testing in- ports. Many of these are anticipated during installation, volves functionals, treating two mathematical objects at a but many are not. Data tends to create “feeding frenzies” time: probability density functions f1 (·) and f2 (·). as organizations, starved for data only months before, be- Our job, then, is to advance database methods from scalars gin launching question after question at the database. Being to vectors to functions to functionals. Further, we must do nimble in this stage is crucial, as the business analysts begin this in a massively parallel environment. This is not triv- to enter the environment. They want to know things at the ial. Even the apparently “simple” problem of representing daily or monthly level. Questions about daily performance matrices does not have a unique optimal solution. In the are turned into dashboards. next few sections, we describe methods we have used to con- Analysts should also be given a fourth class of schema vince a parallel database to behave like a massively scalable within the warehouse, which we call a “sandbox”1 . The statistical package. We begin with vector arithmetic and sandbox schema is under the analysts’ full control, and is work toward functionals, with additional powerful statisti- to be used for managing their experimental processes. Ana- cal methods along the way. lysts are data-savvy developers, and they often want to track and record their work and work products in a database. For 5.1 Vectors and Matrices example, when developing complex SQL like we will see in Relational databases are designed to scale with cardinal- Section 5, it is typical to use SQL views as “subroutines” to ity. We describe how we have represented large “vector” structure a coding task. During development, these views and “matrix” objects as relations, and implemented basic are likely to be defined and edited frequently. Similarly, ana- operations for them. This gives us vector arithmetic. lysts may want to materialize query results as they are doing Before constructing operators, we need to define what a their work, and reuse the results later; this materialization vector (often in the form of a matrix) would mean in the can also help the software engineering process, and improve context of a database. There are many ways to partition efficiency during iterative design of an analysis workflow. In (“block”, “chunk”) such matrices across nodes in a par- addition, analysts often want to squirrel away pet data sets allel system (e.g., see [2], Chapter 4). A simple scheme for their own convenience over time, to use in prototyping that fits well with parallel databases is to represent the ma- new techniques on known inputs. trix as a relation with schema (row number integer, vector The ability to leap from very specific to very general en- numeric[]) and allow the DBMS to partition the rows across courages investigation and creativity. As the data gets used, processors arbitrarily – e.g. via hashing or a round-robin transformed, discussed and adopted, the organization learns scheme. In practice, we often materialize both A and A and changes its practices. The pace of progress is bound by to allow this row-representation method to work more effi- the pace and depth of investigation. MAD design is intended ciently. to accelerate this pace. Given matrices represented as horizontally partitioned re- lations in this manner, we need to implement basic matrix arithmetic as queries over those relations, which can be ex- 5. DATA-PARALLEL STATISTICS ecuted in a parallel fashion. Analysts and statisticians are an organization’s most data- Consider two matrices A and B of identical dimensions. savvy agents, and hence key to its MAD skills. In this sec- Matrix addition A + B is easy to express in SQL: tion, we focus on powerful, general statistical methods that SELECT A.row_number, A.vector + B.vector make the data warehouse more “Magnetic” and “Agile” for FROM A, B these analysts, encouraging them to go “Deep” and substan- WHERE A.row_number = B.row_number; tially increase the sophistication and scale of data analytics. Note that the + operator here is operating on arrays of nu- Our general approach is to develop a hierarchy of math- meric types and returns a similarly-dimensioned array, so ematical concepts in SQL, and encapsulate them in a way the output is a matrix whose dimensions are equal to the that allows analysts to work in relatively familiar statistical inputs. If vector addition is not provided by the DBMS, it terminology, without having to develop statistical methods is very easy to implement via object-relational extensions in SQL from first principles for each computation. Similar and register as an infix operator [19]. A query optimizer is functionality could be coded up in a MapReduce syntax. likely to choose a hash join for this query, which parallelizes Traditional SQL databases provide data types and func- well. tions for simple (scalar) arithmetic. The next layer of ab- Multiplication of a matrix and a vector Av is also simple: straction is vector arithmetic, which brings its own suite of SELECT 1, array_accum(row_number, vector*v) FROM A; operators. Vector objects combined with vector operators bring us the language of linear algebra. We suggest methods Again, the * operator here is operating on arrays of numer- for these operators in Section 5.1. It is this level that allows ics, but in this case returns a single numeric value – the us to speak in the language of machine learning, mathemat- dot product of its inputs x · y = Σi xi yi . This too can be ical modeling, and statistics. The next layer of abstraction implemented via a user-defined function, and registered as is the function level; probability densities are specialized an infix operator with the query language [19]. The pairs (row number,vector*v) represent a vector as (index, value) functions. Inductively, there is another layer of abstraction, where functions are the base objects and algebras are cre- pairs. To get back to our canonical row-wise representation, we convert to an array type in a single output row via the 1 This is not to be confused with “sandboxing” software pro- custom aggregation function array accum(x,v), which accu- cesses for computer security. Our usage is intended to con- mulates a single array field, setting position x to value v for vey a sense of play. each row of input. 

6 . Most RDBMSs have sequence functions. In PostgreSQL lend themselves very well to SQL methods. First, triples of and Greenplum, the command generate series(1, 50) will (document, term, count) must be created. Then marginals generate 1, 2, . . . 50. One way to compute a matrix transpose along document and term are calculated, via simple SQL A of an m × n matrix A is expressible as follows (for n = 3): GROUP BY queries. Next each original triple can be expanded SELECT S.col_number, with a tf-idf score along every “dimension” – i.e., for ev- array_accum(A.row_number, A.vector[S.col_number]) ery word in the resulting dictionary – by joining the triples FROM A, generate_series(1,3) AS S(col_number) with the document marginals and dividing out the document GROUP BY S.col_number; counts from the term counts. From there, the cosine simi- Unfortunately if A stores n-dimensional vectors, then this larity of two document vectors is calculated on tf-idf scores results in up to n copies of the table A being fed into the and the standard “distance” metric is obtained. grouping operator. An alternative is to convert to a differ- Specifically, it is well known that given two term-weight ent matrix representation, for example a sparse represen- vectors x and y, the cosine similarity θ is given by θ = tation of the form (row number, column number, value). An x·y . It is not difficult to construct “vanilla” SQL to x 2 y 2 advantage to this approach is that the SQL is much easier to construct for multiplication of matrices AB. reproduce this equation. But analysts with backgrounds in statistics do not think that way – this approach (and the SELECT A.row_number, B.column_number, SUM(A.value * B.value) sparse matrix example of Section 5.1) focuses on pairing up FROM A, B scalar values, rather than higher-level “whole-object” rea- WHERE A.column_number = B.row_number soning on vectors. Being able to express ideas like tf-idf in GROUP BY A.row_number, B.column_number terms of linear algebra lowers the barrier to entry for statis- ticians to program against the database. The dot-product This query is very efficient on sparse matrices, as 0 values operator reduces tf-idf to a very natural syntax. Suppose A would not be stored. In general, it is well-known in par- has one row per document vector. allel computation that no single storage representation will SELECT a1.row_id AS document_i, a2.row_id AS document_j, service all needs, and in practice blends need to be used. (a1.row_v * a2.row_v) / Without proper abstractions, this can lead to confusion as ((a1.row_v * a1.row_v) * (a2.row_v * a2.row_v)) AS theta custom operators need to be defined for each representa- FROM a AS a1, a AS a2 tion. In SQL, different representations can be achieved via WHERE a1.row_id > a2.row_id naming conventions on (materialized) views, but the choice of views typically is done by the analyst, since a traditional To any analyst comfortable with scripting environments query optimizer is unaware of the equivalence of these views. such as SAS or R, this formation is perfectly acceptable. Fur- Work on this front can be found in the parallel computing ther, the DBA has done the work of distributing the objects literature [23], but has yet to be integrated with relational and defining the operators. When the objects and operators query optimization and data-intensive computing. become more complicated, the advantages to having pre- The above conversation applies to scalar multiplication, defined operators increases. From a practical standpoint, vector addition and vector/matrix multiplication, which are we have moved the database closer to an interactive, an- essentially single-pass methods. The task of matrix division alytic programming environment and away from a simple is not definitively solved in a parallel context. One awkard- data retrieval system. ness in SQL is the lack of convenient syntax for iteration. The fundamental routines for finding a matrix inverse in- 5.2 Matrix Based Analytical Methods volve two or more passes over the data. However, recursive The matrices of primary interest in our setting are large, or iterative procedures can be driven by external processes dense matrices. A common subject is a distance matrix D with a minimal amount of data flow over the master node. where D(i, j) > 0 for almost all (i, j). Another theme is For instance, in the conjugate gradient method described in covariance matrices Σ in tightly correlated data sets. Section 5.2.2, only a single value is queried between itera- tions. Although matrix division is complicated, we are able 5.2.1 Ordinary Least Squares to develop the rest of our methods in this paper via pseudo- We begin with Ordinary Least Squares (OLS), a classical inverse routines (with textbook math programming caveats method for fitting a curve to data, typically with a poly- on existence and convergence.) nomial function. In web advertising, one standard appli- A comprehensive suite of (now distributed) vector objects cation is in modeling seasonal trends. More generally, in and their operators generate the nouns and verbs of statisti- many ad-hoc explorations it is where analysis starts. Given cal mathematics. From there, functions follow as sentences. a few simple vector-oriented user-defined functions, it be- We continue with a familiar example, cast in this language. comes natural for an analyst to express OLS in SQL. In our case here we find a statistical estimate of the pa- 5.1.1 tf-idf and Cosine Similarity rameter β ∗ best satisfying Y = Xβ. Here, X = n × k is The introduction of vector operations allows us to speak a set of fixed (independent) variables, and Y is a set of n much more compactly about methods. We consider a spe- observations (dependent variables) that we wish to model cific example here: document similarity, a common tool in via a function of X with parameters β. web advertising. One usage is in fraud detection. When As noted in [3], many different advertisers link to pages that are very sim- β ∗ = (X X)−1 X y (1) ilar, it is typical that they are actually the same malicious party, and very likely using stolen credit cards for payment. can be calculated by computing A = X X and b = X y as It is therefore wise to follow advertisers’ outlinks and look summations. In a parallel database this can be executed by for patterns of similar documents. having each partition of the database calculate the local A The common document similarity metric tf-idf involves and b in parallel and then merge these intermediate results three or four steps, all of which can be easily distributed and in a final sequential calculation. 

7 . This will produce a square matrix and a vector based on To a mathematician, the solution to the matrix equation the size of the independent variable vector. The final cal- Ax = b is simple when it exists: x = A−1 b. As noted in culation is computed by inverting the small A matrix and Section 5.1, we cannot assume we can find A−1 . If matrix multiplying by the vector to derive the coefficients β ∗ . A is n × n symmetric and positive definite (SPD), we can Additionally, calculation of the coefficient of determina- use the Conjugate Gradient method. This method requires tion R2 can be calculated concurrently by neither df (y) nor A−1 and converges in no more than n 1 “X ”2 interations. A general treatment is given in [17]. Here we SSR = b β ∗ − yi outline the solution to Ax = b as an extremum of f (x) = n 1 X 2 1 “X ”2 2 x Ax + b x + c. Broadly, we have an estimate x ˆ to our T SS = yi − yi solution x∗ . Since x ˆ is only an estimate, r0 = Aˆ x − b is n non-zero. Subtracting this error r0 from the estimate allows SSR R2 = us to generate a series pi = ri−1 − {Aˆ Px − b} of orthogonal T SS vectors. The solution will be x∗ = i αi pi for αi defined below. We end at the point rk 2 < for a suitable . In the following SQL query, we compute the coefficients There are several update algorithms, we have written ours β ∗ , as well as the components of the coefficient of determi- in matrix notation. nation: r0 r0 CREATE VIEW ols AS r0 = b − Aˆx0 , α0 = v0 Av0 , SELECT pseudo_inverse(A) * b as beta_star, v 0 = r0 , i=0 (transpose(b) * (pseudo_inverse(A) * b) - sum_y2/count) -- SSR Begin iteration over i. / (sum_yy - sumy2/n) -- TSS as r_squared ri ri FROM ( αi = vi Avi SELECT sum(transpose(d.vector) * d.vector) as A, sum(d.vector * y) as b, xi+1 = xi + αi vi sum(y)^2 as sum_y2, sum(y^2) as sum_yy, ri+1 = ri − αi Avi count(*) as n FROM design d check ri+1 2 ≤ ) ols_aggs; r ri+1 vi+1 = ri+1 + i+1 vi ri ri Note the use of a user-defined function for vector transpose, and user-defined aggregates for summation of (multidimen- sional) array objects. The array A is a small in-memory To incorporate this method into the database, we stored matrix that we treat as a single object; the pseudo-inverse (vi , xi , ri , αi ) as a row and inserted row i+1 in one pass. This function implements the textbook Moore-Penrose pseudoin- required the construction of functions update alpha(r i, p i, verse of the matrix. A), update x(x i, alpha i, v i), update r(x i, alpha i, v i, All of the above can be efficiently calculated in a single A), and update v(r i, alpha i, v i, A). Though the function pass of the data. For convenience, we encapsulated this yet calls were redundant (for instance, update v() also runs the further via two user-defined aggregate functions: update of ri+1 ), this allowed us to insert one full row at a time. An external driver process then checks the value of ri SELECT ols_coef(d.y, d.vector), ols_r2(d.y, d.vector) before proceeding. Upon convergence, it is rudimentary to FROM design d; compute x∗ . The presence of the conjugate gradient method enables Prior to the implementation of this functionality within even more sophisticated techniques like Support Vector Ma- the DBMS, one Greenplum customer was accustomed to cal- chines (SVM). At their core, SVMs seek to maximize the culating the OLS by exporting data and importing the data distance between a set of points and a candiate hyperplane. into R for calculation, a process that took several hours to This distance is denoted by the magnitude of the normal complete. They reported significant performance improve- vectors w 2 . Most methods incorporate the integers {0, 1} ment when they moved to running the regression within the as labels c, so the problem becomes DBMS. Most of the benefit derived from running the analy- sis in parallel close to the data with minimal data movement. 1 2 argmax f (w) = w , subject to c w − b ≥ 0. w,b 2 5.2.2 Conjugate Gradient In this subsection we develop a data-parallel implementa- This method applies to the more general issue of high tion of the Conjugate Gradiant method for solving a system dimensional functions under a Taylor expansion fx0 (x) ≈ of linear equations. We can use this to implement Sup- f (x0 ) + df (x)(x − x0 ) + 12 (x − xo ) d2 f (x)(x − x0 ) With a port Vector Machines, a state-of-the-art technique for binary good initial guess for x∗ and the common assumption of classification. Binary classifiers are a common tool in mod- continuity of f (·), we know the the matrix will be SPD near ern ad placement, used to turn complex multi-dimensional x∗ . See [17] for details. user features into simple boolean labels like “is a car en- thusiast” that can be combined into enthusiast charts. In 5.3 Functionals addition to serving as a building block for SVMs, the Conju- Basic statistics are not new to relational databases – most gate Gradiant method allows us to optimize a large class of support means, variances and some form of quantiles. But functions that can be approximated by second order Taylor modeling and comparative statistics are not typically built- expansions. in functionality. In this section we provide data-parallel 

8 .implementations of a number of comparative statistics ex- 5.3.2 Log-Likelihood Ratios pressed in SQL. Likelihood ratios are useful for comparing a subpopula- In the previous section, scalars or vectors were the atomic tion to an overall population on a particular attributed. As unit. Here a probability density function is the founda- tional object. For instance the Normal (Gaussian) density an example in advertising, consider two attributes of users: 2 2 beverage choice, and family status. One might want to know f (x) = e(x−µ) /2σ is considered by mathematicians as a single “entity” with two attributes: the mean µ and vari- whether coffee attracts new parents more than the general ance σ. A common statistical question is to see how well a population. data set fits to a target density function. The z−score of This is a case of having two density (or mass) functions a datum x is given z(x) = (x−µ) √ and is easy to obtain in for the same data set X. Denote one distribution as null σ/ n standard SQL. hypothesis f0 and the other as alternate fA . Typically, f0 and fA are different parameterizations of the same density. SELECT x.value, (x.value - d.mu) * d.n / d.sigma AS z_score For instance, N (µ0 , σ0 ) and N (µA , σA ). The likelihood L FROM x, design d under fi is given by Y 5.3.1 Mann-Whitney U Test Lfi = L(X|fi ) = fi (xk ). Rank and order statistics are quite amenable to relational k treatments, since their main purpose is to evaluate a set of The log-likelihood ratio is given by the quotient −2 log (Lf0 /LfA ). data, rather then one datum at a time. The next example Taking the log allows us to use the well-known χ2 approxi- illustrates the notion of comparing two entire sets of data mation for large n. Also, the products turn nicely into sums without the overhead of describing a parameterized density. and an RDBMS can handle it easily in parallel. The Mann-Whitney U Test (MWU) is a popular substi- X X tute for Student’s t-test in the case of non-parametric data. LLR = 2 log fA (xk ) − 2 log f0 (xk ). The general idea it to take two populations A and B and k k decide if they are from the same underlying population by This calculation distributes nicely if fi : R → R, which most examining the rank order in which members of A and B do. If fi : Rn → R, then care must be taken in managing show up in a general ordering. The cartoon is that if mem- the vectors as distributed objects. Suppose the values are bers of A are at the “front” of the line and members of in table T and the function fA (·) has been written as a user- B are at the “back” of the line, then A and B are differ- defined function f llk(x numeric, param numeric). Then the ent populations. In an advertising setting, click-through entire experiment is can be performed with the call rates for web ads tend to defy simple parametric models SELECT 2 * sum(log(f_llk(T.value, d.alt_param))) - like Gaussians or log-normal distributions. But it is often 2 * sum(log(f_llk(T.value, d.null_param))) AS llr useful to compare click-through rate distributions for differ- FROM T, design AS d ent ad campaigns, e.g., to choose one with a better median This represents a significant gain in flexibility and sophisti- click-through. MWU addresses this task. cation for any RDBMS. Given a table T with columns SAMPLE ID, VALUE, row num- bers are obtained and summed via SQL windowing func- Example: The Multinomial Distribution tions. The multinomial distribution extends the binomial dis- tribution. Consider a random variable X with k discrete CREATE VIEW R AS outcomes. These have probabilities p = (p1 , . . . , pk ). In n SELECT sample_id, avg(value) AS sample_avg trials, the joint probability distribution is given by sum(rown) AS rank_sum, count(*) AS sample_n, ! sum(rown) - count(*) * (count(*) + 1) AS sample_us n n FROM (SELECT sample_id, row_number() OVER P(X|p) = p n1 · · · p k k . (ORDER BY value DESC) AS rown, (n1 , . . . , nk ) 1 value FROM T) AS ordered To obtain pi , we assume a table outcome with column GROUP BY sample_id outcome representing the base population. CREATE VIEW B AS Assuming the condition of large sample sizes, for instance SELECT outcome, greater then 5,000, the normal approximation can be justi- outcome_count / sum(outcome_count) over () AS p fied. Using the previous view R, the final reported statistics FROM (SELECT outcome, count(*)::numeric AS outcome_count are given by FROM input GROUP BY outcome) AS a SELECT r.sample_u, r.sample_avg, r.sample_n (r.sample_u - a.sum_u / 2) / In the context of model selection, it is often convenient to sqrt(a.sum_u * (a.sum_n + 1) / 12) AS z_score compare the same data set under two different multinomial FROM R as r, (SELECT sum(sample_u) AS sum_u, distributions. sum(sample_n) AS sum_n „ « FROM R) AS a P(X|p) LLR = −2 log GROUP BY r.sample_u, r.sample_avg, r.sample_n, P(X|˜ p) a.sum_n, a.sum_u ` n ´ n1 n ! n1 ,...,nk p1 · · · pk k = −2 log n n p˜n ` ´ 1 ···p 1 The end result is a small set of numbers that describe a n1 ,...,nk ˜k k relationship of functions. This simple routine can be en- X X capsulated by stored procedures and made available to the = 2 ni log p˜i − ni log pi . i i analysts via a simple SELECT mann whitney(value) FROM table call, elevating the vocabulary of the database tremendously. Or in SQL: 

9 .SELECT 2 * sum(T.outcome_count * log B.p) have 10, 000 trials each with subsample size 3. - 2 * sum(T.outcome_count * log T.p) FROM B, test_population AS T CREATE VIEW design AS WHERE B.outcome = T.outcome SELECT a.trial_id, floor (100 * random()) AS row_id FROM generate_series(1,10000) AS a (trial_id), generate_series(1,3) AS b (subsample_id) 5.4 Resampling Techniques The reliance upon the random number generator here is Parametric modeling assumes that data comes from some system dependent and the researcher needs to verify that process that is well-represented by mathematical models scaling the random() function still returns a uniform random with a number of parameters – e.g., the mean and variance variable along the scale. Performing the experiment over of a Normal distribution. The parameters of the real-world the view now takes a single query: process need to be estimated from existing data that serves CREATE VIEW trials AS as a “sample” of that process. One might be tempted to SELECT d.trial_id, AVG(a.values) AS avg_value simply use the SQL AVERAGE and STDDEV aggregates to do FROM design d, T this on a big dataset, but that is typically not a good idea. WHERE d.row_id = T.row_id Large real-world datasets like those at FAN invariable con- GROUP BY d.trial_id tain outlier values and other artifacts. Naive “sample statis- This returns the sampling distribution: the average values tics” over the data – i.e., simple SQL aggregates – are not of each subsample. The final result of the bootstrapping robust [10], and will “overfit” to those artifacts. This can process is a simple query over this view: keep the models from properly representing the real-world SELECT AVG(avg_value), STDDEV(avg_value) process of interest. FROM trials; The basic idea in resampling is to repeatedly take samples of a data set in a controlled fashion, compute a summary This query returns the statistic of interest after the given statistic over each sample, and carefully combine the sam- number of resamples. The AVG() and STDDEV() functions ples to estimate of a property of the entire data set more are already done in parallel, so the entire technique is done robustly. Intuitively, rare outliers will appear in few or no in parallel. Note that the design view is relatively small samples, and hence will not perturb the estimators used. (∼ 30, 000 rows) so it will fit in memory; hence all 10, 000 There are two standard resampling techniques in the statis- “experiments” are performed in a single parallel pass of the tics literature. The bootstrap method is straightforward: table T; i.e., roughly the same cost as computing a naive from a population of size N , pick k members (a subsam- SQL aggregate. ple of size k) from the population and compute the desired Jackknifing makes use of a similar trick to generate mul- statistic θ0 . Now replace your subsample and pick another tiple experiments in a single pass of the table, excluding a random k members. Your new statistic θ1 will be different random subpopulation in each. from your previous statistic. Repeat this “sampling” pro- cess tens of thousands of times. The distribution of the re- 6. MAD DBMS sulting θi ’s is called the sampling distribution. The Central The MAD approach we sketch in Section 4 requires sup- Limit Theorem says that the sampling distribution is nor- port from the DBMS. First, getting data into a “Magnetic” mal, so the mean of a large sampling distribution produces database must be painless and efficient, so analysts will play an accurate measure θ∗ . The alternative to bootstrapping is with new data sources within the warehouse. Second, to en- the jackknife method, which repeatedly recomputes a sum- courage “Agility”, the system has to make physical storage mary statistic θi by leaving out one or more data items from evolution easy and efficient. Finally, “Depth” of analysis the full data set to measure the influence of certain sub- – and really all aspects of MAD analytics – require the populations. The resulting set of observations is used as a database to be a powerful, flexible programming environ- sampling distribution in the same way as in bootstrapping, ment that welcomes developers of various stripes. to generate a good estimator for the underlying statistic of interest. 6.1 Loading and Unloading Importantly, it is not required that all subsamples be of The importance of high-speed data loading and dumping the exact same size, though widely disparate subsample sizes for big parallel DBMSs was highlighted over a decade ago [1], can lead to incorrect error bounds. and it is even more important today. Analysts load new data Assuming the statistic of interest θ is easy to obtain via sets frequently, and quite often like to “slosh” large data sets SQL, for instance the average of a set of values, then the only between systems (e.g., between the DBMS and a Hadoop work needing to be done is to orchestrate the resampling cluster) for specific tasks. As they clean and refine data and via a sufficiently random number generator. We illustrate engage in developing analysis processes, they iterate over this with an example of bootstrapping. Consider a table tasks frequently. If load times are measured in days, the T with two columns (row id, value) and N rows. Assume flow of an analyst’s work qualitatively changes. These kinds that the row id column ranges densely from 1 . . . N . Because of delays repel data from the warehouse. each sample is done with replacement, we can pre-assign the In addition to loading the database quickly, a good DBMS subsampling. That is, if we do M samples, we can decide in for MAD analytics should enable database users to run queries advance that record i will appear in subsamples 1, 2, 25, . . . directly against external tables: raw feeds from files or ser- etc. vices that are accessed on demand during query processing. The function random() generates a uniformly random ele- ment of (0, 1) and floor(x) truncates to the integer portion By accessing external data directly and in parallel, a good of x. We use these functions to design a resampling exper- DBMS can eliminate the overhead of landing data and keep- iment. Suppose we have N = 100 subjects and we wish to ing it refreshed. External tables (“wrappers”) are typically 

10 .discussed in the context of data integration [18]. But the Greenplum provides multiple storage engines, with a rich focus in a MAD warehouse context is on massively parallel SQL partitioning specification to apply them flexibly across access to file data that lives on a local high-speed network. and within tables. As mentioned above, Greenplum includes Greenplum implements fully parallel access for both load- external table support. Greenplum also provides a tradi- ing and query processing over external tables via a technique tional “heap” storage format for data that sees frequent called Scatter/Gather Streaming. The idea is similar to tra- updates, and a highly-compressed “append-only” (AO) ta- ditional shared-nothing database internals [7], but requires ble feature for data that is not going to be updated; both coordination with external processes to “feed” all the DBMS are integrated within a transactional framework. Green- nodes in parallel. As the data is streamed into the system plum AO storage units can have a variety of compression it can be landed in database tables for subsequent access, modes. At one extreme, with compression off, bulk loads run or used directly as a purely external table with parallel I/O. very quickly. Alternatively, the most aggressive compression Using this technology, Greenplum customers have reporting modes are tuned to use as little space as possible. There is loading speeds of a fully-mirrored, production database in also a middle ground with “medium” compression to provide excess of four terabytes per hour with negligible impact on improved table scan time at the expense of slightly slower concurrent database operations. loads. In a recent version Greenplum also adds “column- store” partitioning of append-only tables, akin to ideas in 6.1.1 ETL and ELT the literature [20]. This can improve compression, and en- Traditional data warehousing is supported by custom tools sures that queries over large archival tables only do I/O for for the Extract-Transform-Load (ETL) task. In recent years, the columns they need to see. there is increasing pressure to push the work of transforma- A DBA should be able to specify the storage mechanism tion into the DBMS, to enable parallel execution via SQL to be used in a flexible way. Greenplum supports many transformation scripts. This approach has been dubbed ways to partition tables in order to increase query and data ELT since transformation is done after loading. The ELT load performance, as well as to aid in managing large data approach becomes even more natural with external tables. sets. The top-most layer of partitioning is a distribution Transformation queries can be written against external ta- policy specified via a DISTRIBUTED BY clause in the CREATE bles, removing the need to ever load untransformed data. TABLE statement that determines how the rows of a table This can speed up the design loop for transformations sub- are distributed across the individual nodes that comprise stantially – especially when combined with SQL’s LIMIT clause a Greenplum cluster. While all tables have a distribution as a “poor man’s Online Aggregation” [11] to debug trans- policy, users can optionally specify a partitioning policy for formations. a table, which separates the data in the table into parti- In addition to transformations written in SQL, Green- tions by range or list. A range partitioning policy lets users plum supports MapReduce scripting in the DBMS, which specify an ordered, non-overlapping set of partitions for a can run over either external data via Scatter/Gather, or in- partitioning column, where each partition has a START and database tables (Section 6.3). This allows programmers to END value. A list partitioning policy lets users specify a set write transformation scripts in the dataflow-style program- of partitions for a collection of columns, where each parti- ming used by many ETL tools, while running at scale using tion corresponds to a particular value. For example, a sales the DBMS’ facilities for parallelism. table may be hash-distributed over the nodes by sales id. On each node, the rows are further partitioned by range 6.2 Data Evolution: Storage and Partitioning into separate partitions for each month, and each of these partitions is subpartitioned into three separate sales regions. The data lifecycle in a MAD warehouse includes data in Note that the partitioning structure is completely mutable: various states. When a data source is first brought into a user can add new partitions or drop existing partitions or the system, analysts will typically iterate over it frequently subpartitions at any point. with significant analysis and transformation. As transfor- Partitioning is important for a number of reasons. First, mations and table definitions begin to settle for a particular the query optimizer is aware of the partitioning structure, data source, the workload looks more like traditional EDW and can analyze predicates to perform partition exclusion: settings: frequent appends to large “fact” tables, and occa- scanning only a subset of the partitions instead of the entire sional updates to “detail” tables. This mature data is likely table. Second, each partition of a table can have a different to be used for ad-hoc analysis as well as for standard re- storage format, to match the expected workload. A typical porting tasks. As data in the “fact” tables ages over time, arrangement is to partition by a timestamp field, and have it may be accessed less frequently or even “rolled off” to an older partitions be stored in a highly-compressed append- external archive. Note that all these stages co-occur in a only format while newer, “hotter” partitions are stored in a single warehouse at a given time. more update-friendly format to accommodate auditing up- Hence a good DBMS for MAD analytics needs to support dates. Third, it enables atomic partition exchange. Rather multiple storage mechanisms, targeted at different stages of than inserting data a row at a time, a user can use ETL or the data lifecycle. In the early stage, external tables pro- ELT to stage their data to a temporary table. After the data vide a lightweight approach to experiment with transforma- is scrubbed and transformed, they can use the ALTER TABLE tions. Detail tables are often modest in size and undergo ... EXCHANGE PARTITION command to bind the temporary periodic updates; they are well served by traditional trans- table as a new partition of an existing table in a quick atomic actional storage techniques. Append-mostly fact tables can operation. This capability makes partitioning particularly be better served by compressed storage, which can handle useful for businesses that perform bulk data loads on a daily, appends and reads efficiently, at the expense of making up- weekly, or monthly basis, especially if they drop or archive dates slower. It should be possible to roll this data off of the older data to keep some fixed size “window” of data online warehouse as it ages, without disrupting ongoing processing. 

11 .in the warehouse. The same idea also allows users to do scripts via a command line interface that passes the configu- physical migration of tables and storage format modifica- ration and MapReduce code to the DBMS, returning output tions in a way that mostly isolates production tables from to a configurable location: command line, files, or DBMS loading and transformation overheads. tables. The only required DBMS interaction is the specifi- cation of an IP address for the DBMS, and authentication 6.3 MAD Programming credentials (user/password, PGP keys, etc.) Hence develop- ers who are used to traditional open source tools continue Although MAD design favors quick import and frequent to use their favorite code editors, source code management, iteration over careful modeling, it is not intended to re- and shell prompts; they do not need to learn about database ject structured databases per se. As mentioned in Sec- utilities, SQL syntax, schema design, etc. tion 4, the structured data management features of a DBMS The Greenplum executor accesses files for MapReduce can be very useful for organizing experimental results, trial jobs via the same Scatter/Gather technique that it uses for datasets, and experimental workflows. In fact, shops that external tables in SQL. In addition, Greenplum MapReduce use tools like Hadoop typically have DBMSs in addition, scripts interoperate with all the features of the database, and and/or evolve light database systems like Hive. But as we vice versa. MapReduce scripts can use database tables or also note in Section 4, it is advantageous to unify the struc- views as their inputs, and/or store their results as database tured environment with the analysts’ favorite programming tables that can be directly accessed via SQL. Hence com- environments. plex pipelines can evolve that include some stages in SQL, Data analysts come from many walks of life. Some are and some in MapReduce syntax. Execution can be done en- experts in SQL, but many are not. Analysts that come tirely on demand – running the SQL and MapReduce stages from a scientific or mathematical background are typically in a pipeline – or via materialization of steps along the way trained in statistical packages like R, SAS, or Matlab. These either inside or outside the database. Programmers of differ- are memory-bound, single-machine solutions, but they pro- ent stripes can interoperate via familiar interfaces: database vide convenient abstractions for math programming, and ac- tables and views, or MapReduce input streams, incorporat- cess to libraries containing hundreds of statistical routines. ing a variety of languages for the Map and Reduce functions, Other analysts have facility with traditional programming and for SQL extension functions. languages like Java, Perl, and Python, but typically do not This kind of interoperability between programming metaphors want to write parallel or I/O-centric code. is critical for MAD analytics. It attracts analysts – and The kind of database extensibility pioneered by Postgres [19] hence data – to the warehouse. It provides agility to de- is no longer an exotic DBMS feature – it is a key to modern velopers by facilitating familiar programming interfaces and data analytics, enabling code to run close to the data. To be enabling interoperability among programming styles. Fi- inviting to a variety of programmers, a good DBMS exten- nally, it allows analysts to do deep development using the sibility interface should accommodate multiple languages. best tools of the trade, including many domain specific mod- PostgreSQL has become quite powerful in this regard, sup- ules written for the implementation languages. porting a wide range of extension languages including R, In experience with a variety of Greenplum customers, we Python and Perl. Greenplum takes these interfaces and en- have found that developers comfortable with both SQL and ables them to run data-parallel on a cluster. This does not MapReduce will choose among them flexibly for different provide automatic parallelism of course: developers must tasks. For example, MapReduce has proved more conve- think through how their code works in a data-parallel envi- nient for writing ETL scripts on files where the input or- ronment without shared memory, as we did in Section 5. der is known and should be exploited in the transformation. In addition to work like ours to implement statistical meth- MapReduce also makes it easy to specify transformations ods in extensible SQL, there is a groundswell of effort to im- that take one input and produce multiple outputs – this is plement methods with the MapReduce programming paradigm also common in ETL settings that “shred” input records popularized by Google [4] and Hadoop. From the perspec- and produce a stream of output tuples with mixed formats. tive of programming language design, MapReduce and mod- SQL, surprisingly, has been more convenient than MapRe- ern SQL are quite similar takes on parallelism: both are duce for tasks involving graph data like web links and so- data-parallel programming models for shared-nothing archi- cial networks, since most of the algorithms in that setting tectures that provide extension hooks (“upcalls”) to inter- (PageRank, Clustering Coefficients, etc.) can be coded com- cept individual tuples or sets of tuples within a dataflow. pactly as “self-joins” of a link table. But as a cultural phenomenon, MapReduce has captured the interest of many developers interested in running large-scale analyses on Big Data, and is widely viewed as a more at- tractive programming environment than SQL. A MAD data 7. DIRECTIONS AND REFLECTIONS warehouse needs to attract these programmers, and allow The work in this paper resulted from a fairly quick, it- them to enjoy the familiarity of MapReduce programming erative discussion among data-centric people with varying in a context that both integrates with the rest of the data in job descriptions and training. The process of arriving at the the enterprise, and offers more sophisticated tools for man- paper’s lessons echoed the lessons themselves. We did not aging data products. design a document up front, but instead “got MAD”: we Greenplum approached this challenge by implementing a brought many datapoints together, fostered quick iteration MapReduce programming interface whose runtime engine among multiple parties, and tried to dig deeply into details. is the same query executor used for SQL [9]. Users write As in MAD analysis, we expect to arrive at new questions Map and Reduce functions in familiar languages like Python, and new conclusions as more data is brought to light. A Perl, or R, and connect them up into MapReduce scripts few of the issues we are currently considering include the via a simple configuration file. They can then execute these following: 

12 .Package management and reuse: In many cases, an 9. REFERENCES analyst simply wants to string together and parameterize [1] T. Barclay et al. Loading databases using dataflow textbook techniques like linear regression or resampling “off parallelism. SIGMOD Record, 23(4), 1994. the shelf”. To support this, there is a pressing need – in [2] J. Choi et al. ScaLAPACK: a portable linear algebra both the SQL and MapReduce environments – for a pack- library for distributed memory computers – design age management solution and repository akin to the CRAN issues and performance. Computer Physics repository for R, to enable very easy code reuse. Among Communications, 97(1-2), 1996. High-Performance other challenges, this requires standardizing a vocabulary Computing in Science. for objects like vectors, matrices, functions and functionals. [3] C.-T. Chu et al. Map-Reduce for machine learning on Co-optimizing storage and queries for linear alge- multicore. In NIPS, pages 281–288, 2006. bra: There are many choices for laying out matrices across [4] J. Dean and S. Ghemawat. MapReduce: Simplified nodes in a cluster [2]. We believe that all of them can be data processing on large clusters. In OSDI, pages captured in records, with linear algebra methods written 137–150, 2004. over them in SQL or MapReduce syntax. The next step of [5] S. Dubner. Hal Varian answers your questions, sophistication is for a query optimizer to reason about (a) February 2008. multiple, redundant layouts for matrices, and (b) choosing [6] M. Franklin, A. Halevy, and D. Maier. From databases among equivalent libraries of linear algebra routines that are to dataspaces: a new abstraction for information customized to the different layouts. management. SIGMOD Rec., 34(4), 2005. Automating physical design for iterative tasks: Ana- [7] G. Graefe. Encapsulation of parallelism in the volcano lysts engaged in either ETL/ELT or in core analytics often query processing system. SIGMOD Rec., 19(2), 1990. take multiple passes over massive data sets in various forms. [8] J Gray et al. Data cube: A relational aggregation They are currently required to think about how to store that operator generalizing group-by, cross-tab, and data: leave it external, land it into one of many storage for- sub-totals. Data Min. Knowl. Discov., 1(1), 1997. mats, materialize repeated computations, etc. Analysts are [9] Greenplum. A unified engine for RDBMS and not interested in these questions, they are interested in the MapReduce, 2009. data. It would be useful for a system to (perhaps semi-) http://www.greenplum.com/resources/mapreduce/. automatically tune these decisions. [10] F. R. Hampel et al. Robust Statistics – The Approach Based on Influence Functions. Wiley, 1986. Online query processing for MAD analytics: Agility in the design of analytics depends on how frequently an an- [11] J. M. Hellerstein, P. J. Haas, and H. J. Wang. Online alyst can iterate. Techniques like Online Aggregation [11] aggregation. In ACM SIGMOD, 1997. can be useful to radically speed up this process, but the [12] W. Holland, February 2009. Downloaded from literature on the topic needs to be extended substantially http://www.urbandictionary.com/define.php?term=mad. to cover the depth of analysis discussed here. This includes [13] W. H. Inmon. Building the Data Warehouse. Wiley, techniques to provide useful running estimates for more com- 2005. plex computations, including ad-hoc code like MapReduce [14] Y. E. Ioannidis et al. Zoo: A desktop experiment programs. It also includes techniques to appropriately pri- management environment. In VLDB, 1996. oritize data for processing in a way that captures interesting [15] A. Kaushik. Web Analytics: An Hour a Day. Sybex, data in the tails of distributions. 2007. [16] N. Khoussainova et al. A case for a collaborative 7.1 When is the Future? query management system. In CIDR, 2009. We are not just speculating when we say that MAD ap- [17] K. Lange. Optimization. Springer, 2004. proaches are the future of analytics. For a number of leading [18] M. T. Roth and P. M. Schwarz. Don’t scrap it, wrap organizations, that future has already arrived, and brings it! A wrapper architecture for legacy data sources. In clear and growing value. But for more conservative organi- VLDB, 1997. zations, there may not even be a roadmap to get MAD, and [19] M. Stonebraker. Inclusion of new types in relational they may have been burned in the past by staff statisticians data base systems. In ICDE, 1986. or data mining initiatives that failed to gain ground. Those [20] M. Stonebraker et al. C-store: a column-oriented lessons have to be taken in the context of their time. Return- dbms. In VLDB, 2005. ing to Varian’s point that opens the paper, the economics [21] M. Stonebraker et al. Requirements for science data of data are changing exponentially fast. The question is not bases and SciDB. In CIDR, 2009. whether to get MAD, but how and when. In nearly all envi- [22] A. S. Szalay et al. Designing and mining ronments an evolutionary approach makes sense: tradition- multi-terabyte astronomy archives: the sloan digital ally conservative data warehousing functions are maintained sky survey. SIGMOD Rec., 29(2), 2000. even as new skills, practices and people are brought together to develop MAD approaches. This coexistence of multiple [23] R. Vuduc, J. Demmel, and K. Yelick. Oski: A library styles of analysis is itself an example of MAD design. of automatically tuned sparse matrix kernels. In SciDAC, 2005. [24] M.J. Zaki and C.-T. Ho. Large-Scale Parallel Data 8. ACKNOWLEDGMENTS Mining. Springer, 2000. Thanks to Noelle Sio and David Hubbard of FAN for their [25] Y. Zhang, H. Herodotou, and J. Yang. Riot: input, and to James Marca of UC Irvine for a fix to our I/O-efficient numerical computing without SQL. In bootstrapping discussion. CIDR, 2009.