2018/05/22 by Pietro Michiardi, Michiardi, Pietro, Damiano Carra +3
Computer Science · #Cloud Computing and Resource Management #Databases (cs.DB) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1805.08650
openalex publication_date 2018/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In modern large-scale distributed systems, analytics jobs submitted by\nvarious users often share similar work, for example scanning and processing the\nsame subset of data. Instead of optimizing jobs independently, which may result\nin redundant and wasteful processing, multi-query optimization techniques can\nbe employed to save a considerable amount of cluster resources. In this work,\nwe introduce a novel method combining in-memory cache primitives and\nmulti-query optimization, to improve the efficiency of data-intensive, scalable\ncomputing frameworks. By careful selection and exploitation of common\n(sub)expressions, while satisfying memory constraints, our method transforms a\nbatch of queries into a new, more efficient one which avoids unnecessary\nrecomputations. To find feasible and efficient execution plans, our method uses\na cost-based optimization formulation akin to the multiple-choice knapsack\nproblem. Extensive experiments on a prototype implementation of our system show\nsignificant benefits of worksharing for both TPC-DS workloads and detailed\nmicro-benchmarks.\n