MapReduce vs SQL Databases

A Comparison of Approaches to Large-Scale Data Analysis: MapReduce vs. DBMS Benchmarks

...we present the results of running the benchmark on a 100-node cluster to execute each task. We tested the publicly available open-source version of MapReduce, Hadoop [1], against two parallel SQL DBMSs, Vertica [3] and a second system from a major relational vendor.

First, as we demonstrate in Section 4, at 100 nodes the two parallel DBMSs range from a factor of 3.1 to 6.5 faster than MapReduce on a variety of analytic tasks. While MR may indeed be capable of scaling up to 1000s of nodes, the superior efficiency of modern DBMSs alleviates the need to use such massive hardware on datasets in the range of 1–2PB (1000 nodes with 2TB of disk/node has a total disk capacity of 2PB). For example, eBay’s Teradata configuration uses just 72 nodes (two quad-core CPUs, 32GB RAM, 104 300GB disks per node) to manage approximately 2.4PB of relational data. As another example, Fox Interactive Media’s warehouse is implemented using a 40-node Greenplum DBMS. Each node is a Sun X4500 machine with two dual-core CPUs, 48 500GB disks, and 16 GB RAM (1PB total disk space) [7]. Since few data sets in the world even approach a petabyte in size, it is not at all clear how many MR users really need 1,000 nodes.

In section 3.1 there's some points made about the advantages of databases over MR in relation to data integrity, "...a MR framework and its underlying distributed storage system has no knowledge of these rules, and thus allows input data to be easily corrupted with bad data. By again separating such constraints from the application and enforcing them automatically by the run time system, as is done by all SQL DBMSs, the integrity of the data is enforced without additional work on the programmer’s behalf."

They mention that "all DBMSs require that data conform to a well-defined schema, whereas MR permits data to be in any arbitrary format. Other differences also include how each system provides indexing and compression optimizations, programming models, the way in which data is distributed, and query execution strategies."

If you strip it away they are talking about text processing versus indexed data structures (and other parts of a DBMS).

For loading, "Without using either block-or record-level compression, Hadoop clearly outperforms both DBMS-X and Vertica since each node is simply copying each datafile from the local disk into the local HDFS instance and then distributing two replicas to other nodes in the cluster." The obvious difference to me would be that the SQL databases are creating "...a hash partitioned across all nodes on the salient attribute for that particular table, and then sorted and indexed on different attributes..."

For text processing, they note that the main problems with Hadoop are the start-up costs (10-25 seconds before all Map tasks start) and during the Reduce phase the cost of combining many small files. When you are comparing a fully indexed system versus text processing then you would expect the indexed system to be faster. Compression was also considered an advantage in the systems like Vertica's over Hadoop - where it actually reduced performance. It depends on the work being done whether the overhead of compression is worth the overhead so obviously - it's not explained why compression was a negative for Hadoop.

They also talk about the problems in setting up and configuring the parallel databases over Hadoop, which is not an insignificant difference when you are scaling to 100s and 1000s of nodes.

In the summary they talk about 25 years of database development and the advantages of B-Trees and column stores. It begs the question, then why wasn't a similar system used on the Hadoop infrastructure? MR is really more like distributed processing not an indexed, querying system.

If you took away the distributed layer what they are doing is comparing something like grep (a really bad implementation of grep) with Lucene or MySQL. Would anyone be surprised with the results then? A better comparison would've been comparing it against HBase or other distributed, indexed, data stores like Hive or Cloudbase.

Update: There's a good followup on the hadoop list by Jonathan Gray "Hadoop is not suited for random access, joins, dealing with subsets of
your data; ie. it is not a relational database! It's designed to
distribute a full scan of a large dataset, placing tasks on the same nodes
as the data its processing. The emphasis is on task scheduling, fault
tolerance, and very large datasets, low-latency has not been a priority.
There are no "indexes" to speak of, it's completely orthogonal to what it
does, so of course there is an enormous disparity in cases where that
makes sense. Yes, B-Tree indexes are a wonderful breakthrough in data
technology". He suggested Pig, Hive and Cascading would be more suitable for comparison.

Solid State Drives

I was wondering what the effect would be on data structures and algorithms given the new features of SSD (solid state drives) - that is, drives with ten times the seek performance and improved read speeds. Desktop hard drives are about the same (18% slower) or beat SSDs in a straight line, sequential access, especially writes. In the short term, it looks like solid state drives biggest impact is likely to be in providing laptop drives the same performance as desktop ones.

