The Database Column tag:databasecolumn.vertica.com,2007-08-30://1 2009-06-23T13:37:48Z A multi-author blog on database technology and innovation. Movable Type Publishing Platform 4.0 The Truth About MPP & Data Warehousing tag:www.databasecolumn.com,2009://1.48 2009-06-24T02:07:06Z 2009-06-23T13:37:48Z The purpose of this post is to explore alternative data warehouse architectures and understand the advantages MPP column store databases offer. It also debunks some of the myths of MPP data warehousing and suggests some evaluation criteria when comparing different MPP implementations. Michael Stonebraker
Shared Memory, Shared-Disk and MPP Database Architectures
Students of database technology learn early on that there are three hardware architectures on which DBMSs can run:

Shared-memory:  Here, a collection of CPUs share a common main memory and disk system. This architecture was the dominant one in the 1970's and 1980's. All of the early RDBMSs, including Oracle, DB2, Sybase and Ingres were written originally for this architecture.  Some, including Postgres and MySQL only run on shared-memory today.

Shared-disk:  Here, a collection of processors share a common main memory as above. However, a number of these "nodes" then share a common disk system. This architecture was popularized in the 1990s by Sun and HP. Several vendors, including Oracle and Sybase IQ have extended their implementations to support this architecture.

Shared-nothing (or massively parallel processing - MPP). Here, a collection of computing nodes is connected via high-speed networking. This architecture grew out of the pioneering parallel DBMS work in prototypes such as Gamma [1] and Grace [2] in the late 1980s, and early commercial implementations included Teradata and Tandem. Essentially all DBMSs written in the last decade have used this MPP architecture.

Shared memory is the least scalable of the three architectures. The memory subsystem is shared by all processors and all disks, and becomes a bottleneck.

The next architecture in terms of scalability is shared disk. In this case all processors share a common lock table and buffer pool. Synchronizing such shared data structures is very costly and limits scalability to a small number of nodes, typically a half-dozen or less.

The most scalable architecture is MPP. There are commercial implementations today on MPPs of 100 nodes or more. There is no technical reason why this number cannot move much higher if users' requirements warrant it.

In summary, shared-memory runs on one node, shared-disk scales to a few nodes, while MPP is the only option that easily scales to 100 or more nodes.

MPP & Data Warehousing
Right now data warehouses are growing in size every year, as business analysts wish to correlate more and more data. Unfortunately, query complexity in a data warehouse goes up super-linearly (probably quadratically or worse) with data warehouse size. Therefore, if your data warehouse data volume is increasing by 35% per year, the query workload is getting harder at much greater rate than 35% per year.  

Most data warehouse administrators running on shared-memory or shared-disk can predict when they are going to "hit the wall"; i.e. not be able to process the workload with available resources.   Consequently, scalability issues are very likely to be in your future. The only answer is very clear:  Don't run a DBMS for datawarehousing unless it has an MPP architecture!

Other MPP Advantages
A few additional (very nice to have) features that are possible in an MPP architecture include:

High availability:  the DBMS has a single state "up." If a component fails, then processing switches over to a backup copy on the fly, with no downtime. The test of this feature is to "pull the plug"; i.e. turn off some component and see if the DBMS continues without a hiccup. Note: make sure you can pull the plug on ANY node--some MPP databases include nodes, which must serve dedicated functions such as loading, querying or acting as a "master" node.  Such dedication of function drives up the required number of nodes, and makes failover more difficult.  Hence, such MPP configurations will be more expensive to run in HA environments.

(On-the-fly) incremental scalability:  the DBMS should be able to add nodes on the fly to handle a greater workload, without requiring a restart or other down time.

(On-the-fly)  schema migration:  the DBMS should be able to add attributes to tables, without requiring downtime for the table.

Trickle load:  the DBMS should be able to load and query data at the same time in a transactionally consistent manner. This requires some sort of time travel or multi-version concurrency control.  One should not be forced into the paradigm of loading during the night and querying during the day. Instead one should load data as it becomes available.

Hardware flexibility:  Some MPP implementations are done using proprietary hardware.  When it comes time to add processing power or storage capacity you are restricted to the options available from your original vendor.  You should be able to purchase and use industry standard hardware in your MPP configuration.  Generally this hardware will be less expensive per unit of processing power than proprietary hardware since it is produced in much larger quantities than any specialized proprietary hardware.

Shared Storage: Although MPP systems can be referred to as "shared-nothing" systems, many organizations rely on shared storage as part of their standard IT infrastructure.  The DBMS should be able to leverage shared storage subsystems such as SANs.

Deployment Flexibility: MPP configurations should naturally and easily take advantage of public and private cloud (i.e., virtualized) configurations.  Make sure your DBMS can be run easily on a group of cloud-based resources.
 
You should not buy an MPP DBMS, without evaluating all of these features.

MPP Row-Store DBMS vs. MPP Column-Store DBMS
A popular tactic for bringing an MPP data warehouse database to market is to add a "sharding layer" on top of Postgres [3] or other open source DBMS, such as Greenplum and Aster have done. This tactic gives you an MPP row store.

As a rule, spreading the data warehouse workload across many shared-nothing servers will enable an MPP row-store to scale larger and perform faster than a non-MPP row store such as Oracle.

However, for most data warehousing workloads, an MPP "column-store" DBMS will provide even faster performance and hardware cost savings than an MPP row-store.

Column stores are a factor of 50 faster than row stores on typical data warehouse workloads.  This performance advantage results from:

a)    reading only the columns you need and not all columns.  When fact tables have 40 or 50 attributes, this results in an order of magnitude less data coming off the disk.
b)    Superior compression. Column stores are better at compression than row stores by a factor of 2 to 8.

Column vs. Row Data Density & MPP Hardware Costs
In order to deliver a larger performance benefit, MPP row stores need to spread data out as thinly as possible. They need lots of spindles, which increases hardware, space and power costs, plus there are more disks to fail. This is why Netezza needs 128 spindles for 12 TB of data; Greenplum and Aster also typically require many spindles per terabyte of data.

With the compression capabilities of MPP column stores like Vertica, you get fast performance with very high data density, which means fewer disks, less power and less space. Depending on the schema you could fit up to 10TB per node using a cluster of DL380s running Vertica.  And with higher density nodes your MPP system will also benefit from less traffic being spread around the network.

One should always be cognizant that for a given set of hardware (as determined by business constraints or operational requirements) you can get better hardware utilization, keep more data online and achieve higher performance with an MPP column store than an MPP row store.

Summary
In summary, any MPP database will scale larger and run faster on clusters of shared-nothing "jellybean" hardware than a non-MPP DBMS. One should always consider using an MPP DBMS to handle a large data warehouse or data mart workload. When comparing MPP DBMS, column stores have an inherent performance and compression advantage over MPP row stores. As such, whether it is cost or performance you care about, you should consider an MPP column store over MPP row stores for most data warehouse applications. 

[1]  David Dewitt et. al., Gamma:  A High Performance Dataflow Database Machine, Proc. 12th VLDB Conference, Sept. 1986.

[2]  Shinya Fusimi et. al., An Overview of the System Software of a Parallel Relational Database Machine GRACE, Proc. 12th VLDB Conference, Sept. 1986.

[3] www.postgresql.org
]]> http://databasecolumn.vertica.com/2009/06/the-truth-about-mpp-data-wareh.html Securing Your Data in the Cloud tag:www.databasecolumn.com,2009://1.46 2009-03-30T17:48:28Z 2009-03-30T19:31:34Z The information technology world is buzzing about cloud computing, but what about cloud security? The good news is that cloud security is not that different from enterprise security -- you can use many of the same tools you use to secure your external Web servers, Omer Trajman The information technology world is buzzing about cloud computing, and in my circles specifically, cloud-based data management. The questions I'm asked most frequently (aside from what exactly cloud computing is) are about cloud security. In my presentation at Sys-Con, I outlined four different aspects to cloud security: VPNs, firewalls, encryption, and intelligent data management (click here for a PDF of the slide deck). In this blog post I will highlight the first few and expand on the last item.

When you connect to a cloud computing provider, such as Amazon EC2, AppNexus, GoGrid, and the Rackspace Cloud, et al, the interface is generally an API and the machines you use are often virtualized, but otherwise the service is similar to what you get from classic hosting. The provider gives you a machine, perhaps with some network isolation and assurance that the physical box is secure, and hands over the keys (root password) to you. From there security is in your hands. The good news is that cloud security is not that different from enterprise security and you can use many of the same tools you use to secure your external Web servers:

  • You may secure your cloud machine(s) using a Virtual Private Network to isolate network communication that would otherwise travel in the clear over the Internet. 
  • You should firewall your cloud machine -- at a minimum using the cloud provider-supplied network isolation tools and preferably using the built-in operating system firewall capabilities.
  • You should consider encrypting some or all of the file system on the host machine. This may be available natively (e.g., NTFS encryption, built in database encryption) or you may have to do it yourself using add-on file systems and tools.

All of these tools will enhance security but they are not a guarantee. The most important principle when it comes to cloud security is that, as with any kind of secrecy or privacy, security is a tradeoff. Before diving in and uploading all your databases and proprietary information, assess what data should be hosted out on the cloud. Even the best security is not perfect and you need to evaluate whether the trade off is appropriate for your organization.

