# PyTond: Efficient Python Data Science on the Shoulders of Databases

Hesam Shahrokhi  School of Informatics
University of Edinburgh
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Amirali Kaboli  School of Informatics
University of Edinburgh
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Mahdi Ghorbani  School of Informatics
University of Edinburgh
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Amir Shaikhha  School of Informatics
University of Edinburgh
Edinburgh, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

Python data science libraries such as Pandas and NumPy have recently gained
immense popularity. Although these libraries are feature-rich and easy to use,
their scalability limitations require more robust computational resources. In
this paper, we present PyTond, an efficient approach to push the processing of
data science workloads down into the database engines that are already known
for their big data handling capabilities. Compared to the previous work, by
introducing TondIR, our approach can capture a more comprehensive set of
workloads and data layouts. Moreover, by doing IR-level optimizations, we
generate better SQL code that improves the query processing by the underlying
database engine. Our evaluation results show promising performance improvement
compared to Python and other alternatives for diverse data science workloads.

###### Index Terms:

Data Science, In-Database Execution, Code Generation, Python, Pandas, NumPy

##  I Introduction

Python, as a user-friendly language with extensive library support, has become
a de-facto standard for data science. While Python excels in prototyping, its
interpreted nature hinders its scaling on larger datasets and more complex
workloads. This limitation also affects the performance of popular Python
libraries like Pandas [1] and NumPy [2]. To overcome the Python interpretation
overhead, these libraries have implemented their APIs in C language (using
Python/C API) and utilize them as pre-compiled kernels. However, they still
miss the chance to harness global program optimization opportunities such as
fusion and dead-code elimination. Consequently, users still need to enhance
their computational resources to achieve the expected performance,
specifically when processing large amounts of data in data science pipelines.

In recent years, researchers have proposed innovative approaches to overcome
the scalability constraints of Python and its associated libraries by
leveraging techniques from compilers and database communities [3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]. One of the mainstream
solutions [3, 4, 5, 6, 7, 8] focuses on leveraging the proven computational
capabilities of database engines. These approaches translate the source code
into SQL, allowing it to be executed on any standard relational database
engine (portability). As data often resides inside databases, this approach
can also bring the computation near the data and lessen unnecessary data
movements. Moreover, by delegating query optimizations to query engines, the
solution yields an efficient execution.

Although transforming Python Data Science to SQL has promising benefits, the
existing proposals have limitations. First, their translation coverage is
restricted to a limited set of Pandas or NumPy APIs; For example, to the best
of our knowledge, none of the existing proposals fully support the TPC-H
benchmark [6]. Second, their generated code is not idiomatic SQL to fully
exploit the potential performance benefits offered by the query engines.
Lastly, the efforts on translating linear algebra expressions (e.g., NumPy
APIs) to SQL are limited to the sparse data layout, which is not optimized for
workloads with dense vectors/matrices [3, 4].

This paper presents PyTond, an automated approach for in-database execution of
Python data science workloads. PyTond takes workloads written in Pandas and/or
NumPy and generates their semantically equivalent SQL code. The translated
code is rewritten to idiomatic SQL code to make it more prone to optimizations
offered by the underlying query processing engine. Finally, the translation
process supports both sparse and dense data layouts for tensors (e.g., vectors
and matrices), which enables PyTond to generate optimized SQL code for linear
algebra operations.

TABLE I: A summary of state-of-the-art in-database Python execution approaches. Blatcher et al. [4] only supports the einsum API in NumPy on sparse data layout. Grizzly [6] has limited support for different Pandas APIs. PyTond provides support for data stored in dense and sparse layouts. Approach | Generic Python | Pandas | NumPy | Multiple Data Layout | SQL Rewriting
---|---|---|---|---|---
ByePy [5] | ● | ○ | ○ | ◐ | ○
Blatcher et al. [4] | ○ | ○ | ◐ | ◐ | ○
Grizzly [6] | ◐ | ◐ | ○ | ◐ | ○
PyFroid [8] | ○ | ● | ○ | ◐ | ◐
PyTond (This Approach) | ○ | ● | ● | ● | ●

The contributions of this paper are as follows:

  * •

We present PyTond, a framework for the portable in-database execution of
hybrid Python data science workloads. This is achieved by translating
Pandas/NumPy APIs to SQL code. We discuss its high-level design that offers
expressiveness and efficiency and the background in Section II.

  * •

We show that PyTond is unique in capturing Pandas (relational algebra), NumPy
(linear algebra), and their hybrid workloads while considering different data
layouts. The key enabling technology in achieving expressiveness is TondIR, a
novel intermediate language that enables an extensible translation of
Pandas/NumPy APIs (Section III).

  * •

We apply optimizations on the TondIR program to generate SQL code that paves
the way to further optimizations and more efficient processing by the
underlying database engine. Our discussion on the efficiency of the approach
is covered in Section IV.

  * •

We conduct benchmarks (Section V) to showcase the superiority of our approach
over Python and state-of-the-art for various workloads, including all TPC-H
queries and hybrid data science workloads.

Table I summarizes the characteristics of the existing research on in-database
scalable Python data analytics and compares them with PyTond. We refer to
Section VI for a more detailed discussion on state-of-the-art.

##  II Background and Overview

In this section, we provide the background knowledge that is necessary for a
better understanding of the work. Then, we present the design of our approach.

###  II-A Background

In this section, we provide contextual information and present the high-level
design of our approach.

Background on Pandas. The Pandas library is a popular tool for relational
algebra (RA) operations in Python. Pandas introduces DataFrame as its primary
data structure. The DataFrame data structure is a flexible representation of
2-dimensional data; it is easy to add, modify, and remove the columns and rows
of a given DataFrame by calling their related APIs. Table II shows a set of
primary Pandas APIs.

The merge API works similarly to a join in RA. The how argument of this API
determines the type of requested operations including the Cartesian product,
inner join (default value), left, right, and full outer join.

To demonstrate the pivot_table API, consider the following expression:

⬇

df.pivot_table(index=’a’, columns=’b’, values=’c’, func=’sum’)

TABLE II: A summary of primary Pandas APIs. API | Description
---|---
⬇ df[col] | df.col | Column selection
⬇ df[condition] | Rows filtering
⬇ df.head(n) | Top n rows selection
⬇ df.col.unique() | Distinct column values
⬇ df.sort_values(by, ascending) | Sorting on columns list
⬇ df.apply(func) | Mapping using func
⬇ df.aggregate(func) | Reduction using func
⬇ df.groupby(by, axis) | Grouping
⬇ df1.merge(df2, how, on) | Joining DataFrames
⬇ df1.isin(df2) | Containment filtering
⬇ df.pivot_table(index,…,func) | Making a pivot table

In this example, the output DataFrame has a column a, and its distinct values
are used as group representatives. Then, for all rows that fall into each
group, a column will be associated with each distinct value of the column b.
In any of those columns, we have the sum of values in column c. A sample input
DataFrame (df) and the result of applying the above API call on it is shown
below:

| a | b | c
---|---|---
x | v1 | 10
y | v3 | 30
y | v1 | 60
z | v2 | 20
y | v3 | 40
x | v2 | 60
z | v2 | 50
$\longrightarrow$ |  | a | v1 | v2 | v3
---|---|---|---
x | 10 | 60 | 0
y | 60 | 0 | 30
z | 0 | 70 | 0

Background on NumPy. The NumPy library is a popular tool for linear algebra
(LA) computations in Python. This library is based on fine-tuned kernels that
offer an efficient execution. The basic data structure in NumPy is called
array which is an efficient representation of a tensor of an arbitrary order.
Here is an example of tensors of different orders defined in NumPy:

⬇

# Order-1 Tensor (Vector)

vector = np.array([1, 2, 3])

# Order-2 Tensor (Matrix)

matrix = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])

# Order-3 Tensor (3D Tensor)

tensor_3d = np.array([[[1, 2, 3], [4, 5, 6]], [[7, 8, 9], [10, 11, 12]]])

One of the interesting and powerful APIs NumPy provides is called einsum.
Adopted from the concept of Einstein Notation (Summation) [21], this API
provides a concise, comprehensive, and efficient way to write linear algebra
operations in Python. Each einsum API call takes a list of arguments. The
first argument is a string that defines the requested LA operation, while the
rest are the required operands. Table III lists some common LA operations and
their equivalent NumPy expression. As it can be inferred from the table, many
of the specific APIs for LA in NumPy (e.g., sum, transpose, inner, matmul) can
be expressed in terms of an einsum API. However, APIs such as all, nonzeros,
round, and compress cannot be expressed solely by using einsum.

