Bridging the gap: towards optimization across linear and relational algebra
Bridging the gap: towards optimization across linear and relational algebra
复制标题
DOI：
10.1145/2926534.2926540
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Andreas Kunft;Alexander B. Alexandrov;Asterios Katsifodimos;V. Markl
中科院分区：
文献类型：
--
作者：
Andreas Kunft;Alexander B. Alexandrov;Asterios Katsifodimos;V. Markl
高级数据分析通常需要某种形式的预处理，以便在使用机器学习和统计分析技术处理数据之前提取和转换数据。预处理管道在数据流API（例如MapReduce，Flink等）中自然表达，而机器学习则以迭代为单位性代数表示。因此，程序员使用多个编程范式和系统执行端到端数据分析。这种阻抗不匹配不仅会阻碍生产率，而且还阻止了优化机会，例如共享物理数据布局（例如，分区）和数据分析程序不同部分之间的数据结构。这项工作的目标是双重的。首先，它旨在通过允许程序员以一种自动并行化的一种独立于引擎的语言来制作完整的端到端程序来减轻阻抗不匹配。其次，它旨在使关系优化对关系和线性代数。为了实现这一目标，我们介绍了Lara的设计，Lara是Scala中深层嵌入式语言的设计，该语言可以使用两种抽象数据类型（数据库和矩阵）和控制流量结构来创建可扩展程序。用LARA编写的程序汇编为中间表示（IR），该表示可以在线性和关系代数之间进行优化。 IR最终用于编译不同执行引擎的代码。
Advanced data analysis typically requires some form of pre-processing in order to extract and transform data before processing it with machine learning and statistical analysis techniques. Pre-processing pipelines are naturally expressed in dataflow APIs (e.g., MapReduce, Flink, etc.), while machine learning is expressed in linear algebra with iterations. Programmers therefore perform end-to-end data analysis utilizing multiple programming paradigms and systems. This impedance mismatch not only hinders productivity but also prevents optimization opportunities, such as sharing of physical data layouts (e.g., partitioning) and data structures among different parts of a data analysis program. The goal of this work is twofold. First, it aims to alleviate the impedance mismatch by allowing programmers to author complete end-to-end programs in one engine-independent language that is automatically parallelized. Second, it aims to enable joint optimizations over both relational and linear algebra. To achieve this goal, we present the design of Lara, a deeply embedded language in Scala which enables authoring scalable programs using two abstract data types (DataBag and Matrix) and control flow constructs. Programs written in Lara are compiled to an intermediate representation (IR) which enables optimizations across linear and relational algebra. The IR is finally used to compile code for different execution engines.