Two Vertica for the Cloud customers went through this exercise and, using similar tools and methodologies, deployed secure architectures, allowing them to leverage the efficiencies of cloud computing without compromising on security. Both companies set out to build a platform for customers to do analysis on a specific set of data. One focused on auditing and fraud detection; the other on service delivery performance and optimization.


Extension of the Enterprise

The first company has extensive experience with infrastructure management and with hosting. They deployed a Vertica database on the Amazon EC2. When a Vertica database instance is provisioned by the Amazon EC2, it provides users full root access so users can secure the system as they see fit. They chose to create a VPN between their enterprise users and their Vertica for the Cloud instance and set up a firewall to the outside world. Aside from the VPN port and software, they blocked off all external communication.  

cloud_security1.jpg
This approach provides a very high level of security. Data is automatically transmitted fully encrypted both when uploading and when receiving query results. The firewall guards against unwarranted intrusion. The cloud machine effectively becomes part of the enterprise infrastructure -- at least as secure as any Internet connected machine.


De-identification and Data Isolation

Another Vertica for the Cloud customer took a very inventive approach to further protect customer-related information stored on the Amazon cloud. In addition to the measures described above, they designed a hybrid, private/public cloud database.

In order to benefit from the cost-efficiency of the cloud, they placed the bulk of their data (terabytes of transactional information) in Vertica running on the Amazon EC2. They removed customer-identifiable data from the transactions; replacing it with a single encrypted key field that related it to customer-identifiable information contained in dimension tables (a few gigabytes of data) stored in Microsoft SQLServer running inside the firewall. Reports written in Pentaho (and run only by people with auditable access to the de-indentified data) relate data from the two sources, with very good performance.

cloud_security2.jpg
In many analytic systems, most of the data stored for analysis is not customer-identifiable. For example, think about the volume of clickstream data relative to the volume of information about the customers doing the clicking; the former dwarves the latter. In this case, it's economically advantageous to eliminate in-house storage costs by puting the clicks on the cloud, where Vertica compresses it and queries it fast. And by splitting out the just the private and identifiable information, this customer eliminates the risk of uploading confidential information to the cloud.

Even though data is in the cloud is anonymous, the machine is still secured with a firewall and guarded against unauthorized intrusion using public/private key access and secure passwords. This trade off of security and analysis of which data should be analyzed in the cloud helps you provision just enough security (and the accompanying maintenance) for the data you choose to manage in the cloud. Once you have identified what, if any, data can benefit from the resources in the cloud, the same tools used within the enterprise can be used on the cloud to secure your data.

For more information on designing database applications for the cloud, I recommend this webcast (registration required) in which Sonian CTO Greg Arnette and Amazon Web Services Evangelist Jeff Barr provide specifics on how they've architected production cloud applications.

]]> http://databasecolumn.vertica.com/2009/03/securing-your-data-in-the-cloud.html The Innovator's Dilemma for Analytic Database Systems tag:www.databasecolumn.com,2009://1.45 2009-03-09T21:40:19Z 2009-03-09T22:01:22Z Could the tidal wave of virtualization and cloud computing sweeping today's data centers trigger in the analytic database arena a repeat of the historic demises suffered by 14" and 8" disc manufacturers decades earlier? I think so. Over the next very few years, I predict that proprietary hardware DBMS products will look like albatrosses in a sea of uniformity in both the public and private data centers. Jerry Held Could the tidal wave of virtualization and cloud computing sweeping today's data centers trigger in the analytic database arena a repeat of the historic demises suffered by 14" and 8" disc manufacturers decades earlier? I think so.

In his classic book The Innovator's Dilemma, Clayton Christensen describes the trap that many companies have fallen into by continuing to optimize their products around customer-driven priorities while failing to see a fundamental change in market economics. Christensen delineates between "disruptive innovations" and "sustaining innovations." Disruptive innovations improve products in ways that the current mass market does not expect either through cost reduction or by enabling a completely new market segment through drastic innovation.  By contrast, sustaining innovations merely add incremental features that improve performance or functionality to incumbent solutions.

In the case of the disc industry, Christensen's most cited example, performance and storage capacity were the historic customer requirements. While 14" mainframe discs continued to have superior performance and capacity over new, 8" entrants to the market, the dramatic volume increase driven by the new minicomputer market changed the economic equation and led to the demise of the 14" suppliers. This cycle repeated with the PCs economic disruption leading to the 5.25" disc again putting old suppliers out of business. It also was a key enabler to help spawn the much larger PC market.

The classic thinking in the world of analytic data base systems is that absolute performance and capacity (database size) are the key customer priorities. Benchmark wars have been fought for years over who has the fastest DBMS and can support the biggest databases. Recently, vendors have introduced new products built around specialized hardware that try to squeeze every last ounce of performance out of traditional database architectures. This custom hardware has significantly higher cost than commodity hardware yet delivers less performance gain than completely re-architected, software only solutions. Simultaneously the proprietary hardware creates long-term platform lock in.  But most importantly, this approach runs counter to the disruptive changes in the macro environment -- virtualization and cloud computing.

The knee-jerk reaction to any type of virtualized environment for an analytic DBMS is that the inherent overhead of virtualization will inhibit performance. This view misses the importance of other criteria in the overall total cost of ownership. Organizations are discovering the operational advantages of configuring large arrays of computing and storage components in a utility computing system. These facilities can be within the enterprise (private clouds) or on outside services (public clouds). It is likely that many organizations will use a mix of public and private clouds to meet their future needs. The advantages are many:

  • Rapid provisioning for immediate access.
  • Rapid re-provisioning to meet varying analysis demands.
  • Hardware procurement separate from software -- allowing bulk procurement at lower cost.
  • Higher hardware utilization rates -- requiring less hardware to be purchased. More or less processing power can be assigned to an application at varying times of the day, week, month, quarter, etc. By sharing capacity across applications with different peak demand cycles, the total capacity requirement is reduced (typically very significantly reduced).
  • Operational cost reduction -- fewer different systems to manage, less training, more automation possible.
  • Improved system availability as mean-time-to-repair (MTTR) can be near zero with a small number of spares improving reliability for all applications.
  • If pricing is by data volume (terabytes), then users can decide to apply more processing power to support more users, faster queries or occasional peak demands for additional reporting. This can all be done without additional software cost.
Vendors offering proprietary hardware appliances to accelerate their DBMS performance are running counter to the utility computing trend. In a datacenter (public or private) that is looking for economies of scale by using large numbers of a few basic compute and storage modules, the proprietary hardware doesn't fit. While pre-configured appliances are a good idea conceptually and are easy to install and manage, these advantages can be gained without special-purpose hardware.

By offering a virtualized appliance, the analytic DBMS can run on the utility computing platform and gain all of its cost, operations and reliability advantages. By utilizing advanced DBMS algorithmic approaches (columnar, MPP, high compression, fault tolerance, etc.), the most sophisticated of these systems can outperform proprietary hardware based systems even when run in a virtualized environment. Combining a next-generation analytic database management system with virtualization offers the industry disruptive innovation that will open up an enormous new segment of the analytic database market.

Database systems have been the major holdout in the move to data center virtualization. Over the next very few years, I predict that this will change dramatically and that proprietary hardware DBMS products will look like albatrosses in a sea of uniformity in both the public and private data centers.

]]> http://databasecolumn.vertica.com/2009/03/the-innovators-dilemma-for-dbms.html Debunking Yet Another Myth: Column-Stores As A Storage-Layer Only Optimization tag:www.databasecolumn.com,2008://1.44 2008-12-10T20:04:53Z 2008-12-10T22:22:47Z In this post, we debunk the myth that the performance advantages of a column store can gained by replacing a row-oriented storage layer of a DBMS with a column-oriented storage layer without also rewriting the row-oriented query execution system that plans and processes queries on top of the storage system. Read how we did this by running experiments with the C-Store column-store database to discover how closely related the performance of column stores is to these storage layer optimizations. Daniel Abadi http://www.databasecolumn.com Editors note: This post was co-authored by Daniel Abadi and Samuel Madden

Our goal in this myth-debunking series has been to shed some light on common misconceptions about column-store databases that we have come across in our conversations with people in the database community. For example, many people think a column in a column store and an index in a row store are similar data structures. We debunked this two posts ago. Other people think that you can simulate a column-store by vertically partitioning a row-store. We debunked this previously, though the difference between these two is more subtle than the difference between a column and an index. This post we debunk yet another myth, which is perhaps even more subtle than the vertical partitioning myth:

Myth: The performance advantages of a column store can gained by replacing a row-oriented storage layer of a DBMS with a column-oriented storage layer without also rewriting the row-oriented query execution system that plans and processes queries on top of the storage system.


Experiments that debunk this myth

At first blush, it may seem that all of the benefits of column orientation can be had by simply replacing the storage layer. For example, one commonly cited benefit of column stores is: Because they store each attribute of a table separately, they are better for read queries since they can avoid reading in unnecessary attributes. This benefit for read queries can clearly be obtained solely by replacing the storage layer -- the query executor simply requests the columns it needs and the storage layer reads them off disk and merges them into rows so that the query executer can process them in the standard fashion. The other commonly cited advantage of column stores is that by storing data from the same attribute domain consecutively, they see higher data value locality, and thus an improved compression ratio. Again, this improvement is at the storage layer, and the executor need not be aware of compression at all if data is decompressed as it is read off of disk.

