Automatic Optimization for MapReduce Programs

Jahani, Eaman; Cafarella, Michael J.; Ré, Christopher
Jahani, E
Cafarella, M
Ré, C

The MapReduce distributed programming framework has
become popular, despite evidence that current implemen-
tations 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 ex-
ample, 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 pro-
grammer 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 ana-
lyzes MapReduce programs and applies appropriate data-
aware optimizations, thereby requiring no additional help
at all from the programmer. We show that Manimal suc-
cessfully detects optimization opportunities across a range of
data operations, and that it yields speedups of up to 1,121%
on previously-written MapReduce programs.

VLDB 2011
Citations range: 
p385-jahani.pdf364.05 KB