UDF to SQL translation through compositional lazy inductive synthesis
UDF to SQL translation through compositional lazy inductive synthesis
复制标题
DOI：
10.1145/3485489
复制
发表时间：
2021-10
影响因子：
--
通讯作者：
Guoqiang Zhang;Yuanchao Xu;Xipeng Shen;Işıl Dillig
中科院分区：
文献类型：
--
作者：
Guoqiang Zhang;Yuanchao Xu;Xipeng Shen;Işıl Dillig
许多数据处理系统允许使用传统编程语言编写的用户定义功能（UDF）的SQL查询，而此类SQL扩展名为用户提供了便利性，涉及UDF的查询不如其纯SQL SQL对应物高效优化的内置功能是由此问题的动机，我们提出了一种新技术，用于将UDF的SQL查询转换为纯SQL表达式。 UDF类。对于所有UDF的作品，我们提出了一种新型的懒惰感应合成方法，该方法产生了一系列分解序列，这些分解序列与越来越硬的诱导合成问题相对应。归纳合成方法比传统的cegis明显好。在纯SQL中，我们对这63个UDF的评估表明，在92％的情况下，CLI可以自动合成等效的SQL表达式，并且与不使用我们的复合方法相比，它可以解决2.4倍的基准。在端到端的应用程序性能方面，CLI的平均速度为3.5倍，为1.3×至3.1×。
Many data processing systems allow SQL queries that call user-defined functions (UDFs) written in conventional programming languages. While such SQL extensions provide convenience and flexibility to users, queries involving UDFs are not as efficient as their pure SQL counterparts that invoke SQL’s highly-optimized built-in functions. Motivated by this problem, we propose a new technique for translating SQL queries with UDFs to pure SQL expressions. Unlike prior work in this space, our method is not based on syntactic rewrite rules and can handle a much more general class of UDFs. At a high-level, our method is based on counterexample-guided inductive synthesis (CEGIS) but employs a novel compositional strategy that decomposes the synthesis task into simpler sub-problems. However, because there is no universal decomposition strategy that works for all UDFs, we propose a novel lazy inductive synthesis approach that generates a sequence of decompositions that correspond to increasingly harder inductive synthesis problems. Because most realistic UDF-to-SQL translation tasks are amenable to a fine-grained decomposition strategy, our lazy inductive synthesis method scales significantly better than traditional CEGIS. We have implemented our proposed technique in a tool called CLIS for optimizing Spark SQL programs containing Scala UDFs. To evaluate CLIS, we manually study 100 randomly selected UDFs and find that 63 of them can be expressed in pure SQL. Our evaluation on these 63 UDFs shows that CLIS can automatically synthesize equivalent SQL expressions in 92% of the cases and that it can solve 2.4× more benchmarks compared to a baseline that does not use our compositional approach. We also show that CLIS yields an average speed-up of 3.5× for individual UDFs and 1.3× to 3.1× in terms of end-to-end application performance.