In our recent SIGMOD paper, "Column-Stores vs. Row-Stores: How Different Are They Really?", we ran some experiments to discover how closely related the performance of column stores is to these storage layer optimizations. We took the C-Store column-store database (the academic precursor to Vertica) and ran it on the same Star Schema Benchmark discussed in our previous two posts. We then ran the same benchmark on the same C-Store software after stripping out all column-specific operations in the query executer (which sits on top of the storage layer). More specifically, the column-oriented storage layer reads in the subset of data needed to answer a particular query (i.e., only those columns accessed by the query), merges these columns into tuples, and then runs a traditional query executer on these tuples. So in the first case we have a column-oriented executer sitting on top of a column-oriented storage layer, and in the second case we have a traditional (row-oriented) executer sitting on top of a column-oriented storage layer. Our benchmark results of these two systems are presented in the figure below:

Executor performance in row and column stores
Surprisingly, there is an order of magnitude difference between the two systems despite the identical column-oriented storage layer from the C-Store codebase. Clearly, the query executer plays a central role in the column-store performance story.


Examining strategies that lead to performance improvements

In our paper we describe four key column-oriented execution strategies that are responsible for the bulk of the performance difference. We successively remove each of these strategies in order to break down the performance contribution of each one. In the following, we give a brief overview of these four strategies:

  • Operating directly on compressed data
  • Late materialization
  • Block iteration
  • The invisible join


Operating Directly On Compressed Data

Compression is usually considered a tradeoff: One trades reduced I/O (reading in less data) for increased CPU cycles (to perform the decompression). If I/O is the main system bottleneck, then this is a good tradeoff to make. However, if a query executor can operate directly on compressed data, decompression can be avoided completely and there is no longer a CPU tradeoff. Column stores are well suited for operating directly on compressed data since they can use schemes like run-length encoding, where a sequence of repeated values is replaced by a count and the value (e.g., 1, 1, 1, 2, 2 → 1 × 3, 2 × 2) that are very easy to operate on directly. Repeated values are far more likely to occur within a column of data from the same attribute than across different attributes within a row (tuple). Run-length encoding is also particularly useful for sorted or secondarily sorted columns. (In fact, operating directly on run-length encoded data does more to improve performance than simply avoiding the need to perform decompression; it also allows the query executor to perform the same operation on multiple column values at once, further reducing CPU costs.)


Late Materialization

A row-oriented query executer sitting on top of a column-oriented storage layer results in query plans where columns that are needed for a particular query are read off disk (or from memory) and immediately merged together into tuples so that standard, row-oriented database operations (e.g., selections and joins) can be performed over these projected tuples. This approach to query execution forces an "early materialization" of rows from component columns, since tuples need to be materialized at the beginning of a query plan before the row-oriented executer can process its input data. In contrast, a sophisticated column-oriented query executer will maintain the input data in columns and run query operators over these columns in isolation as much as possible. For example, a selection predicate can be applied to just the column involved in the predicate (of course, the query executer needs to keep track of the tuple ids of the tuples that match the predicate). Such an approach is typically called "late materialization" since tuples are not materialized until late in a query plan (sometimes not until the end).

The advantages of late materialization are four-fold. First, selection and aggregation operators tend to render the construction of some tuples unnecessary (if the executor waits long enough before constructing a tuple, it might be able to avoid constructing it altogether). Second, if data is compressed using a column-oriented compression method, it can be operated on directly when using late materialization, but must be decompressed before it can be combined with values from other columns. Hence, not using late materialization removes the advantages of operating directly on compressed data. Third, cache performance is improved when operating directly on column data, since a given cache line is not polluted with surrounding irrelevant attributes for a given operation (as shown in the PAX research paper). Fourth, the block iteration optimization described in the next subsection has a higher impact on performance for fixed-length attributes. In a row store, if any attribute in a tuple is variable-width, then the entire tuple is variable width. In a late materialized column store, fixed-width columns can be operated on separately.


Block Iteration

In order to process a series of tuples, most row stores first iterate through each tuple, and then need to extract the needed attributes from these tuples through a tuple representation interface. In many cases, such as in MySQL, this leads to tuple-at-a-time processing, where there are 1-2 function calls to extract needed data from a tuple for each operation (which can result in a relatively high overhead if the operation is simple, such as a predicate application).

Some row stores (such as IBM DB2) reduce the overhead of tuple-at-a-time processing by making many tuples available at once to query operators and evaluating this entire block of tuples in single operator call. However, most row-stores do not perform this optimization, since they tend to be optimized for transactional workloads where tuple-at-a-time processing tends not to be a key bottleneck. On the other hand, most column-stores operate on blocks of values at once, and since attributes are already stored separately, no attribute extraction is needed. Furthermore, if the column is fixed width, these values can be iterated through directly as an array. Operating on data as an array not only minimizes per-tuple overhead, but it also exploits potential for parallelism on modern CPUs, as loop-pipelining techniques can be used.


Invisible Join

C-Store uses a special column-oriented join technique (designed especially for star schema joins) that rewrites a join into a special type of predicate evaluation on a fact table column that can in some cases be evaluated without repeatedly consulting the dimension table (see our paper for more details).


Summary: Understanding the performance differences

Of the four techniques discussed so far, we found that operating directly on compressed data and late materialization accounted for the majority of the performance difference between the column-oriented executors. In particular, operating directly on compressed data resulted in about a factor of two performance improvement and late materialization resulted in about a factor of three.

The bottom line is that column stores are more than just a storage layer optimization. They also contain many optimizations at the query executer level which also contribute greatly to query performance.

Two more side notes on this topic:

  1. Observation clarifies performance claims. Without the observations in this blog post, the column store claims that they are two orders of magnitude faster than row stores would be confusing. You would need to have tables that are hundreds of columns wide, with queries accessing 1% of these columns to get two orders of magnitude if column-stores only yielded the storage layer benefit of reading in fewer columns. Now, it should be clear that column-stores rely on the storage layer to get one order of magnitude performance improvement and the query executer to get the other order of magnitude.

  2. Not all column stores perform identically. The reason for this is that even though the storage layer is similar across these systems, they often have substantially different query executers. It is worth understanding the column-oriented query execution features a system offers before selecting a particular column store to use. Some systems that claim to be "column stores" got their start by taking an open source row store database and upgrading the storage layer to be column-oriented. Such systems are doomed to perform worse than true column-stores, that provide both a column-oriented storage system and a column-oriented query executor.

Editors note: For 150 more pages on column-oriented query execution, see Daniel Abadi's PhD thesis

]]> http://databasecolumn.vertica.com/2008/12/debunking-yet-another-myth-col.html Field Fodder -- Compression in Real World Datasets tag:www.databasecolumn.com,2008://1.43 2008-09-23T13:15:18Z 2008-09-23T13:39:36Z With database volumes growing exponentially and CPUs far out performing disks, compression has become a hot topic among database management solutions. Just don't believe everything you hear about compression. Real world compression rates will vary dramatically depending on the data in your warehouse and how you load and query it. Omer Trajman

With database volumes growing exponentially (see this previous post) and CPUs far out performing disks (see this previous post), compression has become a hot topic among database management solutions. Just don't believe everything you hear about compression. Product marketing is ripe with claims of anywhere from 2:1 to 30:1 compression (Note: A ratio of 2:1 is equivalent to 50% compression while 30:1 is equivalent to 96.6% compression). While these ratios may be true for data cooked up in the lab, real world compression rates will vary dramatically depending on the data in your warehouse and how you load and query it.

Compression is very data dependent. It is expected that "your mileage may vary," but with compression the differences may vary by orders of magnitude. Analyzing applications across industries we have found databases are compressible to different extents.


Compression in the Real World

In financial services, stock market trade data for all US exchanges includes 250 days of data and 10,000 instruments each year. At 100 million trades per day (a conservative number), a dataset that records the date and time, instrument, price, and volume will use between 3GB and 10GB (uncompressed) per day depending on the representation (e.g., binary vs. ASCII). By one year, this raw data will be anywhere from 1-3TB. Using an off the shelf Lempel-Ziv (LZ) algorithm may compress it by 2:1.

In the telecommunications space, call detail records include information describing the call path, times, features, and switches. An average record may be 550 bytes long, and a regional telco may record 500 million per day resulting in uncompressed source data of 275GB per day (or 100TB a year). This data, also using off the shelf LZ, compresses by 5:1. These compression factors relative to raw data can vary dramatically depending on whether the data is preprocessed (e.g., encoding long names into ids, changing timestamps with time-zones into GMT, or replacing empty strings with nulls).  

In contrast, column stores often achieve up to three times more compression, reaching factors of 20:1 versus raw data by isolating variability in the data. In a column store, each block contains data of the same attribute and type, and sorted columns guarantee homogeneity even for trickle loads and high cardinality data. This also allows column stores to use more effective algorithms than vanilla LZ. 

Vertica's customers span many industries and applications, so we have been able to assess compression with a large variety of real world datasets. For example, looking at the compressibility of different datasets that customers load into Vertica, we see the following as typical compression ratios, relative to raw ASCII delimited data (e.g., comma separated values):

  • CDR - 8:1 (87%)
  • Consumer Data - 30:1 (96%)
  • Marketing Analytics - 20:1 (95%)
  • Network logging - 60:1 (98%)
  • Switch Level SNMP - 20:1 (95%)
  • Trade and Quote Exchange - 5:1 (80%)
  • Trade Execution Auditing Trails - 10:1 (90%)
  • Weblog and Click-stream - 10:1 (90%)


