2013/11/25 by Astrid Rheinländer, Rheinländer, Astrid, Arvid Heise +7
Computer Science · #Advanced Data Storage Technologies #Advanced Database Systems and Queries #Cloud Computing and Resource Management #Databases (cs.DB) #FOS: Computer and information sciences #cs.DB
paper · pdf · doi:10.48550/arxiv.1311.6335
arxiv created 2013/11/25 · openalex publication_date 2013/11/25 · arxiv updated 2013/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Recent years have seen an increased interest in large-scale analytical dataflows on non-relational data. These dataflows are compiled into execution graphs scheduled on large compute clusters. In many novel application areas the predominant building blocks of such dataflows are user-defined predicates or functions (UDFs). However, the heavy use of UDFs is not well taken into account for dataflow optimization in current systems. SOFA is a novel and extensible optimizer for UDF-heavy dataflows. It builds on a concise set of properties for describing the semantics of Map/Reduce-style UDFs and a small set of rewrite rules, which use these properties to find a much larger number of semantically equivalent plan rewrites than possible with traditional techniques. A salient feature of our approach is extensibility: We arrange user-defined operators and their properties into a subsumption hierarchy, which considerably eases integration and optimization of new operators. We evaluate SOFA on a selection of UDF-heavy dataflows from different domains and compare its performance to three other algorithms for dataflow optimization. Our experiments reveal that SOFA finds efficient plans, outperforming the best plans found by its competitors by a factor of up to 6.