PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic Optimization for MapReduce Programs

Eaman Jahani, Michael J. Cafarella, Christopher Ré

arXiv:1104.3217v1cs.DBcs.DC

TL;DR

MapReduce systems can be substantially slower and more hardware-intensive than relational databases, while existing systems often do not apply data-semantics optimizations without developer changes. Manimal statically analyzes unmodified MapReduce programs to detect safe selections, projections, and compression opportunities, achieving speedups up to 1,121% on published programs.

  • Problem

    MapReduce systems lag behind relational databases in query-processing sophistication and runtime efficiency, with similar queries running 2-50x slower on identical hardware.

  • Method

    Manimal statically analyzes wholly unmodified MapReduce programs and detects safe selection, projection, and data-compression optimizations without requiring developer code changes.

  • Results

    Manimal achieved speedups ranging from 296% to 1,121% on real MapReduce code, including previously published benchmark programs.

  • Takeaways & Limitations

    Manimal provides data-semantics-driven optimization for MapReduce without requiring code changes from developers.

  • Takeaways & Limitations

    Manimal can miss safe optimizations when program behavior is difficult to analyze, including selection through a Java Hashtable in Benchmark 4.

Abstract

from arXiv · show

The MapReduce distributed programming framework has become popular, despite evidence that current implementations are inefficient, requiring far more hardware than a traditional relational databases to complete similar tasks. MapReduce jobs are amenable to many traditional database query optimizations (B+Trees for selections, column-store- style techniques for projections, etc), but existing systems do not apply them, substantially because free-form user code obscures the true data operation being performed. For example, a selection in SQL is easily detected, but a selection in a MapReduce program is embedded in Java code along with lots of other program logic. We could ask the programmer to provide explicit hints about the program's data semantics, but one of MapReduce's attractions is precisely that it does not ask the user for such information. This paper covers Manimal, which automatically analyzes MapReduce programs and applies appropriate data- aware optimizations, thereby requiring no additional help at all from the programmer. We show that Manimal successfully detects optimization opportunities across a range of data operations, and that it yields speedups of up to 1,121% on previously-written MapReduce programs.

1. INTRODUCTION

Manimal addresses MapReduce’s efficiency gap with relational systems by automatically detecting data semantics in unmodified programs and applying data-aware optimizations. The system targets this challenge without requiring developer code changes or explicit semantic annotations.

  • Challenge: MapReduce semantics are difficult to optimize automatically because programs use traditional languages, bytestreams, and no explicitly declared metadata.Relational systems expose semantics through query languages and metadata, whereas MapReduce programs obscure the underlying data operations.
  • Results: Up to 1,121% speedups were observed on wholly unmodified, previously published MapReduce programs using identical hardware.The experiments included all benchmarks published by Pavlo and additional programs examining individual optimization methods.
  • Approach: Manimal automatically analyzes wholly unmodified MapReduce programs to detect safe optimization opportunities.Its best-effort analyzer prioritizes safety, sacrificing potential optimizations when non-safety is possible.
  • Contribution: Manimal is presented as the first MapReduce system to use data-semantics-driven optimizations without requiring developer code changes.The paper substantially expands earlier preliminary work with new techniques, technical detail, and full experimental results.
  • Approach: The system detects and exploits three optimization types: selection, projection, and data compression.These optimizations target data-centric programming idioms embedded in ordinary program code.

2. SYSTEM OVERVIEW

Manimal combines static analysis, index generation, optimization planning, and execution to optimize MapReduce jobs without modifying their source programs. Its overview covers selection, projection, compression, and the practical constraints governing when indexes are worthwhile.

  • System architecture: The analyzer produces optimization descriptors, the optimizer selects an execution plan using indexes, and the execution fabric runs the resulting program.The optimized execution descriptor may accompany a potentially modified copy of the original program.
  • System architecture: Manimal requires no programmer modifications, while preserving the output expected from conventional MapReduce execution.Submitting a job may additionally yield an index-generation program for later administrative use.
  • Scope: Manimal currently focuses on single, mainly relational-style MapReduce programs rather than program chains or tasks such as inverted-index construction.The authors identify broader text-processing and iterative numeric workloads as possible future targets.
  • Selection: Selection optimization uses detected conditional predicates and B+Tree indexes to skip map invocations that would produce no output.Manimal’s distinctive contribution is detecting these selections automatically in unmodified developer code.
  • Projection: Projection optimization stores only fields examined by the user code, reducing processed bytes without changing program behavior.The technique resembles a simplified column-store approach and can potentially be extended with column-groups.
  • Compression: Delta compression stores differences between numeric values rather than absolute values, enabling storage savings when values have small deltas.Manimal discovers field and numeric-type information through serialized input classes.
  • Compression: Direct-operation compression can process compressed values directly when the compressed representation preserves the operation needed by map().Equality-only URL tests are one example; sorted final output can constrain use on map() output keys.
  • Operational constraints: Indexing is not worthwhile for ephemeral read-once files because indexes incur disk-space and computation costs.Choosing among several possible indexes also depends on index-space budget and expected future workloads.

3. ANALYZER IN DEPTH

