Froid: Optimization of Imperative Programs in a …

1 Froid: Optimization of Imperative Programs in a RelationalDatabaseKarthik RamachandraMicrosoft Gray Systems ParkMicrosoft Gray Systems Venkatesh Emani IIT HalversonMicrosoft Gray Systems esar decades, RDBMSs have supported declarative SQL aswell as Imperative functions and procedures as ways for usersto express data processing tasks. While the evaluation ofdeclarative SQL has received a lot of attention resulting inhighly sophisticated techniques, the evaluation of imperativeprograms has remained na ve and highly inefficient. Impera-tive Programs offer several benefits over SQL and hence areoften preferred and widely used. But unfortunately, theirabysmal performance discourages, and even prohibits theiruse in many situations.

2 We address this important problemthat has hitherto received little present Froid, an extensible framework for optimiz-ing Imperative Programs in relational databases. Froid snovel approach automatically transforms entire User De-fined Functions (UDFs) into relational algebraic expressions,and embeds them into the calling SQL query. This form isnow amenable to cost-based Optimization and results in ef-ficient, set-oriented, parallel plans as opposed to inefficient,iterative, serial execution of UDFs. Froid s approach addi-tionally brings the benefits of many compiler optimizationsto UDFs with no additional implementation effort. We de-scribe the design of Froid and present our experimental eval-uation that demonstrates performance improvements of upto multiple orders of magnitude on real Reference Format:Karthik Ramachandra, Kwanghyun Park, K.

3 Venkatesh Emani,Alan Halverson, C esar Galindo-Legaria and Conor : Optimization of Imperative Programs in a Relational , 11(4): 432 - 444, : INTRODUCTIONSQL is arguably one of the key reasons for the popular-ity of relational databases today. SQL s declarative way of Work done as an intern at Microsoft Gray Systems to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.

4 Articles from this volume were invited to presenttheir results at The 44th International Conference on Very Large Data Bases,August 2018, Rio de Janeiro, of the VLDB Endowment,Vol. 11, No. 4 Copyright 2017 VLDB Endowment 2150-8097/17 $ : intent has on one hand provided high-level ab-stractions for data processing, while on the other hand, hasenabled the growth of sophisticated query evaluation tech-niques and highly efficient ways to process the expressive power of declarative SQL, almostall RDBMSs support procedural extensions that allow usersto write Programs in various languages (such as Transact-SQL, C#, Java and R) using Imperative constructs suchas variable assignments, conditional branching, and extensions are quite widely used.

5 For instance, wenote that there are of the order of tens of millions of Transact-SQL (T-SQL) UDFs in use today in the Microsoft AzureSQL Database service, with billions of daily and procedures offer many advantages over stan-dard SQL. (a) They are an elegant way to achieve modular-ity and code reuse across SQL queries, (b) some computa-tions (such as complex business rules and ML algorithms)are easier to express in Imperative form, (c) they allow usersto express intent using a mix of simple SQL and imperativecode, as opposed to complex SQL queries, thereby improv-ing readability and maintainability. These benefits are notlimited to RDBMSs, as evidenced by the fact that manypopular BigData systems also support , the above benefits come at a huge perfor-mance penalty, due to the fact that UDFs are evaluatedin a highly inefficient manner.

6 It is a known fact amongstpractitioners that UDFs are evil when it comes to perfor-mance considerations [35, 28]. In fact, users are advised byexperts to avoid UDFs for performance reasons. The inter-net is replete with articles and discussions that call out theperformance overheads of UDFs [34, 36, 37, 24, 25]. This istrue for all popular RDBMSs, commercial and open encourage good programming practices and pro-vide a powerful abstraction, and hence are very attractiveto users. But the poor performance of UDFs due to na veexecution strategies discourages their use. The root causeof poor performance of UDFs can be attributed to what isknown as the impedance mismatch between two distinctprogramming paradigms at play the declarative paradigmof SQL, and the Imperative paradigm of procedural this mismatch is crucial in order to address thisproblem, and forms the crux of our present Froid, an extensible Optimization frameworkfor Imperative code in relational databases.

7 The goal ofFroid is to enable developers to use the abstractions of UDFsand procedures without compromising on performance. Froid432achieves this goal using a novel technique to automaticallyconvert Imperative Programs into equivalent relational alge-braic forms whenever possible. Froid models blocks of im-perative code as relational expressions, and systematicallycombines them into a single expression using theApply[14]operator, thereby enabling the query optimizer to chooseefficient set-oriented, parallel query , we demonstrate how Froid s relational algebraictransformations can be used to arrive at the same resultas that of applying compiler optimizations (such as deadcode elimination, program slicing and constant folding) toimperative code.

8 Although Froid s current focus is T-SQLUDFs, the underlying technique is language-agnostic, andtherefore extending it to other Imperative languages is quitestraightforward, as we show in this have been some recent works that aim to convertfragments of database application code into SQL in orderto improve performance [12, 4]. However, to the best of ourknowledge, Froid is the first framework that can optimizeimperative Programs in a relational database by transform-ing them into relational expressions. While Froid is builtinto Microsoft SQL Server, its underlying techniques can beintegrated into any make the following contributions in this We describe the unique challenges in Optimization ofimperative code executing in relational databases, andanalyze the reasons for their poor We describe the novel techniques underlying Froid, anextensible framework to optimize UDFs in MicrosoftSQL Server.

9 We show how Froid integrates with thequery processing lifecycle and leverages existing sub-query Optimization techniques to transform inefficient,iterative, serial UDF execution strategies into highlyefficient, set-oriented, parallel We show how several compiler optimizations such asdead code elimination, dynamic slicing, constant prop-agation and folding can be expressed as relational al-gebraic transformations and simplifications that arriveat the same end result. Thereby, Froid brings theseadditional benefits to UDFs with no extra We discuss the design and implementation of Froid,and present an experimental evaluation on several realworld customer workloads, showing significant benefitsin performance and resource rest of the paper is organized as follows.

10 Section 2gives the background. Sections 3, 4, 5 and 6 describe Froidand its techniques. Design details are discussed in Section 7followed by an evaluation in Section 8. We discuss relatedwork in Section 9 and conclude in Section BACKGROUNDIn this section, we provide some background regardingthe way Imperative code is currently evaluated in MicrosoftSQL Server and analyze the reasons for their poor perfor-mance. SQL Server primarily supports Imperative code intwo forms: UDFs and Stored Procedures (SPs). UDFs can-not modify the database state whereas SPs can. UDFs andSPs can be implemented in either T-SQL or Common Lan-guage Runtime (CLR). T-SQL expands on the SQL stan-dard to include Imperative constructs, various utility func-tions, etc.