Achieving Better Compression

In order to achieve compression rates higher than LZ, Vertica implements a variety of homegrown encoding and compression algorithms specifically designed for a column store database. In addition to optimized block layouts and well-known algorithms, such as run length encoding and delta value encoding, Vertica uses optimized integer and floating point compression algorithms and compound encoding that combines algorithms to increase compression and overall system performance.

Note that Vertica not only reads compressed data off of disk but also processes queries on the compressed data, saving memory and CPU bandwidth (see this previous post). This cannot be done when compressing with LZ. 

Applying LZ to any database, a server with enough CPU and a threaded storage subsystem will reduce I/O at the expense of CPU. The result is performance improvements as high as 30% and space savings up to 7:1 compared to raw data. These numbers approximate the best you can get out of a traditional database, storing records as variable sized rows with headers and applying per-block compression. These numbers also assume that data in any given block is homogenous (e.g., same date, instrument, and customer), which may be the case for bulk loaded data but is not necessarily the case when trickle loading. In a trickle load stream that adds only thousands of records per second, most databases add records into any block with free space, resulting in mixed data values and reducing overall compression. In addition, auxiliary structures such as indexes and materialized views add bloat that is more difficult to compress when these structures need to be updated as records are added.

In a recent head-to-head comparison with a competitor, a prospective customer was able to only test 300GB of raw data on a popular row store because its server was limited to 1TB of disk and the additional structures required to achieve adequate performance consumed three times the raw data size. Loading into Vertica the calculated capacity was close to 4TB of raw data on the same 1TB of disk.

You can use the compression ratio in the table to determine what your storage requirements would be using Vertica. With other vendors, you mileage will most certainly vary, but don't forget to factor in indexes, materialized views, and other auxiliary structures for row stores (such as per tuple headers), which are likely to require 2-5x these sizes.


]]> http://databasecolumn.vertica.com/2008/09/field-fodder-compression-in-re.html Debunking Another Myth: Column-Stores vs. Vertical Partitioning tag:www.databasecolumn.com,2008://1.42 2008-07-31T19:46:00Z 2008-08-01T16:11:48Z We debunk another commonly proposed approach for making a row-store perform like a column-store: vertically partitioning a row-store. Vertical partitioning is a performance enhancing trick that some DBAs perform to enhance performance on read-mostly data warehouse workloads. The idea is to store an n-column table in n new tables. Each of these new tables contains two columns - a tuple ID column and data value column from the original table. Daniel Abadi http://www.databasecolumn.com Editors note: This post was co-authored by Daniel Abadi and Samuel Madden

Last week we discussed the myth that a heavily indexed row-store can provide column-store-like performance. In particular, there is a common misconception that a column-store is basically like having a row-store with an index on every column. In fact, an indexed column in a row-store and a regular column in a column-store are very different data structures: an index maps column values to tuple IDs while a column maps tuple IDs to column values. The different data structures are useful in different situations.

This week, we debunk another commonly proposed approach for making a row-store perform like a column-store: vertically partitioning a row-store. Vertical partitioning is a technique that can be used to enhance performance on read-mostly data warehouse workloads. The idea is to store an n-column table in n new tables. Each of these new tables contains two columns - a tuple ID column and data value column from the original table. For example, the three column-table:

 
myth2_img1.jpg

could be transformed into the following three tables:
 
myth2_img2.jpg
Each table is clustered by Tuple ID. Queries over the original table are then rewritten into queries over the new tables. For example, the simple query:

SELECT name, city
FROM customers

Would be rewritten into:

SELECT t1.value, t2.value
FROM Name AS t1,
             City AS t2
WHERE t1.tuple_id = t2.tuple_id

Note that a vertically partitioned store functions like a column-store. If only 2 out of the 3 attributes of a table are requested by a query (as in the example above), then only 2 out of the 3 partitions need to be accessed. Of course, a join must be performed to merge these multiple attributes together, but since each vertical partition is clustered by the join key (Tuple ID), the join is not expensive. Furthermore, due to the clustering on Tuple ID, a vertically partitioned data structure is like a column-store in that each partition is a Tuple_ID-to-value mapping (which, as we showed in last week's post, is the opposite of the value-to-Tuple_ID mapping used in indexes).

Hence, a column store and a vertically partitioned row-store are very similar. They have the same set of trade offs relative to normal row-stores (better for read queries, slower for non-batch write queries). Thus, it is only natural to expect the two approaches to perform similarly well on read-mostly data warehouse workloads.

Surprisingly, in practice, this is not the case.

In the same SIGMOD 2008 paper that we discussed in last week's blog posting, "Column-Stores vs. Row-Stores: How Different Are They Really?," we implemented vertical partitioning inside of a commercial row-store on a read-only benchmark. The benchmark we used was the Star Schema Benchmark, a recently proposed benchmark designed to be more "typical" of data warehousing data and queries than TPC-H. We compared the performance of the vertically partitioned commercial row-store with the same row-store under a more normal configuration (optimized by a professional DBA using best practices) and with a column-store. The results are shown in the figure below:

 
myth2_img3.jpg

On this read-only data warehouse benchmark, one expects the column-store to outperform the row-store. We found this to indeed be the case. However, the surprising result is that instead of the vertically partitioned row-store performing similarly to the column-store as the discussion above suggests it should, it performs an order of magnitude worse than the column-store and a factor of 3 worse than the original row-store!

In the paper, we explore the reasons behind this surprising result, looking in detail at performance on different queries in the benchmark. The following are a list of high level reasons we came across for the poor performance of vertical partitioning on the row-store.

1) Data sizes. Table scans are often the best choice (relative to index scans) for data access in data warehouse workloads. The reason is that, in general, a large amount of data is needed by the query operators (e.g. to perform a summarization or an aggregation). A good rule of thumb is that unless less than 0.1-1% of the tuples are accessed by a query, an index scan will be slower than (or no faster than) a simple sequential scan. However, the time to perform a table scan is directly proportional to the size of the table.

Unfortunately, the Tuple ID column significantly increases the total storage required for the vertical partitioning approach. Since the columns that are accessed from the fact table in data warehouse queries are generally foreign keys (for joins with a dimension table) or are otherwise a numeric type (such as 'price' or 'revenue') that will be input to an aggregate operator, the size of the Tuple ID is generally on the order of the same size as the actual column value data. Thus, the existence of the Tuple ID column basically doubles the size of the table.

Furthermore, each tuple in a table contains a tuple header. Usually the size of a tuple header is insignificant, since the size of the actual data stored in a tuple is generally much larger. However, in the vertical partitioning case, where each table is really narrow (each containing two narrow columns), the size of the tuple header relative to the size of the rest of the tuple is no longer insignificant.  For example, in the open source PostgreSQL database, which is reputed to have a small header relative to most commercial products, the header size is 24 bytes. Compare this to the 8 bytes of actual data per tuple for a two-column vertical partition containing two integer columns. Column-stores avoid the tuple header overhead problem by storing tuple headers just once in their own separate column, and using concurrency control schemes that do not require checking the tuple header on every tuple access.

The bottom line is that the full 17 column fact table in our benchmark took up approximately 4 GB of space after compression. Meanwhile, each vertical partition took up between 0.7 and 1.1 GB of space after compression. In the star schema benchmark, the average query accesses 4-5 vertical partitions. This results in approximately the same amount of data being scanned in the vertical partitioning case as in the normal row-store case (even though only 25% of the vertical partitions need to be accessed per query). Thus, these space overheads completely eliminate the 'efficient data reading' advantage of vertical partitioning!

(As a side note, the row-store product that we used would not allow the use of 'virtual tuple ids' if we wanted to use tuple id as a join key. If the product allowed this, some of the space overhead could have been avoided).

2)  Horizontal partitioning. Under the normal configuration, the row-store product was able to take advantage of horizontal partitioning to improve performance. In particular, many of the queries in the benchmark contain a predicate on the 'year' attribute of the date dimension table. The row-store was able to use a 'partition-by-reference' feature to partition the fact table by the year dimension attribute to yield a factor of two performance improvement on average. Once we vertically partitioned the data, we could no longer use the 'partition-by-reference' feature to horizontally partition the vertical partitions, since only one of the vertical partitions contained the appropriate reference to the date dimension table. If the product allowed for an extra level of indirection in 'partition-by-reference' (using the tuple id) we could have partitioned the vertical partitions by year and seen the factor of two performance improvement; but as far as we know, no row-store product allows for 'partition-by-reference-by-reference'.

3)  Partition joins. Although joins between vertical partitions can generally be done using high performance techniques due to the clustering by tuple id; the sheer number of joins required by the vertical partitioning approach occasionally overwhelmed the query optimizer, resulting in suboptimal plans. Column-stores generally avoid this issue by considering joins of columns within the same table separately from joins across tables, and since joins within a table are so common, they typically heuristically push high-performance column merge-joins to the bottoms of query plans.

We found a variety of other reasons why vertical partitioning does not in practice yield column-store performance, including a lack of column-oriented compression and a lack of optimizations for fixed-width attributes; but the above three reasons were responsible for the bulk of the observed performance difference.

In conclusion, our published experiments show that vertically partitioning a row-store can yield very different performance relative to using a column-store. The observed poor performance of the vertically partitioned row-store is likely the reason why most DBAs do not employ complete vertical partitioning to improve row-store performance; rather, they tend to use hybrid methods such as multi-column vertical partitions or column-subset materialized views (nonetheless, our paper contains some experiments that show that the column-store still outperforms the row-store, even when the row-store contains the optimal set of materialized views).