TABLE III: A list of common LA operations in NumPy and their equivalent einsum expressions. NumPy API | Args of np.einsum | Description
---|---|---
⬇ m.sum(axis=0) | (’ij->j’,m) | Matrix ColSum
⬇ m.sum(axis=1) | (’ij->i’,m) | Matrix RowSum
⬇ m.sum() | (’ij->’,m) | Matrix Sum
⬇ inner(v1, v2) | (’i,i->’,v1,v2) | Vector Inner Prod.
⬇ outer(v1, v2) | (’i,j->ij’,v1,v2) | Vector Outer Prod.
⬇ m.transpose() | (’ij->ji’,m) | Matrix Transpose
⬇ matmul(m1,m2) | (’ij,jk->ik’,m1,m2) | Matrix Mult.
⬇ v.all() | - | All Set Check
⬇ v.nonzero() | - | Non-Zeros Index
⬇ v.round() | - | Rounding
⬇ v.compress(c) | - | Slicing

###  II-B Overview of Approach

The high-level overview of PyTond is depicted in Figure 1. Here we elaborate
on each element of the presented design.

Data Science Code. PyTond supports the data science workloads that are written
using Pandas, NumPy, or a combination of them. Since our approach is based on
static analysis of the source code, data scientists do not need to change
their program logic or even the imported libraries. The only required change
is to add the @pytond decorator on top of their functions (cf. Section III).

Translation. The translator module starts by finding the decorated functions
in the source code and constructs the abstract syntax tree (AST) of them.
Then, it transforms the ASTs into our tailored intermediate representation
(IR), based on pre-defined translation rules. The translation process and its
various challenges will be discussed in Sections III-B, III-C, and III-D.

TondIR. TondIR is our gateway to expressiveness and our lever to improve
efficiency. This IR is designed to capture the intended workloads and is
amenable to applying a variety of optimizations. An in-depth analysis of this
IR will be done in Section III-A.

Optimization. The optimizer module gets an TondIR code and applies a set of
well-defined optimization rules to construct a more efficient version of the
input. In Section IV, we will investigate the transformations done during the
optimization phase. We will also assess its effects on the overall performance
of PyTond (Section V).

Code Generation. After the optimization is done, we translate the optimized
TondIR code to standard SQL. Our SQL code generation challenges are discussed
in Section III-E.

Data. The data that is fed into the data science pipelines is usually stored
either in files (e.g. CSV files) or databases. For huge data sizes, the poor
performance of Pandas popular file reader API (read_csv) pushes the developers
towards using the databases as their main data storage locations. The
capability of databases for handling massive data besides their recent
advances (e.g. in-memory databases [22]) also justifies this preference. By
taking the opportunity of data being kept in databases, our approach can gain
access to the data and bring the computation (execution of the optimized SQL
code) near the data. Before the execution, by querying the database catalog,
our approach can access the meta-data information (e.g., schema and integrity
constraints) and use it during the optimization process. We discuss the
potential benefits of having such knowledge in Section III.

Figure 1: High-level design of PyTond.

Focusing on the numerical data, specifically matrices, regardless of the
storage location, the data is usually kept in a 2-dimensional format. We refer
to it as a dense layout,111Blatcher et al. [3] call this representation
database-friendly. comparing it to sparse layouts. To construct a sparse (COO)
representation of a given dense input, we first create an ID column (starting
from 0), an incremental integer column associated with each row. Then, we
virtually assign a unique integer number (starting from 0) to each column.
Finally, we transform the given matrix to a new 2-dimensional representation
with this header: (row_ID, col_ID, val). This layout is beneficial whenever
the input data is sparse (many values are None or 0) but needs extra
transformations on input/output.

In PyTond, we provide the flexibility of using both dense and sparse layouts
by passing this information to function decorators (Section III). Having the
support for both layouts, specifically for the LA workloads, makes it possible
to process numerical data in its natural format (dense) while benefiting from
the advantages of sparse layout when the data is sparse. The state-of-the-art
[4] only supports the sparse format.

RDBMS. As the final step in our pipeline, the optimized SQL code is passed to
the underlying relational database management system (RBDMS) for further
optimization and final execution. The RDBMS receives the query, does a bunch
of thoughtful optimizations over it, and passes it to its query engine to be
executed on the already-loaded data. It is worth mentioning that the
optimizations that are done in both TondIR and query planner level, could not
be easily done by the developers or in the interpreted Python environment.
Last but not least, the query engine executes the generated physical plan of
the query in a fine-tuned hardware-conscious fashion. This execution can
exploit the recent advances in query processing including push-based and
vectorized engines [22].

##  III TondIR

TABLE IV: Grammar of TondIR. In atoms we have $\theta\in\\{$ <,<=,=,<>,>=,> $\\}$ Program | $P$ | $::=$ |  $R$ $\mid$ $P$ $R$ | List of rules.
---|---|---|---|---
Rule | $R$ | $::=$ |  $H$ :- $B$. | Head (access) and body (products).
Head | $H$ | $::=$ |  ${r}$[group($\overline{\text{${x}$}}$)][sort($\overline{\text{${x}$}},\overline{\text{${b}$}}$)[limit($n$)]] | Aggregates over a relation. Arguments in [] are optional.
Relation | ${r}$ | $::=$ |  $X$($\overline{x}$) | Access to a relation $X$ with variables $\overline{x}$.
Body | $B$ | $::=$ |  ${a}$ $\mid$ $B$ , ${a}$ | Body is a chain of atoms.
Atom | ${a}$ | $::=$ |  ${r}$ $\mid$ [$\overline{{\footnotesize\texttt{<c>}}}$] $\mid$ exists($B$) $\mid$ ${x}$ $\theta$ ${t}$ | Relation access, constant relation, existential filter, or logical/assignment.
Term | ${t}$ | $::=$ |  ${x}$ $\mid$ ${agg(t)}$ $\mid$ ${ext(\overline{x})}$ $\mid$ if($t,t,t$) $\mid$ ${t}$ $\diamond$ ${t}$ $\mid$ ${c}$ | Variable, aggregation, external function, conditional, binary op, or constant.
Constants | ${c}$ | $::=$ |  ${n}$ $\mid$ ${f}$ $\mid$ ${b}$ $\mid$ ${s}$ | integer, floating point, boolean, or string.

In this section, we present TondIR, our intermediate representation designed
to capture Python data science workloads efficiently and pave the way for
subsequent optimizations. We start by specification of the TondIR design.
Following that, we explain the integration of our translation approach into
Python that ensures a seamless transition to TondIR. Next, in dedicated
sections, we discuss the translation process from Pandas and NumPy to TondIR.
Then, we elaborate on our strategy for translating TondIR to SQL. Ultimately,
we wrap up all components and demonstrate an end-to-end translation from
Python to SQL.

###  III-A TondIR Design

To design an appropriate intermediate representation (IR) for our approach, we
consider its ability to express hybrid data science workloads involving
relational and linear algebra, and its flexibility for applying different
optimizations. To this end, we designed an IR inspired from Datalog-like logic
programming languages [23, 24, 25, 26, 27] with the mentioned properties. The
grammar of this IR is shown in Table IV.

Grammar. Each program ($P$) is composed of several rules ($R$). Each rule is
in the form of an assignment from a body ($B$) to a head ($H$). A head is an
access to a relation (${r}$) with an optional group-by
([group($\overline{\text{${x}$}}$)]) and an optional ascending/descending
($\overline{\text{${b}$}}$) sort with/without limiting
([sort($\overline{\text{${x}$}},\overline{\text{${b}$}}$)[limit($n$)]]), over
a list of variables. The relation access (${r}$) is described by providing the
relation name ($X$) and a list of variables assigned to each relation column
($\overline{x}$). The relation column names are bound to the position of each
variable $X$ inside $\overline{x}$. This will guarantee sound code generation
for column names even after local changes during the translation and
optimization. The body is a chain of atoms (${a}$). Each atom can be a
relation access, creation of a constant relation, an existential filter
(exists($B$)), or a comparison/assignment ($\theta$) between a variable
(${x}$) and a term (${t}$). If the left side of an assignment is an already
defined variable, we consider the operation an equality comparison rather than
an assignment. Finally, a term is an aggregation over another term
(${agg(x)}$), an external function call over variables
(${ext(\overline{x})}$), a conditional statement (if($t,t,t$)), a binary
operation over terms (${t}$ $\diamond$ ${t}$) or a constant value (integer
(${n}$), floating point (${f}$), string (${s}$), or boolean (${b}$)). Binary
operations include arithmetic, and/or, like, etc.

Contextual Information. Collection of contextual information about the
workload can guide the optimizations on the generated TondIR. In PyTond, we
use two distinct sources to gather such information: database catalog and
decorator arguments.

Since we assume that the data is imported into the database, PyTond queries
the DBMS catalog to implicitly collect contextual information about the
dataset, and embed them into TondIR constructs. The extracted information
includes but is not limited to the table constraints (e.g., primary key,
foreign key, uniqueness), and schema information (e.g. cardinality, column
names and types).

