  In modern large-scale distributed systems, analytics jobs submitted by
various users often share similar work, for example scanning and processing the
same subset of data. Instead of optimizing jobs independently, which may result
in redundant and wasteful processing, multi-query optimization techniques can
be employed to save a considerable amount of cluster resources. In this work,
we introduce a novel method combining in-memory cache primitives and
multi-query optimization, to improve the efficiency of data-intensive, scalable
computing frameworks. By careful selection and exploitation of common
(sub)expressions, while satisfying memory constraints, our method transforms a
batch of queries into a new, more efficient one which avoids unnecessary
recomputations. To find feasible and efficient execution plans, our method uses
a cost-based optimization formulation akin to the multiple-choice knapsack
problem. Extensive experiments on a prototype implementation of our system show
significant benefits of worksharing for both TPC-DS workloads and detailed
micro-benchmarks.