These results present a snapshot of the state of affairs as they exist today. However, as column-stores continue to gain market share in the data warehousing market, we expect some of the commercial row-store products to fix some of the issues mentioned above. The data size issue seems to be particularly low hanging fruit--it is easy to envision a row-store that uses virtual tuple IDs as join keys and that avoids the duplication of tuple headers across vertical partitions. So while vertical partitioning performance can (and most likely will) improve, how close it can get to column-store performance remains an open question.

Intuitively, one expects a DBMS designed specifically for vertical partitioning (i.e., a column-store) will have a fundamental advantage, since column-stores can make column-specific optimizations in all parts of the DBMS code (the query executer, the query optimizer, the storage layer, etc.) while a row-store will have to occasionally make trade offs to perform well for both row-oriented and column-oriented processing. In our next blog posting, we will explore this topic in more detail, showing how column-oriented optimizations made to DBMS components outside of the traditional (storage layer) realm associated with column-stores can yield order of magnitude performance improvements.  Hence, it will require wide spread and extensive code modifications to for row-stores to even approach column-store performance.
]]> http://databasecolumn.vertica.com/2008/07/debunking-another-myth-columns.html Debunking a Myth: Column-Stores vs. Indexes tag:www.databasecolumn.com,2008://1.41 2008-07-18T17:53:21Z 2008-07-18T18:50:13Z Consider a traditional, row-oriented database. Indexes are known to improve performance in database systems. They can greatly reduce I/O costs by avoiding the need to perform table scans since they directly contain the data you need to answer a query or contain pointers to such data. If you have a query that accesses only two out of thirty columns from a large table, and you have an index on these two columns, then you can use the indexes to avoid scanning all of the data in a table. Daniel Abadi http://www.databasecolumn.com
A challenge when using a traditional database is deciding what indexes to create on your tables.  One either pays a DBA to carefully choose the right set of indexes to optimize a target workload, or you buy a database with an auto-tuning feature to create this set of indexes automatically (which might not be as good as a human DBA).

Ideally, it would be possible to have an index on every column. Unfortunately, every index you create results in the materialization of another copy of the column data (in addition to having other space overheads for pointers and other parts of the index data structure). Thus, the size of your database would be enormous if you had an index on every column. Even if you had infinite storage space (so that this explosion in data storage was not an issue), index maintenance is very expensive. Updates and inserts need to be reflected in the raw data and all of the indexes. Hence, there is a fundamental trade off - indexes improve query performance, but cost you in storage and maintenance. This is why you need an expert to choose the right set of indexes.

Now consider a column-store. By storing each column separately, the benefit appears similar to having an index on every column in a table in a row-store. If you have a query that accesses only two out of thirty columns from a large table, the column-store only reads  those two columns and can avoid the enormous table scan (just like having an index). However, since it is the raw copy of the data that is stored in columns, no additional copies of the data need to be created, so the storage and update overheads associated with indexes is avoided.

Thus, one might expect column-stores to perform similarly to a row-store with an index on every column without the corresponding negatives of creating many indices. In fact, this is a common argument we have often heard regarding column-stores and their expected performance relative to carefully designed row-stores -- both approaches provide good read performance, with the column store providing lower total cost of ownership (since you don't have to figure out what indexes to create anymore).

Though this argument sounds reasonable, it is completely incorrect.  It is also dangerous since it might cause you to end up choosing a row-store when what you really need is a column-store.

Assume the following situation:
a) You already have a license for a commercial row-store
b) You have tons of extra storage space
c) You have a read-only workload (so index maintenance is not an issue)

Using the above reasoning, in this situation you would not need to go out and buy a column-store. You would just create an index on every column on your row-store.

In our SIGMOD 2008 paper, "Column-Stores vs. Row-Stores: How Different Are They Really?" which we presented last month in Vancouver, we explored this situation, running a commercial row-store (with no storage restrictions) on a read-only benchmark. The benchmark we used was the Star Schema Benchmark, a recently proposed benchmark designed to be more "typical" of data warehousing data and queries than TPC-H. We compared the performance of the commercial row-store (where we created an index on every column and forced the database to always use these indexes to access data instead of using a full table scan to access data) with the same row-store under a more normal configuration (optimized by a professional DBA) and with a column-store. The results are shown in the figure below:
DA_mythimg_1.jpg

The fact that the column-store was almost a factor of six faster than the row-store was not surprising. After all, column-stores are supposed to outperform row-stores for data warehousing workloads. But if one views a column-store as similar to a row-store with an index on every column, one would have expected the row-store (all-indexes) approach to perform about as fast as the column-store. Instead, it performed over a factor of 50 slower, and almost an order of magnitude slower than the same commercial row-store that used full table scans to access data instead of index accesses!

So what's going on here? It turns out that a column in a column-store is very different from an index. A column in a column-store stores attribute data in the same order that it appeared in the original table (or from a sorted projection of that table). You can think of this as mapping tuple ID to column value. For example, as shown in Figures 2 - 4, if you want the value for the "customer city" attribute for the 6th tuple in a table (or projection), you can find this value by jumping to the 6th value in the "customer city" column. On the other hand, an index contains the exact opposite mapping. It maps a column value to tuple ID. If you want to find the tuple ID for all tuples whose "customer city" is "Denver", an index is great. But what if you want to find the "customer city" of the 6th tuple? You would have to scan the whole index, looking for tuple ID 6.

 
DA_mythimg_2.jpg

 
DA_mythimg_3.jpg



 
 
DA_mythimg_4.jpg

So indexes are often useful in first part of query execution where predicate evaluation occurs (dealing with the "WHERE" part of a SQL statement), where you are looking for tuples with specific values (it turns out that even then, indexes are only useful for very selective predicates). But for the later part of the query plan, where the database is extracting values for attributes for specific tuple IDs (the "SELECT" and "GROUP BY" part of a SQL statement), you want a tuple ID to value mapping, and a column is better than an index. The reason why the "row-store all-indexes" approach went so slow in our experiments is that for each tuple ID produced by evaluating the predicates in the SQL "WHERE" clause, the database would have to search the index (using the wrong mapping) for each attribute that appeared in the "GROUP BY" and "SELECT" clauses. This can be thought of as adding one additional join to the query for each attribute that appears in the "GROUP BY" and "SELECT" clauses.

Hence, an index and a column are quite different data structures. Of course, there are some situations where what you really want is an index and not a column. For example, if you had a query workload with a lot of "needle-in-the-haystack" queries (queries with very selective predicates), you need to use a lot of indexes. If you have the incorrect perception that a column-store is pretty much the same as a row-store with an index on every column, you might be tempted to use a column-store. In fact, what you really want is a heavily indexed database (either a row-store, an indexed column-store, or a column-store with multiple redundant sort orders).

An astute reader might ask the question: what if the row-store was able to have indexes that mapped tuple-ID to value instead of the other way around? We studied that idea too, and although this significantly improves the performance of the all-index approach, it still does not approach the performance of the column-store. We will explain why this is the case in a future blog post.

(Ed.  This article was co-authored by Sam Madden)

]]> http://databasecolumn.vertica.com/2008/07/debunking-a-myth-columnstores.html Understanding the Difference Between Column-Stores and OLAP Data Cubes tag:www.databasecolumn.com,2008://1.39 2008-07-08T01:47:39Z 2008-07-09T13:29:20Z Both column-stores and data cubes are designed to provide high performance on analytical database workloads (often referred to as Online Analytical Processing, or OLAP.) These workloads are characterized by queries that select a subset of tuples, and then aggregate and group along one or more dimensions. In this post, we study how column-stores and data cubes would evaluate a query on a sample database. Sam Madden
SELECT month, store, COUNT(*)
FROM sales, products
WHERE productType = 'technology'
AND products.id = sales.productID
GROUP BY month, store

In this post, we study how column-stores and data cubes would evaluate this query on a sample database:

cubes_1.jpgColumn Store Analysis
In column-stores, this query would be answered by scanning the productType column of the products table to find the ids that have type technology.  These ids would then be used to filter the productID column of the sales table to find positions of records with the appropriate product type.  Finally, these positions would be used to select data from the months and stores columns for input into the GROUP BY operator.  Unlike in a row-store, the column-store only has to read a few columns of the sales table (which, in most data warehouses, would contain tens of columns), making it significantly faster than most commercial relational databases that use row-based technology.

Also, if the table is sorted on some combination of the attributes used in the query (or if a materialized view or projection of the table sorted on these attributes is available), then substantial performance gains can be obtained both from compression and the ability to directly offset to ranges of satisfying tuples.  For example, notice that the sales table is sorted on productID, then month, then storeID.   Here, all of the records for a given productID are co-located, so the extraction of matching productIDs can be done very quickly using binary search or a sparse index that gives the first record of each distinct productID.  Furthermore, the productID column can be effectively run-length encoded to avoid storing repeated values, which will use much less storage space (see my previous post on compression in column-stores).  Run-length encoding will also be effective on the month and storeID columns, since for a group of records representing a specific productID, month is sorted, and for a group of records representing a given (productID,month) pair, storeID is sorted.  For example, if there are 1,000,000 sales records of about 1,000 products sold by 10 stores, with sales uniformly distributed across products, months and stores, then the productID column can be stored in 1,000 records (one entry per product), the month column can be stored in 1,000 x 12 = 12,000 records, and the storeID column can be stored in and 1,000 x 12 x 10 = 120,000 records.  This compression means that less the amount of data read from disk is less than 5% of its uncompressed size.