The other source of collecting contextual information is through the function
decorators. As discussed in Section II, to transform a Python function to SQL
using PyTond, users need to add @pytond decorator on top of their functions.
The contextual information can be explicitly passed to PyTond as the arguments
of function decorators.

###  III-B Python Embedding

PyTond scans the Python code to identify functions decorated with @pytond. The
abstract syntax tree (AST) is extracted for each function using the ast
module. Then, the extracted AST is passed to the translation preprocessing
pipeline.

Normalization. PyTond converts the AST to A-Normal Form (ANF) [28, 29]. In the
ANF representation, we extract each nested logic, assign it to a variable, and
put a variable access instead of the nested logic. This makes the translation
easier as we only need to define rules for simple expressions. Here is an
example of converting a Pandas code to ANF:

⬇

res = (df1[df1.b>10][’a’]).merge((df2[df2.y==’r’][’x’]), left_on=’a’,
right_on=’x’)

$\big{\Downarrow}$

⬇

v1 = df1.b>10

v2 = df1[v1]

v3 = v2[’a’]

v4 = df2.y==’r’

v5 = df2[v4]

v6 = v5[’x’]

res = v3.merge(v6, left_on=’a’, right_on=’x’)

As shown above, the nested projection and filtering logic are decoupled into
consecutive assignments to globally unique variables. After this program
transformation, PyTond only needs to use a single transformation rule to
transform each line of source code. In the normalization phase, to preserve
the program semantics, the input variable names (df1 and df2) remain
unchanged.

TABLE V: Translation of sample Pandas/NumPy APIs to TondIR. df, df1, df2, m, m1, m2 all have n columns. The result of each API call is stored in variable R. For example, the first Python code equals to: R=df[col] API Library | Python | TondIR
---|---|---
⬇ R(col) :- df(c1, ... , cn).
⬇ R(c1, ... , cn) :- df(c1, ... , cn), (condition).
⬇ R(c1, ... , cn) :- df(c1, ... , cn), (c1=func(c1)), ... , (cn=func(cn)).
⬇ R(x1, ... , x(2n-1)) :- df(a1, ... , x , ... , an), df(b1, ... , cx , ... ,
bn).
⬇ R(c1, ... , cn) sort(by, ascending) limit(n) :- df(c1, ... , cn).
⬇ R(c1, ... , cn) group([col]) :- df(c1, ... , cn), (c1=sum(c1), .... ,
cn=sum(cn)).
⬇ R(c1) :- v(ID, c1), (c1=min(c1)).
⬇ R(ID) :- v(ID, c1), (c1!=0).
⬇ R(ID, c1) :- v(ID, c1), (c1=round(c1)).
⬇ R(ID, cx, ... , cy) :- m(ID, c1, ... , cn)).
⬇ R(ID, c1) :- m(ID, c1, ... , cn), (c1=if(ID=1, c1, if(ID=2, c2, ... ,
if(ID=n, cn) ... )))
⬇ R(ID, c1, ... , cn) :- m1(ID, a1, ... , an), m2(ID, b1, ... , bn),
(c1=a1*b1), ... , (cn=an*bn).

Type Inference. PyTond fetches the contextual information (cf. Section III-A)
from decorator arguments and database catalog. Then, having the normalized
program and its context, PyTond will do type inference. The extracted type
information will be used in translation/optimization pipelines.

Relation Access Renaming. To avoid variable name collisions in TondIR
translation/optimization, PyTond assigns a unique name to each variable in
each body relation access (r).

###  III-C Pandas to TondIR

The TondIR equivalents of sample Pandas APIs are listed in Table V. Due to the
flexible and expressive nature of TondIR, the common Pandas expressions can be
easily transformed to this IR.

To translate the merge API, PyTond takes different translation approaches
based on the how attribute of the API. If it is a Cartesian product
(how=’cross’), PyTond assigns unique names for all variables in both
relations. If it is an inner join (how=’inner’), PyTond assigns unique names
to all variables except the join variables, which will have similar names. For
the case of full, left, and right outer joins, it takes an approach similar to
the Cartesian. However, it introduces special external atoms
${ext(\overline{x})}$ that contain information about the join type and joined
columns. These atoms are called ${outer\\_full(\overline{x})}$,
${outer\\_left(\overline{x})}$, and ${outer\\_right(\overline{x})}$.

Although the presented APIs are only a subset of what is covered by PyTond and
Pandas, the extensibility of TondIR makes the coverage of the other APIs
feasible. Next, we focus on the challenges in translation from Pandas to
TondIR.

Implicit Renaming. In Pandas, when we use the merge API to combine DataFrames
with overlapping column names, the API will automatically rename the shared
columns of the first DataFrame to [col_name]_x and their corresponding columns
in the second DataFrame to [col_name]_y. The _x and _y constants can be
changed by setting the suffixes argument of merge API. If the shared column is
the one used for the merging operation, the API retains the original column
name and includes only one instance of it in the merged result. An example of
a merge operation with the mentioned properties is shown below:

⬇

df1 = … # df1 column names: [a,b,c]

df2 = … # df2 column names: [a,c,d]

df3 = df1.merge(df2, left_on=’a’, right_on=’a’)

In this example, the header of the output DataFrame (df3) will be [a, b, c_x,
c_y, d]. During its type inference phase, PyTond considers this implicit
renaming to generate correct types for merge API calls.

Implicit Joins. Pandas allows users to append to the columns of a DataFrame.
This can be expressed as an implicit join operation. Consider the following
example in Pandas:

⬇

df1 = … # df1 column names: [a,x,y]

df2 = … # df2 column names: [b,z]

df3 = DataFrame()

df3[’a’] = df1[’a’]

df3[’b’] = df2[’b’]

In this example, we create a new column on the left-hand side DataFrame by
using the values from a column on the right-hand side. Note that the program
can be even more complex when we update (instead of create) a column in df3 or
have more complex expressions from different DataFrames on the right-hand
side. The high abstraction level of DataFrames in Pandas can hide the
challenges of handling such scenarios. However, to generate SQL, we must
explicitly express the implicit operations done at Pandas background. Back to
our example, since df3 is initially empty, we can generate a projection from
df1 that only projects column a. But, in the next line, we need to add a
column b from another DataFrame (df2) and it needs a join between df3 and df2.
Here, there is an assumption that the source and target columns have equal
rows. PyTond generates the following TondIR in this scenario:

⬇

df3(a) :- df1(a, x, y).

df3(ID, a) :- df3(a), (ID=UID()).

df2(ID, b, z) :- df2(b, z), (ID=UID()).

df3(a, b) :- df3(ID, a), df2(ID, b, z).

The UID term is an external atom (${ext(\overline{x})}$) and is used to create
an identity (PK) column for a relation. In this code, PyTond automatically
adds the necessary rules/terms to make the implicit join on df2 and df3
explicit. As it will be discussed in IV, PyTond optimizer will finally remove
unnecessarily introduced rules/terms (e.g. when there is a self-join).

Pivot Translation. We presented the interface of Pandas pivot_table API in
Table II. To translate this API, we need information about the distinct values
specified by the columns argument. This information can be provided via the
decorator or by querying the target columns before code generation.
Considering the example from Section II-A, its equivalent TondIR code is as
follows:

⬇

R1(a, v1, v2, v3) group(a) :-

R(a, b, c), (v1=sum(if(b=v1,c,0))),

(v2=sum(if(b=v2,c,0))), (v3=sum(if(b=v3,c,0))).

We must generate distinct columns for unique values in column b. To achieve
this, we examine the value of this column in every row and determine to which
designated columns (v1, v2, and v3) that particular value should contribute.
Subsequently, we aggregate the contributed values for each column using a sum
expression and assign the result to the respective column name. Finally, the
embedding of the group clause ensures that accurate grouping is done within
the program. It is worth noting that the information about the distinct values
of b can be passed to PyTond using the @pytond decorator arguments.

###  III-D NumPy to TondIR

Table V also shows translations of a subset of NumPy APIs to TondIR. In all
NumPy APIs that use arrays in their input, we assume a unique id column stored
in the input. We also generate/project such a column after each API call if
the result is an array. The all API checks if all values in the vector are
True. We implemented it by applying the min function to vector values. The
compress API with axis=1, slices the array vertically (picks the columns that
are selected by mask). The following section will cover the detailed
discussion on einsum API translations.

Einsum Translation. The einsum API translation in our approach has a two-phase
pipeline. First, we compute an execution plan for a given einsum expression,
and then we generate code by considering the extracted plan.

In the planning phase, we first take the information about data layout (dense
vs. sparse) from the function decorator. If nothing is passed, we consider the
default data layout, which is dense. If the data layout is sparse, we take the
approach proposed by Blacher et al. [4] but generate TondIR (not SQL). The
fully denormalized nature of the COO sparse layout allows us to easily
generate TondIR code for different einsum expressions. On the other hand, if
the dense format is requested, we will continue planning for the given einsum
expression as will be discussed.