Manimal’s analyzer translates MapReduce code into identifiable data operations using static control-flow and data-flow analysis, while conservatively rejecting unsafe optimizations. It currently targets selection, projection, and compression within map(), using functional-dependence checks to preserve program semantics.

  • Analyzer role: The analyzer is central to moving MapReduce programs from opaque binaries into identifiable data operations that can receive automatic optimization.Its goal is to apply established optimization techniques without requiring programmers to modify their programs.
  • Limitations: The current analyzer handles only a subset of possible optimizations, while complex cases such as iterative jobs, joins, arbitrary control flow, and some language features remain difficult or unsupported.The authors specifically note limitations involving cross-job data flow, complicated joins, jumps, and language constructs that obstruct accurate analysis.
  • Static analysis: Static analysis builds control-flow graphs and use-def chains to inspect possible execution paths and determine which definitions influence emitted output.The analyzer uses code inspection rather than live instrumentation and computes reaching definitions through data-flow analysis.
  • Optimization scope: Manimal currently searches for selection, projection, and compression opportunities at the map() function level.The analyzer operates at a micro-scale; reduce() optimization remains future work.
  • Safety checks: An optimization is considered safe only when the relevant computation depends on map() parameters or constants rather than class members or external variables.This functional test prevents indexed inputs from omitting invocations whose side effects could alter output decisions.
  • Selection analysis: Selection analysis constructs a disjunctive-normal-form formula whose disjuncts represent paths to emit() and whose conjunctions encode required conditional tests.The resulting formula evaluates true exactly when the function emits a tuple.

4. EXPERIMENTS

The experiments evaluate Manimal’s analyzer recall and end-to-end runtime gains on four benchmark programs, while documenting missed optimizations and workload limitations. Manimal achieves substantial speedups on detected opportunities, including more than 11x on Benchmark 1 and roughly one-third of Hadoop’s runtime on Benchmark 2.

  • Evaluation design: Manimal’s experiments measure analyzer recall, overall runtime improvement, and the gains from individual optimization types.The evaluation uses Pavlo et al.’s benchmark programs and includes separate tests of optimization methods.
  • Analyzer recall: The tested workload is limited because few open-source MapReduce programs are available and the benchmarks may overrepresent database-style operations.The programs may underrepresent text-centric and numeric processing, although they align reasonably with surveyed Hadoop applications.
  • Analyzer recall: The analyzer produces no false positives and misses only three optimization opportunities across the tested benchmark programs.The missed cases involve Benchmark 1’s custom serialization and Benchmark 4’s use of Java Hashtable.
  • End-to-end performance: Benchmark 1 achieves greater than 11x speedup over standard Hadoop using a selection index at 0.02% selectivity.The analyzer misses projection and delta-compression opportunities for this task, but the reported projection benefit is undetectable beside the selection gain.
  • End-to-end performance: Benchmark 2 detects projection and delta-compression opportunities and runs in roughly one-third of Hadoop’s time.Its index is 20% of the original input file’s size.
  • End-to-end performance: Benchmark 3 achieves a 6.73x speedup by recognizing a selection predicate that removes all but 0.095% of UserVisits records.Manimal reduces the bytes passing through the processing pipeline, although its result is below join-aware systems’ gains.
  • Overall results: Across four real-life programs, Manimal obtains substantial speedups for three, with two gains roughly commensurate with those of a traditional relational system.The summary also reports that the analyzer’s missed optimizations generally have limited impact, except for Benchmark 4’s selection condition.

5. RELATED WORK

Related work improves MapReduce through scheduling, joins, storage organization, and relational systems, but these approaches differ from Manimal’s automatic optimization of MapReduce programs. Manimal’s compiler-based approach targets data semantics without requiring programmer changes, while remaining compatible with physical optimizations from other systems.

  • MapReduce systems: Prior MapReduce research includes task scheduling, efficient joins, and extensions such as Map-Reduce-Merge.These projects address execution or programming-model improvements rather than the same fully automated optimization approach.
  • Relational integration: HadoopDB combines relational and MapReduce qualities but is a scalable parallel relational database rather than an optimizer for MapReduce programs.Its use of Hadoop internally does not make it a system that optimizes submitted MapReduce code.
  • Index and storage techniques: Hadoop++ requires explicit programmer support, whereas column-oriented storage work requires physical reorganization; both could serve as targets for Manimal.These approaches improve MapReduce performance through index-style or storage-level techniques.
  • Manimal’s approach: Manimal employs compiler techniques and static analysis to apply database-style optimizations automatically to MapReduce programs.The paper positions this approach alongside, but distinct from, prior systems-level and XQuery optimization work.

6. CONCLUSIONS

Manimal automatically optimizes MapReduce programs and obtains substantial speedups on real code. The reported speedups range from 296% to 1,121%, and the system can support further MapReduce optimization techniques.

  • Conclusion: Manimal automatically obtains substantial speedups ranging from 296% to 1,121% on real MapReduce code.The conclusion presents these gains as the system’s overall performance result.
  • Conclusion: Manimal provides a framework for deploying additional MapReduce-optimization research.The paper describes this extensibility as part of the system’s contribution.