Data Cube Analysis

cubes_2.jpg
Data cube-based solutions (sometimes referred to as MOLAP systems for "multidimensional online analytical processing"), are represented by commercial products such as EssBase.  They  store data in array-like structures, where the dimensions of the array represent columns of the underlying tables, and the values of the cells represent pre-computed aggregates over the data.  A data cube on the product, store, and month attributes of the sales table, for example, would be stored in an array format as shown in the figure above.  Here, the cube includes "roll-up" cells that summarize the values of the cells in the same row, column, or "stack" (x,y position.) If we want to use a cube to compute the values of the COUNT aggregate, as in the query above, the cells of this cube would look like:

cubes_3.jpg 

Here, each cell contains the count of the number of records with a given (productID,month,storeID) value.  For example, there is one record with storeID=1, productID=2, and month=April.  The "sum" fields indicate the values of the COUNT "rolled up" on specific dimensions; for example, looking at the lower left hand corner of the cube for Store 1, we can see that in storeID 1, productID 1 was sold twice across all months.  Thus, to answer the above query using a data cube, we first identify the subset of the cube that satisfies the WHERE clause (here, products 3, 4, and 5 are technology products--this is indicated by their dark shading in the above figure.)  Then, the system reads the pre-aggregated values from sum fields for the unrestricted attributes (store and month), which gives the result that store 2 had 1 technology sale in Feburary and 1 in June, and that store 3 had 1 technology sale in February and 1 in October.

The advantages of a data cube should be clear--it contains pre-computed aggregate values that make it a very compact and efficient way to retrieve answers for specific aggregate queries.  It can be used to efficiently compute a hierarchy of aggregates--for example, the sum columns in the above cube make it is very fast to compute the number of sales in a given month across all stores, or the number of sales or a particular product across the entire year in a given store.  Because the data is stored in an array-structure, and each element is the same size, direct offsetting to particular values may be possible. However, data cubes have several limitations:

  • Sparsity:  Looking at the above cube, most of the cells are empty.  This is not simply an artifact our sample data set being small--the number of cells in a cube is the product of the cardinalities of the dimensions in the cube.  Our 3D cube with 10 stores and 1,000 products would have 120,000 cells, and adding a fourth dimension, such as customerID (with, say, 10,000 values), would cause the number of cells to balloon to 1.2 billion!  Such high dimensionality cubes cannot be stored without compression.  Unfortunately, compression can limit performance somewhat, as direct offsetting is no longer possible. For example, a common technique is to store them as a table with the values and positions of the non-empty cells, resulting in an implementation much like a row-oriented relational database!
  • Inflexible, Limited ad-hoc query support:  Data cubes work great when a cube aggregated on the dimensions of interest and using the desired aggregation functions is available.  Consider, however, what happens in the above example if the user wants to compute the average sale price rather than the count of sales, or if the user wants to include aggregates on customerID in addition to the other attributes.  If no cube is available, the user has no choice but to fall back to queries on an underlying relational system.  Furthermore, if the user wants to drill down into the underlying data--asking, for example "who was the customer who bought a technology product at store 2 in February?"--the cube cannot be used (one could imagine storing entire tuples, or pointers to tuples, in the cells of a cube, but like sparse representations, this significantly complicates the representation of a cube and can lead to storage space explosions.)  To deal with these limitations, some cube systems support what is called "HOLAP" or "hybrid online analytical processing", where they will automatically redirect queries that cannot be answered with cubes to a relational system, but such queries run as fast as whatever relational system executes them.
  • Long load times:  Computing a cube requires a complex aggregate query over all of the data in a warehouse (essentially, every record has to be read from the database.)  Though it is possible to incrementally update cubes as new data arrives, it is impractical to dynamically create new cubes to answer ad-hoc queries.
Summary and Discussion

Data cubes work well in environments where the query workload is predictable, so that cubes needed to answer specific queries can be pre-computed.  They are inappropriate for ad-hoc queries or in situations where complex relational expressions are needed.  

In contrast, column-stores provide very good performance across a much wider range of queries (all of SQL!) However, for low-dimensionality pre-computed aggregates, it is likely that a data-cube solution will outperform a column store. For many-dimensional aggregates, the tradeoff is less clear, as sparse cube representations are unlikely to perform any better than a column store.

Finally, it is worth noting that there is no reason that cubes cannot be combined with column-stores, especially in a HOLAP-style configuration where queries not directly answerable from a cube are redirected to an underlying column-store system.  That said, given that column-stores will typically get very good performance on simple aggregate queries (even if cubes are slightly faster), it is not clear if the incremental cost of maintaining and loading an additional cube system to compute aggregates is ever worthwhile in a column-store world.  Furthermore, existing HOLAP products, which are based on row-stores, are likely to be an order of magnitude or more slower than column-stores on ad-hoc queries that cannot be answered by the MOLAP system, for the same reasons discussed elsewhere in this blog.



]]> http://databasecolumn.vertica.com/2008/07/understanding-the-difference-b.html Designing Systems for the Grid: The Problem with "Retrofitting," Part 1 tag:www.databasecolumn.com,2008://1.38 2008-06-19T18:26:28Z 2008-06-21T00:09:14Z In a two-part post, we will illustrate how -- using a database query optimizer as an example -- the strategy of retrofitting databases in a distributed, shared-nothing grid computing architecture can fail. This argument will require some understanding of how centralized query optimizers work. Therefore, we will divide this discussion into two parts. The first installment will provide a background on centralized query optimization; the second installment will show why retrofitting a centralized query optimizer to work on the grid can lead to poor performance when evaluating queries. Mitch Cherniack
Some database vendors have attempted to "retrofit" their centralized DBMS designs to work in a distributed world. The basic idea of retrofitting is to reuse as much of the centralized code base as possible in producing a distributed design. The motivation for retrofitting is clear: In building a database system, it is often easier to reuse existing components and adapt them for new uses than it is to build a new system from scratch. This reduces the time-to-market of a product that can claim grid support. But the performance improvements of these retrofitted systems often do not live up to the raw increases in horsepower that grid architectures provide.  There are two reasons for this:

  1. Code that gets reused in a retrofitted system is often brittle as a result of many years of patchwork. To change this code introduces potential instabilities, and thus, there is a natural desire to instead treat such code as "black boxes."

  2. Black box code was often designed with assumptions of a centralized architecture, and these assumptions may constrain performance when executed over a distributed system over which the assumptions do not hold.

We will illustrate this point using the database query optimizer as an illustrative example of how retrofitting strategies can fail. This argument will require some understanding of how centralized query optimizers work.  Therefore, we will divide this discussion into two parts. The first installment will provide a background on centralized query optimization; the second installment will show why retrofitting a centralized query optimizer to work on the grid can lead to poor performance when evaluating queries.


Part 1:  A Primer on Centralized Query Optimization

In this installment, we present a primer on centralized query optimization.  

The purpose of a query optimizer is to produce a cost-effective evaluation plan (or just plan) for any query submitted to the database. The basic strategy used to come up with this plan is largely the same for every query optimizer:

a) It first formulates a set of candidate plans that could be used to evaluate the query

b) It then applies a cost model to predict the execution time (cost) of each of the candidate plans. A cost model consists of a set of formulas that specify the sizes of intermediate query results, and the cost (e.g., time) required to produce them. For example, a simplistic cost model measures cost as the number of disk reads required to evaluate the query, with the idea that queries that perform the fewest disk reads will execute in the least time.

c)  Upon evaluating the cost of each candidate plan, the query optimizer then selects the plan with least cost.

One of the most crucial design decisions that affects the effectiveness of a query optimizer lies in how it limits the size of the space of candidate plans (the search space) that it must consider. Specifically, a query that includes multiple tables in its FROM clause can be evaluated using any of a number of plans that differ only by the order in which these tables are joined. Consider, for example, the SQL query fragment below:

       SELECT     *
       FROM      T1, T2, T3, T4
       WHERE     ...

This query must join 4 tables: T1, T2, T3, and T4. The order in which pairs of tables are joined can vary. For example, the binary tree below (hereafter referred to as a join plan) shows one possible join ordering.

img1.jpgThe join plan above specifies that the first join to be performed is of T1 and T2 (the "bowtie" icon specifies a join), followed by the result being joined with T3, and the result of this in turn being joined with T4. This join plan has a structure which is left-deep (or equivalently, right-shallow) because the right branch of every join in the plan is a base table.  

For the 4-table query above, there are 4! = 24 different left-deep join plans that differ according to which tables correspond to which leaves of the tree (4! = the number of sequences of a set of 4 items). Aside from the left-deep plans, there are 4 other join plan structures that are possible for the query above as illustrated below.  Note that each of these join plan structures also has 24 variations given a query with 4 tables (by permuting the tables at the leaves), so in all, there are 5 * 24 = 120 join plans for an optimizer to consider for this query.

opt_img2.jpg
In general, given n tables to be joined, there are:  

(2(n-1))!
---------------
n! * (n-1)!

possible join plan structures(1), and for each join plan structure, n! possible join plans, giving a total of:

(2(n-1))!
---------------
(n-1)!
 