After thoroughly exploring possible binary einsum expressions (with
matrix/vector operands), we came up with a minimal set of kernels listed in
Table VI. Our planner will use these kernels to construct the other possible
einsum expressions. Here, there is a trade-off between automation and
efficiency. We can implement more efficient kernels manually, but it needs
much more effort. We decided to go with this minimal set of kernels and let
the optimizer take the responsibility for optimizing the generated TondIR. The
translations for the ES3 and ES7 kernels are shown in the last two rows of
Table V. ES7 has a final matrix reshaping part that is not shown in the table
for the sake of brevity. However, a sample of such reshape will be presented
in our final end-to-end example (Figure V-B).

Now, we explain the translation of einsum expressions to our fundamental
kernels based on an example binary einsum expression. Assume that we have the
einsum expression ’ab,cc->ba’ as input. This expression can be represented as
’ij,kk->ji’ in TondIR since a, b, and c appeared in the first, second, and
third non-repeated position of the expression respectively. Since variable k
does not appear on the right-hand side, TondIR needs to sum over the whole
matrix (’kk->’). Therefore, TondIR applies kernel ES3 over the right-hand side
of the compression and transforms ’kk->k’. Then, TondIR proceeds to apply
kernel ES1 on the same matrix to produce the expected result ’k->’. Now, the
computation is simplified and turned into ’ij,->ji’. However, this computation
is not a fundamental kernel yet. As the next step, TondIR swaps the left-hand
side and right-hand side of this computation and converts it to ’,ij->ji’. As
the final step, TondIR transposes the input using kernel ES4 and creates the
einsum expression ’,ji->ji’ which is kernel ES6. By using this tail of einsum
operations (plan), PyTond generates appropriate TondIR code for the given
einsum expression. During the code generation for einsums, if either inputs to
the einsum API are constant, PyTond will inline constant values inside its
predefined kernels (constant folding).

TABLE VI: List of base einsum kernels in PyTond. All other einsum expressions can be reduced to these kernels. Given an einsum expression, the characters i, j, and k show the first, second, and third non-repeated variables respectively. _ represents an scalar value. The kernels are presented as args of a NumPy einsum. ID | Fundamental Kernels | Description
---|---|---
ES1 | (’i->’,v) | Vector ColSum
ES2 | (’ij->i’,m) | Matrix ColSum
ES3 | (’ii->i’,m) | Diagonal to Column
ES4 | (’ij->ji’,m) | Transpose
ES5 | (’,->’,s1,s2) | Scalar Product
ES6 | (’,ij->ij’,s1,m1) | Scalar Times Matrix
ES7 | (’ij,ij->ij’,m1,m2) | Hadamard Product
ES8 | (’ij,ik->jk’,m1,m2) | Batch Vector Outer Product
ES9 | (’ij,ik->ij’,m1,m2) | Matrix-Vector Multiplication

TondIR also supports einsum expressions with more than two inputs (non-binary)
using the Python opt_einsum library [30]. First, PyTond passes the einsum
expression to the opt_einsum path optimizer. Then, opt_einsum breaks the
computation to several einsum computations with less number of inputs.
Finally, TondIR processes and translates the computations if all the einsum
expressions produced by opt_einsum are in a binary format.

###  III-E TondIR to SQL

To generate SQL from TondIR, we take each rule and create a SQL WITH clause
that contains the SQL equivalent of the logic defined by the rule. Here is an
example rule and its equivalent SQL code:

⬇

R1(a, s) :- R(a, b, c),(s=sum(b)).

$\big{\Downarrow}$

⬇

WITH R1(a, s) AS { SELECT a, SUM(b) AS s FROM R }

SELECT * FROM R1

Using this translation approach, a program will be translated to a chain of
WITH clauses followed by a final SELECT statement that returns the results of
the last translated rule.

Sort and Limit. A Common Table Expression (CTE) in SQL is very similar to the
concept of views, but it is temporarily defined in the context of a larger
query. CTEs are defined using WITH clause in SQL, and similar to the views,
they cannot keep the results ordered after an ORDER BY command. Since in
analytical queries, it is usual to sort and pick only a subset of the results
(e.g., almost all of the TPC-H queries), our code generation must be
considerate about ORDER BY and LIMIT clauses in the program. To have a
semantic-preserving translation, we alter the TondIR program such that
separately-defined ORDER BY/LIMIT pairs are done within a single CTE.
Moreover, the individual ORDERBY clauses are only allowed in the final rule of
a program.

Unique ID Generation. To keep the semantics of the Pandas indexes in our
translations, we generate a unique ID column for the input relations. To
generate such columns (translation of UID() expression) in TondIR(), we use
the following window function in SQL:

⬇

SELECT

row_number() OVER(ORDER BY col) AS ID

FROM rel

In this SQL command, the order of col is used as a reference to generate
sequential unique IDs. If this argument is not set, the database systems
usually use the order of the first column in rel. However, because of the non-
deterministic behavior of query engines in creating IDs when no ordering
column is passed, we only use UID in the first appearance of a relation in the
code and carry the generated column down to the end of the pipeline. It
guarantees our immediate access to the ID column of a relation when it is
required. We also do not allow translation rules to remove such a column. In
the optimization phase (cf. Section IV), we prune the unused IDs and make the
code as simple as possible. The generated IDs can be reset in specific
situations discussed in Section IV.

|
---|---
|

⬇

a=x.merge(y, on=’id’).

drop(’id’, axis=1).

to_numpy()

b=np.einsum(’ij,ik->jk’,a, a)

(a) Original Python code.

⬇

v1=x.merge(y, on=’id’)

v2=v1.drop(’id’, axis=1)

v3=v2.to_numpy()

v4=np.einsum(’ij,ik->jk’,v3,v3)

(b) Python code after ANF.

⬇

v1(ID, c0, c1) :-

x(ID, c0),

y(ID, c1).

v4_1(ID, c0, c1, c2, c3)

group(ID) :-

v1(ID, c0, c1),

v1(ID, c2, c3),

(c0=sum(c0*c2)), (c1=sum(c0*c3)),

(c2=sum(c1*c2)), (c3=sum(c1*cf3)).

v4_2(c0) :- (c0=[0, 1]).

v4_3(ID, c0, c1) :-

v4_1(ID, c0, c1, c2, c3), v4_2(c4),

(c0=(if(c4=0, c0, c2))),

(c1=(if(c4=1, c1, c3))).

(c) Translated TondIR code.

⬇

WITH v1(ID, c0, c1) AS {

SELECT r1.ID, r1.c0, r2.c1

FROM x AS r1, y AS r2 WHERE r1.ID = r2.ID },

v4_1(ID, c0, c1, c2, c3) AS {

SELECT r1.ID,

SUM(r1.c0*r2.c0) AS c0, SUM(r1.c0*r2.c1) AS c1,

SUM(r1.c1*r2.c0) AS c2, SUM(r1.c1*r2.c1) AS c3

FROM v1 AS r1, v1 AS r2

WHERE r1.ID = r2.ID GROUP BY r1.ID },

v4_2(c0) AS { VALUES (0), (1) },

v4_3(ID, c0, c1) AS { SELECT

(CASE WHEN r2.c0=0 THEN r1.c0 ELSE r1.c2) AS c0,

(CASE WHEN r2.c0=1 THEN r1.c1 ELSE r1.c3) AS c1,

FROM v4_1 AS r1, v4_2 AS r2 } SELECT * FROM v6

(d) Generated SQL code.

Figure 2: Example of an end-to-end translation from Python to SQL.

Backend Adaptation. Although most relational database engines have adopted the
standard SQL as their interface language, there are minor details, mostly in
the interface of their external functions (e.g. string operations), that the
code generator should be aware of to generate a target-compliant SQL code.
TondIR makes it easy to support different dialects of SQL required by DBMSes,
without the need to change any other components of PyTond; we generate SQL
code compatible with two modern database systems (cf. Section V-A).

###  III-F Putting it All Together

To conclude Section III, we present an end-to-end example, demonstrating the
compilation from a hybrid (Pandas/NumPy) program to SQL (Figure 2). In this
example, we first join relations x and y on their shared id column. Then, we
drop the id and convert the result DataFrame to a NumPy array (a).
Subsequently, we pass the created array as the operands to an einsum API call
that computes a covariance matrix.

As the first step, Python code will be transformed to its ANF version (Figure
2(b)). Then, the equivalent TondIR code of the ANF program is generated
(Figure 2(c)). As discussed in Section III-E, TondIR does not allow dropping
the ID columns. Thus, the drop API call is ignored in the translation. Since
we already have the ID column, the to_numpy API call is also ignored. Finally,
PyTond plans the einsum API call and generates TondIR using the ES8 kernel
(cf. Table VI). In the last phase of the transformations, based on the rules
and techniques discussed in Section III-E, PyTond generates SQL code using the
TondIR representation of the program (Figure 2(d)).