A. LAYERED TOOLS

Layered tools such as Pig, Hive, and Mahout generate MapReduce jobs from higher-level interfaces, but their indirection obscures user-program semantics from static analysis. Manimal therefore accepts direct optimization descriptions for such tools, using their available high-level semantics while retaining its physical optimizations.

  • Layered tools: Pig, Hive, and Mahout commonly generate MapReduce jobs from tool-specific languages rather than exposing users to the MapReduce programming interface.Hive, for example, processes SQL queries through MapReduce.
  • Semantic indirection: The generated Pig and Hive code acts as an interpreter, making program-specific semantics difficult for static analysis to recover.Mahout’s generic textual format likewise does not directly represent the user’s task semantics.
  • Adoption: Use of layered tools is increasing relative to raw Java MapReduce programming in survey evidence cited by the paper.The cited survey reports planned increases for Hive and Mahout alongside a decrease for raw Java.
  • Manimal integration: Manimal can bypass its analyzer when layered tools provide high-level job semantics and accept optimization descriptions directly.The resulting synthesized jobs can still use Manimal’s physical optimizations.

B. BENCHMARKS AND WORKLOADS

Manimal’s evaluation uses several imperfect workload options and therefore combines Pavlo et al.’s analytical tasks with synthetic tasks targeting individual optimizations.

  • Evaluating Manimal is difficult because no agreed-upon MapReduce workload exists.
  • Gridmix stresses Hadoop at the byte level but provides no task semantics for Manimal to analyze.
  • TPC-H evaluates report-generation queries but does not exercise many MapReduce-specific features, such as easy text parsing.
  • Pavlo et al.’s suite covers selection, aggregation, join, and UDF-driven aggregation, but contains only a few programs and lacks a documented workload model.
  • Manimal therefore evaluates end-to-end performance on Pavlo et al.’s tasks and uses synthetic per-optimization tasks to isolate individual techniques.

C. ADDITIONAL ANALYSIS

The additional analysis explains how Manimal uses static program analysis to identify fields relevant to projections and conditions suitable for compression-based optimization.

  • Projection analysis enumerates input fields that are never used by emit() calls or the control-flow decisions leading to them.
  • Figure 5 represents use-def relationships between map() instructions or variable definitions, with edges pointing from uses to required definitions.
  • Figure 6 detects projection opportunities by comparing serialized parameter fields with fields appearing in relevant use-def chains.
  • For direct operation on compressed data, Manimal selects input parameters whose uses are exclusively equality tests.
  • Delta compression is considered when serialized key and value inputs contain numeric values.

D. ADDITIONAL EXPERIMENTS

Additional experiments examine projection using generated WebPages and UserVisits data, varying content size and document count to measure how removing unused fields affects runtime.

  • The generated WebPages data uses unique pages with Zipfian popularity, while UserVisits fields are drawn mainly from real-world datasets.
  • The experiments store raw input in a binary format used by both standard Hadoop and Manimal runs.
  • Projection removes serialized fields irrelevant to the query, with Large and Small configurations varying average content size and total file size.
  • Small-1 matches Large in tuple count but is more affected by Hadoop startup time, whereas Small-2 increases document count to lengthen runtime.
  • 27x was exceeded in the Large configuration, while Small-1 achieved a 2.4x speedup and Small-2 was somewhat higher.

D.0.2 Compression

Manimal evaluates delta compression and operation directly on compressed data as separate strategies, finding substantial space savings for delta compression and a larger runtime gain when compressed values remain encoded during execution.

  • Manimal uses delta compression for relevant numeric fields and can operate directly on compressed data when program semantics permit.
  • 47% space savings from delta compression produced only a moderate performance boost.
  • Delta compression reduces map() input bytes, while map() computation may slightly increase and shuffle and reduce() loads remain unchanged.
  • Compressing destURL as a dictionary-coded integer yielded a roughly 2.3x speedup over conventional Hadoop MapReduce.
  • The compressed-data speedup came from reduced input size, reduced intermediate data, and faster sorting, although no opportunities were found in the test set.

E. FUTURE WORK

Manimal’s future work includes extending optimization beyond the map phase and across processing pipelines, while preliminary compressed-data aggregation results show a 2.3x speedup over standard Hadoop MapReduce.

  • Future work includes examining additional optimization techniques and extending analysis beyond the map phase.
  • 2.3x speedup over standard Hadoop MapReduce is achieved for aggregation-style programs by operating on compressed data.The result is reported in Table 6 as an existing optimization outcome.
  • Map-shuffle-reduce sequences resemble GROUPBY queries, and filtering reduce outputs resembles a GROUPBY with a WHERE clause.Predicting which temporary map outputs will be removed could enable deleting that temporary data.
  • Infrastructure for these beyond-map optimizations has been implemented, but performance results remain inconclusive.
  • Another proposed direction is tracking relational-style operations across chained MapReduce jobs and heterogeneous pipelines involving programs such as C crawlers and Python analyzers.The authors identify detecting links between chained jobs as a potential difficulty.
Loading 1104.3217v1…