join plans that an optimizer could consider. As the number of tables in a query grows, the number of join plans to consider quickly becomes infeasible. For example, whereas a query with 4 tables requires consideration of 120 join plans, a query with 5 tables requires consideration of 151,200 join plans, a query with 6 tables requires consideration of 3,991,680 join plans, and so on.

To cope with this enormous search space, all query optimizers must somehow limit the set of join plans considered. IBM's System R (from the late 1970s) first introduced the idea of limiting the search space to the set of join plans with a left-deep join plan structure because left-deep plans ensure that every binary join is performed with at least one participant table on disk, thereby ensuring that a join operator can produce output incrementally as its input data arrives (pipelining). The left-deep restriction reduces the number of join plans to consider for a query of n tables to n!, and dynamic programming techniques can be used to find the "best" query plan in this space in exponential time. In practice, this is a reasonable amount of time to process queries consisting of roughly 30 tables or fewer (YMMV), and thus, this heuristic is still used to narrow the search space of most commercial DBMS. 

Of course, there are many other challenges in designing an effective query optimizer aside from managing the search space, including proper choices of access methods and indexes, query unnesting, etc. But in the next installment of this blog, I will show how the typical retrofitted query optimizer determines its search space for plans that apply to the grid and how the resulting optimizer can fail to produce appropriate plans.
 
(1) This is the known as the nth Catalan number, which specifies (among other things) the number of binary tree "shapes" consisting of n leaves.

Part 2 will be available next week . . .

]]> http://databasecolumn.vertica.com/2008/06/designing-systems-for-the-grid.html DBMS innovations that will make analytics in the cloud a reality tag:www.databasecolumn.com,2008://1.37 2008-06-03T22:08:04Z 2008-06-03T22:30:55Z There will soon be a myriad of announcements of DBMS offerings in the cloud. Many of these will NOT be marriages made in heaven. However, the most innovative new DBMS software married to new cloud computing services are here today and truly take advantage of the cloud architecture in order to change the economics and the responsiveness of business analytics. Jerry Held
In my last article, I described how I think cloud computing will change the economics of business intelligence (BI) and enable a variety of new analytic data management projects and business possibilities. It does so by making the hardware, networking, security, and software needed to create data marts and data warehouses available on demand with a pay-as-you-go approach to usage and licensing.

A computing cloud, such as the Amazon Elastic Compute Cloud, is composed of thousands of commodity servers running multiple virtual machine instances (VMs) of the applications hosted in the cloud. As customer demand for those applications changes, new servers are added to the cloud or idled and new VMs are instantiated or terminated.

Cloud computing infrastructure differs dramatically from the infrastructure underlying most in-house data warehouses and data marts. There are no high-end servers with dozens of CPU cores, SANs, replicated systems, or proprietary data warehousing appliances available in the cloud. Therefore, a new DBMS software architecture is required to enable large volumes of data to be analyzed quickly and reliably on the cloud's commodity hardware. Recent DBMS innovations make this a reality today, and the best cloud DBMS architectures will include:

  1. Shared-nothing, massively parallel processing (MPP) architecture. In order to drive down the cost of creating a utility computing environment, the best cloud service providers use huge grids of identical (or similar) computing elements. Each node in the grid is typically a compute engine with its own attached storage. For a cloud database to successfully "scale out" in such an environment, it is essential that the database have a shared-nothing architecture utilizing the resources (CPU, memory, and disk) found in server nodes added to the cluster. Most databases popularly used in BI today have shared-everything or shared-storage architectures, which will limit their ability to scale in the cloud.

  2. Automatic high availability. Within a cloud-based analytic database cluster, node failures, node changes, and connection disruptions can occur. Given the vast number of processing elements within a cloud, these failures can be made transparent to the end user if the database has the proper built-in failover capabilities. The best cloud databases will replicate data automatically across the nodes in the cloud cluster, be able to continue running in the event of 1 or more node failures ("k-safety"), and be capable of restoring data on recovered nodes automatically -- without DBA assistance. Ideally, the replicated data will be made "active" in different sort orders for querying to increase performance.

  3. Ultra-high performance. One of the game-changing advantages of the cloud is the ability to get an analytic application up quickly (without waiting for hardware procurement). However, there can be some performance penalty due to Internet connectivity speeds and the virtualized cloud environment. If the analytic performance is disappointing, the advantage is lost. Fortunately, the latest shared-nothing columnar databases are designed specifically for analytic workloads, and they have demonstrated dramatic performance improvements over traditional, row-oriented databases (as verified by industry experts, such as Gartner and Forrester, and by customer benchmarks). This software performance improvement, coupled with the hardware economies of scale provided by the cloud environment, results in a new economic model and competitive advantage for cloud analytics.

  4. Aggressive compression. Since cloud costs are typically driven by charges for processor and disk storage utilization, aggressive data compression will result in very large cost savings. Row-oriented databases can achieve compression factors of about 30% to 50%; however, the addition of necessary indexes and materialized views often swells databases to 2 to 5 times the size of the source data. But since the data in a column tends to be more similar and repetitive than attributes within rows, column databases often achieve much higher levels of compression. They also don't require indexes. The result is normally a 4x to 20x reduction in the amount of storage needed by columnar databases and a commensurate reduction in storage costs.

  5. Standards-based connectivity. While there are a number of special-purpose file systems that have been developed for the cloud environment that can provide high performance, they lack the standard connectivity needed to support general-purpose business analytics. The broad base of analytic users will use existing commercial ETL and reporting software that depend on SQL, JDBC, ODBC, and other DBMS connectivity standards to load and query cloud databases. Therefore, it's imperative for cloud databases to support these connection standards to enable widespread use of analytic applications.
In summary, cloud databases with the architectural characteristics described above will be able to not just run in the cloud, but thrive there by:

  • "Scaling out," as the cloud itself does

  • Running fast without high-end or custom hardware

  • Providing high availability in a fluid computing environment

  • Minimizing data storage, transfer, and CPU utilization (to keep cloud computing fees low)


]]> http://databasecolumn.vertica.com/2008/06/dbms-innovations-and-cloud.html Database Column contributor: Daniel Abadi tag:www.databasecolumn.com,2008://1.40 2008-05-15T01:49:30Z 2008-07-18T01:52:42Z Daniel's research interests are in database system architecture and implementation, cloud computing, and the Semantic Web. He currently serves on the Yale computer science faculty as an Assistant Professor. At Yale heteaches both undergraduate and graduate level classes on database systems, and directs DR@Y, the database research group at Yale.... Admin teaches both undergraduate and graduate level classes on database systems, and directs DR@Y, the database research group at Yale. Before joining Yale, he spent four years at the Massachusetts Institute of Technology
where he published numerous papers on column-store databases, lead the C-Store development effort, and wrote his Ph.D. dissertation on "Query Execution in Column-Oriented Database Systems". Daniel has been a recipient of a Churchill Scholarship, an NSF Graduate Research Fellowship, and a VLDB best paper award.

For more, Daniel's Website can be found at: http://cs-www.cs.yale.edu/homes/dna/ ]]> http://databasecolumn.vertica.com/2008/05/database-column-contributor-da.html There's a bright cloud on the horizon ... and it will transform the economics of BI tag:www.databasecolumn.com,2008://1.36 2008-05-13T22:07:09Z 2008-05-21T12:32:44Z Cloud computing is ushering in a new era of analytic data management for business intelligence by enabling organizations to analyze terabytes of data faster and more economically than ever before. The key change: It's delivered in an on-demand basis. This alternative to traditional, in-house data analytics infrastructure will transform the economics of BI and open up many new possibilities for organizations of all sizes. Jerry Held
Organizations no longer need to justify spending hundreds of thousands of capital expense budget dollars for upfront hardware and software purchases or spend weeks waiting for hardware delivery and installation. Instead, they can sign up to tap into a computing cloud, such as Amazon's Elastic Compute Cloud (Amazon EC2), and have a dedicated, high-performance analytic database cluster provisioned and hosted for them. They can then use it on a pay-per-use basis, usually for a monthly fee.

This shouldn't be confused with software as a service (SaaS) models. Cloud customers are, in effect, renting dedicated servers and the people needed to house, secure, and manage them. These cloud offerings are more secure than multi-tenant SaaS models in which data from one customer may co-exist with data from another customer within the same application. Cloud customers have full control over server and firewall settings to ensure security.
 

Transforming BI