##  IV Efficiency

In this section, we discuss the optimizations applicable to the TondIR
representation of a data science workload. We will evaluate the effects of
these optimizations in Section V-C.

Local Dead Code Elimination. Local optimizations are applicable to a single
rule in TondIR. Here is an example:

⬇

R1(y) :- R(a, b), (x=a), (y=a*b).

$\big{\Downarrow}$

⬇

R1(y) :- R(a, b), (y=a*b).

As it is shown, there is an assignment in the rule that its variable is not
listed in the head of the rule. In such cases, we remove the redundant
assignment.

Global Dead Code Elimination. Global optimizations are applied to a TondIR
program beyond the scope of a single rule. Consider the following code in
TondIR:

⬇

R1(a, b, c, d) :- R(a, b, c, d), (a<10), (c=d).

R2(a, s) group(a) :- R1(a, b, c, d), (s=sum(a)).

$\big{\Downarrow}$

⬇

R1(a, b) :- R(a, b, c, d), (a<10), (c=d).

R2(a, s) group(a) :- R1(a, b), (s=sum(b)).

We see that the attributes in the positions of variables c and d are not used
in the second rule but are listed on the head of the first rule. In this
scenario, we eliminate these unnecessary attributes from the first rule.

Group-Aggregate Elimination. There are cases where we can eliminate group-by
aggregations. Consider this example:

⬇

R1(ID, s) group(ID) :- R(ID, a, b, c), (s=sum(b)).

$\big{\Downarrow}$

⬇

R1(ID, s) :- R(ID, a, b, c), (s=b).

In this example, there is a group-by-summation on the primary key of the
relation R1. In such cases, if we know that the grouping column(s) are unique,
we can remove the grouping and all the summation columns. PyTond brings this
knowledge from the annotations or database catalog during the Python to TondIR
translation (Section III-A).

Self-Join Elimination. In certain situations, there are redundant self-joins.
Consider the following example:

⬇

R1(z) :- R(a,b1,c1,d1), R(a,b2,c2,d2), (z=b1*c2).

$\big{\Downarrow}$

⬇

R1(z) :- R(a1,b1,c1,d1), (z=b1*c1).

In this example, we can eliminate the self-join since (1) it is on a unique
column and (2) no filter is applied to either of the relations. In this case,
all the information needed from the second relation can be obtained from the
first one without any loss.

Rule Inlining. By applying this optimization, we aim to fuse a chain of rules
until we reach specific rules that are not fusible. We call these specific
rules flow breakers.222Not be confused with pipeline breakers in query
engines. Thus, in the first step, we find the dependency among rules and make
a dependency graph. Then, based on the structure of each rule and the
information in the dependency graph, we find the flow-breaker rules. In Table
VII, we summarized different kinds of flow breakers. To preserve the program
semantics, we reset the index column (using UID) in each flow-breaker rule. We
also do the same when facing joins in the rules. An example of rule inlining
is shown below:

TABLE VII: List of the flow breakers used in rule inlining. Flow Breaker | Description
---|---
Aggregate |  agg term in the body
Group By |  group clause in the head
Distinct |  unique term in the body
Sort/Limit |  sort and limit clauses in the head
Outer Join | outer-join terms (cf. Section III-C) in the body
Sink Rule | final rule in the program

⬇

R2(b, c, d) :- R1(a, b, c, d), (a > 1000).

R3(b, d) :- R2(b, c, d), (c != "A").

R5(e, g) :- R4(e, f, g), (f > 100).

R6(b, g) :- R3(b, x), R5(x, g)

R7(b, m) group(b) :- R6(b, g), (m = max(g)).

$\big{\Downarrow}$

⬇

R7(b, m) group(b) :-

R1(a, b, c, x), (a > 1000), (c != "A"),

R4(x, f, g), (f > 100), (m = max(g)).

Back to our end-to-end translation example, now we see the opportunity for
applying group-aggregate elimination, self-join elimination, and rule inlining
on the TondIR representation of the program in Figure V-B.

##  V Evaluation

Figure 3: Performance results for TPC-H workloads on a single thread. Figure
4: Performance results for TPC-H workloads on 4 threads.

In this section, we evaluate our approach using different workloads and assess
its performance compared to competitors. After presenting the experimental
setup, we discuss the results of our end-to-end benchmarks. Then, through
micro-benchmarks, we analyze the scalability of PyTond and discuss the impact
of different optimizations.

###  V-A Experiments Setup

To conduct the experiments, we used a single machine equipped with 16GB of
DDR4 RAM and an Intel Core i5 1.6GHz with four cores and 256KB, 1MB, and 6MB
of L1, L2, and L3 cache, respectively. Hyper-threading is disabled. We run
experiments on Ubuntu 20.04 and use Python 3.10.13, NumPy 1.25.2, and Pandas
2.2.0. To compare the effects of different database engines as our backends,
we use two modern database engines with different query execution paradigms.
The first one is DuckDB [31], a column-based vectorized in-memory database
engine embedded in Python. The second one is Hyper [32], a column-based in-
memory engine representative of compiled query engines in our experiments. As
our third backend option, we use LingoDB [20], an approach for efficient SQL
to LLVM compilation (cf. Section VI). Since LingoDB is a research prototype,
we show its results whenever the SQL workloads can be executed correctly on
this engine. Specifically, we exclude the Grizzly/LingoDB alternative as it
lacks the support for certain SQL window functions required for UID generation
(cf. Section III-C). We use DuckDB Python API 0.9.1, Hyper Tableau API
0.0.17782, and LingoDB Python API 0.0.1. We did five warm-up rounds in all the
experiments and reported the mean of the next five execution rounds.

Figure 5: Performance results for data science workloads on a single thread.
Figure 6: Performance results for data science workloads on 4 threads.

Workloads. We included a range of experiments to show the applicability of our
approach to various data science workloads. We use the dense layout (cf.
Section III) for linear algebra operations since it is (1) similar to the data
layout to which the original Python code has access and (2) limitedly
investigated by the current approaches [3, 4]. The characteristics of each
approach are defined below.

  * •

TPC-H Queries: TPC-H benchmark [33] is well-known in the analytical query
processing. We use the Pandas version of TPC-H queries from [34] and run the
queries on the TPC-H dataset with a scaling factor of 1. Although this
benchmark does not represent the wide spectrum of data science workloads, it
makes us confident about the system’s ability to capture and process
relational algebra, which is the backbone for most of the data analytics
tasks.

  * •

Crime Index: We include the Crime Index data science notebook [11] (with the
scaling factor of 100) as a hybrid workload containing a sequence of Pandas,
NumPy, and again Pandas operations. It filters an input DataFrame, converts it
to an array, computes an einsum, converts the result of einsum back to a
DataFrame, and returns the results after further filtering and projections.

  * •

Birth Analysis: This is another hybrid data science notebook [11] that
contains NumPy Fancy Indexing and Pandas pivot_table APIs. We used the
available statistical dataset for this experiment.

  * •

Kaggle Data Science Notebooks: We also bring two top-voted Kaggle data science
workloads (N3 and N9) into our evaluation. The details of these benchmarks are
discussed in PyFroid [8]. We used the computational parts of the notebooks
(non-visualization parts) for the experiments.

  * •

Hybrid Matrix Calculation Experiments: Besides the real-world data science
workloads introduced before, this category adds two synthetic hybrid
workloads. In both workloads, we first use Pandas to join two large tables.
Then, we convert the result to a NumPy array. Finally, we execute an einsum
over the results. In the first experiment, the einsum operation is a matrix-
vector multiplication, while in the second one, it is a covariance matrix
computation. We also include a slightly modified version of each experiment
(Filtered version) where a join-dependent filter is applied to the results of
the initial join, before doing the final einsum calculation.

Alternatives and Competitors. To evaluate the performance of our approach, we
included two competitors in our experiments. The first one is Python. We
compare our in-database approach with the normal execution of workloads in
Python, which is backed by Pandas and NumPy implementations. The second
competitor is Grizzly [6]. However, as it will be discussed in Section VI, its
available version cannot provide the necessary support for our Pandas
workloads. We assumed that Grizzly could cover our experimental workloads and
consider the challenges in Python translation and SQL code generation (Section
III). By putting this assumption, its generated SQL code would be similar to
PyTond’s generated code before applying the optimizations. We use this
simulated approach as our second competitor. There are barriers to including
other competitors in our experiments. Firstly, except Grizzly, which we
compare against, other very relevant approaches such as PyFroid [8] and Ponder
[35] lack accessible implementations for comparison. Secondly, certain
competitors such as Daphne [36] do not offer automated translations from
Pandas/NumPy, necessitating different workload versions written in their
specific APIs. These approaches are aligned with our goal of efficient data
science but not with a focus on automated SQL code generation and its
mentioned challenges. Alternatives such as Modin [7] and Dask [37] are known
for their high memory demand or distributed setup requirements [8]. However,
PyTond aims to assist data scientists whether they are on commodity
workstations or the cloud. Our preliminary analysis of Modin (on the same
machine described in Section V-A) shows poor performance (slower than Pandas)
across TPC-H, Crime Index, and Birth Analysis benchmarks.

