  Applications running on parallel systems often need to join a streaming
relation or a stored relation with data indexed in a parallel data storage
system. Some applications also compute UDFs on the joined tuples. The join can
be done at the data storage nodes, corresponding to reduce side joins, or by
fetching data from the storage system to compute nodes, corresponding to map
side join. Both may be suboptimal: reduce side joins may cause skew, while map
side joins may lead to a lot of data being transferred and replicated.
  In this paper, we present techniques to make runtime decisions between the
two options on a per key basis, in order to improve the throughput of the join,
accounting for UDF computation if any. Our techniques are based on an extended
ski-rental algorithm and provide worst-case performance guarantees with respect
to the optimal point in the space considered by us. Our techniques use load
balancing taking into account the CPU, network and I/O costs as well as the
load on compute and storage nodes. We have implemented our techniques on
Hadoop, Spark and the Muppet stream processing engine. Our experiments show
that our optimization techniques provide a significant improvement in
throughput over existing techniques.