This alternative to traditional, in-house data analytics infrastructure will transform the economics of BI and open up many new possibilities for organizations of all sizes. I expect cloud-based analytics to impact BI in the following ways:

  • New BI technology adoption will accelerate. The cloud will become the de facto platform for evaluating new software. The cloud enables software companies to make new technology available to many more evaluators on a self-service basis. Unlike free software downloads, evaluators are spared the time and expense of finding hardware and going through installation and setup and the other tasks required to get the software up and running. As a result, the adoption of new BI software technology should increase much faster than it has in the past.

  • Organizations will conduct more short-term ad-hoc analysis. The need for data marts often arises suddenly, usually in response to new business conditions or events. The need may also last only a short time -- maybe just a few weeks or months. For example, a company might need to suddenly analyze manufacturing data in the wake of a quality or safety breakdown, or it may need a new price plan in response to a new competitor or market condition. The cloud gives companies a way to respond to these requests immediately -- get a mart created in a few hours or days, have business people slice and dice to their hearts' content for as long as they need to, then cancel the cloud cluster, and it goes away with no leftover hardware or software licenses. The cloud makes it economically feasible to conduct more of these short-lived projects.

  • Lines of business will have the flexibility to fund more data mart projects. Because there are no long-term financial commitments required, lines of business can pay monthly cloud-based analytic database usage fees out of the operating expense budgets they directly control rather than going through a lengthy capital expenditure approval process. Companies can fund departmental, proof of concept, and ad-hoc analytic data projects on-demand, giving them the agility to respond to BI needs faster than their competitors and increase the quality of their strategy setting and execution.

  • Data warehousing will increase within medium-size businesses. Despite their size, many midmarket companies have very large volumes of data they would like to analyze. Hedge fund companies with only a handful of IT people at their disposal need to analyze tens of terabytes of stock market history data to hone their trading strategies. Young bio-techs are in similar situations -- they have hundreds of gigabytes of genomic data to cull through. Cloud-based analytic databases will enable them to warehouse and analyze terabytes of data even though their BI budgets and staff are a small fraction of larger enterprises.

  • The analytic SaaS market will develop faster. Companies that collect economic, market, advertising, scientific, and other data and then offer customers the ability to analyze it on line -- analytic SaaS -- will come to market faster and in greater numbers. They will be able to bring their solutions to market with much less risk and cost by basing them on the cloud during the early stages of growth. The companies can use the hundreds of thousands of dollars saved on in-house data center development to invest in customer acquisition, product development, and other market development activities. After the viability of the business model is proven, analytic data can be migrated to internal databases from the cloud if needed.

In order for these pioneering analytic cloud projects to succeed -- especially as data volumes grow -- they will require a database architecture that is designed to function efficiently in elastic, hosted computing environments like the cloud. At a minimum, such databases must include the following architectural features:

  • "Scale-out" shared-nothing architecture to handle changing analytic workloads as elastically as the cloud

  • Aggressive data compression to keep storage costs low

  • Automatic grid replication and failover to provide high availability in the cloud

I'll discuss these cloud analytic database architectural features and others in more detail in my next post.

]]> http://databasecolumn.vertica.com/2008/05/cloud-and-bi.html Supporting Column Store Performance Claims tag:www.databasecolumn.com,2008://1.35 2008-03-14T14:58:21Z 2008-03-20T15:14:54Z In this post, Mike Stonebraker tackles two issues with regards to row- versus column-store databases. In the first issue, he looks at performance challenges given the demands of users. In the second issue, he discusses the availability of third-party connectivity as well as automatic database design tools. Michael Stonebraker

Issue No. 1: Addressing the Performance Claim

There is a well-known adage: "If it's not broken, don't fix it." Any client who is satisfied with his current data warehouse solution would be ill-advised to change it. However, Vertica sees enormous pain in the data warehouse market, due to combinations of the following factors:

  1. Increasing query complexity. The size of data warehouses are going up faster than disks are getting cheaper. An increasing number of people are being trained and equipped to analyze information, and they desire to correlate more and more data. Since query complexity goes up more than linearly with warehouse size, this means that warehouse problems are getting harder over time - not easier.

    Many warehouse DBAs can predict with some precision when they will "hit the wall" with their current solution. The result of hitting the wall is an expensive guided tour through the enterprise wallet for more hardware, different software, or both.

  2. The desire for real-time warehouses. Most warehouses are loaded periodically and are out of date by ½ of the length of this periodicity. But many enterprises want more timely business intelligence. The obvious solution is to "trickle load" data in parallel with user queries. However, this is impossible in many current warehouse products.

  3. The desire for timely answers. In many current products, an ad-hoc query requires one to go out to lunch before the answer is returned. Sometimes response time is even worse than this. The result of delayed answers is lost human productivity and a move to "batch thinking" rather than "interactive thinking."

If the user is in serious pain with his current warehouse solution, then the obvious answer is "find a better one."

In summary, performance is either black or white. Either it is good enough or it isn't. And if performance is important--column databases have demonstrated orders better magnitude performance (50x in round numbers) than row-stores in customer benchmarks and TPC-H benchmarks. Industry experts, such as Gartner, have validated these results (click on this link to launch a Vertica-Gartner podcast on this topic).

We see column databases out-perform row stores by large margins in customer benchmark settings on a frequent basis. Here are some results a customer measured very recently:

benchmark_table.jpgAnd remember -- it doesn't have to be an either-or decision. As Don Feinberg of Gartner suggests in his podcast, using a column database in conjunction with an enterprise data warehouse (EDW) can provide users with better analytic performance and also to offload certain analyses from the EDW in order to improve its performance without costly upgrades or re-designs.


Issue No. 2: Of Connectivity and Automatic Design Tools

My second point concerns the perceived connectivity advantages of row stores. Vertica (and other column-oriented databases) use ODBC/JDBC interfaces. As such, they get connectivity to all of the 3rd party tools that row stores utilize. Hence, "connectivity" is a wash between row stores and column stores. Both kinds of products connect to most -- if not all -- of the popular tools.  

Lastly, there is a perception that column database introduce additional complexity for DBAs. This is untrue. Vertica includes an automatic physical database designer that helps a DBA set all of the performance options in Vertica. Hence, there is no "complexity" factor; manual optimization by a human is a thing of the past. DB2 has a similar tool. The real question is, "How good is the automatic tool from any given vendor?" We are confident in Vertica's ability to automatically generate a good physical design; it would be interesting to conduct a comparative "out-of-the-box" performance benchmark that measured automatic tool effectiveness.



]]> http://databasecolumn.vertica.com/2008/03/supporting-column-store-perfor.html In response to Monash's post on the four categories of RDBMS tag:www.databasecolumn.com,2008://1.33 2008-02-18T18:52:11Z 2008-03-14T15:36:09Z In this response to a Curt Monash post over at the DBMS2 blog, Mike Stonebraker offers his reactions. He sees two categories of relational analytic/data warehouse databases, row stores and column stores, and notes that they have very different characteristics and should not be lumped together. He also points out that if high performance is required, current high-end relational engines can be beaten by a factor of 80 or so on TPC-C. Michael Stonebraker here. In this post, I will discuss the issue I have with Curt's category characterization of DBMS systems.

First, I see two categories of relational analytic/data warehouse databases, row stores and column stores. They have very different characteristics. I would not lump them together, as this post does. Moreover, I expect the overwhelming majority of analytic data management workloads to move to column stores over time as these products become more mature because of the overwhelming performance advantage they offer on most analytic workloads.

I don't know what competitive challenge to current high-end OLTP vendors Curt has in mind; however, I will offer my own. If performance is not a big issue, then current open-source relational DBMSs work quite well. As a result, I expect the "low end" to go to open source systems.

On the other hand, if high performance is required, then I have shown in a recent paper (2007 VLDB proceedings) that current high-end relational engines can be beaten by a factor of 80 or so on TPC-C. This new collection of ideas may be leveragable into ultra-fast future commercial products that will challenge the current vendors at the high end. I think it is likely that the current vendors will be "caught in the middle."

Lastly, most customers that I talk to are upset with the "out-of-box" experience of the current offerings from the high-end vendors. The products are hard to install, hard to tune, hard to learn, and just generally hard to use. If the products don't get much easier to use, then data administration costs will go to 100% sooner or later -- relegating these products to niche markets.

]]> http://databasecolumn.vertica.com/2008/02/responding-to-monash-2.html Responding to Monash's recent post on diversity of database systems tag:www.databasecolumn.com,2008://1.31 2008-02-16T18:11:22Z 2008-02-16T18:39:10Z In this post, Mike Stonebraker comments on a post over at DBMS2 titled "Database management system choices - overview." Mike makes two points. First, he offers his list of the different types of DBMSs that he sees as viable. Second, he discusses OLTP and the shared nothing architecture. Michael Stonebraker DBMS2 blog that makes the argument that in the database world, one size does not fit all. In response, I have one comment and one quibble (read the post in its entirety here).


The comment: Many different kinds of DBMSs

Curt's post leads to the obvious question: Just how many different kinds of viable DBMSs can we expect to see? I can imagine the following:

  1. OLTP DBMSs focused on fast, reliable transaction processing

  2. Analytic/Data Warehouse DBMSs focused on efficient load and ad-hoc query performance

  3. Science DBMSs -- after all MatLab does not scale to disk-sized arrays

  4. RDF stores focused on efficiently storing semi-structured data in this format

  5. XML stores focused on semi-structured data in this format

  6. Search engines -- the big players all use proprietary engines in this area

  7. Stream Processing Engines focused on real-time StreamSQL

  8. "Lean and Mean," less-than-a-database engines focused on doing a small number of things very well (embedded databases are probably in this category)

  9. MapReduce and Hadoop -- after all Google has enough "throw weight" to define a category


I expect all of these to be architected differently, with the possible exception of RDF stores, which are efficiently supported on top of column stores and focused on the warehouse market.


The quibble: OLTP demands shared nothing

Every high-end OLTP application is currently requiring 7 x 24 x 365 x 10 years of availability. That is, the database has only one state, which is "up."  Hence, high availability -- in the face of crashes as well as disasters -- is a requirement. Disaster recovery requires replication over a wide area network; recovery from crashes, requires LAN-based replication. As such, every OLTP system is, in fact, deployed over a shared-nothing architecture, encompassing both LAN and WAN networking.

]]> http://databasecolumn.vertica.com/2008/02/responding-to-monash-1.html