Figure 7: Scalability analysis for representative TPC-H workloads on 1, 2, 3,
and 4 threads. Figure 8: Scalability analysis for hybrid workloads on 1, 2, 3,
and 4 threads. Figure 9: Performance comparison of Covariance Matrix
computation in NumPy vs PyTond with different backends and layouts. The
PyTond/Hyper (Sparse) alternative is eliminated because of its incompetency.
We cut the very large values for PyTond/DuckDB (Sparse) to improve the
readability of the chart. We used 1,000,000 rows, 32 columns, and a sparsity
of 1 for the fixed dimensions. Both axes are on a logarithmic scale.

###  V-B End-to-End Benchmarks

In our end-to-end benchmarks, we measure the performance of all workloads when
executed by our predefined alternatives. Since we assume that the data is
already settled in the database (cf. Section II) and to do a fair comparison,
we exclude the data loading time from all alternatives. The vertical axis in
all Figures is in log-scale format.

We depicted the results of end-to-end experiments in the Figures 3, 4, 5, and
6. Figures 3 and 4 show the results for all TPC-H queries on 1 and 4 threads,
respectively. The initial observation drawn from these two charts is that
PyTond is the first approach, offering complete coverage for the TPC-H
benchmark. Figure 3 also shows that for almost all queries, even the Grizzly-
simulated approach (on different backends) performs better than the normal
Python execution. It also shows that our approach can make the Grizzly-
simulated approach much more efficient using its novel SQL rewriting. The
effects of optimizations done in PyTond are more significant on the DuckDB
backend, as we see a geometric average of 1.55$\times$ and 1.44$\times$
speedup on all queries after enabling them in DuckDB and Hyper. This implies
that Hyper backend does more advanced query planning than DuckDB. Figure 4
also verifies the same observations seen in Figure 3. Furthermore, it
highlights that besides its inherent superiority over Python, our approach can
benefit from parallelization, a feature not offered by Pandas. To summarize
our TPC-H benchmarks, compared to Python and on a single thread, PyTond
achieves a geometric average of 15$\times$ and 3.6$\times$ speedup on Hyper
and DuckDB, respectively. It also achieves a geometric average speedup of
40$\times$ and 8$\times$ on the same engines on 4 threads. About the LingoDB
backend, although its join processing could not process our generated SQL for
Q12, in all other cases, its performance is similar to DuckDB.

The next two figures are related to our real-world and synthetic data science
experiments. Successful execution of these experiments implies that our
approach can capture Pandas/NumPy workloads with a variety of (complex) APIs
such as DataFrame manipulations, pivot_table, and einsum. Figure 5 shows that
PyTond is still competent or more efficient than Python and Grizzly-simulated
approaches. These experiments reveal that even a systematic approach for
Python to SQL translation (Grizzly-simulated) cannot offer high performance
before applying the necessary optimizations. This can be seen in the relative
performance of PyTond and Grizzly-simulated in all experiments, especially N3
and Crime Index. Further investigation on the effect of individual
optimizations on the performance of PyTond is covered in Section V-C. Similar
to Figure 4, Figure 6 also verifies the same mentioned facts about the single-
threaded setting of hybrid experiments while still showing the superiority of
PyTond on 4 threads. An interesting result emerges from the N3 experiment,
where PyTond achieves two orders of magnitude higher performance than Python.
In this experiment, the Pandas data science code conducts a pipeline of
relational algebra operations on 700MB of airline data. By analyzing the
entire code, PyTond generates a compact and efficient SQL that executes the
entire pipeline with minimal data copying and movement, leading to significant
efficiency gains.

To investigate the performance of our approach in the context of linear
algebra, we did a benchmark on Covariance Matrix computation, which is a
fundamental algebraic operation used in machine learning. The results of these
experiments are shown in Figure 9. In this benchmark, we take three primary
properties of the input matrix including the number of rows, number of
columns, and sparsity into account. In each chart, we fix two of these
properties and vary the other one. The sparsity (left-most) charts clearly
demonstrate that our sparse approach overtakes NumPy and other alternatives
when the data is sparse. This is a significant achievement since the majority
of machine learning models are sparse matrices. The other charts also imply
that PyTond on Hyper is faster or competitive to NumPy with different input
shapes.

###  V-C Micro-Benchmarks

This section shows the results of two different sets of micro-benchmarks.
First, we assess the scalability of our approach on the number of threads.
Then, we show the individual effects of each optimization on the PyTond’s
overall performance.

Scalability Analysis. Figures 7 and 8 illustrate the scalability of Python,
Grizzly-simulated approach, and PyTond on DuckDB, Hyper, and LingoDB backends.
The scalability of each approach is shown in terms of speedup over its single-
threaded performance. For brevity, we included a representative set of TPC-H
queries [12] in our scalability experiments. These Figures show a smooth
scale-up in PyTond’s performance specifically on DuckDB and Hyper backends. We
can even find a near-linear scale-up in different cases including Q4, Q6, Q13,
Crime Index, N3, and N9. In the Birth Analysis and N9 cases, the overall
optimized run time is small, so the scalability results show saturated
performance for some backends. In all of these experiments, there are two root
causes behind Python’s poor scalability. First, Pandas library does not
support parallelization. Second, the more time-consuming part of hybrid
workloads is attributed to Pandas code.

Figure 10: Break-down of optimizations applied to experimental workloads. O1:
Global/Local Dead Code Eliminations, O2: O1 + Group/Aggregate Elimination, O3:
O2 + Self-join Elimination, O4: O3 + Rule Inlining

Effect of Optimizations. We analyzed the effects of optimizations for a
representative subset of the workloads by starting from our baseline code
(Grizzly-simulated) and applying each optimization on top of the others. The
results are portrayed in Figure 10. This figure implies that all of the
optimizations introduced in Section IV are beneficial in their relevant
scenarios. The O1 alternative shows the effects of Dead Code Eliminations that
improve the performance of Q9 in DuckDB. The O2 alternative adds the
Group/Aggregate Elimination and affects the Crime Index on both backends. This
inefficiency is because of using a generalized einsum translation in the Crime
Index that cannot be avoided (cf. Section III-D). The O3 alternative further
improves the previous ones by applying Self-join Elimination, which affects
the Hybrid Covar on both backends. Finally, in O4, we introduce Rule Inlining,
that its individual and combined effects result in huge performance
improvements in most of the experiments.

##  VI Related Work

In this section, we review state-of-the-art research on scalable data
analytics in Python, discussing their characteristics and analyzing their
strengths and weaknesses.

Compilation to Low-Level Code. Solutions in this category [12, 10, 13, 11, 9,
36] generate the low-level equivalent of Python code (e.g. in C++ or LLVM)
that will be compiled for the target machine. SDQL.py [12] generates finely-
tuned parallel C++ code for Pandas workloads by providing a domain-specific
language (DSL) [38, 39] that is embedded [40] in Python. Numba [10] generates
efficient low-level code for numerical operations written using the NumPy
library. Numba users only need to add @jit decorator to their target functions
to make them compiled. Tuplex [13] and Klabe et. al [9] propose code
generation for UDFs (User Defined Functions) in Python. Weld [11] generates
LLVM code by lazy construction of an IR after each library API call. As
opposed to Numba and PyTond, Weld users need to slightly modify the library
APIs to make them adaptable to its compilation pipeline. Daphne [36] provides
an embedded DSL in Python for transforming integrated analytics to low-level
code via MLIR. However, it lacks a compiler for translating Python data
science code like Pandas and NumPy into its DSL, making user adaptation,
benchmarking, and comparison difficult. PyTond provides interfaces for deeply
embedding [41] DSLs including Pandas, NumPy, and TondIR itself in Python. This
is achieved by adding a @pytond decorator to the functions that need to be
compiled into SQL instead of low-level code.

Compilation of SQL queries to low-level code is a well-studied topic [14, 15,
16, 17, 18, 19, 20]. LingoDB [20] introduces an MLIR-based framework that
converts SQL into low-level efficient code. While they demonstrate a use-case
of their approach with a PyTorch example, there is currently no available
implementation of a Python interface for LingoDB for comparison purposes.
Another related research [42] around LingoDB has only shown limited support of
translation from Pandas (only three TPC-H queries), which contrasts with
PyTond’s broad coverage.

