PL/SQL functions sufer from poor runtime performance due to the frequent context switches that occur between the PL/SQL interpreter and the SQL executor. This switching causes friction that can slow down UDF execution significantly. Table-valued UDFs incur the additional challenge of the eficient treatment of the sizable results they generate. In this paper, we generalize our PL/SQL UDF compilation strategy to also handle such table-valued UDFs. The generated SQL code carefully separates control flow from data flow at runtime. Compiled UDFs eficiently stream their table-valued results (as opposed to UDF variants that need to hold and copy intermediate states in array variables) and thus impose significantly less memory pressure.
PL/SQL is a high-level procedural programming language
that allows developers to write custom user-defined
functions (UDFs), operators, and algorithms that are not
tem. PL/SQL enables a style of imperative programming—
which is quite diferent from the declarative set-oriented
SQL paradigm—but still provides immediate access to
database-resident tables. The distinctive PL/SQL features
are (
PL/SQL SQL Q
WHILE Q1 in march
time
Typically, PL/SQL is implemented as an interpreted language on top of SQL host engines.
The imperative, non-SQL statements are interpreted by the PL/SQL subsystem, while all embedded SQL queries are sent to the SQL executor. Because both execution environments are completely disparate, each switch from one context to the other (and back) takes time and therefore causes
PL/SQL (FOR or WHILE) loops. In that case, switching back and forth between PL/SQL and the SQL executor occurs very frequently, which multiplies the overhead, and ultimately slows down execution. Figure 1 visualizes this.
It has thus become common developer lore that PL/SQL nonetheless been used for decades to implement complex database-driven applications [2]. Research has since recognized this as an important issue, resulting in several publications addressing this pressing challenge [1, 3–5].
The scope of the PhD project. The overarching goal of the PhD project is to allow developers to use imperative programming, e.g., in the form of PL/SQL UDFs, while maintaining the high performance of plan-based SQL execution. To accomplish this, we develop new ways to compile imperative PL/SQL UDFs into SQL queries. This compilation can handle arbitrary nesting of the PL/SQL features mentioned on the left. This includes looping control flow. As a side efect of this efort, database systems without PL/SQL support—but with support for a contemporary SQL dialect—will be able to run imperative PL/SQL UDFs after compilation, since no PL/SQL interpreter is required. In the present paper, we focus on the compilation of imperative (typically: iterative) table-valued UDF code into recursive yet plain SQL queries. 1.1. From Scalar Values to Tables scalar PL/SQL UDFs to a single recursive SQL CTE (WITH RECURSIVE). While keeping the basic idea and compilation chain as is, the present work separates the management of control flow and data flow to make the compilation suitable for table-valued UDFs. To this end, we introduce the concept of control rows and data rows. Previously, the compiler used only control rows and could
Let us look at an example. UDF march of Figure 2a is a ing as UDF march executes. dire when these embedded queries are placed in tight VLDB 2023 PhD Workshop, co-located with the 49th International 0000-0001-7040-1780 (D. Hirn) 1 CREATE FUNCTION march-arr(start vec2) RETURNS vec2[] AS $$ 2 DECLARE 3 goal vec2 := start; 4 cur vec2 := start; 5 dir vec2; 6 result vec2[] := ARRAY[] :: vec2[]; 7 BEGIN 8 WHILE true LOOP 109 dir := (SFERLOEMCT ddi.dreicrtions AS d, squares AS sQ1[⋅] 11 WHERE s.xy = cur 12 AND (s.ll, s.lr, s.ul, s.ur) 13 = (d.ll, d.lr, d.ul, d.ur)); 14 result := result || cur; 15 cur := (cur.x + dir.x, cur.y + dir.y) :: vec2; 16 EXIT WHEN cur = goal OR dir IS NULL; 17 END LOOP; 18 RETURN result; 19 END; 20 $$ LANGUAGE PLPGSQL STRICT; (a) Table-Valued version of PL/SQL UDF march.
(b) Marching Squares as an array-based PL/SQL UDF.
table-valued function and implements the popular
computer graphics algorithm Marching Squares [6] in Post- ff SSA ANF ANF SQL QQff
greSQL’s PL/pgSQL. Whenever such a table-valued UDF
encounters a RETURN NEXT, the PostgreSQL interpreter iterative goto recursive trampolined style WITH RECURSIVE
adds a new result to the function’s result set before the Figure 3: Compilation stages and intermediate UDF forms.
UDF resumes execution. This, potentially sizable, return See [5] for a detailed description of this compilation.
set is materialized during execution and returned as a
whole when the function exits. start:
(seAenmaarlctehr-naartrivine Fimigpulreem2ebn)tiatetiroantivaeslay sbcuailladrs tPhLe/SrQeLsuUltDaFs cdguiorra00l0←← ← sNtUsaLtrLat;r;t; ReExTiUtR:N;
an array of type vec2[]. Our previous compilation strat- GOTO while;
egy does handle march-arr, but the resulting SQL query
will exhibit disappointing performance: the compilation wchuirl0e:← o|(start:cur0,while:cur1);
creates a recursive CTE whose iteration expresses the dir1 ← (Q1[cur0]);
iteration of the original UDF. This CTE maintains the emit cur0;
local state of all UDF variables in a single row of the cur1 ← (cur0.x + dir1.x, cur0.y + dir1.y);
CTE’s working table. For UDF march-arr, maintaining IpF1 p←1(TcHuErN1 = goal0 OR dir1 IS NULL);
the array result iteratively results in significant runtime GOTO exit;
overhead because the array has to be copied (and ex- ELSGEOTO while;
tended) in each iteration. For iterations, this amounts
to a total of × (1 + 2 + ... + ( − 1 )) ≡ 12 2 × ( − 1) copy
operations. In consequence, the CTE’s working table Figure 4: CFG for UDF march with code blocks in SSA form.
grows to 16 MB during the execution of the compiled
UDF march-arr. Note that this copy overhead is not spe- termediate results, and (
In what follows, we sketch how to adapt and
generalize the CTE-based PL/SQL UDF compilation to also cover
table-valued UDFs like march of Figure 2a. We aim to
(
A program in trampolined style is organized as a single “scheduler” loop, the so called trampoline, which manages all control flow. Execution of such programs proceed in discrete steps. After each step, control is returned to the trampoline, which then proceeds to transfer control EXIT From PL/SQL to SQL. The compiler performs a series of transformations (see Figure 3) to get from PL/SQL to a plain recursive SQL query. The first step is to lower the UDF to static single assignment (SSA) form. Any iterative control flow is mapped to an equivalent program with labeled basic blocks that end with either GOTO to pass control to the block labeled , or RETURN. From the resulting CFG (see Figure 4) we derive the recursive SQL CTE run of Figure 5. again [8]. This cycle continues until the program execu- line” and how it realizes the control flow for UDF march. tion is finished. Using trampolined style, the program The SQL query reads the call column is efectively transformed into a state machine. We ex- to select one block ∈ {while, exit} for ploit the property, that only a single loop is required to evaluation. All blocks must return a start express arbitrary control flow. This restricted form of new control row with columns "rec?" control flow perfectly matches the semantics of SQL’s and call, so the dispatcher knows trampoline WITH RECURSIVE construct. how to proceed in the next iteration (see Lines 13, 16, and 21 of Figure 5). exit This process continues until a block returns a control row with column "rec?"=false (see Line 21 of Figure 5).
The working table in the next iteration Figure 6: Tramwill be empty, and WITH RECURSIVE polined style. evaluation stops.
New: Data Flow Management. While scalar UDFs return a single value in the last trampoline iteration, tableControl Flow Management. After compilation, each valued UDFs can return any number of values during excall to UDF march is encoded as a control row in the ecution (see emit cur0 in Figure 4). The CTE of Figure 5 working table of run. This row determines the state of encodes these returned values in dedicated rows marked the machine, and thus which part of the computation in Line 8 of Figure 5. Two columns manage this data to perform next. In Figure 4, each CFG construct that flow: yields a control row is marked . It is initially created data? ∈ {true, false}: Column data? indicates if this in the non-recursive part of run (see Line 2 of Figure 5). row has a valid return value in column res. In the recursive part of run, the row is read, because res: Contains this return value. two columns determine the transfer of control during We call rows with column data?=true data rows. When a execution: UDF uses either RETURN NEXT or RETURN QUERY, such data rec? ∈ {true, false}: If column rec? is false, the tram- rows are created in addition to control rows.
poline will stop calculating and return. Given the UDF of Figure 2a and assuming a call
call ∈ {while, exit}: Otherwise, column call specifies march((
data emit cur
Return Type
Overhead
Runtime
Memory march-arr vec2[]
march SETOF vec2
run Recall that the
rec? data? call res cur original PL/SQL UDF
true false while NULL (
tion prevents the
surrounding execution plan from terminating
prematurely, for example, when a LIMIT clause is used:
SELECT * FROM march((
Separating the concepts of data rows and control rows is essential for translating table-valued functions. We save working table space and are rewarded with a significant runtime advantage over array-centric UDF alternatives.
But it does not stop there. In the future, we plan to generalize this concept to add support for recursion in UDFs. Data rows could be used to model call stack entries, which—in one form or another—are required for functions that are not tail-recursive.
A further generalization would be to remove the restriction that one control row always yields exactly one new control row. This property causes trampolined style to model single-threaded computation. If the SQL back3. Data Rows in Trampolined Style end supports parallel plan execution, the creation of multiple control rows in a single iteration efectively spawns Both UDFs, march and march-arr, indeed exhibit the in- independent threads. UDF evaluation would benefit from famous context switching overhead that gives PL/SQL its parallelization just like regular SQL queries. bad reputation. We have measured that the back and forth between PL/SQL and SQL accounts for 20% of the overall evaluation time for both variants (see Table 1). References The compilation to recursive SQL CTEs described in [5] avoids this particular overhead for the two UDFs.
However, the naive treatment of the iterative result array construction and copying in the CTE for the scalar UDF march-arr quickly eats up all the gains: the quadratic array maintenance cost mentioned in the introduction add up to about 50% of the overall CTE runtime.
If we double the size of UDF input, the working table of the CTE for march-arr grows by a factor of four (from 16 MB to 64 MB) and the array maintenance overhead increases to 56%. Ultimately, this leads to a slowdown of march-arr after compilation.
In stark contrast, the control- and data-flow-aware compilation strategy sketched in Section 2, translates the table-valued UDF into the recursive SQL CTE of Figure 5.
Array construction and copying is avoided altogether and working table size remains small: doubling the UDF input size—and thus the number of iterations performed— linearly grows the working table’s size from 110 kB to a mere 220 kB. Overall, compilation of UDF march leads to runtime reduction of 62% (i.e., post-compilation the UDF runs about 2.6 times faster). In addition, materialization is entirely avoided: the CTE of Figure 5 can stream the rows of the resulting table to the downstream plan.