Profiling, what-if analysis, and cost-based optimization of MapReduce programs
Proceedings of the VLDB EndowmentPublished 1 August 2011
Herodotos Herodotou, Shivnath Babu
Citations370
SJR quartileQ1
SJR score1.83
SNIP1.80
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work introduces, to its knowledge, the first Cost-based Optimizer for simple to arbitrarily complex MapReduce programs, which focuses on the optimization opportunities presented by the large space of configuration parameters for these programs.
Abstract
MapReduce has emerged as a viable competitor to database systems in big data analytics. MapReduce programs are being written for a wide variety of application domains including business data processing, text analysis, natural language processing, Web graph and social network analysis, and computational science. However, MapReduce systems lack a feature that has been key to the historical success of database systems, namely, cost-based optimization. A major challenge here is that, to the MapReduce system, a program consists of black-box map and reduce functions written in some programming language like C++, Java, Python, or Ruby. We introduce, to our knowledge, the first Cost-based Optimizer for simple to arbitrarily complex MapReduce programs. We focus on the optimization opportunities presented by the large space of configuration parameters for these programs. We also introduce a Profiler to collect detailed statistical information from unmodified MapReduce programs, and a What-if Engine for fine-grained cost estimation. All components have been prototyped for the popular Hadoop MapReduce system. The effectiveness of each component is demonstrated through a comprehensive evaluation using representative MapReduce programs from various application domains.
Keywords
Computer Science
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
Hadoop: The Definitive Guide
2,714 Citations2009Tom White
This comprehensive resource demonstrates how to use Hadoop to build reliable, scalable, distributed systems: programmers will find details for analyzing large datasets, and administrators will learn how to set up and run Hadoops clusters.
Proceedings of the VLDB EndowmentHadoopDB
856 Citations2009A. A. ABOUZEID, Kamil Bajda-Pawlikowski +3 more
This paper explores the feasibility of building a hybrid system that takes the best features from both technologies; the prototype built approaches parallel databases in performance and efficiency, yet still yields the scalability, fault tolerance, and flexibility of MapReduce-based systems.
Proceedings of the VLDB EndowmentHaLoop
688 Citations2010Yingyi Bu, Bill Howe +2 more
HaLoop is presented, a modified version of the Hadoop MapReduce framework that is designed to serve iterative applications and dramatically improves their efficiency by making the task scheduler loop-aware and by adding various caching mechanisms.
Starfish: A Self-tuning System for Big Data Analytics.
572 Citations2011Herodotos Herodotou, Harold Lim +5 more
Starfish is introduced, a self-tuning system for big data analytics that builds on Hadoop while adapting to user needs and system workloads to provide good performance automatically, without any need for users to understand and manipulate the many tuning knobs in Hadoops.
Data-intensive text processing with MapReduce
451 Citations2009Jimmy Lin, Chris Dyer
A comparison of join algorithms for log processing in MaPreduce
410 Citations2010Spyros Blanas, Jignesh M. Patel +4 more
Key implementation details of a number of well-known join strategies in MapReduce are described and a comprehensive experimental comparison of these join techniques on a 100-node Hadoop cluster is presented.
Proceedings of the VLDB EndowmentThe performance of MapReduce
394 Citations2010Dawei Jiang, Beng Chin Ooi +2 more
By carefully tuning these factors, the overall performance of Hadoop can be improved by a factor of 2.5 to 3.5, and is thus more comparable to that of parallel database systems.
Proceedings of the VLDB EndowmentHadoop++
368 Citations2010Jens Dittrich, Jorge-Arnulfo Quiané-Ruiz +4 more
This paper proposes a new type of system named Hadoop++: it boosts task performance without changing the Hadooper framework at all (Hadoop does not even 'notice it'), and shows the superiority of Hadoo++ over both Hadoops and HadoOPDB for tasks related to indexing and join processing.
Optimizing joins in a map-reduce environment
331 Citations2010Foto Afrati, Jeffrey D. Ullman
The problem of optimizing the shares, given a fixed number of Reduce processes, is studied, and an algorithm for detecting and fixing problems where an attribute is "mistakenly" included in the map-key is given.
Towards automatic optimization of MapReduce programs
285 Citations2010Shivnath Babu
This position paper makes a case for techniques to automate the setting of tuning parameters for MapReduce programs to provide good out-of-the-box performance for ad hoc Map Reduce programs run on large datasets.
Proceedings of the VLDB EndowmentMRShare
226 Citations2010Tomasz Nykiel, Michalis Potamias +3 more
This paper proposes a sharing framework, MRShare, that transforms a batch of queries into a new batch that will be executed more efficiently, by merging jobs into groups and evaluating each group as a single query.
No one (cluster) size fits all
220 Citations2011Herodotos Herodotou, Fei Dong +1 more
The Elastisizer is introduced, a system to which users can express cluster sizing problems as queries in a declarative fashion and provides reliable answers to these queries using an automated technique that uses a mix of job profiling, estimation using black-box and white-box models, and simulation.
A simulation approach to evaluating design decisions in MapReduce setups
206 Citations2009Guanying Wang, Ali R. Butt +2 more
The resulting simulator, MRPerf, captures such aspects of MapReduce setups as node, rack and network configurations, disk parameters and performance, data layout and application I/O characteristics, among others, and uses this information to predict expected application performance and can serve as a tool for optimizing existing MapReduces setups as well as designing new ones.
Proceedings of the VLDB EndowmentAutomatic optimization for MapReduce programs
177 Citations2011Eaman Jahani, Michael Cafarella +1 more
Manimal is shown, which automatically analyzes MapReduce programs and applies appropriate data-aware optimizations, thereby requiring no additional help at all from the programmer, and that it yields speedups of up to 1,121% on previously-written Map Reduce programs.
Skew-resistant parallel processing of feature-extracting scientific user-defined functions
128 Citations2010YongChul Kwon, Magdalena Bałazińska +2 more
SkewReduce is a new system implemented on top of Hadoop that enables users to easily express feature extraction analyses and execute them efficiently, and can improve execution times by a factor of up to 8 compared to a naive implementation.
A recursive random search algorithm for large-scale network parameter configuration
127 Citations2003Tao Ye, Shivkumar Kalyanaraman
A new heuristic search algorithm, Recursive Random Search (RRS), for large-scale network parameter optimization, based on the initial high-efficiency feature of random sampling, which has been applied to the configuration of several network protocols, such as RED, OSPF and BGP.
arXiv (Cornell University)Hadoop Performance Models
112 Citations2011Herodotos Herodotou
A detailed set of mathematical performance models for describing the execution of a MapReduce job on Hadoop are described, which can be used to estimate the performance of Map Reduce jobs as well as to find the optimal configuration settings to use when running the jobs.
Automatic optimization of parallel dataflow programs
66 Citations2008Christopher Olston, Benjamin Reed +2 more
A set of optimization strategies for large-scale parallel dataflow systems, e.g., Dryad and Map-Reduce, are proposed, drawing on and extending techniques from the database community.