The mentioned approaches have shown performance improvements by leveraging a
variety of optimizations (e.g. parallelization and vectorization).
Nevertheless, they introduce compilation overhead and potential portability
issues. They also need users to declare input types, a requirement for low-
level code generation, which can reduce the overall user-friendliness of the
approach.

Compilation to SQL. Approaches in this category [4, 3, 6, 5, 8, 7] aim to push
the execution down into existing database engines by generating SQL code from
source code. By taking this approach, the effort is mostly on a precise
translation and then leveraging the proven optimization and execution power of
databases. ByePy [5] automatically generates SQL for generic imperative Python
code with no support for its popular libraries such as Pandas and NumPy.
Blacher et al. [3] proposed their translation methods based on training simple
machine learning models (e.g., logistic regression). They experimentally show
the merits of a database-friendly (dense) data layout versus the COO (sparse)
one for numerical analysis, however, their approach is not automated. In
another work, Blacher et al. [4] presented a method to generate SQL for linear
algebra workloads written in Einstein notation (einsum API in NumPy). While
their approach can cover n-ary einsum and higher-order tensors, it can only
operate on the data stored in a sparse format which, according to their
experiments, is not always efficient. Grizzly [6] and PyFroid [8] generate SQL
for Pandas. Our reconstruction efforts show that Grizzly APIs are not fully
consistent with their Pandas equivalents and require the user to modify the
source code. Moreover, Grizzly falls short in capturing different query
operators, resulting in a limited coverage of standard TPC-H queries. It is
also important to mention that its generated queries are not idiomatic SQL;
they do not get the best performance from query engines. PyFroid [8] covers a
broader set of APIs and incorporates optimizations on the generated code, the
codebase of which is not accessible for experimentation.

Parallelization. Modin [7] introduces a Dataframe algebra designed to
encapsulate Pandas code and enable parallel execution. However, its reliance
on Pandas as the backend limits achieving optimal performance on each core.

In this paper, by adopting the high-level strategy of the second category, we
convert a wide range of Pandas (RA) and NumPy (LA) workloads to SQL. We use a
decorator-based approach (like Numba [10]) for source code translation to
offer a good user experience. We rewrite (optimize) the generated SQL to fully
exploit the capabilities of the query engine and let it do the
parallelization, vectorization, and other advanced optimizations to
efficiently execute the workload.

##  VII Conclusion and Future Work

Towards enhancing the efficiency of Python data science workloads, we
presented PyTond, a framework for translating Python (Pandas/NumPy) to fine-
tuned SQL that will be executed efficiently by database engines. We discussed
the design of TondIR, our intermediate representation, and elaborated on the
required measures in translation, optimization, and code generation to make
the most of DBMSes. Finally, we evaluated the performance of our approach in
real-world scenarios, demonstrating its competency versus the alternatives. In
the future, we aim to expand the work to capture more complex workloads with
iterations [24, 43], recursions [44, 45], and advanced numeric computations
over higher-order tensors [39, 46].

## Acknowledgement

The authors would like to thank Huawei for their support of the distributed
data management and processing laboratory at the University of Edinburgh. This
work was funded in part by a gift from RelationalAI.