A secondary short term impact may well be in providing another level of storage between spinning hard disks and other caches. This is mentioned in, "The five-minute rule twenty years later, and how flash memory changes the rules".

The name of their rule refers to the break-even interval between accesses. If a record (or page) is accessed more often, it should be kept in memory; otherwise, it should remain on disk and read when needed.

Not surprisingly, the optimal page size for B-tree indexes on modern high-bandwidth disks is much larger than traditional database systems have employed. The access time dominates for all small page sizes, such that additional byte transfer and thus additional utility are almost free. B-tree nodes of 256 KB are very near optimal...a traditional rotating hard disk, Table 3 indicates 337 seconds or just over 5 minutes.

Due to the lack of mechanical seeking and rotation, the transfer time dominates even for small pages. The optimal page size for B-trees on flash memory is 2 KB, much smaller than for traditional disk drives. In Table 3, the break-even interval for pages of 4 KB is 351 seconds.

Using O’Neil’s SB-trees, extents of 256 KB are the units of transfer between flash memory and disk, whereas pages of 4 KB are the unit of transfer between RAM and flash memory.

Mentions this paper, SB-Tree : An Index-Sequential Structure for High-Performance Sequential Access.

Via, Flash Memory and Databases.

Wondering About Transactions

Transactionless

A couple of years ago I was talking to a couple of friends of mine who were doing some work at eBay. It's always interesting to hear about the techniques people use on high volume sites, but perhaps one of the most interesting tidbits was that eBay does not use database transactions.

My immediate follow-up to the news of transactionless was to ask what the consequences were for the application programmer, in particular the overall feeling about transactionlessness. The reply was that it was odd at first, but ended up not being a big deal - much less of a problem than you might think. You have to pay attention to the order of your commits, getting the more important ones in first. At each commit you have to check that it succeeded and decide what to do if it fails.

I've been wondering about the usefulness of transactions for sometime and ACID in particular. One of the easiest to dismiss, suprisingly perhaps, is isolation. For example, skip list implementations ruin it as the data may change during iteration and it can easily be avoided by writing the information of one transaction to a file to be read by something else in another (either by accident or on purpose). The alternative might be something like CAS and RDF triples. Expecting application programmers to do it sounds awful however.

Also, noticed by, "Living Without Database Transactions".

Leading the Way

Semantic Breakthrough "McDonald Bradley's Parmelee agrees, saying that defining terms in an ontology is not very different from what developers do in the database world. "The same logic that goes into an ER [entity relationship] diagram or a multidimensional database allows you to distinguish between objects and relationships in an ontology," she says. "We are conducting lab experiments associated with a large data integration project in which we use the Oracle Spatial RDF capabilities of Oracle Database 10g for storing data in RDF format. This format preserves the true graph-based representation of the ontology model, rather than trying to fit a graph-based structure into a standard relational mold.""

""Oracle is leading the marketplace by embedding Semantic Web capabilities into its database, enabling computers to aggregate data and make inferences about data relationships," he says. "Oracle is in a great position here since the companies that benefit the most from the Semantic Web are large, distributed, global operations, where Oracle is already the database vendor of choice.""

Better searching, Web Services, grid computing, and enterprise integration are all mentioned as applications.

Via, Semantic Mainstream.

A Link in Time

• Getting more than what you pay for with open source databases. The tale of using a free database, using a commercial one and then putting the free one back. A quote: "There are a lot of companies out there paying dearly for commercial databases (and operating systems for that matter). As far as I'm concerned they might as well be flushing that money down the toilet. Actually, they might be better off. We certainly would have been."


• For the metrically minded, "Two Motivational Metrics for Agile Teams". So as long as you convince people that "Time to Obstacle Removal" and "Obstacles Removed per Iteration" are good metrics.


• The, "I'm sick of the comparison between building and software" rant.


• Martin Fowler has recently updated his "The New Methodology" with half a dozen or so flavours of agile, which one are you?


• Don't Click It for those people with zero button mice. The first example of a gesture to replace a click just seems ridiculously hard.


• Examples of using Chickenfoot for Firefox: Rewrite the Web
  The table sort, how to get a book from the library, simple examples and timely.


• Another REST framework - Restlet.


• Getting stuff done - the quick version


• How not to get a PhD