  Large-scale systems, such as MapReduce and Hadoop, perform aggressive
materialization of intermediate job results in order to support fault
tolerance. When jobs correspond to exploratory queries submitted by data
analysts, these materializations yield a large set of materialized views that
typically capture common computation among successive queries from the same
analyst, or even across queries of different analysts who test similar
hypotheses. We propose to treat these views as an opportunistic physical design
and use them for the purpose of query optimization. We develop a novel
query-rewrite algorithm that addresses the two main challenges in this context:
how to search the large space of rewrites, and how to reason about views that
contain UDFs (a common feature in large-scale data analytics). The algorithm,
which provably finds the minimum-cost rewrite, is inspired by nearest-neighbor
searches in non-metric spaces. We present an extensive experimental study on
real-world datasets with a prototype data-analytics system based on Hive. The
results demonstrate that our approach can result in dramatic performance
improvements on complex data-analysis queries, reducing total execution time by
an average of 61% and up to two orders of magnitude.