## References

  * [1] “Pandas library,” 2024, https://pandas.pydata.org/.
  * [2] “Numpy library,” 2024, https://numpy.org/.
  * [3] M. Blacher, J. Giesen, S. Laue, J. Klaus, and V. Leis, “Machine learning, linear algebra, and more: Is SQL all you need?” in _12th Conference on Innovative Data Systems Research, CIDR 2022, Chaminade, CA, USA, January 9-12, 2022_. www.cidrdb.org, 2022. [Online]. Available: https://www.cidrdb.org/cidr2022/papers/p17-blacher.pdf
  * [4] M. Blacher, J. Klaus, C. Staudt, S. Laue, V. Leis, and J. Giesen, “Efficient and portable einstein summation in SQL,” _Proc. ACM Manag. Data_ , vol. 1, no. 2, pp. 121:1–121:19, 2023. [Online]. Available: https://doi.org/10.1145/3589266
  * [5] T. Fischer, D. Hirn, and T. Grust, “Snakes on a plan: Compiling python functions into plain SQL queries,” in _SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022_ , Z. G. Ives, A. Bonifati, and A. E. Abbadi, Eds. ACM, 2022, pp. 2389–2392. [Online]. Available: https://doi.org/10.1145/3514221.3520175
  * [6] S. Hagedorn, S. Kläbe, and K. Sattler, “Putting pandas in a box,” in _11th Conference on Innovative Data Systems Research, CIDR 2021, Virtual Event, January 11-15, 2021, Online Proceedings_. www.cidrdb.org, 2021. [Online]. Available: http://cidrdb.org/cidr2021/papers/cidr2021\\_paper07.pdf
  * [7] D. Petersohn, W. W. Ma, D. J. L. Lee, S. Macke, D. Xin, X. Mo, J. Gonzalez, J. M. Hellerstein, A. D. Joseph, and A. G. Parameswaran, “Towards scalable dataframe systems,” _Proc. VLDB Endow._ , vol. 13, no. 11, pp. 2033–2046, 2020. [Online]. Available: http://www.vldb.org/pvldb/vol13/p2033-petersohn.pdf
  * [8] K. V. Emani, A. Floratou, and C. Curino, “Pyfroid: Scaling data analysis on a commodity workstation,” in _Proceedings 27th International Conference on Extending Database Technology, EDBT 2024, Paestum, Italy, March 25 - March 28_ , L. Tanca, Q. Luo, G. Polese, L. Caruccio, X. Oriol, and D. Firmani, Eds. OpenProceedings.org, 2024, pp. 61–67. [Online]. Available: https://doi.org/10.48786/edbt.2024.06
  * [9] S. Kläbe, R. DeSantis, S. Hagedorn, and K. Sattler, “Accelerating python udfs in vectorized query execution,” in _12th Conference on Innovative Data Systems Research, CIDR 2022, Chaminade, CA, USA, January 9-12, 2022_. www.cidrdb.org, 2022. [Online]. Available: https://www.cidrdb.org/cidr2022/papers/p33-klaebe.pdf
  * [10] S. K. Lam, A. Pitrou, and S. Seibert, “Numba: a llvm-based python JIT compiler,” in _Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, LLVM 2015, Austin, Texas, USA, November 15, 2015_ , H. Finkel, Ed. ACM, 2015, pp. 7:1–7:6. [Online]. Available: https://doi.org/10.1145/2833157.2833162
  * [11] S. Palkar, J. Thomas, D. Narayanan, P. Thaker, R. Palamuttam, P. Negi, A. Shanbhag, M. Schwarzkopf, H. Pirk, S. P. Amarasinghe, S. Madden, and M. Zaharia, “Evaluating end-to-end optimization for data analytics applications in weld,” _Proc. VLDB Endow._ , vol. 11, no. 9, pp. 1002–1015, 2018. [Online]. Available: http://www.vldb.org/pvldb/vol11/p1002-palkar.pdf
  * [12] H. Shahrokhi and A. Shaikhha, “Building a compiled query engine in python,” in _Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction, CC 2023, Montréal, QC, Canada, February 25-26, 2023_ , C. Verbrugge, O. Lhoták, and X. Shen, Eds. ACM, 2023, pp. 180–190. [Online]. Available: https://doi.org/10.1145/3578360.3580264
  * [13] L. F. Spiegelberg, R. Yesantharao, M. Schwarzkopf, and T. Kraska, “Tuplex: Data science in python at native code speed,” in _SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021_ , G. Li, Z. Li, S. Idreos, and D. Srivastava, Eds. ACM, 2021, pp. 1718–1731. [Online]. Available: https://doi.org/10.1145/3448016.3457244
  * [14] T. Neumann, “Efficiently Compiling Efficient Query Plans for Modern Hardware,” _PVLDB_ , vol. 4, no. 9, pp. 539–550, 2011.
  * [15] C. Koch, Y. Ahmad, O. Kennedy, M. Nikolic, A. Nötzli, D. Lupei, and A. Shaikhha, “DBToaster: higher-order delta processing for dynamic, frequently fresh views,” _VLDBJ_ , vol. 23, no. 2, pp. 253–278, 2014.
  * [16] A. Shaikhha, Y. Klonatos, and C. Koch, “Building efficient query engines in a high-level language,” _ACM Transactions on Database Systems_ , vol. 43, no. 1, pp. 4:1–4:45, Apr. 2018.
  * [17] A. Shaikhha, Y. Klonatos, L. Parreaux, L. Brown, M. Dashti, and C. Koch, “How to architect a query compiler,” in _Proceedings of the 2016 International Conference on Management of Data_ , ser. SIGMOD’16. New York, NY, USA: ACM, 2016, pp. 1907–1922.
  * [18] S. Viglas, G. M. Bierman, and F. Nagel, “Processing Declarative Queries Through Generating Imperative Code in Managed Runtimes,” _IEEE Data Eng. Bull._ , vol. 37, no. 1, pp. 12–21, 2014.
  * [19] A. Shaikhha, M. Dashti, and C. Koch, “Push versus pull-based loop fusion in query engines,” _J. Funct. Program._ , vol. 28, p. e10, 2018. [Online]. Available: https://doi.org/10.1017/S0956796818000102
  * [20] M. Jungmair, A. Kohn, and J. Giceva, “Designing an open framework for query optimization and compilation,” _Proc. VLDB Endow._ , vol. 15, no. 11, pp. 2389–2401, 2022. [Online]. Available: https://www.vldb.org/pvldb/vol15/p2389-jungmair.pdf
  * [21] “Numpy einsum api,” 2024, https://numpy.org/doc/stable/reference/generated/numpy.einsum.html.
  * [22] T. Kersten, V. Leis, A. Kemper, T. Neumann, A. Pavlo, and P. A. Boncz, “Everything you always wanted to know about compiled and vectorized queries but were afraid to ask,” _Proc. VLDB Endow._ , vol. 11, no. 13, pp. 2209–2222, 2018. [Online]. Available: http://www.vldb.org/pvldb/vol11/p2209-kersten.pdf
  * [23] S. Abiteboul, R. Hull, and V. Vianu, _Foundations of Databases_. Addison-Wesley, 1995. [Online]. Available: http://webdam.inria.fr/Alice/
  * [24] A. Shaikhha, D. Suciu, M. Schleich, and H. Q. Ngo, “Optimizing nested recursive queries,” _Proc. ACM Manag. Data_ , vol. 2, no. 1, pp. 16:1–16:27, 2024. [Online]. Available: https://doi.org/10.1145/3639271
  * [25] M. Ghorbani, M. Huot, S. Hashemian, and A. Shaikhha, “Compiling structured tensor algebra,” _Proc. ACM Program. Lang._ , vol. 7, no. OOPSLA2, pp. 204–233, 2023. [Online]. Available: https://doi.org/10.1145/3622804
  * [26] M. Abo Khamis, H. Q. Ngo, and A. Rudra, “FAQ: Questions Asked Frequently,” in _Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , ser. PODS ’16. New York, NY, USA: Association for Computing Machinery, 2016, pp. 13–28.
  * [27] “The Rel Language,” 2024, https://docs.relational.ai/rel.
  * [28] L. Maurer, P. Downen, Z. M. Ariola, and S. L. P. Jones, “Compiling without continuations,” in _Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, Barcelona, Spain, June 18-23, 2017_ , A. Cohen and M. T. Vechev, Eds. ACM, 2017, pp. 482–494. [Online]. Available: https://doi.org/10.1145/3062341.3062380
  * [29] C. Flanagan, A. Sabry, B. F. Duba, and M. Felleisen, “The essence of compiling with continuations,” in _Proceedings of the ACM SIGPLAN’93 Conference on Programming Language Design and Implementation (PLDI), Albuquerque, New Mexico, USA, June 23-25, 1993_ , R. Cartwright, Ed. ACM, 1993, pp. 237–247. [Online]. Available: https://doi.org/10.1145/155090.155113
  * [30] D. G. A. Smith and J. Gray, “opt\\_einsum - A python package for optimizing contraction order for einsum-like expressions,” _J. Open Source Softw._ , vol. 3, no. 26, p. 753, 2018. [Online]. Available: https://doi.org/10.21105/joss.00753
  * [31] M. Raasveldt and H. Mühleisen, “Duckdb: an embeddable analytical database,” in _Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019_ , P. A. Boncz, S. Manegold, A. Ailamaki, A. Deshpande, and T. Kraska, Eds. ACM, 2019, pp. 1981–1984. [Online]. Available: https://doi.org/10.1145/3299869.3320212
  * [32] T. Neumann, “Efficiently compiling efficient query plans for modern hardware,” _Proc. VLDB Endow._ , vol. 4, no. 9, pp. 539–550, 2011. [Online]. Available: http://www.vldb.org/pvldb/vol4/p539-neumann.pdf
  * [33] “Tpc-h benchmark,” 2024, https://www.tpc.org/tpch/.
  * [34] H. Shahrokhi, C. Groeger, Y. Yang, and A. Shaikhha, “Efficient query processing in python using compilation,” in _Companion of the 2023 International Conference on Management of Data, SIGMOD/PODS 2023, Seattle, WA, USA, June 18-23, 2023_ , S. Das, I. Pandis, K. S. Candan, and S. Amer-Yahia, Eds. ACM, 2023, pp. 199–202. [Online]. Available: https://doi.org/10.1145/3555041.3589735
  * [35] “Ponder,” 2024, https://ponder.io/.
  * [36] P. Damme, M. Birkenbach, C. Bitsakos, M. Boehm, P. Bonnet, F. M. Ciorba, M. Dokter, P. Dowgiallo, A. Eleliemy, C. Faerber, G. I. Goumas, D. Habich, N. Hedam, M. Hofer, W. Huang, K. Innerebner, V. Karakostas, R. Kern, T. Kosar, A. Krause, D. Krems, A. Laber, W. Lehner, E. Mier, M. Paradies, B. Peischl, G. Poerwawinata, S. Psomadakis, T. Rabl, P. Ratuszniak, P. Silva, N. Skuppin, A. Starzacher, B. Steinwender, I. Tolovski, P. Tözün, W. Ulatowski, Y. Wang, I. P. Wrosz, A. Zamuda, C. Zhang, and X. Zhu, “DAPHNE: an open and extensible system infrastructure for integrated data analysis pipelines,” in _12th Conference on Innovative Data Systems Research, CIDR 2022, Chaminade, CA, USA, January 9-12, 2022_. www.cidrdb.org, 2022. [Online]. Available: https://www.cidrdb.org/cidr2022/papers/p4-damme.pdf
  * [37] “Dask,” 2024, https://dask.org/.
  * [38] A. Shaikhha, M. Huot, J. Smith, and D. Olteanu, “Functional collection programming with semi-ring dictionaries,” _Proc. ACM Program. Lang._ , vol. 6, no. OOPSLA1, pp. 1–33, 2022. [Online]. Available: https://doi.org/10.1145/3527333
  * [39] M. Schleich, A. Shaikhha, and D. Suciu, “Optimizing tensor programs on flexible storage,” _Proc. ACM Manag. Data_ , vol. 1, no. 1, pp. 37:1–37:27, 2023. [Online]. Available: https://doi.org/10.1145/3588717
  * [40] P. Hudak, “Building domain-specific embedded languages,” _ACM Comput. Surv._ , vol. 28, no. 4es, p. 196, 1996. [Online]. Available: https://doi.org/10.1145/242224.242477
  * [41] V. Jovanovic, A. Shaikhha, S. Stucki, V. Nikolaev, C. Koch, and M. Odersky, “Yin-yang: concealing the deep embedding of dsls,” in _Generative Programming: Concepts and Experiences, GPCE’14, Vasteras, Sweden, September 15-16, 2014_ , U. P. Schultz and M. Flatt, Eds. ACM, 2014, pp. 73–82. [Online]. Available: https://doi.org/10.1145/2658761.2658771
  * [42] R. Imschweiler, “Transforming data frame operations from python to mlir,” Master’s thesis, Technische Universität München, 2022.
  * [43] A. Shaikhha, M. Schleich, A. Ghita, and D. Olteanu, “Multi-layer optimizations for end-to-end data analytics,” in _CGO ’20: 18th ACM/IEEE International Symposium on Code Generation and Optimization, San Diego, CA, USA, February, 2020_. ACM, 2020, pp. 145–157. [Online]. Available: https://doi.org/10.1145/3368826.3377923
  * [44] D. Hirn and T. Grust, “One WITH RECURSIVE is worth many gotos,” in _SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021_ , G. Li, Z. Li, S. Idreos, and D. Srivastava, Eds. ACM, 2021, pp. 723–735. [Online]. Available: https://doi.org/10.1145/3448016.3457272
  * [45] ——, “A fix for the fixation on fixpoints,” in _13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8-11, 2023_. www.cidrdb.org, 2023. [Online]. Available: https://www.cidrdb.org/cidr2023/papers/p14-hirn.pdf
  * [46] A. Shaikhha, M. Huot, and S. Hashemian, “A tensor algebra compiler for sparse differentiation,” in _IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2024, Edinburgh, United Kingdom, March 2-6, 2024_ , T. Grosser, C. Dubach, M. Steuwer, J. Xue, G. Ottoni, and ernando Magno Quintão Pereira, Eds. IEEE, 2024, pp. 1–12. [Online]. Available: https://doi.org/10.1109/CGO57630.2024.10444787