text:
\subsection{New Algebra Challenges}\label{sec:algebra-challenges}

\section{data model challenges}\label{sec:datamodel}

\rebuttal{
Supporting
the dataframe data model and algebra from
Section~\ref{sec:definitions} efficiently
motivates a new set of
research challenges.
We organize
these challenges based on
unique properties of dataframes,
and discuss their impact
on query optimization, data layout,
and metadata management.
We first discuss the impact of flexible schemas.
}

\subsection{Flexible Schemas, Dynamic Typing}
\input{flexible-schema-new.tex}

\subsection{Order and Equivalence}\label{sec:order_challenges}
\rebuttal{
Unlike relations, dataframes are ordered
along both rows and columns---and users
rely on this ordering for debugging and validation
as they compose dataframe queries incrementally.
This order is maintained as rows are transformed
into columns and columns into rows via \code{TRANSPOSE},
ensuring near-equivalence of rows and columns.
Finally, as we saw in Section~\ref{sec:algebra-example},
row and column label metadata is
tightly coupled with the dataframe content,
and inherits the order and typing
properties.
Unlike in
relational databases,
where metadata is largely distinct from the data,
data and
metadata are interchangeable within dataframes.
Data can be promoted into metadata via \code{TOLABELS},
likewise metadata can be demoted
into the data via \code{FROMLABELS}.
In this section, we discuss
the challenges imposed by enforcing
order and the frequently changing
schema across row and column labels and row/column orientation.
}

\rebuttal{
\subsubsection{Order is Central}
The order of a dataframe is determined by the
order of ingested data.
For example, a CSV file ingested as a
dataframe would have the same
row and column order as the file.
This ordering is crucial for the trial-and-error-based
interaction between a user and a dataframe system.
User expect to see the same rows
in the dataframe in the same order
as they process it---allowing
them to validate and debug each step
by comparing its result to the previous step.
For example, to ensure that
a CSV file is ingested and parsed correctly,
users will expect the first few rows
of the dataframe to be the same
as those they would see when examining the CSV
file.
To examine a dataframe, users
will either use the operator
\code{head/tail} to see the prefix/suffix
or simply type the name of the dataframe
for both the prefix and suffix
in the expected order.
Additionally,
operators such as \code{WINDOW} and \code{MAP}
from Section~\ref{sec:df-algebra}
expect a specific
order for the rows (\code{WINDOW}) and
columns (\code{MAP}).
since the UDF
argument to these operators may
rely on that order.
Dataframes also support \code{SELECTION} and \code{PROJECTION}
based on the position of the rows and
columns respectively.
}

\rebuttal{
To support order, current dataframe systems,
such as pandas\xspace,
physically store the dataframe
in the same conceptual order as defined by the user.
As a result, they do not obey physical data independence.
}\moved{%
This constraint is not necessary,
and removing it may open up new optimization
opportunities,
from recognizing that as long as
the displayed results preserve
the desired order semantics
to the users, it is not necessary
that all intermediate products
or artifacts (unobserved by user)
adhere to the order constraint.
For example,
a sort operation can be ``conceptual''
in that a new order can be defined without
actually performing the expensive
sorting operation.
Likewise, a transpose
doesn't require the data to be reoriented
on physical storage unless beneficial
for subsequent operations, instead
being captured using metadata updates
to reflect the new
orientation of the dataframe.
}

\rebuttal{To ensure correct semantics,
while respecting physical data independence,
we must devise means to capture ordering
information, either tracked
as a separate ``order column'',
if it is not implied via existing columns,
or recording as metadata that the dataframe
must be ordered based on one or more
of the preexisting
columns.
Then, the \code{ORDER BY}
on this ``order column'' or one of the existing columns
will be treated as an
operator in the query plan, and will only need to be
done ``on-demand'' when the user requests to view a result.
Additionally, since users
are only ever looking at the first and/or last few lines
of the dataframe, those are the only lines that are required
to be ordered; we discuss this further
in Section~\ref{sec:immediate-feedback}.}

\rebuttal{%
Extending physical data independence even further,
we can adapt other data representation
techniques from the database community,
optimized for dataframes.
This includes columnar
or row-column hybrid storage~\cite{abadi2013design},
as well as those from
scientific computing~\cite{choi1992scalapack},
array databases~\cite{rusu2013survey}
or spreadsheets~\cite{bendre2015dataspread}.
Since dataframes are neither relations,
matrices, arrays, or spreadsheets, none
of these representations are a perfect fit.
Given that rows and columns are equivalent,
one promising representation for
dataframes is storing it as
key-value pairs,
where the key corresponds to the
(row number, column number)
pair.
This representation
is especially effective when
the dataframe is ``sparse'', allowing
us to omit pairs where the value is null.
Then, \code{TRANSPOSE} conceptually
swaps the row and column for each value:
$(column, row, value)$,
and can be recorded in metadata.
However, some operations become more expensive,
e.g. reconstructing a row for a \code{MAP}
operation requires a join.
Overall,
automatically detecting the right representation
and updating it over the course of dataframe query
execution will be substantial challenge.}

\techreport{
\moved{%
Given a certain physical representation,
operations on dataframes,
from a relational perspective, often make use
of ordered access, e.g.,
editing the $i^{\textrm{th}}$ row,
as well as access
based on the row labels, e.g.,
filtering based on row labels (named notation)
or row position (positional notation).
Because
selecting the $i^{\textrm{th}}$ physical row or projecting the $j^{\textrm{th}}$ physical column
will not necessarily correspond to selecting (resp.\ projecting) the desired {\em logical}
row (resp.\ column), additional metadata
that serves as the "order column" or "order row" must be maintained to facilitate
order-independence of the physical data.
Automatically
maintaining
indexes for this purpose can be beneficial.
Recent work has developed positional
indexing~\cite{bendre2018towards}, allowing ordered
access to be supported in $O(\log n)$,
in the presence of edits (e.g., adding or removing
rows).
Column stores take a different approach
to avoid expensive edits across columns,
instead
recording edits separately as deltas,
and periodically merging them back in~\cite{abadi2013design};
it would be interesting to investigate which approach is more effective for a given set of dataframe operations.
Similarly, for matrices, accesses often
happen in a row-major or column-major order,
and identifying the right indexes to efficiently
support them in conjunction
with relational-style accesses, is an important
challenge.
In particular, when a dataframe
has many rows and many columns,
we may need both row-
and column-oriented indexing.
}
}

\input{pivotplans.tex}

\rebuttal{
\subsubsection{Row/Column Equivalence}
\label{sec:rowcolumneq}
}
\rebuttal{
The presence of a \code{TRANSPOSE} operator in the
dataframe algebra
presents novel challenges in data layout and query optimization.
\code{TRANSPOSE} allows users to flexibly alter
their data into a desired shape or schema that can be
parsed according to an appropriate schema, and
queried using ordered relational operators.
}

\rebuttal{
To keep our data model and algebra compact,
we have schemas only for columns, and
our operators are defined on ordered sets of rows.
By contrast, in pandas\xspace and other dataframe implementations,
it is possible to
perform many operations
along either the rows or
columns via the \code{axis}
argument.
Hence programs written in (or translated to) our algebra
are likely to have more uses of \code{TRANSPOSE} than dataframe
programs in the wild, to represent columnwise operations and/or
to reason about per-row schemas.}
\rebuttal{These operations are expressible in our simpler algebra
by first performing a
\code{TRANSPOSE}, applying
the operation, and then a \code{TRANSPOSE}
again to return to the original orientation.
}

\rebuttal{The prevalence of \code{TRANSPOSE} in
dataframe programs overturns many axis-specific assumptions made in traditional database storage.
Axis-specific data layouts like columnar compression are problematic in this context.
Metadata management also requires rethinking, since dataframes are as likely to
be extremely
``wide'' (columnwise) as they are ``tall'' (rowwise).}
\rebuttal{
Both traditional and embedded RDBMSs typically limit the number of columns in a
relation (e.g., SQL Server has an upper limit of 1024
columns, or 30k columns using the wide-table feature)~\cite{raasveldt2019duckdb, sqlite2020hipp}.
By applying \code{TRANSPOSE} on
a tall and narrow dataframe,
the number of columns can easily exceed the millions
in the resulting short and wide dataframe.
}

\rebuttal{
Dataframe systems
will need careful consideration to ensure that a \code{TRANSPOSE} call does not
break assumptions made by the data layout layer.
}
\rebuttal{
Given that the cost of performing a physical transpose will often
be high,
one potential way to handle the data layout layer optimization
problem is to do a {\em logical} \code{TRANSPOSE} ``pull-up''. This would
delay or eliminate transpose in the physical plan as much as
possible since it will often destroy or render moot many
existing data layout optimizations.
}

\rebuttal{
In some cases, we may want to consider optimizing
the \emph{physical} layout of the data given a \code{TRANSPOSE}
operator as a part of a query plan.
This is in stark contrast with most existing data
systems which create and optimize for a static data layout.
A physical transpose may help the optimizer match the layout to the
access pattern (e.g. matrix multiplication). A fixed data layout
is likely to have a significant performance penalty when
the access pattern changes.
Additionally, consider a case where \code{TRANSPOSE}
allows us more flexibility in query planning.
In the \code{pivot} case in Section~\ref{sec:algebra-example},
we observed that transposing the result of a pivot
is effectively a pivot across the other column.
This flexibility allows us to potentially do the \code{GROUP BY}
on a sorted column, if it more cost effective
to do the \code{TRANSPOSE} at the end.
This is an interesting example of a
new class of potential optimizations within
dataframe query plans that exploit an efficient
\code{TRANSPOSE}. Because the axis transpositions are happening in query expressions,
the data layout becomes a physical plan property akin to ``interesting orders''~\cite{selinger1979access}
or ``hash teams''~\cite{graefe1998hash},  expanding the rules for query optimization.
}

\rebuttal{
\subsubsection{Metadata is Data (and Data is Metadata).}
Dataframes have the unique capability to move data to metadata
and back. This is available through the \code{TOLABELS}
and \code{FROMLABELS} operators, where a column of
data is elevated to the row labels in \code{TOLABELS},
or the labels are inserted into the data with \code{FROMLABELS}.
This capability provides extreme flexibility in manipulating
and coercing data, but presents some new challenges in
metadata management.
}

\rebuttal{
From the perspective
of an RDBMS, integration of row labels would not be particularly
challenging;
they can be defined as a ``special column'',
perhaps optimized for fast performance of filter or point queries
with an index structure.
However in the presence of millions of rows,
a \code{TOLABELS} becomes as expensive as
creating a new index,
which is frustrating if the new labels
only serve an aesthetic purpose.
It may make sense in some cases to do a logical
\code{TOLABELS} by flagging the label column, and postpone building an index on the
labels in the interest of performance.
The tradeoff with this optimization will be the
speed at which filter queries on the labels can
execute.
This requires an understanding not only of the workload of expressions in the data science
program, but also the user's intent (Section~\ref{sec:interactivity}).
}

\jmh{I think we should redo or chop this paragraph. I think what we're saying here (that's not
somewhere above) is
that TOLABELS/FROMLABELS changes the column position values, which could cause you
to consider changing the table layout. We already said that we have expensive type induction
and optimization opportunities for table layout; I'm not sure why we're focusing on it here.
The idea that we have to redo all the column position indexing is vaguely annoying but probably easily handled
in an appropriate index.}
\rebuttal{
The column and row label metadata in dataframes
come from the same
set of domains as the data.
This creates new challenges in metadata placement
for dataframes. Metadata placement is likely to
become a new operator in the query plan, where
a dataframe query optimizer will need to decide whether to
keep metadata in the data or separate.
Since the schema induction function $S$
is not defined on the column labels,
a column's type must be induced before
it is physically separated from the data.
This introduces new tradeoffs between physically
separating the labels from the data to create
fast point queries with indexing structures.
There is a non-trivial overhead to physically
separating a column of data into the metadata
due to the maintenance of the indexing structure,
type induction, and the cost of physical data movement.
If the user is frequently
moving data to and from the dataframe
labels, the performance penalty for physical
updates is likely to dominate the overall query cost.
The query optimizer must model likely user interactions
in the physical plan for a \code{TOLABELS} operation.
}

\jmh{I have problems with this paragraph too. (1) This is not schema \emph{mutation}, since we don't update the dataframes, we just compute new ones.
It's not really like DDL or migrations. The example is not like DDL. And relational operations like Project ``change the schema'' of the output relative to the input. So I don't get what's new from that perspective. (2) The example doesn't require
metadata manipulation like pivot, I don't think. I believe it's an example of a groupby optimization: if your table $(X,Y,Z)$ is sorted by $X$ and you want to group by $Y$ and there are lots of different $Z$ values, you can group by $(X,Y)$ for cheap first to shrink the $Z$s away, and then group the smaller result by $Y$. I'm not sure where I've seen it, probably in datacube papers. In any case, I don't think it has much to do with schema changes.}
\rebuttal{
Schema changes are typically performed offline
as explicit DDL statements in relational databases. In contrast,
dataframe schemas mutate frequently \emph{during} typical queries,
thanks to the transpose and label-moving operations.
As such, {\em dataframe query
optimizers must model schema-changing operations explicitly}.
Consider the pivot example from Section~\ref{sec:algebra-example},
and suppose the narrow table in Figure~\ref{fig:pivot} is to be pivoted
into the wide table with \code{Month}s as columns.
The desired output can be achieved in at least two ways: {\em (i)} the straightforward way,
whereby the \code{Month} column is used in an initial \code{GROUP BY}, or {\em (ii)}
the optimized way, whereby the optimizer proceeds as if the pivot were over the \code{YEAR}
column, but then transposes the final result so that the \code{Month} attribute values
are used as column headers.
These two plans are depicted in Figure~\ref{fig:pivotplans}.
The latter plan will be faster if the optimizer leverages knowledge
about the sorted order of the \code{Year} column to avoid hashing the groups.
To do so, however, the optimizer must be deeply aware of how the \code{Month} attribute values
(ultimately destined to be column headers) flow through the plan, which we foresee as a
major challenge moving forward.
}

\jmh{If I don't like FROM/TOLABELS or this schema mutation idea, what would I say here? Why is the promotion of data into metadata hard for query processing? (1) Operations like pivot or map make query cost estimation
tricky because now we have to estimate the number of rows AND columns in output. For pivot or 1-hot-encoding this is distinct value estimation so maybe some tricks, but MAP is a black box! (2) We have to derive the metadata before we derive the data, so it's easy to end up with 2-pass algorithms if you're not smart. Example: UNION over two MAPs, where the MAPs can return an unknown schema. Do we first run the maps, then scan them to figure out types, then check union-compatibility? Can we pipeline? Sorry not to write this out in more detail but it's late and I need to get to the next paper.}

\section{data model challenges}\label{sec:datamodel}

\rebuttal{
Supporting
the dataframe data model and algebra from
Section~\ref{sec:definitions} efficiently
motivates a new set of
research challenges.
We organize
these challenges based on
unique properties of dataframes,
and discuss their impact
on query optimization, data layout,
and metadata management.
We first discuss the impact of flexible schemas.
}

\subsection{Flexible Schemas, Dynamic Typing}
\label{sec:flexschemas}
\input{flexible-schema-new.tex}

\subsection{Order and Equivalence}\label{sec:order_challenges}
\rebuttal{
Unlike relations, dataframes are ordered
along both rows and columns---and users
rely on this ordering for debugging and validation
as they compose dataframe queries incrementally.
This order is maintained as rows are transformed
into columns and columns into rows via \code{TRANSPOSE},
ensuring near-equivalence of rows and columns.
Additionally, as we saw in Section~\ref{sec:algebra-example},
row and column label metadata is
tightly coupled with the dataframe content,
and inherits the order and typing
properties.
In this section, we discuss
the challenges imposed by enforcing
order and the frequently changing
schema across row and column labels and row/column orientation.
}

\rebuttal{
\subsubsection{Order is Central}
The order of a dataframe is determined by the
order of ingested data.
For example, a CSV file ingested as a
dataframe would have the same
row and column order as the file.
This ordering is crucial for the trial-and-error-based
interaction between a user and a dataframe system.
Users expect to see the rows
in their dataframe stay in the same order
as they process it---allowing
them to validate and debug each step
by comparing its result to the previous step.
For example, to ensure that
a CSV file is ingested and parsed correctly,
users will expect the first few rows
of the dataframe to be the same
as those they would see when examining the CSV
file.
To examine a dataframe, users
will either use the operator
\code{head/tail} to see the prefix/suffix
or simply type the name of the dataframe
for both the prefix and suffix
in the expected order.
Additionally,
operators such as \code{WINDOW} and \code{MAP}
from Section~\ref{sec:df-algebra}
expect a specific
order for the rows (\code{WINDOW}) and
columns (\code{MAP}).
since the UDF
argument to these operators may
rely on that order.
Dataframes also support \code{SELECTION} and \code{PROJECTION}
based on the position of the rows and
columns respectively.
}

\rebuttal{
To support order, current dataframe systems
such as pandas\xspace
physically store the dataframe
in the same conceptual order as defined by the user.
Said differently, they do not embrace physical data independence.
}\moved{%
Physical independence may open up new optimization
opportunities,
recognizing that as long as
the displayed results preserve
the desired order semantics
to the users, it is not necessary
that all intermediate products
or artifacts (unobserved by user)
adhere to the order constraint.
For example,
a sort operation can be ``conceptual''
in that a new order can be defined without
actually performing the expensive
sorting operation.
Likewise, a transpose
doesn't require the data to be reoriented
in physical storage unless beneficial
for subsequent operations; the transpose can be
captured logically
to reflect the new
orientation of the dataframe.
}

\rebuttal{To ensure correct semantics
while respecting physical data independence,
we must devise means to capture ordering
information, either tracked
as a separate ``order column'',
if it is not implied via existing columns,
or recording as metadata that the dataframe
must be ordered based on one or more
of the preexisting
columns.
Then, the \code{ORDER BY}
on this ``order column'' or one of the existing columns
will be treated as an
operator in the query plan, and will only need to be
done ``on-demand'' when the user requests to view a result.
Additionally, since users
are only ever looking at the first and/or last few lines
of the dataframe, those are the only lines that are required
to be ordered; we discuss this further
in Section~\ref{sec:immediate-feedback}.}

\rebuttal{%
Extending physical data independence even further,
we can adapt other data representation
techniques from the database community,
optimized for dataframes.
This includes columnar
or row-column hybrid storage~\cite{abadi2013design},
as well as those from
scientific computing~\cite{choi1992scalapack},
array databases~\cite{rusu2013survey}
or spreadsheets~\cite{bendre2015dataspread}.
Since dataframes are neither relations,
matrices, arrays, or spreadsheets, none
of these representations are a perfect fit.
Given that rows and columns are equivalent,
one candidate for dataframe representation
is as a collection of key-value pairs,
where the key corresponds to the
(row number, column number)
pair.
This representation
is especially effective when
the dataframe is ``sparse'', allowing
us to omit pairs where the value is null.
Then, \code{TRANSPOSE} conceptually
swaps the row and column for each value:
$(column, row, value)$,
and can be recorded in metadata.
However, some operations become more expensive,
e.g. reconstructing a row for a \code{MAP}
operation requires a join.
Automatically detecting and updating to the right representation
over the course of dataframe query
execution will be a substantial challenge.}

\techreport{
\moved{%
Given a certain physical representation,
operations on dataframes,
from a relational perspective, often make use
of ordered access, e.g.,
editing the $i^{\textrm{th}}$ row,
as well as access
based on the row labels, e.g.,
filtering based on row labels (named notation)
or row position (positional notation).
Because
selecting the $i^{\textrm{th}}$ physical row or projecting the $j^{\textrm{th}}$ physical column
will not necessarily correspond to selecting (resp.\ projecting) the desired {\em logical}
row (resp.\ column), additional metadata
that serves as the "order column" or "order row" must be maintained to facilitate
order-independence of the physical data.
Automatically
maintaining
indexes for this purpose can be beneficial.
Recent work has developed positional
indexing~\cite{bendre2018towards}, allowing ordered
access to be supported in $O(\log n)$,
in the presence of edits (e.g., adding or removing
rows).
Column stores take a different approach
to avoid expensive edits across columns,
instead
recording edits separately as deltas,
and periodically merging them back in~\cite{abadi2013design};
it would be interesting to investigate which approach is more effective for a given set of dataframe operations.
Similarly, for matrices, accesses often
happen in a row-major or column-major order,
and identifying the right indexes to efficiently
support them in conjunction
with relational-style accesses, is an important
challenge.
In particular, when a dataframe
has many rows and many columns,
we may need both row-
and column-oriented indexing.
}
}

\input{pivotplans.tex}

\rebuttal{
\subsubsection{Row/Column Equivalence}
\label{sec:rowcolumneq}
}
\rebuttal{
The presence of a \code{TRANSPOSE} operator in the
dataframe algebra
presents novel challenges in data layout and query optimization.
\code{TRANSPOSE} allows users to flexibly alter
their data into a desired shape or schema that can be
parsed according to an appropriate schema, and
queried using ordered relational operators.
}

\rebuttal{
To keep our data model and algebra compact,
we have schemas only for columns, and
our operators are defined on ordered sets of rows.
By contrast, in pandas\xspace and other dataframe implementations,
it is possible to
perform many operations
along either the rows or
columns via the \code{axis}
argument.
Hence programs written in (or translated to) our algebra
are likely to have more uses of \code{TRANSPOSE} than dataframe
programs in the wild, to represent columnwise operations and/or
to reason about per-row schemas.}
\rebuttal{These operations are expressible logically in our simpler algebra
by first performing a
\code{TRANSPOSE}, applying
the operation, and then a \code{TRANSPOSE}
again to return to the original orientation. Doing frequent physical reorganizations
for these operations would be a mistake, however.
}

\rebuttal{The prevalence of \code{TRANSPOSE} in
dataframe programs overturns many axis-specific assumptions made in traditional database storage.
Axis-specific data layouts like columnar compression are problematic in this context.
Metadata management also requires rethinking, since dataframes are as likely to
be extremely
``wide'' (columnwise) as they are ``tall'' (rowwise).}
\rebuttal{
Both traditional and embedded RDBMSs typically limit the number of columns in a
relation (e.g., SQL Server has an upper limit of 1024
columns, or 30k columns using the wide-table feature)~\cite{raasveldt2019duckdb, sqlite2020hipp}.
By applying \code{TRANSPOSE} on
a tall and narrow dataframe,
the number of columns can easily exceed the millions
in the resulting short and wide dataframe.
}

\rebuttal{
Dataframe systems
will need careful consideration to ensure that a \code{TRANSPOSE} call does not
break assumptions made by the data layout layer.
}
\rebuttal{
Given that the cost of performing a physical transpose will often
be high,
one potential way to handle the data layout layer optimization
problem is to do a {\em logical} \code{TRANSPOSE} ``pull-up''. This would
delay or eliminate transpose in the physical plan as much as
possible since it will often destroy or render moot many
existing data layout optimizations.
}

\rebuttal{
In certain cases, we may indeed want to consider optimizing
the \emph{physical} layout of the data given a \code{TRANSPOSE}
operator as a part of a query plan.
This is in contrast with existing data
systems that create and optimize for a static data layout.
A physical transpose may help the optimizer match the layout to the
access pattern (e.g., matrix multiplication). A fixed data layout
is likely to have a significant performance penalty when
the access pattern changes.
Additionally, consider a case where \code{TRANSPOSE}
allows us more flexibility in query planning.
In the \code{pivot} case in Section~\ref{sec:algebra-example},
we observed that transposing the result of a pivot
is effectively a pivot across the other column.
Specifically, if we must pivot into the wide table with \code{Month}s as columns,
we can either use the original plan (Figure~\ref{fig:pivotplans}a) or
one where we proceed as if the pivot is over \code{Year},
but then transpose the final result so that the \code{Month} attribute values
are used as column headers (Figure~\ref{fig:pivotplans}b).
The latter plan will be faster if the optimizer leverages knowledge
about the sorted order of the \code{Year} column to avoid hashing the groups.
This is an interesting example of a
new class of potential optimizations within
dataframe query plans that exploit an efficient
\code{TRANSPOSE}. Because the axis transpositions are happening in query expressions,
the data layout becomes a physical plan property akin to ``interesting orders''~\cite{selinger1979access}
or ``hash teams''~\cite{graefe1998hash},  expanding the rules for query optimization.
}

\rebuttal{
\subsubsection{Metadata is Data (and Data is Metadata)}
A standard feature of dataframes is the ability to fluidly move values from
data to metadata and back. This is made explicit in the \code{TOLABELS} and
\code{FROMLABELS} operators of our algebra, especially in combination with \code{TRANSPOSE}.
These semantics cannot be
represented in languages like SQL or relational algebra that are grounded in
first-order logic; this is a signature of second-order logic, as explored in
languages like OQL~\cite{alashqur1989oql}, SchemaSQL~\cite{lakshmanan1996schemasql}
and XQuery~\cite{chamberlin2001xquery}.
There is significant prior work on optimizing second-order operations like
the unnesting of nested data (e.g.~\cite{fegaras1998query, shanmugasundaram2001querying, wang2007optimization}).
A distinguishing aspect of our setting is that a dataframe operation like \code{TOLABELS} commonly generates a
volume of metadata that is dependent on the size of the data; this raises new challenges.
The closest prior work to our needs
is on implementing spreadsheet-style pivot/unpivot in databases (e.g., ~\cite{cunningham2004pivot,wyss2005formal});
this work needs to be generalized to the richer semantics of a dataframe algebra.
}

\rebuttal{To address representational aspects, we could treat row labels
the way we treat primary keys in a relational database---by noting the sequence of label columns
in a metadata catalog. Some additional details arise in the support of positional notation:
invoking \code{TOLABELS($c_1$, ..., $c_n$)} removes the relevant columns from their positions, requiring
a recalculation of the positions of all labels to the right of $c_1$. This can be
handled by representing column order in dynamic ranked data structures like ranked B-trees~\cite{knuth1997art} or
range min-max trees~\cite{navarro2014fully}. In terms of data access, we may want to efficiently process
data columns without paying to access (dynamically reassigned) metadata columns, and vice versa. In this case, columnar
layouts become attractive for projection. Alternatively,
labels can be moved into separate \emph{property tables}~\cite{cunningham2004pivot}, a form of ``vertical partitioning'' that does not rely on
columnar storage layouts.}

\rebuttal{Challenges arise in more complex expressions that include both \code{TOLABELS} and other operators--notably \code{MAP}
and \code{TRANSPOSE}. In these cases, the number and types of \emph{columns} in the dataframe is data-dependent. This exacerbates the
metadata storage issues discussed in the previous section, and brings up additional challenges.}

\rebuttal{In terms of query optimization, we now have a two-dimensional estimation problem: both cardinality estimation (\#rows)
and \emph{arity estimation} (\#columns). For most operations in our algebra this would appear straightforward: even for \code{TRANSPOSE}, we
know the cardinality and arity of output based on input. The challenge that arises is easy to see in a standard data science ``macro'',
namely 1-hot encoding (\texttt{get\_dummies} in pandas\xspace). This operation takes a single column as input, and produces a result table whose schema
concatenates the input schema with an (typically large) array of boolean-typed columns, one column per distinct data value of the input. Pivot presents
a similar challenge: the width of the output schema is based on the number of distinct data values in the input columns. In our algebra, these
macros can be implemented using \code{GROUPBY} followed by \code{MAP} and \code{TRANSPOSE}. The resulting arity estimation problem reduces to
distinct value estimation for the input to \code{GROUPBY}.
Techniques like hyperloglog sketches~\cite{flajolet2007hyperloglog} come to mind to assist here. But
note that we need to compute these estimates not only on base tables that may be pre-sketched, but on intermediate results of expressions! In short,
we need to do distinct value estimation for the \emph{outputs} of query operators---including arithmetic calculations (e.g. sums, products) and string manipulations (e.g. expanding a document into constituent words).}

\rebuttal{In some scenarios, arity \emph{estimation} is insufficient---we need exact numbers and labels of columns. Consider the example of performing a \code{UNION}
of feature vectors generated from two different text corpora, say wikipedia articles unioned with DBLP articles.
Each text corpus begins as a dataframe with schema \texttt{(documentID, content)}. After a standard series of text featurization steps
(word extraction with stemming and stop-word filtering followed by 1-hot encoding), each corpus becomes a dataframe with a \texttt{documentID} column, and one boolean column for each word in the corpus. The problem is that the \code{UNION} needs to dynamically check for compatibility of the input schemas---it needs to first generate the full (large!) schema for each input, and compare the two.
Even if we relax our semantics to an ``outer'' union,
we want to identify and align the common words across the corpora.
These metadata requirements seem to require two passes of the inner expression's data: one to compute and align metadata,
and another to produce a result.
There are opportunities for optimization here to return to single-pass pipelining techniques, but they merit thoughtful investigation. This pipeline-breaking problem generalizes to any operator that reasons about its input schema(s), so it needs to be
handled comprehensively.
\\}
\rebuttal{
In short, we expect that the fluid movement of large volumes of data into metadata and vice versa
introduces new challenges for query processing and optimization in dataframes.}

\section{Optimizing for Execution}\label{sec:datamodel}

\techreport{In this section we discuss several directions of future work to support optimized execution of dataframes.
We divide these optimizations along several directions including physical data layout, query planning, improved support for interactive data exploration, and multi-query optimization.}

Dataframes combine functionality from relational and linear algebra, so there are opportunities to leverage, combine, and extend advances in physical data layout pioneered in both the database and scientific computing communities.
Over the last two decades, the database community has explored many directions for table
storage, including both row- and column-oriented storage as well as various hybrids at
both the disk and in-memory level (as surveyed by Abadi, et al. \cite{abadi2013design}).
Principally, from this work the fundamental concepts of data independence, has the opportunity to play a major role in future dataframe systems.
Today's dataframe systems already share common physical storage of data across multiple derived dataframes to reduce the memory requirements.
However, future dataframe technologies might also explore view based representations where computation is used in place of storage. For example, the Vaex project \cite{vaex}, which is a dataframe-like system
that allows querying on HDF5 files, implements virtual columns. With virtual columns,
the column is not actually materialized until required for output, printing, or for a query.
In cases where the computation that creates a column is expensive, virtual columns will
need to be paired with intelligent caching mechanisms that prioritize caching
columns that were expensive to generate.

Traditional work on dataframes has largely focused on modest-size datasets that fit in RAM
on a single machine. Scaleup in this domain can be achieved in two standard ways: exploting
the aggregate RAM across many machines using data partitionining (``sharding''), and/or
exploiting a memory hierarchy, e.g. by spilling data to secondary storage in bulk algorithms,
or using a paginated buffer cache for random accesses. These techniques are natural aspects
of the design space for a scalable dataframe library, though once again the diversity of
potential access patterns may complicate the story beyond the prior work in databases,
scientific computing and dataframes. This design space is further complicated by technology
trends including the desire to shuttle data to/from GPU memory for matrix operations,
multi-level storage hierarchies both in new hardware and in cloud storage services, and
the ability to autoscale cloud resources including RAM for bursts of memory- and
compute-intensive work.
Given that the dataframe model is a hybrid of both the relational and
matrix-oriented representations,
there must be many considerations about how to store and retrieve a dataframe using both
memory and secondary storage. Like a matrix, a dataframe might be scanned in either
row- or column-major order, and must support retrieval along either axis (or both) by
index, or positional notation.
Vectorization of
execution is important for certain dataframe operations and depends heavily on the physical data layout.
Compression can be important for minimizing memory footprint and
improving I/O bandwidth as in columnar databases, but may be a bad fit to certain access
patterns.

\stitle{Apache Arrow.}
Apache Arrow\cite{pyarrow} is an in-memory column store targeted at setting a cross-language
standard for flat and hierarchical tabular data. \modin uses Apache Arrow for serialization
of dataframe partitions when they being communicated or shuffled between processes. Apache
Arrow has an in-memory tabular format called Arrow Tables and several high-performance
compute kernels that can be used to operate on Arrow Tables. Arrow is not designed to be
a user-facing dataframe library, but does aim to be the in-memory storage format
for tabular data computation. Arrow Tables do not directly conform to the dataframe data model
presented in Section~\ref{sec:dataframedef} primarily because there is no vector of row labels
$R_m$ in an Arrow Table. Arrow Tables also do not yet support \code{TRANSPOSE}, and it is not
clear what the new column labels of a \code{TRANSPOSE} would be without explicit row labels.

Aside from optimizing the physical plan and data layout,
dataframes will need new query rewriting rules due to the new algebra.
Existing dataframe systems execute queries in a strictly imperative way
and do not perform any query rewriting~\cite{mckinney2010data, R, dask}.
Some systems that market themselves as dataframes (e.g. Spark, Dask) are declarative but do not support operations
beyond the traditional relational table operations~\cite{Armbrust:2015:SSR:2723372.2742797, dask}.
The \code{TRANSPOSE} operation presents some particularly interesting opportunities and challenges, and in some cases can be avoided using clever rewrite rules.
For example, the query \code{TRANSPOSE}, \code{SORT}, \code{TRANSPOSE} to reorder columns can be
rewritten as a \code{MAP} and \code{RENAME}.
The challenge of supporting declarative query processing across a wide range of dataframe operators is that
the cost of extending rewrite rules beyond relational operations,
to support spreadsheet and linear algebra operations, requires a significant development effort.
As a result, dataframe users either have to sacrifice performance,
operate on a feasible subset of their data,
or manually construct and profile various possible rewrite to determine the optimal approach to execute the query~\cite{optimizing-pandas}.
When creating rewrite rules for dataframes, we have to consider (i) how to group the dataframe operations into queries and (ii) when to rewrite the queries.
Manual query optimization on the part of the developer can be a daunting task due to the large number of possible ways to perform an operation~\cite{wu2019diel}.
In addition to the numerous ways of writing any given query at the API level,
the problem is further exacerbated by the fact that
there is a large and diverse set of operations beyond relational operators to consider when creating rewrite rules. \eat{An important area of future
work in \modin will be in defining rewrite rules to efficiently
handle cases that traditional systems cannot.}

There is a very wide physical design space for dataframes,
which spans ideas from the literature in databases, scientific computing and recent machine learning systems. It will be important to validate
the research with real-world workloads and new benchmarks that
evaluates how dataframes are used and interacted with in practice.

\techreport{
\subsection{Data Layout and Indexing}\label{sec:datalayout}

\smacke{Professor suggestions: highlight that there are many
existing layout strategies and corresponding optimizations and
the interesting part is hybridizing these for dataframes.}

\jeg{The following was a quick brainstorming session of "ideas" for research directions we want to cover in physical data layout.}

\begin{itemize}
    \item Block oriented storage and the connection between advances in column stores and compressed sparse block representations (eg https://people.eecs.berkeley.edu/~aydin/csb2009.pdf)
    \item referential or view based storage: store data as a reference to other dataframes or store data as a function of other data rather than by value.
    \item Advances in indexing:
    \begin{itemize}
        \item extending to columns and rows
        \item Automatic index generation for intermediate queries (must have already been done?)
    \end{itemize}
    \item Better support for vectorized operations (hardware accelerator aware data layout)
    \item Automatic repartitioning to improve operator performance (must have already been done?)
    \item Discussion on NULL value

\end{itemize}

Because dataframes combine functionality from relational and linear algebra there are opportunities to leverage, combine, and extend advances in physical data layout pioneered in both the database and scientific computing communities.
In the following, we provide a high-level overview of a few of the key advances from each community and how they can be incorporated and extended to support efficient computation on dataframes.

\subsubsection{Databases}
Over the last two decades, the database community has explored many directions for table
storage, including both row- and column-oriented storage as well as various hybrids at
both the disk and in-memory level (as surveyed by Abadi, et al. \cite{abadi2013design}).
Principally, from this work the fundamental concepts of data independence, has the opportunity to play a major role in future dataframe systems.
Today's dataframe systems already share common physical storage of data across multiple derived dataframes to reduce the memory requirements.
However, future dataframe technologies might also explore view based representations where computation is used in place of storage. For example, the Vaex project \cite{vaex}, which is a dataframe-like system
that allows querying on HDF5 files, implements virtual columns. With virtual columns,
the column is not actually materialized until required for output, printing, or for a query.
In cases where the computation that creates a column is expensive, virtual columns will
need to be paired with intelligent caching mechanisms that prioritize caching
columns that were expensive to generate.

\jeg{paragraph on indexing techniques.}
To improve efficient data access the database community has developed sophisticated indexing strategies.
\jeg{Additional transition ... we believe these techniques will play a role in advancing performance of dataframes ...}
Like a relation, the rows of a dataframe may also be
retrieved by name, or named notation, and hence require
value-based indexing. The columns of a dataframe may also be retrieved by name, and given
the potential for massive arity on the order of billions, this also requires value-based indexing.

\jeg{paragraph on array based}
In addition, there has been work on supporting array-based data in databases, for both
``multidimensional'' OLAP workloads in the traditional relational model, e.g.
\cite{deshpande1997cubing, otoo2007optimal}, and for database-backed scientific computing
(e.g. last surveyed by \cite{rusu2013survey}).

\subsubsection{Scientific Computing}

Much of the focus on large scale scientific computing has been on efficient storage and execution of basic linear algebra subroutines.
There is extensive work in the
scientific community on matrix representations for parallel computation (e.g.
\cite{choi1992scalapack}). \jeg{merge first two sentences.}

\subsection{Partitioning and Memory Hierarchies}
\smacke{JMH: maybe all this can be talked about in the data layout section,
dividing that into single vs multi node}
\smacke{AGP: prepartitioning to optimize for stream of subsequent operations is sensible}
\smacke{AGP and Anthony: Maybe merge with Section~\ref{sec:datalayout}}

Traditional work on dataframes has largely focused on modest-size datasets that fit in RAM
on a single machine. Scaleup in this domain can be achieved in two standard ways: exploting
the aggregate RAM across many machines using data partitionining (``sharding''), and/or
exploiting a memory hierarchy, e.g. by spilling data to secondary storage in bulk algorithms,
or using a paginated buffer cache for random accesses. These techniques are natural aspects
of the design space for a scalable dataframe library, though once again the diversity of
potential access patterns may complicate the story beyond the prior work in databases,
scientific computing and dataframes. This design space is further complicated by technology
trends including the desire to shuttle data to/from GPU memory for matrix operations,
multi-level storage hierarchies both in new hardware and in cloud storage services, and
the ability to autoscale cloud resources including RAM for bursts of memory- and
compute-intensive work.

Given that the dataframe model is a hybrid of both the relational and
matrix-oriented representations,
there must be many considerations about how to store and retrieve a dataframe using both
memory and secondary storage. Like a matrix, a dataframe might be scanned in either
row- or column-major order, and must support retrieval along either axis (or both) by
index, or positional notation.
Vectorization of
execution is important for certain dataframe operations and depends heavily on the physical data layout.
Compression can be important for minimizing memory footprint and
improving I/O bandwidth as in columnar databases, but may be a bad fit to certain access
patterns.

Apache Arrow\cite{pyarrow} is an in-memory column store targeted at setting a cross-language
standard for flat and hierarchical tabular data. \modin uses Apache Arrow for serialization
of dataframe partitions when they being communicated or shuffled between processes. Apache
Arrow has an in-memory tabular format called Arrow Tables and several high-performance
compute kernels that can be used to operate on Arrow Tables. Arrow is not designed to be
a user-facing dataframe library, but does aim to be the in-memory storage format
for tabular data computation. Arrow Tables do not directly conform to the dataframe data model
presented in Section~\ref{sec:dataframedef} primarily because there is no vector of row labels
$R_m$ in an Arrow Table. Arrow Tables also do not yet support \code{TRANSPOSE}, and it is not
clear what the new column labels of a \code{TRANSPOSE} would be without explicit row labels.

\jeg{I don't know what this is saying:}
There is a very wide physical design space for dataframes, which spans ideas
from the literature in databases, scientific computing and recent machine learning
systems. Real-world workloads and benchmarks will be important issues in this space.

\subsection{Statement Optimization}
\devin{Fill in with reference to prior sections and introduction}
\devin{Rewrite rules}
\smacke{JMH: grab bag of potential optimizations}

}
\section{Clean-Slate Implementation}\label{sec:clean-slate}

\section{Conclusion}\label{sec:conclusion}

In recent years, the convenience of dataframes
have made them
the tool of choice
for data scientists
to perform a variety of tasks, from data loading, cleaning,
and wrangling to statistical modeling and visualization.
Yet existing dataframe
systems like pandas\xspace
have considerable difficulty in providing interactive responses
on even moderately-large datasets of less than a gigabyte.
\rebuttal{
This paper outlines our research agenda
for making dataframes scalable,
without changing the functionality or usability
that has made them so popular.
Many fundamental assumptions made by
relational algebra are entirely discarded in favor of new ones for dataframes,
including rigid schemas, an unordered data model, rows and columns being
distinct, and a compact set of operators.
Informed by our experience in developing \modin,
a drop-in replacement for pandas\xspace,
we described a number of research challenges
that stem from revisiting familiar data management problems,
such as metadata management, layout and indexing, and
query planning and optimization, under these new assumptions.
As part of this work, we also proposed a
candidate formalism for dataframes,
including a data model
as well as a compact set of operators,
that allowed us to ground our research directions
on a firm foundation.
}
\rebuttal{We hope our work serves as a roadmap and a call-to-action
for others in the database
community to contribute to this emergent, exciting, and challenging
research area of
scalable dataframe systems
development.}

\techreport{
\subsection*{Acknowledgments}
We would like to acknowledge those who have made significant contributions to the \modin codebase: we thank Omkar Salpekar,
Eran Avidan, Kunal Gosar, GitHub user ipacheco-uy, Alex Wu, and Rehan Sohail Durrani.
We also thank Ion Stoica for
initial discussions and encouragement.
}
\subsection{Dataframe Algebra} \label{sec:df-algebra}

\begin{table*}[!t]
\centering
\begin{tabular}{|l|c|c|c|c|c|l|}
\hline
\rowcolor[HTML]{C0C0C0}
\textbf{Operator} & \multicolumn{2}{|c|}{\textbf{(Meta)data}} & \textbf{Schema}    & \textbf{Origin} & \textbf{Order}           & \textbf{Description}                                     \\ \hline
SELECTION         &                   & $\times$        & static & REL             & Parent                   & Eliminate rows                                           \\ \hline
PROJECTION        &                   & $\times$        & static & REL             & Parent                   & Eliminate columns                                        \\ \hline
UNION             &                   & $\times$        & static & REL             & Parent$^\dag$            & Set union of two dataframes                              \\ \hline
DIFFERENCE        &                   & $\times$        & static & REL             & Parent$^\dag$            & Set difference of two dataframes                         \\ \hline

CROSS PRODUCT / JOIN             &                   & $\times$        & static & REL             & Parent$^\dag$            & Combine two dataframes by element                        \\ \hline
DROP DUPLICATES   &                   & $\times$        & static & REL             & Parent                   & Remove duplicate rows                                    \\ \hline
GROUPBY          &                   & $\times$        & static & REL             & New            & Group identical \rebuttal{attribute values for a given (set of) attribute(s)}  \\ \hline
SORT              &             &       $\times$        & static  & REL             & New                      & Lexicographically order rows                             \\ \hline
RENAME            & $(\times)         $            &               & static & REL             & Parent                   & Change the name of a column                              \\ \hline
WINDOW            &                   & $\times$        & static & SQL             & Parent                   & Apply a function via a sliding-window (either direction) \\ \hline
TRANSPOSE         & $(\times)$        & $\times$        & dynamic       & DF              & Parent$^\lozenge$        & Swap data and metadata between rows and columns          \\ \hline
MAP               &  $(\times)$                 & $\times$        & dynamic & DF              & Parent                   & Apply a function uniformly to every row                  \\ \hline
TOLABELS         & $(\times)$            & $\times$        & dynamic       & DF              & Parent                   & Set a data column as the row labels column \\ \hline
FROMLABELS      & $(\times)$            & $\times$        & dynamic       & DF              & Parent                   & Convert the row labels column into a data column      \\ \hline
\end{tabular}
\vspace{-5pt}
\caption{
Dataframe Algebra.
$\dag$: Ordered by left argument first, then right to break ties.
$\lozenge$: Order of columns is inherited from order of rows and vice-versa.
}
\label{tab:df-algebra}
\vspace{-10pt}
\end{table*}

\rebuttal{
While developing \modin, we discovered that there exists a
``kernel'' of operators that encompasses the massive
APIs of pandas\xspace and R. We developed this ``kernel'' into
a new dataframe algebra, which we describe here,
while explicitly contrasting it with
relational algebra.
}
We do not
argue that this set of operators is minimal,
but we do feel it is
both expressive and elegant;
we demonstrate via \rebuttal{a case study}
in Section~\ref{sec:algebra-example}
\rebuttal{can be used to express \code{pivot};
\techreport{other examples of rewriting for operators
within pandas\xspace can be found in our technical report~\cite{petersohn2020towards}.}}
Based on the contrast with relational algebra,
we are in a position
to articulate research challenges in optimizing
dataframe algebra expressions in subsequent sections.

\techreport{
To the best of our knowledge,
an algebra for dataframes has never
been defined previously.
Recent work by Hutchinson et al.~\cite{lara, laradb}
proposes an algebra called Lara that combines
linear and relational algebra, exposing
only three operators:
\code{JOIN}, \code{UNION}, and \code{Ext} (also known as ``flatmap'');
however, the operators below
that manipulate metadata
would not be possible in Lara without
placing the metadata as part of the data.
Other differences stem from the flexible data model
and lazily induced schema.
That said, as we continue to refine our algebra,
we will draw on Lara as a reference.
}

We list the algebra operators we have defined in
Table~\ref{tab:df-algebra}: the rows correspond to the operators,
and the columns correspond to their properties.
The operators encompass
ordered analogs of
extended relational
algebra operators (from \code{SELECTION} to \code{RENAME}),
one operator that is not part of
extended relational algebra but is found in
many database systems
(\code{WINDOW}), \rebuttal{one operator with that admits independent use
unlike in database systems (\code{GROUPBY}),}
as well as four new operators
(\code{TRANSPOSE}, \code{MAP},
\code{TOLABELS}, and \code{FROMLABELS}).
The ordered analogs of relational algebra
operators preserve the ordering of the input dataframe(s).
If there are multiple arguments, the result is
ordered by the first argument first, followed
by the second.
For example, \code{UNION}
simply concatenates the two input dataframes in order,
while \code{CROSS-PRODUCT} preserves
a nested order, where each tuple on the left
is associated, in order,
with each tuple on the right,
with the order preserved.

\papertext{
We succinctly describe the new operators \rebuttal{as well as highlight
any deviating semantics of \code{GROUPBY} and \code{WINDOW}} and leave
detailed semantics to our technical report~\cite{petersohn2020towards}.
The output schema
for most other relational operators
can be carried over
from the inputs
(indicated as {\em \rebuttal{static}} in Table~\ref{tab:df-algebra}).
}

\techreport{

Note that languages choose different approaches to inferring the schema
after a \code{TRANSPOSE} with important implications for usability.
For example, in R, a \code{TRANSPOSE} with heterogeneous $D_n$
ends up coercing everything to \textbf{string}, which may make it impossible to
apply another \code{TRANSPOSE} and yield a dataframe equivalent
to the original $D_n$. In Python, everything is coerced to \code{Object}, which has typing
information embedded at runtime, so the schema induction function can
always recover the original $D_n$ after two transposes.}

\stitle{Transpose.}
\code{TRANSPOSE} interchanges rows and columns,
so that the columns of the
dataframe become the rows, and vice-versa.
Formally, given a dataframe $DF = (A_{mn}, R_m, C_n, D_n)$,
we define $\mbox{\code{TRANSPOSE}}(DF)$ to be a dataframe
$(A_{nm}^T, C_n, R_m,$ $null)$,
where $A_{nm}^T$ is the array
transpose of $A_{mn}$. Note that
the schema of the result may be
induced by $S$, and may not be
similar to the schema of the input.
\code{TRANSPOSE} is useful both for
matrix operations on homogenous dataframes,
and for data cleaning or for presentation
of ``crosstabs'' data.
In step C2 in our example in Figure~\ref{fig:example},
the table was not oriented
properly from ingest,
and a transpose was required to give us the desired
table orientation.

\techreport{
In pandas\xspace and other dataframe implementations,
it is possible to
perform many operations
along either the rows or
columns via the \code{axis}
argument.
Instead, to minimize redundancy,
we define operators on collections
of rows, as in relational algebra,
and enable operations across
columns by first performing a
\code{TRANSPOSE}, applying
the operation, and then a \code{TRANSPOSE}
again to return to the original orientation.
That said, performing
\code{TRANSPOSE} can be expensive
(as we will see in Section~\ref{sec:modin}),
so one of our goals will be to postpone
performing it or avoid it entirely.
Moreover, given the presence of
\code{TRANSPOSE} in the algebra, we need to be prepared to handle
dataframes that are not only extremely high in cardinality (``tall'')
but also extremely high in arity (``wide'').

In the algebra defined above, we define
operators only on collections of rows, as in relational algebra, allowing \code{TRANSPOSE} to toggle
the axis of application of the operators.
Operations along the columns require a \code{TRANSPOSE}, application of
the desired operator,
and a \code{TRANSPOSE} again to return to the
original orientation.
With this flexibility, operators
on the dataframe can be performed along either the columns or
the rows.

The asymmetry of
row and column types in the relational model makes
\code{TRANSPOSE} impossible to define for relations with non-homogeneous
column domains (for which the sets in $D_n$ differ):
there is no data-independent way to derive a relational
output schema for \code{TRANSPOSE} from the input schema. In the
dataframe data model, the data-dependent schema induction function
provides an output schema.

\code{TRANSPOSE} can also be extremely computationally expensive
depending on the system architecture and partitioning.
In its implementation, it will often
be important to postpone the calculation of \code{TRANSPOSE}
until the last possible moment because of the associated computation
costs.
Moreover, given the presence of
\code{TRANSPOSE} in the algebra, we need to be prepared to handle
dataframes that are not only extremely high in cardinality (``tall'')
but also extremely high in arity (``wide'').
}

\stitle{Map.}
The map operator takes some function {\em f}
and applies it to each row individually,
returning a single output row of fixed arity.
The purpose
of the map operator is to alter each dataframe row
uniformly.
\code{MAP} is useful for data cleaning
and feature engineering
(e.g., step C3 in Figure~\ref{fig:example}).
Given a dataframe $DF = (A_{mn}, R_m, C_n, D_n)$, the result of
\code{MAP(DF, {\em f})} is a dataframe $(A_{mn'}', R_m, C_{n'}', D_{n'}')$
with $f:D_n \rightarrow D_{n'}'$, where
$A_{mn'}'$ is the result of the function {\em f} as applied to
each row, $C_{n'}'$ is the resulting column labels, and $D_{n'}'$ is the resulting
vector of domains. Notice that in this definition,
the number of columns ($n'$) {\em and} the column
labels ($C_{n'}'$) can change based on this definition, but they must be changed
uniformly for every row.
The vector of domains $D_{n'}'$
may, in many cases, be inferred from the type
of the function $f$.

\techreport{
Extended relational algebra supports map via the use of functions
in the subscript of projection operators (i.e., in the \code{SELECT}
clause of SQL). However, this
projection
syntax is linear in the arity of the relation, which is cumbersome
for very wide schemas (e.g., after a \code{TRANSPOSE}).
In this definition, \code{MAP} is passed an entire
row as an argument so it can reason across columns
in a generic fashion without enumerating them, whereas
SQL expressions (including UDFs) typically require specific fields
from the row as scalar arguments. For example,
consider a transformation that needs to ensure the values in
all \textbf{float}-domain columns
in a given row sum to 1.0; a generic, reusable \code{MAP} function can
normalize the value in each \textbf{float}
field by the sum of the \textbf{float}
fields in that row;
instead, a SQL expression
would have to be crafted specially for each schema.
\jmh{I think there's maybe more to say
here but we need a type theory person to help!}
\jmh{On a less technical note, can we assume the reader knows
\code{fillna} and that they realize it's a macro over \code{MAP}?}
}

\stitle{ToLabels.}
The \code{TOLABELS} operator projects one column out
of the matrix of data, $A_{mn}$, to be set as new row labels for the resulting
dataframe, replacing the old labels.
Given $DF = (A_{mn}, R_m, C_n, D_n)$
and some column label $L$,
\code{TOLABELS($DF$, $L$)} returns
a dataframe $(A'_{m(n-1)}, L, C_n', D_n')$,
where $C_n'$ (respectively $D_n'$) is the result of removing the label $L$ from $C_n$ (respectively $D_n$).
With this capability,
data from $A_{mn}$ can be promoted
into the metadata of the dataframe and referenced
by name during future interactions.

\techreport{
From a relational perspective, this operator is rather unusual
in that it converts data into metadata.
Dataframe users are interested in wrangling and cleaning data,
so operations that let them move entries
between metadata
and data are popular and convenient to use.
In fact, \code{TOLABELS}
followed by \code{TRANSPOSE}
is, in effect, promoting data values into column
labels, which is impossible using
relational operators.
}

\stitle{FromLabels.} \code{FROMLABELS} creates a new dataframe
with the row labels inserted
into the array $A_{mn}$ as a new column of data at position 0 with a provided column label.
The data type of the new column starts as $null$ until it can be induced by
the schema induction function $S$.
The row labels of the resulting dataframe are set to the default label:
the order rank of each row (positional notation). Formally,
given a dataframe $DF = (A_{mn}, R_m, C_n, D_n)$ and
a new column label $L$ we define
\code{FROMLABELS($DF$, $L$)} to be a dataframe
$(R_m + A_{mn}, P_m, [L] + C_n, [null] + D_n)$,
where $R_m + A_{mn}$ is the concatenation of the row labels
$R_m$ with the array of data $A_{mn}$,
$P_m$ is the positional notation values for all of the rows: $P_m = (0, ..., m - 1)$,
and $[L] + C_n$ is the
result of prepending the new column label $L$ to the column labels $C_n$.

\input{groupby-and-window-new.tex}

\techreport{
\code{FROMLABELS} is the opposite of
the \code{TOLABELS} operator, and the two of these give the
user complete control over moving data to and from the
dataframe's labels. This allows users to apply operators
on the dataframe's metadata (specifically the row labels),
which is particularly useful for
operators like \code{JOIN} and \code{GROUPBY}.
Conceptually,
this operator also allows the positional
notation of the dataframe to be treated as data if
multiple \code{FROMLABELS} are chained together.
\techreport{However, because the order is immutable,
it is impossible to update the order of the dataframe
directly in this way.
Despite providing the ability to promote data to row
labels (named notation),
it is impossible in this algebra to
promote data to positional notation.
If the users wished to reorder the
data, they may \code{JOIN} with another dataset
with a specific order
or \code{SORT} based on some column(s).}

From a relational point of view, \code{FROMLABELS} enables
the capability to push metadata into the data to be queried
and operated on.
Thanks to this operator and \code{TOLABELS}
specifically, column and row labels must be of type
$\Sigma^*$ so that these operators make sense.
\code{FROMLABELS} also has some interesting interaction
with the schema induction function $S$, where labels
can be interpreted as any type in $Dom$ when they
are added to the data via \code{FROMLABELS} and then operated on. It
is important to point that out here in the definition, but we leave
the enumeration of the nuances of this interaction to future work.
}
\techreport{
\subsection{Algebra Examples}\label{sec:algebra-example}
}
\papertext{
\subsection{Pivot Case Study}\label{sec:algebra-example}
}
To demonstrate the expressiveness of the algebra above,
we show how it can
\rebuttal{be used to elegantly and succinctly
express \code{pivot}, which is particularly
challenging in relational databases due to the need
for relations to be declared schema-first~\cite{wyss2005formal,cunningham2004pivot}.
\techreport{The flexible schemata inherent in the dataframe data model
enables a succinct description of pivot.}
}

\techreport{
To start off, many pandas\xspace functions
provide essentially identical functionality
to dataframe operators, e.g., \code{sort\_values} for \code{SORT},
\code{merge} for \code{JOIN},
\code{groupby} for \code{GROUPBY},
\code{append} for \code{UNION},
\code{reset\_index} for \code{FROMLABELS},
and \code{set\_index} for \code{TOLABELS}.
The function
\code{transform} is a special case of \code{MAP}
that applies a fixed function to each value
within a row,
thereby preserving the input arity,
while \code{apply} is another special case
where a fixed function is applied on a per-row-basis
to combine values across multiple columns
to generate a new column.
}

\techreport{
A number of pandas\xspace functions correspond to
dataframe operators, with specific UDFs.
As examples for \code{WINDOW},
\code{cummax} computes the cumulative max of values
for one or more columns, \code{diff} takes the difference between
elements in a column and preceding values,
and \code{shift} shifts rows down to align with a new row label,
maintaining the order of the data.
Likewise, for \code{MAP},
\code{fill\_na} converts
all null values to another value,
\code{isna} replaces
each value with a boolean based on whether or not
they are null, and
\code{str.upper} converts all the string values to upper case.
In fact, pandas\xspace has many functions that
implement string and date-time transformations.
}

\techreport{
Finally, there are several pandas\xspace
functions that are compositions of
dataframe operators.
We list a few examples below,
with informal descriptions on
how they may be rewritten using
the algebra.
}%

\techreport{
The \code{agg[`f1',`f2', ...]} function in pandas\xspace
computes aggregate functions \code{f1}, \code{f2}, ...,
for each of the columns individually, with the resulting dataframe
containing one row per aggregate,
i.e., the first row corresponds
to the \code{f1} aggregates,
the second to the \code{f2} aggregates, and so on.
This function can be rewritten using one \code{GROUPBY} operator
per aggregate function to produce a single row
corresponding to the aggregates, followed
by a \code{UNION} to append these rows to each other in
the order the aggregates are listed.
Another approach is to perform a \code{TRANSPOSE},
then a \code{MAP} to compute all the necessary aggregates,
one per column, followed by another \code{TRANSPOSE}
to bring the result to the right orientation.
}

\techreport{
The pandas\xspace function \code{target.reindex\_like(reference)}
supports changing a given
dataframe (the \code{target}) by reordering its rows and columns to match those of another dataframe (the \code{reference}).
This operator is useful for aligning two dataframes
for comparison purposes.
One way to express this function using dataframe operators
would be to first \code{FROMLABELS} on both dataframes
to allow the row labels to become part of the data,
followed by a \code{INNER JOIN} between the two dataframes
on the row labels,
with the reference as the left operand;
followed by a \code{MAP} to project out the reference
dataframe attributes (leaving behind \code{reference}'s ordering).
Finally, \code{TOLABELS} can be used to move
the row labels back from the data.
}

\begin{figure}[t]
\scriptsize
\centering
\begin{tikzpicture}
  \path
    (2.6,0.5) coordinate (A) node[above, inner sep=0] {
    \begin{tabular}{| c | c | c | c | }
	    \multicolumn{4}{c}{Wide Table of \textsc{Month}s} \\ \hline
        \rowcolor[HTML]{C0C0C0}
    	\textbf{Month} & \textbf{2001} & \textbf{2002} & \textbf{2003} \\ \hline
    	Jan & 100 & 150 & 300 \\ \hline
    	Feb & 110 & 200 & 310 \\ \hline
    	Mar & 120 & 250 & \code{NULL} \\ \hline
    \end{tabular}
    }
    (2.6,-0.5) coordinate (B) node[below, inner sep=0] {
    \begin{tabular}{| c | c | c | c | }
        \rowcolor[HTML]{C0C0C0} \hline
    	\textbf{Year} & \textbf{Jan} & \textbf{Feb} & \textbf{Mar} \\ \hline
    	2001 & 100 & 110 & 120 \\ \hline
    	2002 & 150 & 200 & 250 \\ \hline
    	2003 & 300 & 310 & \code{NULL} \\ \hline
	    \multicolumn{4}{c}{Wide Table of \textsc{Year}s}
    \end{tabular}
    }
    (0,0) coordinate (C) node[left, inner sep=0] {
	    \begin{tabular}{| c | c | c | }
	        \multicolumn{3}{c}{Narrow Table (\textsc{Sales})} \\ \hline
        	\rowcolor[HTML]{C0C0C0}
	    	\textbf{Year} & \textbf{Month} & \textbf{Sales} \\ \hline
	    	2001 & Jan & 100 \\ \hline
	    	2001 & Feb & 110 \\ \hline
	    	2001 & Mar & 120 \\ \hline
	    	2002 & Jan & 150 \\ \hline
	    	2002 & Feb & 200 \\ \hline
	    	2002 & Mar & 250 \\ \hline
	    	2003 & Jan & 300 \\ \hline
	    	2003 & Feb & 310 \\ \hline
	    \end{tabular}
    };
  \draw[-] (A)--(B) (2.6,0) --
	  node[above]{\textbf{Pivot} $\longrightarrow$}
	  node[below]{$\longleftarrow$ \textbf{Unpivot}}(C);
\end{tikzpicture}
\vspace{-5pt}
    \caption{%
        Pivot table example, reproduced
        from~\cite{cunningham2004pivot}, demonstrating
        pivoting over two separate columns, ``Month'' and ``Year''.
    }
\label{fig:pivot}
\end{figure}
The \code{pivot} operator elevates \rebuttal{a column of} data
into the column labels and creates a new dataframe reshaped
around these new labels (see Figure~\ref{fig:pivot}).
\techreport{\rebuttal{The} \code{pivot} operator has been
described and implemented in relational systems~\cite{wyss2005formal, cunningham2004pivot}
but it is simpler to express in the algebra from Section~\ref{sec:df-algebra}.}

\rebuttal{Since} there is no need to know the names of the new columns
\rebuttal{or the resulting schema} \emph{a priori},
\rebuttal{a pivot can be expressed concisely in dataframe algebra
as a combination of four operators in the plan shown
 in Figure~\ref{fig:pivotplan}.}
\begin{figure}[t]
{\vspace{-5pt}
\begin{tikzpicture}
\tikzset{
    mynode/.style={rectangle,rounded corners,draw=black},
    myarrow/.style={->, >=latex', shorten >=1pt, thick},
}
   \node[mynode] (df) at (0,-0.75) {\code{DF}};
   \node[mynode] (year1) at (0,0) {\code{"Year"}};
   \node[mynode] (collect) at (1.3,0) {\code{collect}};
   \node[mynode] (groupby) at (1.3,-0.75) {\code{GROUPBY}};
   \node[mynode] (map) at (2.7,-0.75) {\code{MAP}};
   \node[mynode] (flatten) at (2.7,0) {\code{flatten}};
   \node[mynode] (tolabels) at (4.3,-0.75) {\code{TOLABELS}};
   \node[mynode] (year2) at (4.3,0) {\code{"Year"}};
   \node[mynode] (transpose) at (6.4,-0.75) {\code{TRANSPOSE}};
   \draw[myarrow] (df.south)-- ++(0,-.25) -- ++(.85,0) ->  (groupby.south);
   \draw[myarrow] (groupby.south)-- ++(0,-.25) -- ++(1,0) ->  (map.south);
   \draw[myarrow] (map.south)-- ++(0,-.25) -- ++(1.2,0) ->  (tolabels.south);
   \draw[myarrow] (tolabels.south)-- ++(0,-.25) -- ++(1.7,0) ->  (transpose.south);
   \draw[myarrow] (year1.south) -> (groupby.north);
   \draw[myarrow] (collect.south) -| (groupby.north);
   \draw[myarrow] (year2.south) -| (tolabels.north);
   \draw[myarrow] (flatten.south) -| (map.north);
   \draw[myarrow] (transpose.east)-- ++(.5,0);
\end{tikzpicture}
}
\vspace{-10pt}
\caption{Logical plan for pivoting a dataframe around the ``Year'' column
using the dataframe algebra from this section.}
\label{fig:pivotplan}
\vspace{-10pt}
\end{figure}
Recall that it is possible to elevate data to the column labels by
using \code{TOLABELS} followed by \code{TRANSPOSE}. In this case, the \code{TOLABELS}
operator would be applied on the label of the column being pivoted over,
\rebuttal{\code{"Year"} in this example}.
\rebuttal{After this step,
we perform a \code{GROUPBY} on the pivoted attribute, \code{"Year"}
with a \code{collect} aggregation applied to the remaining attributes to produce
a per-\code{Year} dataframe as a composite aggregated value.
This aggregated value is manipulated
by a} \code{MAP} operator with
a function that flattens the grouped data into the correct orientation.
This
results in a table pivoted around the attribute
selected for the \code{TOLABELS}
operator.
\rebuttal{
Notice in Figure~\ref{fig:pivot} that transposing the dataframe labeled
``Wide Table in Months'' results in the correct data layout for
the ``Wide Table in Years''. This is one example of how
\code{TRANSPOSE} can be exploited: cost models in dataframe
query optimizers can choose the more efficient pivot column
and \code{TRANSPOSE} at the end.}

\techreport{
To demonstrate the expressivity and power of
of this algebra, we demonstrate the real-world application of applying
it to pandas\xspace.
In this section, we demonstrate how a few of the more
exotic pandas\xspace operators can be written with
the algebra presented in Section \ref{sec:df-algebra}. We will illustrate that
there are operators which have a one-to-one mapping with the algebra
we described in the algebra, and that there are compositions of the
algebra operators.

One-to-one mappings are shown in Table~\ref{tab:one_to_one}. pandas\xspace has an
operator for each of the

\begin{table}[]
\begin{tabular}{|p{0.125\textwidth}|p{0.09\textwidth}|p{0.2\textwidth}|}
\hline
\rowcolor[HTML]{C0C0C0}
\textbf{Algebra Op}   & \textbf{Pandas Op} & \textbf{Pandas Op Description}                                             \\ \hline
                      & fillna             & Convert null values to another value                                       \\ \cline{2-3}
\multirow{-2}{*}{MAP} & isnull             & Determine if elements are null                                             \\ \hline
TRANSPOSE             & transpose          & Exchange the columns and row                                               \\ \hline
AS\_LABELS            & set\_index         & Set the dataframe row labels using existing column(s)                      \\ \hline
RESET\_LABELS         & reset\_index       & Insert the row labels into the dataframe and set row labels to the default \\ \hline
\end{tabular}
\caption{
pandas\xspace operators that directly map to algebra operators.
}
\label{tab:one_to_one}
\end{table}
}

\techreport{
Not all of the more than 200 \code{pandas.DataFrame} methods
map one-to-one to the algebra operators we have described. We now
describe some of the more interesting and complicated pandas\xspace
operations and how they can be written in the algebra
we have defined.
}

\section{Dataframe Fundamentals}\label{sec:definitions}

There are many competing open-source and commercial
implementations of dataframes, but
there is no formal definition or
enumeration of dataframe properties
in the literature to date.
\rebuttal{
We therefore
propose a formal definition of dataframes
to allow us to describe
our subsequent research challenges
on a firm footing, and also
to provide background to readers who are
unfamiliar with dataframes.
}
In this section, we start with a brief history (Section~\ref{sec:dataframe-history}), and
provide a reference data model (Section~\ref{sec:dataframedef})
and algebra (Section~\ref{sec:df-algebra})
to ground discussion. We then
demonstrate the expressiveness of the
algebra via \rebuttal{a case study}
(Section~\ref{sec:algebra-example})\techreport{ and
discuss extensions (Section~\ref{sec:dataframe-extensions}).
We finally provide
some quantitative statistics
into dataframe usage in Section~\ref{sec:usage}}.
\papertext{\rebuttal{Our technical report
has additional details about the formalism,
the mapping to the pandas\xspace API,
other extensions to the data model,
as well as quantitative statistics on dataframe usage~\cite{petersohn2020towards}}.}

\subsection{A Brief History of Dataframes}\label{sec:dataframe-history}

The S programming language was developed at Bell Laboratories
in 1976 to support statistical computation.
Dataframes were first
introduced to S in 1990, and presented by
Chambers, Hastie, and Pregibon at the Computational Statistics
conference~\cite{chambers-compstat-1990}.
The authors state: ``We have introduced into S a class of objects
called \code{data.frames}, which can be used if convenient
to organize all of the variables relevant to a particular
analysis ...''
Chambers and Hastie then extended this paper into a 1992 book~\cite{chambers1992statistical}, which states
``Data frames are more general than matrices in the sense
that matrices in S assume all elements to be of the same mode---all
numeric, all logical, all character string, etc.'' and ``... data frames support matrix-like
computation, with variables as columns and observations as rows,
and, in addition, they allow computations in which
the variables act as separate objects, referred to by name.''

The R programming language, an open-source implementation of
S\techreport{ with some additional innovations},
was first released in 1995,
with a stable version released in 2000, and gained
instant adoption among the statistics community.
Finally, in 2008, Wes McKinney developed pandas\xspace in an effort to bring
dataframe capabilities with R-like semantics to Python, which as we described
in the introduction, is now incredibly popular.
\techreport{In fact, pandas\xspace is often
cited as the reason for Python's popularity~\cite{python-growing-quickly,python-growth-blamed},
now surpassing Java and
C++~\cite{incredible-growth-python}.}
We discuss other dataframe implementations in
Section~\ref{sec:ext}.

\subsection{Dataframe Data Model}\label{sec:dataframedef}

As Chambers and Hastie themselves state,
dataframes are not familiar mathematical objects.
Dataframes are not quite relations, nor are they matrices or tensors.
In our definitions we borrow
textbook relational
terminology
from Abiteboul, et al.~\cite[Chapter~3]{abiteboul1995foundations}
and adapt
it to our use.

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]

The elements in
the dataframe
come from a
known set of
domains $Dom = \{\mbox{\textbf{dom}}_1, \mbox{\textbf{dom}}_2, ...\}$.
For simplicity, we assume in our discussion that
domains are taken from the set
$Dom = \{\Sigma^*$, $\mbox{\textbf{int}}$, $\mbox{\textbf{float}}$, $\mbox{\textbf{bool}}$,
$\mbox{\textbf{category}}\}$, though a few other useful domains
like datetimes are common in practice.
The domain $\Sigma^*$ is the
set of finite strings over an
alphabet $\Sigma$, and serves as a default,
uninterpreted domain;
in some dataframe libraries it is called \textbf{Object}.
Each domain contains a
distinguished $null$ value, sometimes written as \code{NA}.
Each domain $\mbox{\textbf{dom}}_i$
also includes a \emph{parsing function}
$p_i: \Sigma^* \rightarrow \mbox{\textbf{dom}}_i$,
allowing us to interpret the values in dataframe cells as
domain values\techreport{ (including possibly $null$)}.

A key aspect of a dataframe is that the domains of its columns may
be induced from data \textit{post hoc}, rather than
being declared \textit{a priori} as in the relational model.
We define a \textbf{schema
induction function} $S:{\Sigma^*} \rightarrow Dom$
that assigns
an array of $m$ strings to a domain in $Dom$.
This schema induction function is applied to
a given column and returns
a domain that
describes this array of strings;
we will return to this function later.

Armed with these definitions, we can now define a dataframe:
\begin{definition}
A \textbf{dataframe} is a tuple
$(A_{mn}, R_m, C_n, D_n)$, where $A_{mn}$ is an array of entries
from the domain $\Sigma^*$,
$R_m$ is a vector of row labels from $\Sigma^*$,
$C_n$ is a vector of column labels from $\Sigma^*$,
and $D_n$ is a vector of $n$ domains from $Dom$, one per column,
each of which can also be left unspecified.
We call $D_n$ the {\em schema} of the dataframe.
If any of the $n$ entries within $D_n$
is left unspecified,
then that domain can be induced
by applying $S (\cdot)$ to the corresponding column of $A_{mn}$\techreport{ to get its domain $i$ and then
$p(\cdot)$ to get its values}.
\end{definition}
\noindent
We depict our conceptualization of dataframes
in Figure~\ref{fig:datamodel}.
In our example of Figure~\ref{fig:example},
\rebuttal{dataframe \code{products} after step R1} has $R_m$ corresponding to
an array of labels $[$\code{Display}, \code{Camera}, $\ldots]$;
$C_n$ corresponding to an array of labels
$[$\code{iPhone 11 Pro}, \code{iPhone Pro Max}, $\ldots]$;
$A_{mn}$ corresponding to the matrix of values
beginning with \code{5.8-inch}, with $m = 6, n = 4$.
Here, $D_n$ is left unspecified,
and may be inferred using $S (\cdot)$ per column
to possibly correspond to $[\Sigma^*, \Sigma^*, \Sigma^*, \Sigma^*]$,
since each of the columns contains strings.

Rows and columns are symmetric in many ways in dataframes.
Both can be
referenced explicitly, using either numeric indexing (positional
notation) or label-based indexing (named notation).
In our example in Figure~\ref{fig:example},
the \code{products} dataframe
is referenced using positional notation in step C1
with \code{products.iloc[2, 0]} to modify the value in
the third row and first column,
and by named notation in step C3
using \code{products ["Wireless Charging"]} to modify the
column corresponding to \code{"Wireless Charging"}.
The
relational model traditionally provides this kind of referencing
only for columns. Note that row position
is exogenous to the data---it \emph{need not} be correlated in
any way to the data values, unlike sort orderings found
in relational extensions like SQL's \code{ORDER BY} clause.
The positional notation allows for $(row, col)$
references to index individual values, as is familiar from matrices.

A subtler distinction is that row and column labels are from the
same set of domains as the underlying data ($Dom$), whereas in the traditional
relational model, column names are from a separate domain
(called \textbf{att}~\cite{abiteboul1995foundations}).
This is important to point out because there are dataframe
operators that
copy data values into labels, or copy labels into data values,
discussed further in Section~\ref{sec:df-algebra}.

\rebuttal{One distinction between rows and columns
in our model is that columns have a schema,
but rows do not.
Said differently, we parse the value of any cell
based on the domain of its column.
We can also imagine
an orthogonal view, in which we define explicit schemas (or use
a schema induction function) on rows,
and a corresponding row-wise parsing function
for the cells. In our formalism,
this is achieved by an algebraic operator to
transpose the table and treat the result column-wise
(Section~\ref{sec:df-algebra}).
By restricting the data model to a single axis of schematization, we
provide a simple unique interpretation of each cell,
yet preserve a flexibility of interpretation in the
algebra. In Sections~\ref{sec:matviews} and~\ref{sec:rowcolumneq}
we return to the performance and programming implications
of programs that make use of schemas on a dataframe and its transpose (i.e. ``both axes'').}

When the schema $D_n$ has the same
domain \textbf{dom} for all $n$ columns, we call this a \emph{homogeneous}
dataframe\techreport{, and its
rows and columns can be considered symmetrically to have
the domain \textbf{dom} differing only in dimension}.
As a special case, consider a homogeneous dataframe with a domain like
\textbf{float} or \textbf{int} and operators $+, \times$ that satisfy
the algebraic definition of a field. We call this a \emph{matrix}
dataframe, since it has the algebraic properties required of a matrix,
and can participate in linear algebra operations simply
by parsing its values and ignoring its labels.
The dataframe \code{iphone\_df} \rebuttal{after step A2}  in Figure~\ref{fig:example}
is one such example; thus
it was possible to perform the covariance operation in step C3.
\rebuttal{
Matrix dataframes are commonly used in machine learning pipelines.
}

\rebuttal{Overall,
while dataframes have roots in both relational and linear algebra,
they are neither tables nor matrices.
Specifically, when viewed from a relational viewpoint,
the dataframe data model differs in the following ways:
\begin{table}[!htbp]
\vspace{-5pt}
\small
\centering
\begin{tabular}{ll}
Dataframe Characteristic              & Relational Characteristic                \\ \hline
Ordered table                         & Unordered table                          \\
Named rows labels    & No naming of rows                        \\
A lazily-induced schema               & Rigid schema                             \\
Column names from $d \in Dom$ & Column names from att~\cite{abiteboul1995foundations}                                          \\
Column/row symmetry               & Columns and rows are distinct            \\
Support for linear alg. operators  & No native support
\end{tabular}
\vspace{-5pt}
\end{table}

\noindent And when viewed from a matrix viewpoint,
the dataframe data model differs in the following ways:
\begin{table}[!htbp]
\vspace{-5pt}
\small
\centering
\begin{tabular}{ll}
Dataframe Characteristic                 & Matrix Characteristic                    \\ \hline
Heterogeneously typed                    & Homogeneously typed                      \\
Both numeric and non-numeric types       & Only numeric types                       \\
Explicit row and column labels           & No row or column labels                  \\
Support for rel. algebra operators & No native support
\end{tabular}
\vspace{-5pt}
\end{table}
}

\noindent
We will exploit these two viewpoints in our dataframe algebra to
allow us to define both relational and linear algebra operations.
\rebuttal{
Due to these differences, a new body of
work will be needed to support the scale
required for modern data science workflows.}

\begin{figure}
\vspace{-5pt}
    \centering
    \includegraphics[width=0.3\textwidth]{df_data_model.pdf}
    \vspace{-5pt}
    \caption{The Dataframe Data Model}
    \label{fig:datamodel}
    \vspace{-15pt}
\end{figure}

\techreport{
\subsubsection*{Data model Comparisons}\label{sec:data-model-comp}
Before we go on, we address some key distinctions
between dataframes
and other familiar data models.

\stitle{Comparison with matrices.}
All matrices can be represented as
dataframes (with null labels).
Not all dataframes can be matrices, however, even if
we strip off their labels! Matrices are
homogeneous in schema, but dataframes allow for schemas
with multiple domains. Even if we ignore the schema, a
dataframe is still not a matrix---opaque strings from
$\Sigma^*$ do not satisfy the properties of a field as required
by a matrix.

\stitle{Comparison with relational tables.}
A relation is defined by a declared schema, and there are
many possible \emph{instances} of a relation---sets of tuples that
satisfy the schema. An instance can be thought of as a fixed
relational table.
Dataframes are something like relation instances: they represent
a fixed set of data. However their schema can be unspecified
and hence \emph{induced} based on their content by a schema
induction function $S$. This flexibility is critical to dataframes.

Moreover, dataframes impose an ordering and naming on their rows.
Object-oriented relational extensions such as the
Postgres data model also introduced implicit row
identifiers~\cite{rowe1990postgres}, but typically relational
models do not impose a row ordering.
Of course, we can capture this semantics in a relational model via design discipline: we can ensure that
all our relations have a unique key (for naming), and
an ordering key (for ordering), which are exogenous to the actual data columns in the table. In this sense, all dataframes
can be represented as relation instances conforming to some
(potentially induced) schema with appropriate keys.

Even so, a key difference between dataframes
and relations is the symmetry between rows and columns.
This aspect, along with the freedom to induce a schema
on a per-instance basis,
make it possible to define a transpose operator
on dataframes.
Since the underlying representation
is uninterpreted, we are free to induce a different relational
schema after transposition of a dataframe.

\stitle{Comparison with spreadsheets.}
At a high level, a spreadsheet is an array
of heterogeneously-typed cells that may contain strings or
formulae. A spreadsheet thus stores code as well as data.
The strings are dynamically interpreted into a variety of domains.
It is tempting to think of formula-free spreadsheets as being
similar to dataframes, given the common row/column indexing
scheme and the dynamic typing. But in general they are quite different.
The data representations possible in spreadsheets are quite
free, and in practice often quite irregular.
Dense regions of data are often interspersed with empty regions,
or with cells containing comments and other forms of human-centric
annotation or metadata.
Spreadsheets
have a notion of a ``range''---a subarray or even a set of subarrays---which
may be sparsely located in the data grid and represent diverse or unrelated data sets stored in the same spreadsheet.
As a result of this freedom of structure, bulk algebraic operations
are difficult to define generally within spreadsheets.
Some modern spreadsheets allow a range to be labeled as a ``table''
that is interpreted with a schema and maintains an ordering;
further extensions to ``pivot tables'' allow for row and column labels. Using these constructs it is possible for a spreadsheet
to represent one or more dataframes.
But the relative simplicity of dataframes enables a
much simpler algebra and easier
implementation and optimization of the algebra's operators.

\input{dataframe-algebra}

\techreport{
\subsection{Extensions to the Formalism}\label{sec:dataframe-extensions}
\jmh{I feel like what's left here is too thin to bother with. Just say there's more in the tech report and drop the multiple labels (and hence this entire subsection).}

\todo{Make this a part of the original definition.}
Our data model so far is quite simple.
We now describe a few additional extensions
for our data model
that do not provide any additional expressive power,
but make certain operations more convenient.
\papertext{We describe one extension here,
and defer the rest to our technical report.
Our technical report
describes extensions to support
(i) label types, (ii) null values in labels,
as well as (iii) errors due to type mismatch detected
at runtime.}

\stitle{Multiple label columns.}
The data model can, optionally, have multiple row
label columns or multiple column label rows.
Often, these are presented in a hierarchical
or nested manner in pandas\xspace.
As an example, in a dataframe
tabulating sales,
we could have two row label
rows that are nested, with the first (external) row label row
corresponding
to the years,
and the second (internal) row label row
corresponding to the quarters
within each year.
In our representation, we can simply capture
this by repeating the external row label values,
and combining the row label columns to give a single
composite value, as shown below:
\begin{align*}
\small \left.
\begin{array}{lc||r}
2017 & Q1  &  \\
 	 & Q2  & \\
 	 & ... & A_{mn} \\
2018 & Q1  &   \\
	 & ... &
\end{array}
\quad \implies \quad
\begin{array}{l||c}
	(2017, Q1) 	&  \\
	(2017, Q2)  & \\
 	... 		& A_{mn}\\
	(2018, Q1)  &  \\
 	... &
\end{array}
  \right.
\end{align*}
}

\techreport{
\stitle{Label flexibility and types.}
Row labels can have a predefined type
or domain from {\em Dom}---this type
can be recorded separately and
used to augment the schema $D_n$
when performing an \code{AS LABELS} operation,
thereby avoiding having to induce it using $S$.
Due to the symmetry between columns and rows,
column labels also have this constraint.
Additionally, labels can have duplicate values or be null;
so labels are not like primary keys.

We finally define another notion
that will come in handy in future sections:
a {\em dataframe-like} system is one that supports
some, but not all dataframe properties as defined
in the data model and algebra above.
For example, a dataframe-like system might
support unordered weakly-typed relations,
with queries being composed incrementally
over the course of many statements.
We return to this notion and provide some example
systems in Section~\ref{sec:ext}.

\subsubsection*{Workflow Definitions.}
We now briefly introduce
some terms that will allow us
to describe how dataframes are manipulated
during a data analysis workflow.

\stitle{Operator.}
A {\em dataframe operator},
or simply an {\em operator},
is an atomic dataframe processing step
that
takes multiple
dataframe arguments and
returns a dataframe as a result.
We will describe the operators in the context
of the dataframe algebra in Section~\ref{sec:df-algebra}.

\stitle{Statement.}
A {\em dataframe statement}
is an expression
composed entirely of dataframe operators
and is the unit of interaction between
the user and the system.
In a notebook environment, a statement
corresponds to a single cell;
each of which is executed one at a time,
as we saw in Figure~\ref{fig:example}.
In an interpreted environment
(e.g., iPython), a statement is a single block of code.

\stitle{Query.}
A sequence of statements
chained together form a {\em dataframe query}.
Following variable references, a query
can be represented as a DAG of
operators and dataframes,
with the input dataframes
at the leaves, and the queries as the root(s).
A dataframe query is analogous to
a SQL query, but it is composed incrementally
across many statements.

\stitle{Session.}
A {\em session} is a complete, end-to-end analysis workflow,
comprising one or more queries issued
across many statements.
A session begins when the user
starts a notebook or interpreter environment
and ends when the user shuts down that environment.

}

\techreport{
\begin{figure*}
    \centering
    \includegraphics[width=0.9\textwidth]{user_stat_edit.pdf}
    \caption{Pandas user statistics from GitHub dataset.}
    \label{fig:user_stat}
\end{figure*}

\subsection{Dataframe Usage Statistics}\label{sec:usage}

To study how dataframe users interact with the pandas\xspace API, we analyzed a comprehensive dataset of 1 million Jupyter notebooks hosted on \hyperlink{github.com}{github.com} from Rule et al.~\cite{ucsd-dataframe-study}.
Out of the 1 million Jupyter notebooks, about 40\% used pandas\xspace.
We used the \code{jupyter nbconvert} module
to convert each
notebook into to a
python script, the \code{2to3} module
to transform python 2 to python 3,
and the python \code{ast}
module to parse and extract
method invocation calls.
We note that there may be some issues
in our extraction; for example, \code{.append} is both a python built in list method as well as a pandas\xspace method.
However, we expect our trends to largely
hold.

We will focus on three questions to investigate how people work with pandas\xspace.

\stitle{What are some high-density functions used in interactive analysis?}
We studied the \textit{total} occurrence of each pandas\xspace dataframe function in our data.
The most notable ones are those
used
to inspect the data (\code{plot, shape, head}),
perform numeric aggregation (\code{mean, sum}),
and
perform relational operations (\code{groupby, join}).
It is worth noting that
the notebooks contained
a lot of data modification operations
(both point queries as well as column and row queries) using \code{loc, iloc, drop, append}.
Columns and index metadata inspection and manipulation are common as well with \code{index, columns}.

\stitle{What kinds of functions are
common in day-to-day usage?}
We counted the number of files that each pandas\xspace function
has occurred in. The occurrence
measures the frequency of usage per analytic job.
The most commonly used functions
are those that create dataframes (\code{read\_csv, DataFrame}), inspect partial
results (\code{head, shape}), visualizing result (\code{plot}),
perform aggregation (\code{mean, sum, max}),
perform point queries (\code{loc, ilo, ix}), add or remove data (\code{append, drop}),
apply arbitrary user defined transformations (\code{apply}), and
perform relational operations (\code{groupby, join}).
It is worth noting that type-casting (\code{astype}) and direct access or manipulation of columns and index metadata, and underlying data storage (\code{columns, index, values}) are also high in the list.

\stitle{Which functions are common used together?}
We also investigated the
number of co-occurrence of functions
in the same line of code.
This typically involves
the user chaining pandas\xspace functions
together or calling them inside a single statement.
For example, \code{df.dropna().describe()} is fairly common across our sample.
It is also common for pandas\xspace users
to perform multiple operations in single execution cell. For example, \code{print(result = df["col1"].mean(), df["col1"].max())} prints a tuple of summary statistics. The popularity of chained or
parallel invocation suggests
opportunities for acceleration,
going beyond one operation at a
time to more complex queries.
}
\section{Dataframe Example}\label{sec:usecase}

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{motivating_example.png}
    \caption{Example use case of the pandas\xspace library, highlighting the versatility of dataframes for the end-to-end data science workflow, from data ingestion, cleaning, wrangling, to analysis.

    }
    \label{fig:example}
\end{figure}

To illustrate how dataframes can be a more appropriate tool choice over
traditional relational tables, we consider an example of an analyst
exploring the relationship between price, rating, and product
features for different iPhone models. Figure~\ref{fig:example}
illustrates the steps taken and the results in the context
of a Jupyter Notebook\cite{jupyter}. With this example,
we aim to illustrate key aspects of a typical dataframe workflow and contrast
it with that of a relational database.

\stitle{Data ingest and cleaning.} Initially, the analyst reads in the
iPhone comparison chart
from an e-commerce webpage, as shown in the cell labeled
\code{In[1]} in Figure~\ref{fig:example}. The analyst prints out
the first few lines of the dataframe to verify that the pandas\xspace data
loading function call resulted in the expected dataframe.
Based on this preview of the dataframe, the analyst identifies a set of subsequent actions for cleaning their dataset:
\squishlist
\item C1: The Camera description for the iPhone 11 Pro has an anomalous
value of 120MP, far exceeding the capabilities of other models.
This is likely a data entry error.
\item C2: To make it easier to compare across different products, the
rows and columns should be switched.
\item C3: The string column "Wireless Charging" should be converted from Yes/No to 1/0.
\end{list}
To resolve the data entry error (\textbf{C1}), the analyst performs spreadsheet-like
point updates to a separate cell. The cell update can be done by setting a new value for the cell at row 2 column 0 via the \code{iloc} command, as shown in
cell \code{In[3]}.
After performing the update, the analyst prints the dataframe again
to verify that the cell was updated to the correct value.

The analyst also inspects the output after operations C2-C3 and A1-A3, but we omit this in the following for succinctness.
Next, the analyst is interested in
comparing between different iPhones with attributes of the iPhones as columns
and individual iPhones as rows (\textbf{C2}). To represent each
row as an iPhone, the analyst needs to transpose the table.
As shown in the cell \code{In[3]} in Figure~\ref{fig:example},
the analyst prints the resulting dataframe after the transpose operation (\code{.T})
to ensure that dataframe conforms to the anticipated schema.

Since the dataset was scraped from a webpage intended for human consumption,
the column labeled
``Wireless Charging'' contains ``Yes/No'' values instead
of a binary boolean value (\textbf{C3}), the latter of which
may be preferable for downstream processing.
The analyst
can make this change in pandas\xspace by setting an existing
column label to the
result of a \code{map}, and define a user-defined function for that \code{map}
that modifies the data.
Using \code{map} to update columns is a common dataframe workflow pattern during
wrangling and cleaning, as depicted in cell \code{In[4]}.

To prepare integrating a different dataset into the workflow, the analyst
now loads in an additional dataset from a spreadsheet
containing price and rating information for various iPhone models,
depicted in cell \code{In[5]}.

\stitle{Analysis.} With the data cleaned, the analyst intends to perform the
following operations to analyze the data:

\squishlist
\item A1: Encode categorical features as binary indicators (0/1) across multiple columns via the one-hot encoding scheme.
\item A2: Join the product feature dataframe with the price and ratings dataframe.
\item A3: Compute the covariance between each dataframe column.
\end{list}

As shown in line 1 of cell \code{In[6]}, one-hot encoding is invoked via the \code{get\_dummies} function (\textbf{A1}). Next, the analyst performs a left inner join
via \code{.merge()} on the
column corresponding to iPhone model names (\textbf{A2}). The left dataframe
contains the price and review data, and the right dataframe
is the one-hot encoded feature dataframe.

With all the relevant numerical data in the same dataframe,
the analyst now computes the covariance
between the price, ratings, and each of the individual features
via a call to \code{df.cov(...)} (\textbf{A3}).

This example demonstrated only a sample of the capabilities of the
dataframe.
Nevertheless, it serves to illustrate the common use cases for dataframes:
incremental visual inspection after most operations, point and batch updates
via user-defined functions,
and a diverse set of operators for wrangling,
cleaning, and analyzing data. Moreover, dataframes offer additional flexibility
for data manipulation compared to traditional RDBMSs.
In the following section, we formally define the dataframe,
data model, and query language.

\section{Dataframes}\label{sec:definitions}

There are many competing implementations of dataframes in both open source and commercial products, but
there is no formal definition of the dataframe or an
enumeration of its properties described in the literature to date.
In this section, we provide a reference data model (Section~\ref{sec:dataframedef}) and algebra (Section~\ref{sec:df-algebra}) for dataframes to ground subsequent
discussion.
We then
discuss an empirical study detailing commonly-used functionality
from the pandas\xspace library (Section~\ref{sec:usage}).

\subsection{Dataframe Formalization}\label{sec:dataframedef}

Dataframes exhibit a number of fundamental deviations
from traditional relational tables.
In this section, we describe the dataframe data model
and propose a set of dataframe algebra operators that
represents the APIs and operators in
traditional dataframe implementations like pandas\xspace and R.

\subsubsection{Dataframe Data Model}
Due to the wide and varying use of the term {\em dataframe},
we now propose a formal definition.

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\begin{definition}{Dataframe:}
A dataframe is an ordered collection of tabular data
with inherent symmetry between rows and columns. In
a dataframe, both rows
and columns are associated with a label, are ordered,
and have types.
\end{definition}

\begin{figure}
    \centering
    \includegraphics[width=0.45\textwidth]{dataframe_data_model.png}
    \caption{The dataframe data model.

    }
    \label{fig:datamodel}
\end{figure}

At a high-level a dataframe is an {\em ordered}
tabular relation. Dataframes contain an inherent
order for rows and columns which is commonly used for display purposes, order-dependent
operations (e.g. \code{CUMULATIVE MAX}), and selection/projection.
Unlike users of the relational model, dataframe users heavily
depend on the order of the data in their workflows,
similar to the users of a spreadsheet.
A user expects to see and operate on the data in the exact order
that it was ingested.
It is important to note here that the data model
is {\em ordered}, but not necessarily {\em sorted}. This
distinction is important because the order that the user
prefers may not necessarily be the sorted order of any
column in the dataframe. Some recent systems \cite{dask} have adopted a
sorted data model, which deviates from the data model of
traditional dataframe systems like pandas\xspace and R.

Metadata in dataframes are treated differently than that
in the relational data model.
Columns and rows in a dataframe are equivalent
and can be treated interchangeably. This
property is also shared with matrices, where columns and rows both
have associated metadata. As a result, columns {\em and} rows have
data types, labels or names, and an order.

Figure \ref{fig:datamodel} shows a high-level overview of the data
model as it relates to a relational table. The various components
of the dataframe data model will now be explained in detail.

\noindent\circled{1} \stitle{Tabular data.} The tabular data in a
dataframe is a ``grid'' of 2-dimensional data. In this data model,
the tabular data need not be physically ordered so long as the order ranks of each row and
column are maintained in the row and column metadata.

\stitle{Columns.} Columns in a dataframe are conceptually similar to
relational table columns: a series of row values for a particular
label. In dataframes, the columns are ordered, such that a column
can be projected either from its column label or its numeric index
in the column labels.

\noindent\circled{2} \emtitle{Column Labels.} The column labels identify a given column.
Unlike relational algebra, in a dataframe, column labels
have a name and data type. The data type is useful for
classifying non-string data. Dataframes support
hierarchical column labels in the form of multiple column label ``rows'',
each having an individual type and a name.

\noindent\circled{3} \emtitle{Column Metadata.} The column metadata contains each
column's data type and rank order. The rank order for the
column is present to ensure that the column order is maintained
as well. The type of the columns can be \code{ANY} type, which subsumes
all other types.

\stitle{Rows.} Rows in a dataframe are an ordered tuple of values
associated with a given row label. Rows can be selected either by their label
or by the integer offset of the row in rank order. For example,
in Figure~\ref{fig:example} \code{In[2]}, the row was selected
via \code{iloc}, which is the integer rank of the row. This row
could have also been selected via \code{loc["Front Camera"]}, which
is that row's label.

\noindent\circled{4} \emtitle{Row labels.} The row labels in a dataframe
identify a row. They are collectively one or more
special columns in the
dataframe, primarily serving as to give symmetry
with columns (so that rows have names just
like columns, particularly useful after a dataframe
transpose). An important distinction between row
labels and the primary key of a table is that
these row labels need not be distinct.
They also provide syntactic sugar for
selecting rows. The row labels column(s)
has a name and can be any data type. The
order of the dataframe is not necessarily
the lexicographic order of the row labels. As with
column labels, dataframes support
hierarchical row labels in the form of multiple row label columns,
each having an individual type and a name.

\noindent\circled{5} \emtitle{Row metadata.} The row metadata contains
each row's data type and rank order,
an integer offset. The collection of offsets is called
the order column, and can be
conceptualized as an invisible column that allow each row
to be accessed by its offset. Note that in the relational
model, because order is not guaranteed between queries,
this metadata represents the user's row order. Additionally,
each row has an associated type, ensuring
that columns are typed after a transpose. As with columns,
the type of the rows can be \code{ANY} type, which subsumes
all other types.

\noindent\circled{6} \stitle{Global metadata.} The global metadata
serves the function of being metadata about the dataframe's metadata.
Column labels and row labels can have a ``name'', which can make
hierarchical labels distinct and individually accessible. The global
metadata also holds the types of the row and column labels.

\subsubsection{Data model Comparisons}
We now illustrate some of the key similarities and differences
between dataframes, matrices, and relational tables.

\stitle{Comparison with matrices.}
It may be tempting to classify a dataframe as a matrix or an array
with column and row labels.
While such an abstraction would exhibit some of the properties
of dataframes, matrices on their own are not capable of capturing
polymorphic behavior due to differing data types. The abstract
notion of a ``matrix'' does not have a schema, and all the entries
of a matrix must be of the same type so that the matrix is an
element of a vector space over a particular field. For this reason,
it does not make sense to, say, compute the mean of some matrix
column using groups defined by the elements of another column (a group by);
if the matrix elements are categorical, numeric operations like
``take the mean'' lack well-defined semantics, and similarly if
the matrix elements are real-valued, computing groups for a
``group by'' operation likewise does not make sense.
Rather, dataframes subsume matrices: different subsets of dataframe
rows and/or columns with the same numeric type can be used in
familiar linear algebra operations while preserving their relationship
to other dataframe rows / columns when it is desirable to do so.

\stitle{Comparison with relational tables.}
Due to the presence of schema and typing information, dataframes are
more closely related to traditional relational tables than
to matrices. However, it is precisely the characteristics
that are shared with matrices that serve to distinguish
dataframes from traditional relational tables. Namely, in
dataframes, both rows and columns are {\em ordered} and can
be selected via a label or rank order. Furthermore, just as matrices have
symmetry between rows and columns, so do dataframes: while
relational tables typically only give names and types to columns,
dataframe schemata assign names (called ``labels'') and types to rows
as well, so that a dataframe ``transpose'' has well-defined
semantics. It is not surprising, therefore, that dataframes evolved
primarily in runtime-typed languages like Python and R, which allow
for schema-level types like ``Object'' or ``Any'', so that the
same row or column can contain multiple different runtime types.

\stitle{Comparison with spreadsheets.}
Dataframes have many features inspired by and in common
with spreadsheets. Both enable single-point updates
to individual cells and have a data model where
columns and rows are both ordered. In spreadsheets,
however, the data representation can be sparse with
multiple empty values and gaps between data cells.
It is possible in the spreadsheet data model to keep multiple
datasets in the same spreadsheet with some empty cells
separating them. The spreadsheet data model comes at the
cost of complexity in implementing relational operators.
Dataframes, on the other hand, do not allow for this sparse
representation. Dataframes have a dense representation, where
one dataframe correlates to one dataset, enabling easier
implementation and optimization of relational operators.

\subsubsection{Dataframe Algebra} \label{sec:df-algebra}

\begin{table*}[]
\begin{tabular}{|l|c|c|c|c|l|}
\hline
\rowcolor[HTML]{C0C0C0}
\textbf{Operator} & \textbf{Metadata} & \textbf{Data} & \textbf{Origin} & \textbf{Order of Result} & \textbf{Description}                                       \\ \hline
UNION             &                   & \xmark             & REL             & Parent$^\dag$            & Set union of two dataframes                                \\ \hline
INTERSECTION      &                   & \xmark             & REL             & Parent$^\dag$            & Set intersection of two dataframes                         \\ \hline
DIFFERENCE        &                   & \xmark             & REL             & Parent$^\dag$            & Set difference of two dataframes                           \\ \hline
SELECTION         &                   & \xmark             & REL             & Parent                   & Eliminate rows                                             \\ \hline
PROJECTION        &                   & \xmark             & REL             & Parent                   & Eliminate columns                                          \\ \hline
JOIN              &                   & \xmark             & REL             & Parent$^\dag$            & Combine two dataframes by element                          \\ \hline
RENAME            & \xmark                 &               & REL             & Parent                   & Change the name of a column                                \\ \hline
DROP DUPLICATES   &                   & \xmark             & REL             & Parent                   & Remove duplicate rows                                      \\ \hline
GROUP BY          &                   & \xmark             & REL             & Parent$^\dag$            & Group identical attributes                                 \\ \hline
SORT              & \xmark                 &               & REL             & New                      & Lexicographically order rows                               \\ \hline
MAP               &                   & \xmark             & DF              & Parent                   & Apply a function uniformly to every row                    \\ \hline
FLATTEN           &                   & \xmark             & DF              & Parent$^\ddag$           & Convert elements containing collections into multiple rows \\ \hline
WINDOW            &                   & \xmark             & DF              & Parent                   & Apply a function via a sliding-window (either direction)   \\ \hline
TRANSPOSE         & \xmark                 & \xmark             & DF              & Parent$^\lozenge$                & Swap data and metadata between rows and columns            \\ \hline
AS LABELS         & \xmark                 & \xmark             & DF              & Parent                   & Set one or more data columns as the row labels column(s)             \\ \hline
RESET LABELS      & \xmark                 & \xmark             & DF              & Parent                   & Convert the row labels column(s) into a data column        \\ \hline
AUGMENT           &                   & \xmark             & DF              & Parent                   & Create a new column from a function applied to another     \\ \hline
\end{tabular}
\caption{
Dataframe Kernel Algebra. \hfill\break
$\dag$: Ordered by left parent first, then right parent to break ties. \hfill\break
$\ddag$: Ordered by parent first, then by the order of the collection. \hfill\break
$\lozenge$: Order of columns is inherited from order of rows and vice-versa.
}
\label{tab:df-algebra}
\end{table*}

In this section, we propose a set of operators that encompasses
most functionality provided by dataframes. The
purpose of this section is to help frame the
dataframe definition and explicitly contrast dataframe
algebra with relational algebra. We do not
argue that this is the minimum set of operators.
\devin{We cover a lot and will show by examples}. At this time,
we use this set of algebra to help explain the significant
difference between dataframe algebra and relational algebra
and the challenges in bringing this algebra to traditional relational
systems.

The kernel of operators we have derived are described in
Table~\ref{tab:df-algebra}. Our proposed dataframe algebra ecompasses
ordered analogs of the
operators from the extended relational algebra.
Dataframe algebra additionally supports other
data and metadata transformation operators,
and three operators that transforms
both data and metadata: \code{TRANSPOSE}, \code{AS LABELS}, and \code{RESET LABELS}.
Since these are the
main deviations from relational algebra, we
will describe the additional data and metadata manipulation
operators in detail.

\stitle{Transpose.}
Transpose interchanges column and row metadata, so that the columns of the
dataframe become the rows, and vice-versa.
Not only does this allow users extreme flexibility when coercing
a dataset to their desired schema and orientation, but it also
allows them to perform SQL operations along either columns or rows.
In our example in Section~\ref{sec:usecase}, we note a case where
the table was not oriented
properly from ingest, and a transpose was required to give us the desired
table orientation.

In pandas\xspace and other dataframe implementations, it is possible to
perform operations along either the rows or columns via the \code{axis}
argument. We simplify this in the design of the algebra by defining
operators only on the rows and defining the \code{TRANSPOSE} operator.
To do an operation along the columns, take the \code{TRANSPOSE}, apply
the operator, then take the \code{TRANSPOSE} again to return to the
original orientation.
With this flexibility, operators
on the dataframe can be performed along either the columns or
the rows.

\code{TRANSPOSE} presents unique challenges for traditional relational systems
primarily because of the metadata transformation needed.
Relational algebra
does not have an abstraction that provides the ability to
efficiently swap the axes and modify the metadata in this way.
While prior work in the relational literature
describes how to perform
a \code{PIVOT} in a relational database~\cite{cunningham2004pivot},
it is not in general possible to transpose a relational
table with columns of varying types without losing typing information,
as the schema only tracks column-level (and not row-level) metadata.
\code{TRANSPOSE} can also be extremely computationally expensive
depending on the relational database's architecture and partitioning.
In the implementation of \code{TRANSPOSE}, often it will
be important to postpone the calculation of \code{TRANSPOSE}
until the last possible moment because of the associated computation
costs.

\stitle{Map.} The map operator takes some function {\em f}
and applies it to each row individually. The function
{\em f} has only a single requirement: for each row input
there must be a single row output with the same number of attributes.
Thus, the output dataframe will be contain the same number of columns
and rows as the input.
The purpose
of the map operator is to alter the data of each dataframe element
uniformly. \code{MAP} is useful for data cleaning
or to wrangle certain data that is poorly structured
or lacks appropriate formatting (e.g. Figure~\ref{fig:example} \code{In[4]}).

Extended relational algebra supports map via the use of functions
in the subscript of projection operators (i.e., in the \code{SELECT}
clause of SQL). The primary challenge associated with porting map
to existing relational systems is the fact that the dataframe map
is capable of operating on many columns without explicitly naming
them. For example, in a relational system,
the equivalent of a \code{fillna} operation would
likely require code refactoring after a schema changes introduces an
additional column (wherein the new column is explicitly named in the
\code{fillna} equivalent), but no such refactoring is necessary if
an additional column is added to a dataframe.

\stitle{Window.} Window is an operator that is order-dependent
and takes some function {\em f} and applies
it on a sliding-window of a column of the data. The function {\em f} has the special
requirement that it must be applied in the order of the rows,
and the number of output rows for a given window is 1.
Like \code{MAP}, the resulting dimensions of the dataframe
are identical to the input dataframe.
Window allows an arbitrary number of previous rows to
be passed as a parameter to the function {\em f} and can
slide in either direction.

The main challenge that window presents to traditional relational
systems is the order requested by the user. Many relational database
systems already support some version of
window functions \cite{postgresql_window}, so the only additional consideration
would need to be ensuring that
the order is correct.

\stitle{Flatten.} The flatten operator splits a dataframe
element containing an ordered collection (e.g. list)
into multiple dataframe elements, one element for each
element in the collection. This results in
an increased number of rows in the dataframe. The
values in the other columns and the row labels
of each row are replicated for each resulting row in the
flattened dataframe.
Flatten maintains the original order of the dataframe,
but adding rows follows the rank order of the collection
in that column. The
main use-case for flatten is to normalize the dataframe,
such that each row represents a single piece of data.

There are relational database implementations that support
a \code{FLATTEN} operator\cite{postgresql_unnest}. The order semantics
of dataframes may pose some additional challenges related
to correctly setting the rank within the row's metadata to ensure
correct order of the result. \smacke{This doesn't seem like a
unique difficulty faced by relational tables -- if it's been solved
by dataframes, I don't see why a relational system can't just borrow
the same technique?}

\stitle{As Labels.} The \code{AS LABELS}
operator projects one or more columns out
of the tabular data to be
set as new row labels for the
dataframe, dropping and replacing the old labels.
The type(s) of the new labels are inherited
from the type of the column(s) that are set
as the new labels.
This allows the user to have some control over
the row labels they interact with. With this capability,
data can be moved into the dataframe's metadata.

From a relational database perspective, this operator is
rather unusual, because users do not typically interact
with the metadata of a table. Despite this, in a relational
context, the ``movement" of data to metadata could be done
by simply updating the metadata of the selected columns.
Since the row labels can be thought of as ``special columns", it suffices
to update the metadata for the columns. As for a projection,
the rank-order metadata will need to be updated as well.
\smacke{I'm lost after reading this entire paragraph.
Skipping and moving to the next operator.}

\stitle{Reset Labels.} \code{RESET LABELS} takes all of the row label columns
and sets them as data columns at position 0.
The respective data types of the new column(s)
are directly inherited from the labels column(s).
The labels are set to the default label:
the order rank of each row. \code{RESET LABELS} is the opposite of
the \code{AS LABELS} operator, and the two of these give the
user complete control over the row labels, and with \code{TRANSPOSE},
column labels as well. This allows users to apply operators
on the dataframe's metadata, which is particularly useful for
operators like \code{JOIN}, \code{GROUP BY}, and \code{DIFFERENCE}.
Many pandas\xspace operators treat the metadata of a dataframe as data, so
it is important to enable the ability to move columns between
the metadata and the data to support this behavior. Conceptually,
this also allows the order of the dataframe to become data if
multiple \code{RESET LABELS} are chained together. However,
because the order is only mutable in the context of a \code{SORT},
it is impossible to update the order of the dataframe
directly in this way.

In a relational context, \code{RESET LABELS} poses
unique challenges. Inserting the new columns
at position 0 will cause the metadata of all columns
to be updated because each order rank will be shuffled
by the number of columns inserted. The typing information
is maintained between row/column labels during this operation
and its opposite, \code{AS LABELS}. The fact that metadata
can become data explains the need for typed labels.
\smacke{Again, I don't understand why this difficulty is
unique to relational systems. If we can solve it in a system
that uses dataframes, why aren't those techniques directly
applicable to the relational system? To put it in a different
way, the challenge outlined above seems just as applicable
in the context of dataframes.}

\stitle{Augment.} Augment creates a new column in the dataframe
at the last position, \code{LENGTH(COLUMNS)},
from the result of some function \code{f} on the rows.
The name of the new column is provided at invocation. The
function \code{f} must take as argument an entire row
and must return a single value to be inserted into the new
column. For example, the function can sum the numeric
columns of a row. For users, it is often useful to
see some summary statistics alongside the regular
data.

\code{AUGMENT} can be reduced to a \code{MAP} followed by a \code{PROJECT}
and \code{UNION}. We create this operator as a simplification
of these steps, and there is a precedent for this
in relational algebra with \code{JOIN} being \code{CROSS PRODUCT}
followed by a \code{SELECT}. This operator is already
supported by most relational database implementations
with the \code{SELECT} statement: \code{SELECT ID, V1, V2, V1 + V2 FROM table}.

\subsubsection{Kernel Algebra demonstration}\label{sec:algebra-example}

In this section, we demonstrate how a few of the more
exotic pandas\xspace operators can be written with
the algebra presented in Section \ref{sec:df-algebra}.

Some examples of map operators in the pandas\xspace API are:

\squishlist
\item \code{fillna}: Convert NULL values to another value.
\item \code{isna}: Determine if a dataframe element is NULL,
often used as a step in counting NULL values.
\item \code{str.upper}: Converts the string element to upper-case.
\end{list}

Some examples of window operators in the pandas\xspace API are:

\squishlist
\item \code{cummax}: Take the cumulative max of a column.
\item \code{diff}: Take the difference between an element and its neighbor.
\item \code{shift}: Shift rows down to align with a new row label,
maintaining the order of the data.
\end{list}

\code{AS LABELS} is captured in the pandas\xspace API by the following example operators:

\squishlist
\item \code{set\_index}: Set the dataframe row labels using existing column(s).
\item \code{reindex}: Conform the dataframe row labels to new labels.
\item \code{index}: The row labels of the dataframe. They can be assigned to a column.
\end{list}

Flatten is used as a part of the follow pandas\xspace operators:

\squishlist
\item \code{explode}: Transform each element of a list-like to a row, replicating the row labels.
\item \code{melt}: Unpivot a dataframe from wide format to long format
\end{list}

\code{RESET LABELS} is captured in the pandas\xspace API by the
\code{reset\_index} method.

There are several pandas\xspace operations and behaviors that require
\code{TRANSPOSE} when defined in this algebra.
We present a sample of these operators, to be further discussed in
Section~\ref{sec:algebra-example}:

\devin{Move these to the next section}

\squishlist
\item \code{transpose}: Transpose column and row labels.
\item \code{pivot}: Return reshaped dataframe organized by given row/column values.
\item \code{stack}: Stack the prescribed level(s) from columns to rows.
\end{list}

\subsubsection{Workflow definitions}

In this section, we describe the definitions of different
components of a given dataframe workflow.

\stitle{Operator.} A dataframe operator is a single
API call on or with a dataframe. This follows the SQL definition
of an operator, see Section \ref{sec:df-algebra} for the operators
exposed in dataframe APIs.

\stitle{Statement.} A dataframe statement is the smallest unit of
submission a user can
provide to the system and contains one or more operators.
This presents itself in different ways depending on how
the user is interacting with the dataframe system. In an interpreted
environment (e.g. iPython), this will be a single block of code.
In a notebook environment, a statement is a single cell. We define
a statement in this way to draw parallels to a single SQL query statement
in the way it is interacted with, however a statement is not a full
query.

\stitle{Query.} A dataframe query is a series of statements that are
composed to answer a larger overall question. If we consider the
data\-frame system as a DAG
of operators and their dependencies, a query ends at each of the
leaf nodes. A dataframe query is the equivalent of a SQL query.

\stitle{Session.} A session is a complete, end-to-end workflow. It
begins when the user starts a notebook or interpreter environment
and ends when the user shuts down that environment. A session
is composed of one or more queries. Because dataframe systems
are typically in-memory, the results of the query are not
persisted unless the user explicitly expresses this by writing
the result to a file.

\subsection{Dataframe usage statistics}\label{sec:usage}

\begin{figure*}
    \centering
    \includegraphics[width=0.9\textwidth]{user_stats.png}
    \caption{Pandas user statistics from Github dataset.}
    \label{fig:user_stat}
\end{figure*}

To study how dataframe users interact with the pandas\xspace API, we analyzed a comprehensive dataset of 1 million Jupyter notebooks hosted on \hyperlink{github.com}{github.com} from Rule et.al.~\cite{ucsd-dataframe-study}. Out of the 1 million Jupyter notebooks, about 40\% imported and used the pandas\xspace dataframe library at least once. We will focus on three questions to investigate how people work with pandas\xspace.

\stitle{What are some high-density functions used in interactive analysis?}
We studied the \textit{total} occurrence of each pandas\xspace dataframe method in our data. The most notable methods are methods to inspect the data (\code{plot, shape, head}), methods to perform numeric aggregation (\code{mean, sum}), methods to perform relational operations (\code{groupby, join}). It is worth noting a lot of data modification (both point queries as well as column and row queries) using \code{loc, iloc, drop, append}. Columns and index metadata inspection and manipulation are common as well with \code{index, columns}.

\stitle{What kind of functions were common in day-to-day usage?}
We counted the number of files that each pandas\xspace methods has occurred in. The occurance measures the frequency of usage per analytic job.
The most commonly used methods are used to perform actions such as creating DataFrames (\code{read\_csv, DataFrame}), inspect partial result (\code{head, shape}), visualizing result (\code{plot}), perform aggregation (\code{mean, sum, max}), perform point queries (\code{loc, ilo, ix}), adding or removing data (\code{append, drop}), apply arbitrary user defined transformation (\code{apply}), relational operation (\code{groupby, join}). It is worth noting that type-casting (\code{astype}) and direct access or manipulation of columns and index metadata, and underlying data storage (\code{columns, index, values}) are also high in the list.

\stitle{What are some methods are common used together?}
We also investigate the number of co-occurrence of methods in the same line of code. This typically mean user chaining pandas\xspace method together or calling them inside a single statement. For example, \code{df.dropna().describe()} is fairly common across our sample. It is also common for pandas\xspace user to perform multiple operation in single execution cell. For example, \code{print(result = df["col1"].mean(), df["col1"].max())} prints a tuple of summary statistics. The popularity of chained or parallel invocation suggest opportunities to accelerate one statement at a time as well accelerate multiple statements at a time.

\section{Dataframe Example}\label{sec:usecase}

\begin{figure*}[!t]
 \vspace{-10pt}
    \centering

    \includegraphics[width=0.98\textwidth]{modin_workflow.pdf}
     \vspace{-10pt}
    \caption{\rebuttal{Example of an end-to-end data science workflow, from data ingestion, preparation, wrangling, to analysis. }

    }
    \label{fig:example}
     \vspace{-15pt}
\end{figure*}

\rebuttal{
In Figure~\ref{fig:example},
we show the steps taken
in a typical workflow of an analyst exploring the relationship between
various features of different iPhone models in a Jupyter notebook~\cite{perez2015project}.
}

\stitle{Data ingest and cleaning.}
Initially, the analyst reads in the
iPhone comparison chart \rebuttal{using \code{read\_html}}
from an e-commerce webpage, as shown in
R1 in Figure~\ref{fig:example}.
\rebuttal{
The data is verified
by printing out the first few lines of the dataframe
\code{products}. (\code{products.head()} is also often used.)
}
Based on
this preview of the dataframe,
the analyst identifies a sequence of
actions for cleaning their dataset:
\squishlist
    \item C1 [Ordered point updates]:

        \rebuttal{
        The analyst fixes the anomalous value of 120MP for Front Camera
        for the iPhone 11 Pro to 12MP,
        by performing a point update via \code{iloc}, and views the result.
        }
    \item C2 [Matrix-like transpose]:

        \rebuttal{
        To convert the data to a relational format,
        rather than one meant for human consumption,
        the analyst transposes the dataframe (via \code{T})
        so that the rows are now products and
        columns features,
        and then inspects the output.
        }
    \item C3 [Column transformation]:

        \rebuttal{
        The analyst further modifies the dataframe
        to better accommodate downstream data processing by
        changing the column ``Wireless Charging'' from ``Yes/No'' to binary.
        This is done by updating the column using a user-defined \code{map} function, followed by displaying the output.
        }
    \item C4 [Read Excel]:

        \rebuttal{
        The analyst loads price/rating information
        by reading it from a spreadsheet into \code{prices} and then
        examines it.
        }
\end{list}

\stitle{Analysis.}
\rebuttal{Then,} the analyst performs the following operations to analyze the data:

\squishlist
    \item A1 [One-to-many column mapping]:

        \rebuttal{
        The analyst encodes non-numeric features in a one-hot encoding scheme
        via the \code{get\_dummies} function.
        }
    \item A2 [Joins]:

        \rebuttal{
        The iPhone features are joined
        with their corresponding price and rating
        using the \code{merge} function.
        The analyst then verifies the output.
        }
    \item A3 [Matrix Covariance]:
        With all the relevant numerical data in the same dataframe,
        the analyst

        computes the covariance between the features
        via

        \rebuttal{the \code{cov} function, and examines the output}.
\end{list}

\noindent This example demonstrated
only a sample of the capabilities of dataframes.
Nevertheless, it serves to illustrate
the common use cases for dataframes:
immediate visual inspection after most operations,
each incrementally building on the results of previous ones,
point and batch updates
via user-defined functions,
and a diverse set of operators for wrangling,
\rebuttal{preparing,} and analyzing data.

\subsubsection{Rewrite Rules for Schema Induction}
Due to their flexible schemas, dataframes
support addition and removal
of columns as first-class operations,
and at any point in time could
have several columns with unknown type.
Certain dataframe operators need type
information, however---e.g. avoid attempting to
\code{JOIN} two dataframes
on columns with mismatched types or using
a numeric predicate on a column with some strings.
The schema induction function, $S$,
could be used to induce the requisite
typing information, but it is expensive,
and must
be explicitly considered when
modeling cost for query plans.
Specifically, if certain columns are not operated
on, inferring their type via $S$
can be deferred to when they are
first manipulated, and omitted entirely, if,
for example, they are dropped before ever
being accessed.

At least in some cases,
schema inference rules might be able
to avoid the application of $S$ altogether.
As one example, if ordered relational operations
are chained together,
schema induction can be omitted between operations,
suggesting the possibility
of employing rewrite rules to skip applying $S$.
Another example involves
UDFs with known output types
(e.g., a \code{MAP} with a
UDF that always returns an integer).

In the case of operations which
merely shuffle rows around (e.g. moving even-indexed
rows to the beginning of a dataframe, reordering),
schema induction can be omitted entirely.
When filtering or taking a sample of a dataframe,
schema induction can be omitted if the type is already fairly
constrained and will not be additionally constrained
based on the sample.
For example, if we
drop all rows with strings in a specific
column, we may end up with that column having a restricted
type such as float or int, requiring special care.

While omitting or deferring schema inference is promising,
additional complications arise
from the fact that, in a dataframe system,
metadata {\em is} data (see also Section~\ref{sec:order_challenges})
that may itself be
queried by a user.
In particular, it is common for users
to perform {\em runtime type inspections}
as a sanity check.
As a result, the extra effort
for eschewing or deferring schema induction may prove futile
if the user chooses to inspect types anyway.
}

\rebuttal{\subsubsection{Reusing Type Information}}
\label{sec:matviews}

\rebuttal{It is common to reuse a dataframe across
multiple statements in a program.
In cases where the dataframe lacks explicit types,
it can be very helpful to materialize the results of
both schema induction and parsing---both within the
invocation of a program (internal state), and across invocations in storage.}

\rebuttal{Materialization of flexibly-typed schemas introduces
a new set of challenges. Both schema induction and parsing can be
a significant fraction of the cost of processing.
This raises optimization choices for materialization:
we can cache the results
of $S$ (for one or more columns),
and additionally we can cache the results
of parsing functions (in principle, at a granularity down to the cell level).
For complex multistep dataframe expressions,
we can choose to make these decisions at each operator
in the pipeline that introduces a dynamically-typed column. Hence the
optimization search space is large.
Moreover, the workload of ``queries'' is different from
traditional materialized view settings---languages
like Python are more difficult to analyze statically than SQL,
and we can expect usage patterns to differ
from databases as well (Section~\ref{sec:interactivity}).}

\rebuttal{In some cases, it is reasonable to expect
that a programmer will want to declare the
types of the dataframe explicitly---e.g.,
an expression like \texttt{df\_t = \code{TRANSPOSE}(df, [myschema])} where \texttt{myschema}
is an array of type names for the columns.
In this case, there is no need to run schema induction.
In a loosely-typed language like Python,
\texttt{myschema} can be an arbitrary expression returning an array of strings.
For example, it might read a list of type names from a very large
file with the same number of rows as \texttt{\code{TRANSPOSE}(df)}.
Alternatively, the dataframe \texttt{df} itself might have
``row types'' stored as strings in the $i$'th column of the data,
leading to an expression like
\texttt{df\_t = \code{TRANSPOSE}(df, df[i])}.}
\agp{I think we need to add a bit here about why we may want to materialize
schemas prior to transposes.}

\rebuttal{View maintenance has a role in the dataframe context, with new challenges for type induction.
The most direct use is in delta-computation of expressions that have the effect of ``adding'' rows to their inputs.
For example, consider a \code{MAP} operator with a data validation function: for each column it returns the input if it
passes a validation test, else it returns an error message in that column.
The new rows may all respect the constraints
of the types of the input dataframe, or some new rows could break those constraints---e.g. a string-typed error message
appearing in a column of numbers. In both cases, we'd like the type induction to take advantage of the work done to
induce a schema for the input, and differentially decide on a schema for the output. Note that these issues get more subtle as
the type system gets richer---e.g., consider an input with a column of type \emph{percent}
that is passed into an arithmetic \code{MAP} function---the output may be statically
guaranteed to be numeric, and for a given dataframe may or may not still be of type \emph{percent}.}

\rebuttal{Regardless of the source of the schema---whether it be induced,
stored externally, or stored within the data itself---any
implementation should assume that the metadata for a dataframe
could be expensive to compute, and potentially very large.
Storage and computation
of this metadata can have significant overheads,
and methods for ameliorating those costs
will be central to scalable dataframe
research.}

\rebuttal{\subsubsection{Pipelining Schema Induction in Query Plans}}
\rebuttal{When applying $S$ and the parsing function
to columns is unavoidable,
we may be able to reduce its cost by trying to fuse
it with other
operations that are type-agnostic and lightweight
(e.g., data movement
or serialization/deserialization) while adding minimal overhead,
the development of which we foresee to be a fruitful
research direction.

For other operations, the position of $S$ within
the query plan
can have major performance implications.
Consider a \code{MAP} operation that
is being applied to a column of strings.
If the \code{MAP} operation is
relatively inexpensive (e.g., if it is measuring the string length),
it may make sense to to skip type checking via schema induction before the \code{MAP} operation.
Although
a type error (due to, e.g., the presence of an unexpected integer value)
leads to wasted effort,
it may be acceptable, as the
overhead paid by actual application
of the \code{MAP} is not too high.
On the other hand, a \code{MAP}
which performs heavy-duty
regular expression parsing
over long strings may delay error detection
unacceptably if schema
induction is fused with the \code{MAP} application.

Overall, the positioning of the schema induction
operator within the query plan,
by possibly fusing it with existing operators,
combined with schema
induction avoidance and reuse
as previously discussed,
is crucial for the development of a
full-fledged dataframe query optimizer.}

\subsection{Incremental Query Construction}\label{sec:trialanderror}
\rebuttal{
In addition to the challenges around
satisfying the stringent latency requirement
for immediate feedback discussed above,
the need to frequently evaluate and display results for
intermediate sub-expressions (i.e., the results of \stmts)
over the course of a session
complicates query optimization,
as we saw in Section~\ref{sec:opportunistic-evaluation}.
While incrementally
constructing dataframe queries
over the course of an interactive session,
users iterate on query sub-expressions through trial-and-error,
frequently inspecting and revisiting intermediate results
to try alternate exploration paths.
Such fragmented workloads limit the optimizations
that can be applied to each sub-expression.
However, since
user \stmts often build on others,
we can jointly optimize across these \stmts and resulting sub-expressions,
sharing work as much as is feasible.
Further, since users commonly return
to old \stmts to try out new exploration paths,
we can leverage materialization to avoid redundant
reexecution.
We discuss these two ideas next.

\subsubsection{Composable Subexpression Support} \label{sec:mqo}
}
\moved{
As a result of opportunistic evaluation,
there are often many \stmts that
are not completely \rebuttal{executed when issued
by the user}, and are instead executed
in the background asynchronously \rebuttal{during user think time}.
Moreover, by prioritizing
the return of a \rebuttal{prefix or suffix of the results (Section~\ref{sec:prefix})},
often, many \stmts are not computed entirely,
with the computation either deferred (in lazy or eager evaluation),
or being scheduled in the background (in opportunistic evaluation).
Thus, there are many statements that may be
scheduled for execution at the same time.
These statements may operate over similar
or identical subsets of data.
\rebuttal{These overlapping queries that
can be batch processed make dataframes particularly amenable to}
multi-query optimization (MQO),
e.g.,~\cite{sellis1988multiple,harizopoulos2005qpipe,giannikis2012shareddb,roy2000efficient}.
\techreport{In fact, some have argued that MQO has
limited applicability in a general relational context:
``One problem of MQO is its
limited applicability (...). In many workloads (...)
there aren't many opportunities
to factor out common subexpressions''~\cite{giannikis2012shareddb},
\rebuttal{and}
``the synchronization of the execution
of queries with common subexpressions
when queries are submitted at different moments in
time''~\cite{giannikis2012shareddb}.
In the dataframe setting, both these reasons for limited
applicability do not hold:
there are often many statements executed essentially
in sync, and there are lots of opportunities
to factor out common subexpressions since
these statements essentially build on top of each other.}
\rebuttal{However, new challenges emerge because
of the new space of operators,
as well as the prioritization of the return
of prefixes/suffixes over the entire result
when requested by the user.
}

}

\moved{
One \rebuttal{simple approach}
is to allow operations
that share inputs to share
scans\techreport{, thereby
reducing the overhead required to
access data}.
We can go even further if
we recognize that many \stmts
are essentially portions of a query
composed incrementally
(e.g.,
\rebuttal{a \code{TRANSPOSE} followed by a \code{PROJECT}
to simulate \code{SELECT}}).
Therefore, we simply need to construct
a query plan wherein
sub-plans that correspond to
intermediate dataframe results
are materialized as a by-product.
\rebuttal{These intermediates are also
likely to be reused by the user in the future.}
This poses an interesting conundrum,
because ensuring that the sub-plan results
are materialized ``along the way''
may result in suboptimal
overall plan selection,
which is problematic
when the user cares more about the final
dataframe than intermediates.
For example,
\rebuttal{
the optimal way to compute a \code{SELECT}
may not be to first compute a \code{TRANSPOSE}
and then do a \code{PROJECT}, even though
this may}
have the benefit
of producing the appropriate intermediate
results.
\rebuttal{Unlike MQO in relational databases,
wherein it is important to share
join subexpressions, here, an even more expensive
operation is \code{TRANSPOSE}---necessitating sharing
if at all possible.}
By using partial results to help
users avoid debugging mistakes,
we may be able to reduce
the importance of constructing
many of the intermediate results
in entirety, unless requested
by the user explicitly.
Moreover, by observing the user's likelihood
of inspecting the intermediates
over the course of many sessions,
we can do a weighted joint optimization
of all query subexpressions,
where the weights for
each intermediate dataframe corresponds to
its importance.
}
\moved{
\techreport{
Going one step further, we can try
to jointly optimize not just the evaluation
of intermediate and final result dataframes,
but also the partial or approximate results---a
challenging endeavor.
We can estimate
probabilities for what the user
might do next, e.g., inspect an intermediate,
or compose the next statement,
and the time they may take to do so.
We can couple that with quantifying the benefit
of the user seeing a certain portion
of an intermediate result at a certain time,
to construct a globally optimal query plan.
}
}

\moved{
\rebuttal{
\subsubsection{Debugging \& Building Queries Incrementally}\label{sec:materialization-and-reuse}
}
The incremental and exploratory nature of dataframe
query construction over the course of a session
leads to nonlinear code paths
wherein the users revisit the same intermediate
results repeatedly as a step towards constructing
just the right queries they want.
In such cases, \rebuttal{intelligently materializing
key intermediate results can save significant redundant
computation and speed up query processing.
The optimizer needs to handle the
}
trade off between materialization overhead
and the reduced execution time facilitated by availability
of such intermediates
to utilize storage in a way that maximizes
saved compute---small
\rebuttal{intermediate dataframes} that are time-consuming to compute and reused frequently
should be prioritized over \rebuttal{large intermediate dataframes}
that are fast to compute.
\rebuttal{Note however that materialization
doesn't necessarily need to happen on-the-fly, and can
be also performed in the background asynchronously during
during user think-time.}
\rebuttal{Determining what to materialize
requires us
to predict
which intermediates are likely to be used frequently.
The prediction algorithm should take into consideration several factors,
including user intent, past workflows, and operator lineage.

Depending on the underlying intent,
users can interact with dataframes
in very different ways.
A user who is performing data cleaning is
likely to issue point queries and focus on regions
with missing or anomalous values; users exploring the
data for building machine learning models tend to focus on manipulating
columns with high mutual information with the target column,
or more broadly on feature engineering.
Taking advantage of user intent can lead to highly effective
materialization and reuse strategies befitting specific access patterns,
such as in machine learning workflows~\cite{xin2018helix}.
The interactive sessions in dataframe development
make it possible for the system to infer and adapt to user intent.

User intent inference involves extensive offline analysis
of workloads with known intents
as well as online processing of relevant telemetry:
recent Jupyter notebook corpora can provide a
promising starting point~\cite{ucsd-dataframe-study}.
One challenge is that
unlike SQL workloads, dataframe queries tend to be interleaved
with non-dataframe operators in the same session,
which requires special considerations to identify
the dataframe portion of the workload and to handle
the interaction between the dataframe system and other frameworks.

Finally,
dataframe queries in a session often
build upon one another.
In the dataflow graph of dataframe queries,
we are likely to see intermediate results
that lie on the path to many leaf nodes.
A simple heuristic is to persist intermediate
results with high fan-outs;
more advanced graph analysis techniques
can be applied to determine prominent intermediate results.
Opportunistic evaluation can significantly complicate
the analysis as the execution order
can differ drastically from the query order.

In terms of costing operators for materialization and reuse,
the dataframe setting introduces two novel challenges.
Partial views to support fast inspection in conjunction
with opportunistic evaluation can break up operators
into multiple partial operators evaluated at different times,
motivating the need for short and long term costs
on partial views for each operator.
The materialization and reuse decisions
derived from these costs can feed back into the decisions
on filtering for partial views or delaying evaluation.
For example, if several queries based on a new sort order
require immediate feedback in the near future,
it might be prudent to incur a delay on the first query
to materialize the new sort order in its entirety,
in order to significantly speed up subsequent queries on the new order through reuse.
Of course, being able to make such decisions
hinges on the ability to predict future reuse as discussed above.
Secondly, the constantly growing dataflow graph
requires eviction of old materialized results from memory.
The interesting challenge in the dataframe context
is that future reuse is determined by both what
the user will do in the future and what the opportunistic evaluator
will choose to compute, with the former being purely speculative
and the latter being known within the system.
We can reconcile the ``two futures'' by passing
the model we build of the future workflow
to the opportunistic scheduler
for unified materialization/reuse planning.

}

}
\moved{

\techreport{
Another approach to speed up dataframe queries
would be to defer the creation of new
dataframes as a result of queries
and instead allow for the results
of dataframe queries to be essentially
non-materialized ``views''.
This could be useful, for example,
when a dataframe query essentially adds
a new derived column for feature engineering.
In this case, we don't actually add the derived
column and create a new dataframe,
simply recording the operations instead,
and materializing the result on-demand.
Deferring the operations also opens up
opportunities for pipelining through subsequent
operations, saving overall computation costs.
In fact, the Vaex project~\cite{vaex},
which is a dataframe-like system (as we described in Section~\ref{sec:dataframedef})
that supports querying on HDF5 files,
implements virtual columns.
With virtual columns,
the column is not actually materialized
until required for output, printing, or for a query.
In cases where the computation
that creates a column is expensive,
virtual columns will
need to be paired with intelligent caching mechanisms
that prioritize caching
columns that were expensive to generate.
}
}

\section{User Model Challenges}\label{sec:interactivity}
\rebuttal{
Unlike in SQL where queries are submitted {\em all-or-nothing},
dataframe users construct queries
in an incremental, iterative,
and interactive fashion.
Queries are submitted as a series of subqueries,
a few operators at a time,
in trial-and-error-based \textit{sessions}.
Users rely on immediate feedback
to debug and rapidly iterate on subqueries
and frequently revisit subquery results
for experimentation and composition
during exploration.
This interactive session-based
programming model for dataframes
creates novel challenges for overall system performance
and imposes additional constraints on query optimization.
For example, operator reordering is often not beneficial
when the results are materialized for viewing after every step (subquery).
At the same time, dataframe query
development sessions are bursty,
with ample think time between issuance of subqueries,
and tolerant of incomplete results as feedback---as long
as the original goals of experimentation and debugging are met,
offering new opportunities for query optimization.
In this section, we discuss new
challenges and opportunities in query optimization
arising from the interactive and incremental
trial-and-error query construction of a typical
dataframe user.
}

\subsection{Interactive Feedback and Control}\label{sec:immediate-feedback}
\rebuttal{
Dataframes are typically used in
exploratory workloads,
where interactive response times
are crucial to providing a fluid user experience.
Past studies have shown that latency
in response times of greater than 500ms can lead
to fewer hypotheses explored and
insights generated during data exploration~\cite{liu2014effects}.
As another example,
for data preparation---often performed on dataframes---users
often rely on system feedback
to guide and decide what operations
to determine their next steps~\cite{Heer2015}.
This feedback usually comes in the form
of a display output by the dataframe system
that contains a prefix or suffix of rows and columns,
as in Figure~\ref{fig:example}.
The need for frequent materialization
of intermediate subquery results
to provide feedback to the user
makes it particularly
difficult to satisfy the 500ms query
latency requirement for interactivity.
Fortunately, we can leverage two
user behavior characteristics to improve
interactivity:
that users spend time thinking between
steps, and that the inspected intermediate
results are typically restricted
to a prefix/suffix of rows/columns---which is sufficient
for debugging
and validation.
We discuss these ideas next.
}

\rebuttal{
\subsubsection{Subquery inspection and think time}
\label{sec:opportunistic-evaluation}
Present-day dataframe systems
are targeted toward ensuring users
can inspect intermediate results, so they often operate
in an {\em eager} mode where every statement is evaluated as
soon as it is issued.
Thus, program control is not returned to the user
until the statement has been completely evaluated,
forcing the user to be idle during the computation.
However, there are many cases where users do not inspect the
results, or where results are discarded. These
statements can potentially be deferred for computation later.
In fact, users can spend a significant amount of time
between analysis steps, allowing us to perform computation
then.
While interactive latency is important
to support immediate feedback, recent
empirical studies have also shown
that optimizations can be relaxed to account
for user's long think time
between operations in exploratory
analysis~\cite{Battle2019}.
We describe a novel \emph{opportunistic} query
evaluation paradigm suitable for optimizing dataframes
in an interactive setting.
}

\moved{
There are two standard modes of query evaluation
in data processing systems:
lazy and eager.
In the eager paradigm, adopted
by current dataframe systems like pandas\xspace,
program control is not returned to the user
until the statement has been completely evaluated,
forcing the user to be idle during the computation.
Query optimization is not possible in an eager
system because each operator within the statement
must be completely evaluated
\rebuttal{in the order that the statement is written
by the user}.
\devin{
For example,
suppose there are two commutative operations \texttt{op1}, and \texttt{op2}. Suppose the user submits the subquery \texttt{x = df.op1()}
followed by \texttt{y = x.op2()}.
In eager evaluation, \code{x} will be fully materialized before
execution begins on \code{y}, even if \code{x} is never used again.
In lazy evaluation, execution will be deferred until
explicitly requested, so the
expression that creates \code{y}
could be optimized to run \texttt{df.op2().op1()}.
}
Thus, a significant amount of computation
is wasted for statements
that are never used or inspected,
and users are either rewarded or punished
based on the efficiency of a query as it is written.

On the other hand, in the lazy paradigm
control is returned to the user immediately,
and the system defers the computation until the user
requests the result.
By scheduling computation later,
the system can wait for larger query sub-expressions to be assembled,
leading to greater opportunities for optimization,
as is done in systems such as
Spark~\cite{Armbrust:2015:SSR:2723372.2742797}.
For example, if the user composes a cross-product
followed by a filter, this filter
can be rewritten to be performed first.
The downside of lazy evaluation is that
computation only begins when the user
requests the result of a query.
This introduces new burdens for users,
particularly for debugging, since bugs are not revealed
until computation is triggered.
Moreover, during the
time a user is thinking or typing, the system
could be working toward a result---however, in
the lazy paradigm, the system is idle during think time,
leading to lost computation.
For smaller datasets or simple queries this can
potentially lead to a longer overall runtime if there are
periods of think time
that exceed the runtime of the statements
in the query.
\techreport{In fact, most users of such systems
 end up requesting the results after each operation,
 essentially defaulting to the eager mode.}

Instead, we propose a middle ground that aims
to preserve the benefits of both lazy and eager evaluation;
a mode we call {\em opportunistic evaluation}, that
we have started to implement in \modin,
which makes the best use of
system resources during user think time.
Like lazy evaluation, opportunistic evaluation
does not require the user to wait after each statement.
Instead, the system opportunistically
starts execution, while passing control back to users
with a pointer to the eventually computed dataframe,
which is asynchronously computed in the background.
In this manner, opportunistic evaluation
makes use of system resources to compute
results in the background as users
are composing the next step of the query.
Like eager evaluation, opportunistic evaluation
does not wait for users to complete the entire
query to begin evaluation.
However, when a user requests to view a certain
output, opportunistic evaluation prioritizes
producing that output over all else.
Opportunistic evaluation allows queries to be rewritten
as new statements are submitted to get to the requested
answer as fast as possible, taking into account
the statements that are partially computed.
There are also new opportunities within opportunistic evaluation
to do speculative query execution,
where during
idle time the system can start
executing statements that commonly follow previous statements.
Opportunistic evaluation also leads to new
challenges in sharing and reuse
across many query fragments whose computation
has been scheduled in the background,
which we will discuss in Section~\ref{sec:trialanderror}.
}

\rebuttal{
\subsubsection{Prefix and suffix inspection.}
\rebuttal{
The most common form of feedback provided by dataframe systems is the tabular
view of the dataframe, as shown in Figure~\ref{fig:example}. The tabular view
serves as a form of visualization that not only allows users to inspect
individual data values, but also convey the structural information associated
with the dataframe. Structural information, especially as it relates to order,
is important for validating the results of queries that manipulate and
reshapes the dataframe or its index.
This tabular visualization typically contains a partial view of the dataframe,
displaying the first and last few lines of the dataframe. During dataframe
query construction, table visualizations are frequently requested via the
\code{head}, \code{tail}, or other print commands, as we saw in
Section~\ref{sec:usecase}.
}

One way to give the
users immediate feedback
is to return
the output to the user as soon as these $k$
rows are assembled, computing the rest of the output
in the background using opportunistic evaluation.
This is reminiscent of techniques that
optimize for early
results~\cite{viglas2003maximizing,viglas2002rate}
for \code{LIMIT} queries~\cite{kim2018optimally},
or
for representative tuple identification~\cite{singh2012skimmer},
but a key difference in dataframes is that order
must be preserved, and there are many more blocking operators.
Therefore, techniques that try to find
samples anywhere in the data that match query predicates
as in Kim et al.~\cite{kim2018optimally},
will not apply.
One starting point would be to design or select physical operator implementations that not just prioritize high output
rate~\cite{viglas2002rate},
but also preserve order, thereby ensuring
that the first $k$ rows will be produced as quickly as possible.
As an example, if only the first $k$ rows
of an ordered join were to be computed,
a nested loop join, with the result displayed
after $k$ rows are computed, might work well.
Returning the first $k$ rows following a
\code{TRANSPOSE}, especially when using columnar storage,
can be fairly efficient as well.

However, certain blocking operators will cause problems.
For example, it is hard to produce the first $k$ tuples
of a \code{GROUP BY} or \code{SORT}
without examining the entire data first.
\techreport{(Indeed,
for small enough $k$, sorting may be faster
than $O(n \log{n})$, but still requires an $O(n)$ sequential scan.)}
Optimizers in RDBMSs draw upon techniques such as predicate pushdown to reduce the amount of data processed for a query.
Unfortunately, due to the order requirement in dataframes, predicate pushdown is often not directly applicable to prefix/suffix computation.
\code{SORT} is an obvious example where the top $k$ rows cannot be narrowed down a priori; a full scan is inevitable also for \code{GROUPBY} on non-clustered columns.
Since the top and bottom $k$ rows are often the only results inspected for a dataframe query, maintaining additional intermediate results and data structures for these regions \`{a} la incremental view maintenance can significantly speed up query processing without exorbitant storage overhead. What these data structures are and how to maintenance them in the ordered setting present interesting research opportunities.
We may also be able to exploit approximation
to produce
the prefix/suffix early for these blocking operators, discussed next.
}

\moved{
\rebuttal{\agp{This entire subsection seems very generic.
What is new here? One thing that is new is the interaction
with order, allowing us to prioritize samples
targeted towards order. Others?}
\devin{Propose TR next paragraph}
Another way to provide immediate feedback is to take advantage of approximate query processing (AQP) techniques to quickly display inexact
results at significantly reduced latencies. AQP is suitable for interactive query composition since users often do not require exact results when simply inspecting results for debugging or exploratory purposes.}
Traditional AQP has been applied to accelerate
the generation of specific aggregates, e.g.,
\code{SUM} or \code{AVG}, and bound
their estimates with confidence
intervals~\cite{zeng2014analytical,park2018verdictdb}.
AQP is performed either offline, or online,
where the former involves maintenance of materialized
stratified samples, with some
sample selection happening
online~\cite{ding2016sample+,agarwal2013blinkdb,park2018verdictdb},
and the latter involves sampling on-the-fly with no
pre-materialization decisions.
Due to the highly ad-hoc nature of dataframe processing,
we expect online sampling to be more effective.
Specifically, online aggregation-type schemes~\cite{hellerstein1997online}
can be used to produce
progressively improving
aggregates to the
user~\cite{hellerstein1997online,rahman2017ve,Fekete2018}---and
these schemes will work well in the context
of opportunistic evaluation, as discussed in
Section~\ref{sec:opportunistic-evaluation},
but we expect the dataframe model and algebra to introduce
new challenges.
Recent work has also introduced
the notion of guarantees
across collections of aggregates,
often optimizing for user tasks or
perceptual
guarantees \rebuttal{for visualizations}~\cite{kim2015rapid,park2016visualization,macke2018adaptive,alabi2016pfunk},
e.g., ensuring that the
ordering of the aggregates
matches the correct ordering,
even if the values of the aggregates are
inexact,
and these techniques
may be a good fit to the dataframe setting.
}

\techreport{
\moved{
While it is well known that some aggregates like \code{MAX}
cannot be approximated~\cite{mozafari2015handbook},
even blocking operators such as \code{SORT} can return
early approximate results, using results
from the 1990s~\cite{raman1999online}.
There may be additional opportunities for approximation
if the user simply wants to inspect the approximate
structure of the result for debugging purposes,
especially in conjunction with prefix/suffix computation.
For example, we can provide the
overall structure of the output of
a pivot table computation
(displaying the row-wise groups and column headers),
without actually filling
in any of the aggregate values, and doing so
progressively.
Similar ideas of adding ``placeholder'' values
for in-progress tuples have been proposed in
streaming~\cite{raman2002partial}, web-database
hybrid~\cite{goldman2000wsq},
and crowdsourcing~\cite{parameswaran2012deco} contexts,
but not, as far as we can tell, for a group-by aggregation setting.
This idea could also be applied,
for example, to \code{TRANSPOSE},
where the structure of the
output dataframe is prepared first, with
the values filled in progressively.
}
\moved{
Other notions of approximation may also be valuable,
e.g., the incomplete/phantom notions in Lang et al.~\cite{lang2014partial},
wherein the result may contain additional rows
not present in the dataframe query result,
or rows that should be present, but are absent.
This could be valuable, for example, for expensive filters.

In fact, we could also exploit correlations~\cite{joglekar2015exploiting}
between the filtering attribute
and the other attributes in order to quickly approximate
the rows that might pass the filter and
quickly display them to the user, refining as
additional filter evaluations are performed.
}
}

\input{incremetal_query_construction}

\section{User Model Challenges}\label{sec:interactivity}

\rebuttal{
Unlike in SQL where queries are submitted {\em all-or-nothing},
dataframe users construct queries
in an incremental, iterative,
and interactive fashion.
Queries are submitted as a series of {\em \stmts} (as we saw in Figure~\ref{fig:example}),
a few operators at a time,
in trial-and-error-based \textit{sessions}.
Users rely on immediate feedback
to debug and rapidly iterate on these \stmts
and frequently revisit results of intermediate \stmts
for experimentation and composition
during exploration.
This interactive session-based
programming model for dataframes
creates novel challenges for overall system performance
and imposes additional constraints on query optimization.
For example, operator reordering is often not beneficial
when the results are materialized for viewing after every \stmt.
At the same time, dataframe query
development sessions are bursty,
with ample think time between issuance of \stmts,
and tolerant of incomplete results as feedback---as long
as the original goals of experimentation and debugging are met,
offering new opportunities for query optimization.
In this section, we discuss new
challenges and opportunities in query optimization
arising from the interactive and incremental
trial-and-error query construction of a typical
 user.
}

\subsection{Interactive Feedback and Control}\label{sec:immediate-feedback}
\rebuttal{
Dataframes are typically used in
exploratory workloads,
where interactive response times
are crucial to providing a fluid user experience.
Past studies have shown that latency
in response times of greater than 500ms can lead
to fewer hypotheses explored and
insights generated during data exploration~\cite{liu2014effects}.
As another example,
for data preparation---often performed on dataframes---users
often rely on system feedback
to guide and decide what operations
to determine their next steps~\cite{Heer2015}.
This feedback usually comes in the form
of a display output by the dataframe system
that contains a prefix or suffix of rows and columns,
as in Figure~\ref{fig:example}.
The need for frequent materialization
of intermediate results of \stmts
to provide feedback to the user
makes it particularly
difficult to satisfy the 500ms query
latency requirement for interactivity.
Fortunately, we can leverage two
user behavior characteristics to improve
interactivity:
that users spend time thinking between
steps, and that the inspected intermediate
results are typically restricted
to a prefix/suffix of rows/columns is sufficient
for debugging
and validation.}

\rebuttal{
\subsubsection{Intermediate Result Inspection \& Think Time}
\label{sec:opportunistic-evaluation}
Present-day dataframe systems such as pandas\xspace
are targeted toward ensuring users
can inspect intermediate results for debugging and validation,
so they operate
in an {\em eager} mode where every \stmt is evaluated as
soon as it is issued.
Program control is not returned to the user
until the \stmt has been completely evaluated,
forcing the user to be idle during that time.
However, there are many cases where users do not inspect the
intermediate results, or where results are discarded;
in such cases, the user is still forced to wait for each \stmt to
be evaluated.
Moreover, users are either rewarded or punished
based on the efficiency of a query as it is written.

On the other hand, with the {\em lazy} mode of evaluation,
\rebuttal{which is adopted by some dataframe-like}
systems~\cite{dask, Armbrust:2015:SSR:2723372.2742797} (See Section~\ref{sec:ext}),
control is returned to the user immediately,
and the system defers the computation until the user
requests the result.
By scheduling computation later,
the system can wait for larger query sub-expressions to be assembled,
leading to greater opportunities for optimization.
The downside of lazy evaluation is that
computation only begins when the user
requests the result of a query.
This introduces new burdens for users,
particularly for debugging, since bugs are not revealed
until computation is triggered.

For example,
consider two commutative operations \texttt{op1}, and \texttt{op2}.
Say the user submits the \stmt \texttt{x = df.op1()}
followed by \texttt{y = x.op2()}.
In eager evaluation, \code{x} will be fully materialized before
execution begins on \code{y}, even if \code{x} is never used again.
Computing \code{y} could be done using
\texttt{df.op2().op1()}, but it is often more beneficial
to use the materialized version of \code{x} instead.
In lazy evaluation, execution will be deferred until
explicitly requested, so the
expression that creates \code{y}
could be optimized to run \texttt{df.op2().op1()}.
The downside of this approach is that the user has to wait
until they explicitly request \code{y} before
they realize that there is a potential bug in \code{x}.

Furthermore, neither the lazy nor the eager mode
take advantage of the fact that the users
spend time thinking between steps:
the system is idle during think-time.
We can can leverage this time for computation,
allowing us to effectively achieve the benefits
of both paradigms.
While interactive latency is important
to support immediate feedback, recent
empirical studies have also shown
that optimizations can be relaxed to account
for user's long think time
between operations in exploratory
analysis~\cite{Battle2019}.
We describe a novel \emph{opportunistic} query
evaluation paradigm suitable for optimizing dataframes
in an interactive setting.
}

\moved{
Like lazy evaluation, opportunistic evaluation
does not require the user to wait after each statement.
Instead, the system opportunistically
starts execution, while passing control back to users
with a pointer to the eventually computed dataframe (a ''future''),
which is asynchronously computed in the background.
We can then use system resources to compute
results in the background as users
are composing the next step.
Like eager evaluation, opportunistic evaluation
does not wait for users to complete the entire
query to begin evaluation.
However, when a user requests to view a certain
output, opportunistic evaluation can prioritize
producing that output over all else.
Opportunistic evaluation allows queries to be rewritten
as new \stmts are submitted \rebuttal{(e.g., \texttt{df.op2().op1()})}
to get to the requested
answer as fast as possible, taking into account
what is partially computed.
There are also new opportunities within opportunistic evaluation
to do speculation,
where during
idle time the system can start
executing \stmts that commonly follow previous ones.
Opportunistic evaluation also leads to new
challenges in sharing and reuse
across many query fragments whose computation
has been scheduled in the background (see also
 Section~\ref{sec:trialanderror}).
}

\rebuttal{
\subsubsection{Prefix and Suffix Inspection}\label{sec:prefix}
\rebuttal{
The most common form of feedback provided
by dataframe systems is the tabular
view of the dataframe, as shown in Figure~\ref{fig:example}.
The tabular view
serves as a form of visualization
that not only allows users to inspect
individual data values,
but also convey the structural information associated
with the dataframe.
Structural information, especially as it relates to order,
is important for validating the
results of queries that manipulate and
reshapes the dataframe.
This tabular visualization typically
contains a partial view of the dataframe,
displaying the first and last few rows of the dataframe,
accessed using \code{head}, \code{tail}, or other print commands.
}

One way to give the
users immediate feedback
is to return
the output to the user as soon as these $k$
rows are assembled, computing the rest of the output
in the background using opportunistic evaluation.
This is reminiscent of techniques that
optimize for early
results~\cite{viglas2003maximizing,viglas2002rate}
for \code{LIMIT} queries~\cite{kim2018optimally},
or
for representative tuple identification~\cite{singh2012skimmer},
but a key difference in dataframes is that order
must be preserved (so "any-k" result tuples will not suffice~\cite{kim2018optimally}),
and there are many more blocking operators.
One starting point would be to design or select physical operator
implementations that not just prioritize high output
rate~\cite{viglas2002rate},
but also preserve order, thereby ensuring
that the first $k$ rows will be produced as quickly as possible.
As an example, if only the first $k$ rows
of an ordered join were to be computed,
a nested loop join, with the result displayed
after $k$ rows are computed, might work well.
We can progressively process more portions of the
input dataframes until $k$ output rows are produced
in order: this may mean processing more than $k$ rows
of the inputs if there are very selective predicates.
Figuring out the right way to exploit parallelism
to prioritize processing the prefixes
of the ordered input dataframes
to produce the ordered prefix of the output is likely
to be a substantial challenge.

Additionally, certain blocking operators will cause problems.
While returning the first $k$ rows following a
\code{TRANSPOSE}, especially when using columnar storage,
can be fairly efficient,
it may be hard to produce the first $k$ tuples
of a \code{GROUP BY} or \code{SORT}
without examining the entire data first.
\techreport{(Indeed,
for small enough $k$, sorting may be faster
than $O(n \log{n})$, but still requires an $O(n)$ sequential scan.)}
\code{SORT} is an obvious example where the top $k$ rows cannot be narrowed down a priori;
a full scan is inevitable also for \code{GROUPBY} on non-clustered columns.
That said,
since the top and bottom $k$ rows are often the only results
inspected for dataframe queries,
we may benefit from materializing additional intermediate results
or supporting indexes to retrieve them efficiently, without exorbitant
storage overhead.
We could, for example, materialize the prefix and suffix
of a dataframe in original and transposed orientations,
or the prefix or suffix of the dataframe sorted by various
columns to allow for efficient processing subsequently.
These materializations could happen during think-time
as discussed in Section~\ref{sec:opportunistic-evaluation}.
We may also be able to exploit approximate query processing
to produce
the prefix/suffix early for blocking
operators~\cite{ding2016sample+,agarwal2013blinkdb,park2018verdictdb,hellerstein1997online,zeng2014analytical}.
Since the tabular view is only a special form of visualization,
a rich body of related work from visualization on
how to allow users to quickly but approximately make decisions or perform debugging or validation,
may be applicable~\cite{kim2015rapid,park2016visualization,macke2018adaptive,alabi2016pfunk};
however, the rich space of operators that goes beyond simple \code{GROUPBY} aggregation
will lead to new challenges.
Another interesting usability-oriented
challenge is whether this tabular
view of prefixes or suffixes
is indeed best for debugging---perhaps highlighting
possible erroneous values or outliers
in dataframe rows or columns that are not in the prefix
or suffix may also be valuable~\cite{Raman2001}.

}

\techreport{
\moved{
While it is well known that some aggregates like \code{MAX}
cannot be approximated~\cite{mozafari2015handbook},
even blocking operators such as \code{SORT} can return
early approximate results, using results
from the 1990s~\cite{raman1999online}.
There may be additional opportunities for approximation
if the user simply wants to inspect the approximate
structure of the result for debugging purposes,
especially in conjunction with prefix/suffix computation.
For example, we can provide the
overall structure of the output of
a pivot table computation
(displaying the row-wise groups and column headers),
without actually filling
in any of the aggregate values, and doing so
progressively.
Similar ideas of adding ``placeholder'' values
for in-progress tuples have been proposed in
streaming~\cite{raman2002partial}, web-database
hybrid~\cite{goldman2000wsq},
and crowdsourcing~\cite{parameswaran2012deco} contexts,
but not, as far as we can tell, for a group-by aggregation setting.
This idea could also be applied,
for example, to \code{TRANSPOSE},
where the structure of the
output dataframe is prepared first, with
the values filled in progressively.
}
\moved{
Other notions of approximation may also be valuable,
e.g., the incomplete/phantom notions in Lang et al.~\cite{lang2014partial},
wherein the result may contain additional rows
not present in the dataframe query result,
or rows that should be present, but are absent.
This could be valuable, for example, for expensive filters.

In fact, we could also exploit correlations~\cite{joglekar2015exploiting}
between the filtering attribute
and the other attributes in order to quickly approximate
the rows that might pass the filter and
quickly display them to the user, refining as
additional filter evaluations are performed.
}
}

\input{incremetal_query_construction}

\section{Optimizing for Interactivity~\label{sec:interactivity}}

With dataframes,
users tend to build their queries incrementally, where multiple
statements compose a larger overall query.
These queries are typically
built in a trial-and-error approach with sub-queries that are
reused multiple times.
Interactivity, defined by quick feedback, is highly desirable with this style of development.
To optimize for dataframe interactivity, we are required to consider two properties that are not typical in the traditional database use case:
(i) users are more amenable to partial and approximate feedback
(ii) a larger portion of the optimization opportunities exist across multiple queries.
We identify research opportunities associated with each of these properties in the rest of the section.
\devin{Mention skinner and citations of that paper}

\subsection{Evaluation Paradigms}
\smacke{AGP: merge this with 6.2?}

In the \stitle{Eager Computation} paradigm,
users are forced to wait for computation to complete
after each statement they enter.
In this case, the CPU is idle as the users are thinking and typing their query.

\stitle{Lazy Evaluation} has emerged as a popular
method to bring traditional query optimization (planning and rewriting)
techniques to interactive systems~\cite{dask, Armbrust:2015:SSR:2723372.2742797}. However, this approach of delaying computation until results are explicitly requested introduces new burdens for users, particularly when they are debugging, since bugs are not revealed
until computation is triggered. Lazy evaluation can result in wasted
time where the system could be working toward a result while
the user is thinking or typing, but instead waits for the
user to trigger computation. As a result, interactive users often end up manually triggering computation, overriding the system
and limiting the amount of query optimization that could be done.

To address latency issues with the incremental, interactive construction of queries one statement at a time, \stitle{Asynchronous Evaluation} performs computation during user think time.

In an attempt to find a middle ground between these eager and lazy evaluation paradigms,
we developed \modin with an asynchronous computation
scheme that balances between the idle time of
the user and the available system resources.
Instead of making users wait for code to
execute after every statement,
\modin passes control back to the user immediately with a
pointer to the eventual computed dataframe.
Passing back control immediately is an improvement over an eager computation scheme
as users do not have to wait for their code to execute to
continue developing their query.
Furthermore, asynchronous computation is able to improve over
lazy computation
by transparently computing the results immediately after execution,
rather than waiting for the user to request computation.
Although this comes at a cost of being able to find an optimal
query plan for the user's query,
we can leverage prior work in the database community
on incremental query optimization and update
the query plan as new statements are submitted.

\subsection{Immediate Feedback}

Providing immediate feedback is an important interactivity feature that would improve the
usability of dataframes. While it is important to aim for preserving the semantics of
the dataframe, it may be possible to get significantly better performance by sacrificing a bit of the semantics to
gain performance.

In this section we discuss two examples of optimizations common in databases that
can be integrated into \modin to optimize for providing immediate feedback to the user,
and the challenges therein: Prefix/Suffix Computation and Approximation.

\subsubsection{Prefix/Suffix Computation}
As illustrated in Section~\ref{sec:usecase}, building queries incrementally through trial-and-error typically involves printing some subset
of the rows and columns through the
\code{head}, \code{tail}, or \code{print} operations.
The \code{head} and \code{tail} commands print the first
or last $k$ rows (5 by default), respectively.
Printing a dataframe, also,
shows both the first and last $k$ rows.
This is also another case where the user relies heavily on the
order of the data in their mental model. When a user prints
the first $k$ rows, they expect to see the first
$k$ rows ingested,
and they expect that the system will print the same
$k$ rows each time. The performance of displaying these first and last
$k$ rows is important as users rely on these operations to verify the correctness of their data and query and subsequently make decisions about what to do next.

While it is possible to use strategies similar to those that optimize for the \code{LIMIT} clause in RDBMSs \cite{kim2018optimally}, additional
consideration must be made for the \code{ORDER BY} clause to ensure that the order is the same every time.
However, this approach limits interactivity, or the time to reach a partial result,
for increased query performance, or the time to reach the final result,
and increased accuracy as it will be always correct.
At the opposite end of the spectrum,
we can avoid the \code{ORDER BY} on every computation
by logically removing the first and last $k$ rows to be
separate tables and performing computation on those results
to get much better interactivity, as the time to reach a partial result decreases significantly.
Clearly, this will reduce query performance, as it will take longer to reach the final result.
Additionally, this will also reduce the accuracy.
For instance, when calculating \code{GROUP BY} on the first or last $k$ rows
will return a result that is significantly different than
calculating \code{GROUP BY} on the entire dataframe and taking the first or last $k$ rows.
Furthermore, \code{TRANSPOSE}s will be significantly harder with the first and last $k$ rows
logically separated.
Thus, this introduces an interesting line of work
as we can explore the trade-offs between
interactivity, query performance, and accuracy.

\subsubsection{Approximation}
Approximate computation is another way to provide users with faster query responses to facilitate interactive workflows. In some cases, the user may be content with an approximation
rather than waiting for the full result. Existing RDBMS approximation
techniques for online aggregation~\cite{Fekete2018,raman2002partial,lang2014partial,viglas2002rate,rahman2017ve},
barchart, histogram, scatterplot, and map plot generation~\cite{kim2015rapid,ding2016sample+,park2016visualization},
histogram matching~\cite{macke2018adaptive}, stratified sampling~\cite{agarwal2013blinkdb}, and
error estimation~\cite{zeng2014analytical,park2018verdictdb} are directly applicable
toward accelerating individual dataframe operations.
However, dataframe semantics
offer some unique opportunities for further speedups via approximation.

\william{These subsubsections feel like they are just listing a lot of cool things you can do with dataframes from AQP but do not give a research problem. There is also a lot of prefix/suffix computation stuff listed here. The query rewriting section does a good job of giving the research problem.}

\stitle{Cumulative Aggregates.}
The ordering of rows in a dataframe can create bottlenecks when the
computation required to display the bottom $k$ rows depends on the
result of the computation for all previous rows. For example,
a cumulative sum or cumulative max must be done in order from the
top of the dataframe to the bottom, causing significant latency
before the bottom $k$ rows can be displayed.

While it is well known that an aggregate like \texttt{MAX}
cannot be approximated~\cite{mozafari2015handbook},
the user may be satisfied to see approximations of cumulative sums or means
in the bottom $k$ rows that
either update progressively as more data is processed, or satisfy a
probabilistic accuracy requirement.

\stitle{Estimating Counts on Filtered Dataframes.}
Dataframe libraries
like pandas\xspace typically show summary statistics like \texttt{COUNT}
after each operation.
If a user applies a filter on a dataframe, without prior knowledge
it is impossible to know the exact number of rows passing the filter
until the full computation has completed. One strategy is to
automatically identify such cases and adaptively estimate the
selectivity of the filter on-the-fly, again progressively updating the estimate as more tuples passes through the filter.

\stitle{Approximating Expensive Filters.}
For a filter that is both selective and expensive
(e.g., one that performs classification on
a dataframe where one of the columns contains large objects), there might not be any row in the top or bottom
$k$ that satisfies the filter. As such, determining the top and bottom
$k$ rows that pass the filter can itself be a high-latency
operation, even without a complete filter application.
In this case, dataframes present a perfect use case for
{\em exploiting correlations}~\cite{joglekar2015exploiting}
between the filtering attribute
and the other attributes in order to quickly approximate
the top and bottom $k$ rows that might pass the filter and
quickly display them to the user, refining as
additional filter evaluations are performed.

\stitle{Approximation and Asynchrony.}
When used in conjunction with \modin's
inherent asynchronous background execution,
exact results may be scheduled in the background for
later verification (as in~\cite{moritz2017trust}).
This may result in many exact queries getting queued in the
background as the user rapidly issues statements and achieves
immediate approximate feedback. To increase throughput of
these statements that build up in the execution queue,
we can apply {\em multiquery optimization techniques}
and to take advantage of opportunities for shared computation,
to be described in detail in Section~\ref{sec:mqo}.

\subsection{Multiquery Optimization} \label{sec:mqo}
We envision that \modin will prioritize interactivity, returning
control to the user as quickly as possible by displaying
preview (head/tail) or
approximate results and defer calculation of full or exact results to background computation using techniques from Section\label{sec:singlestatement}.
As such, many operations may be queued for execution at once. These statements may
operate over similar or even identical subsets of data.
To exploit this workload, \modin can make use of multiquery optimization (MQO) techniques~\cite{sellis1988multiple}
to allow operations that share significant amounts of data to run underneath the
same scans or seeks, thereby reducing the overhead required to funnel data up
through the memory hierarchy. However, MQO presents a significant challenge when employed
in an interactive environment,
where the results of the operation is displayed in-situ the coding/input environment,
such as a Jupyter notebook cell. In this case, the optimizer will have to balance
between maximizing operation throughput and
minimizing the latency required to compute output of the important ``to-be-displayed'' operations.

\subsubsection{Query Rewriting}
Current approaches to planning queries for dataframes are either
(i) strictly imperative and do not perform any
query planning~\cite{mckinney2010data, R, dask}
or (ii) declarative but do not support operations
beyond the traditional relational table operations~\cite{Armbrust:2015:SSR:2723372.2742797}.
As an example of query rewriting, consider the \code{TRANSPOSE} operation, which in some cases can be avoided using clever rewrite rules. For example, the query \code{TRANSPOSE}, \code{SORT}, \code{TRANSPOSE} to reorder columns can be
rewritten as a \code{MAP} and \code{RENAME}.

\eat{Because it is not feasible
to physically do the \code{TRANSPOSE} in most RDBMSs, the rewrite
rules for these systems will have to work around this architectural limitation.
Developing rewrite rules for relational systems
in the context of the \code{TRANSPOSE} operator will produce some
interesting research on how to support dataframe operators in
relational systems.}
The challenge of supporting declarative query processing across a wide range of dataframe operators is that
the cost of extending rewrite rules beyond relational operations,
to support spreadsheet and linear algebra operations, requires a significant development effort.
As a result, dataframe users either have to sacrifice performance,
operate on a feasible subset of their data,
or manually construct and profile various possible rewrite to determine the optimal approach to execute the query~\cite{optimizing-pandas}.
When creating rewrite rules for dataframes, we have to consider (i) how to group the dataframe operations into queries and (ii) when to rewrite the queries.
Manual query optimization on the part of the developer can be a daunting task due to the large number of possible ways to perform an operation~\cite{wu2019diel}.
In addition to the numerous ways of writing any given query at the API level,
the problem is further exacerbated by the fact that
there is a large and diverse set of operations beyond relational operators to consider when creating rewrite rules. \eat{An important area of future
work in \modin will be in defining rewrite rules to efficiently
handle cases that traditional systems cannot.}

In addition to the large query space to cover with rewrite rules,
we still have to consider when the query rewriting will occur.
Traditional databases operate in a declarative environment.
As a result, it is obvious that the query rewriting occurs
once the query is submitted.
However, there is no clear cut line to even differentiate separate queries for dataframes because most existing dataframe frameworks are imperative and execute operations eagerly.

\subsubsection{Materialization and Reuse}
\smacke{JMH: the distinguishing factor here vs materialization in a traditional
RDBMS setting is that we might reuse an intermediate result an unknown number of
multiple times, and we can do fancy things like predict what we think the user
will use again.}
The incremental and exploratory nature of dataframe query construction
leads to nonlinear code paths
where users revisit the same intermediate results repeatedly
to refine the query results.
We envision the \modin optimizer can automatically materialize and reuse intermediate results
to significantly reduce execution time by removing redundant computation across statements.

The objective of this optimization problem is to trade the
\textit{materialization overhead}, including both the storage and the time to persist the results,
for the \textit{reduced execution time} due to reuse.
There are two components to this optimization.
First, we need to identify reusable intermediate results,
which can be accomplished using standard program analysis.
Then, we need to decide whether an intermediate result should be stored and reused,
and the optimizer needs to utilize storage in a way that maximizes
saved compute---small
objects that are time-consuming to compute and reused frequently
should be prioritized over large objects that are fast to compute.
A storage budget is often imposed, especially in the single-session case, making the problem NP-Hard (by reduction from the Knapsack problem).
Effective solutions need to adapt to variable reuse patterns.

\section{Introduction}

For all of their commercial successes,
relational databases have notable limitations
when it comes to
``quick-and-dirty'' exploratory data analysis
(EDA)~\cite{tukey1977exploratory}. Data needs to be
defined schema-first before it can be
examined,
data that is not well-structured is
difficult to query,
and any query beyond
\code{SELECT *}
requires an intimate
familiarity with the schema, which is particularly problematic for wide tables.
For more complex analyses, the
declarative nature of SQL makes it
awkward to develop and debug queries in a piecewise, modular
fashion, conflicting with best practices for software development.
\rebuttal{In part, thanks to these limitations, SQL is
often not the tool of choice for data exploration.
As an alternative,}
programming languages such as Python and R support
the so-called {\em data\-frame}
abstraction. Dataframes provide a functional interface
that is more tolerant
of unknown data structure and well-suited
to developer and data scientist workflows,
including REPL-style imperative interfaces
and data science notebooks~\cite{perez2015project}.

Dataframes have
several characteristics
that make them an appealing
choice for data exploration:

\squishlist
\item a more
intuitive data model that
embraces an implicit ordering on both rows
and columns and treats them symmetrically;
\item a query
language that bridges a variety of data
analysis modalities including
relational (e.g., filter, join),
linear algebra (e.g., transpose),
and spreadsheet-like (e.g., pivot) operators;
\item an incrementally composable query
syntax that encourages easy and rapid validation
of simple expressions,
and their iterative refinement and composition
into complex queries; and
\item native embedding in a
host language such as Python
with familiar imperative semantics.
\end{list}

\noindent
Characteristics such as these
have helped dataframes become
incredibly popular for EDA;
for instance,
the dataframe abstraction provided by pandas\xspace
within Python (\url{pandas.pydata.org}),
has, as of 2020, been downloaded
over 300 million times, served as a dependency for
over 222,000 repositories in GitHub,
and starred on GitHub more 25,000 times.
Python's own popularity
has been
attributed to the success of pandas\xspace
for data exploration and data science~\cite{python-growing-quickly,python-growth-blamed}.
Due to its ubiquity, we focus on pandas\xspace for concreteness.

Pandas\xspace
has been developed from the ground up
\rebuttal{via open-source contributions
from dozens of contributors,
each providing operators and
their implementations to the DataFrame API}
to satisfy immediate or ad-hoc needs,
spanning capabilities
that mimic
relational algebra,
linear algebra, and
spreadsheet formula computation.
To date,
the pandas\xspace DataFrame API has ballooned to
over 200 distinct operators~\cite{pandas-api}.
R, which is
both more mature and more carefully curated
than pandas\xspace, has only 70 operators---but this
is still far more than, say, relational
and linear algebra combined~\cite{R-dataframe-api}.

While this rich API is sometimes cited as a
reason for pandas\xspace' attractiveness,
the set of operators has significant redundancies,
often with different performance implications.
These redundancies place a considerable burden
on users to select the optimal way of expressing their goal.
For example, one blog post cites five different ways to express
the same goal, with performance varying from 0.3ms to 600ms
(a 1700$\times$ increase)~\cite{optimizing-pandas};
meanwhile, the pandas\xspace documentation itself offers multiple recommendations
for how to enhance performance~\cite{enhancing-performance}.
As a result, many users eschew the bulk of the API,
relying only on a small
subset of operators~\cite{minimally-sufficient}.
The complexity of the API and evaluation semantics
also make it difficult to apply
traditional query optimization techniques.
Indeed, each operator within a pandas\xspace ``query plan''
is executed completely before subsequent operators are executed,
with limited optimization, and
no reordering of operators or pipelining
(unless explicitly done so by the user using \code{.pipe}).
Moreover, the performance of the \code{pandas.DataFrame} API
breaks down when processing
even moderate volumes
of data that do not fit in memory, as we will see
subsequently---this is especially problematic
due to pandas\xspace' eager evaluation semantics, wherein
intermediate data items often surpass main memory limits
and must be paged to disk.

\rebuttal{
To address pandas\xspace' scalability challenges,
we developed \modin (\url{github.com/modin-project/modin}),
our first attempt at a scalable dataframe system,
which employs simple optimization techniques to
enable unmodified pandas\xspace code
to run more efficiently on large dataframes.
\modin is already used by over 60 downstream projects, and
has over 250 forks and 4,800 stars on GitHub
in its first 20 months, indicating
the impact and need for such systems.
\modin rewrites pandas\xspace API calls
into a sequence
of operators in a new, compact
dataframe algebra.
\modin then leverages simple
parallelization and a new physical
representation
to speed up the
execution of these operators,
by up to {\bf 30$\times$} in certain
cases, and is able to run to completion
on datasets {\bf 25$\times$} larger
than pandas\xspace (which crashes instead)
in others.
}

\rebuttal{However, \modin only represents
our first step towards making dataframe systems
scalable and efficient;
we have an entire
research agenda full of novel research challenges
ahead of us.
In this paper,
we begin with an example dataframe workflow
capturing typical
dataframe capabilities and user behaviors.
We then
describe our experiences with \modin
(Section~\ref{sec:modin}).
We use \modin to ground our discussion of
the research challenges.
We {\bf \em (i)
provide a candidate formalism for
dataframes} and enumerate their capabilities with a new algebra
(Section~\ref{sec:definitions}).
We then outline research challenges and
opportunities
 {\bf \em to build on our formalism
and make dataframe systems more scalable,}
by optimizing
and accounting
for
{\bf \em (ii) the unique characteristics
of the new data model and algebra} (Section~\ref{sec:datamodel}),
as well as {\bf \em (iii)
the unique ways in which dataframes are used
in practice for data exploration} (Section~\ref{sec:interactivity}).
We draw on tools
and techniques from the database research literature throughout
and discuss how they might be adapted
to meet novel dataframe needs.
}

\rebuttal{While developing \modin, our original intent
was to adapt standard relational database techniques
to help make dataframes scalable.
However, while the principles (such as parallelism)
do apply, their instantiation in the form of specific
techniques often differ,
thanks to the differences between
the data models and algebra of dataframes and relations.
Therefore, a more principled
foundation for dataframes is needed,
comprising a formal data model
and an elegant, expressive, and compact algebra.
We describe our first attempt
at such a formalization in Section~\ref{sec:definitions}.
Then, armed with our data model
and algebra,
we outline a number of outstanding
research challenges organized around
the unique characteristics of
dataframes and the unique ways in which they are processed.
}

\rebuttal{In Section~\ref{sec:datamodel},
we describe how the dataframe data model and algebra
result in new scalability challenges.
Unlike relations, dataframes
have a flexible schema and are lazily typed,
requiring careful maintenance of metadata,
and avoiding the overhead of type inference as
far as possible.
Moreover, dataframes treat rows and columns
as equivalent, and metadata (e.g., column or row labels) and data
as equivalent, requiring flexible ways
to keep track of metadata and orientation,
placing new metadata awareness
requirements on dataframe query planners in
order to avoid physically transposing data where possible.
Moreover, dataframes are ordered---and common implementations
often enforce a strict coupling between logical and physical
layout; we identify several opportunities to deal
with order in a more light-weight, decoupled, and lazy fashion.
Finally, the new space of operators---encompassing
relational, linear algebra, and spreadsheet operators---introduces
new challenges in query processing and optimization.
}

\rebuttal{In Section~\ref{sec:interactivity},
we describe new challenges and opportunities
that emerge from how dataframes are used
for data exploration.
Specifically, unlike SQL which
offers an all-or-nothing query modality,
dataframe
queries are often
constructed one operator
at a time, with ample think-time between query fragments.
This makes it more challenging to perform query optimization
wherein operators can be reordered for higher overall efficiency.
At the same time, the additional thinking time between steps
can be exploited to do background processing.
Users often inspect intermediate dataframe results of query fragments, usually
for debugging, which requires a costly materialization
after each step of query processing.
However, users are only shown an ordered
prefix or suffix of this intermediate
dataframe as part of the output, allowing
us to prioritize the execution to return
this portion quickly and defer the execution
of the rest.
Finally, users often revisit old processing steps in
an ad-hoc process of trial-and-error data exploration.
We discuss opportunities to minimize redundant computation
for operations completed previously.
}

\vspace{5pt}
\noindent
In describing the aforementioned challenges, we focus on the pandas\xspace dataframe system~\cite{pandas-api}
for concreteness.
Pandas\xspace is much more popular than other dataframe
implementations,
and is therefore well worth our effort to study and optimize.
We discuss other dataframe
implementations and related work in Section~\ref{sec:ext}.
\rebuttal{Many details about \modin as well
as our dataframe data model and algebra are
omitted due to space limitations
and can be found in our technical report~\cite{petersohn2020towards}.}
We begin our paper with a specific dataframe workflow that will serve
as a running example for the paper.

\section{Introduction}\label{sec:intro}

For all of their commercial successes,
relational databases have notable limitations
when it comes to
``quick-and-dirty'' exploratory data analysis
(EDA)~\cite{tukey1977exploratory}. Data needs to be
defined schema-first before it can be
examined,
data that is not well-structured is
difficult to query,
and any query beyond
\code{SELECT *}
requires an intimate
familiarity with the schema, which is particularly problematic for wide tables.
For more complex analyses, the
declarative nature of SQL makes it
awkward to develop and debug queries in a piecewise, modular
fashion, conflicting with best practices for software development.
\rebuttal{In part thanks to these limitations, SQL is
often not the tool of choice for data exploration.
As an alternative,}
programming languages such as Python and R support
the so-called {\em data\-frame}
abstraction. Dataframes provide a functional interface
that is more tolerant
of unknown data structure and well-suited
to developer and data scientist workflows,
including REPL-style imperative interfaces
and data science notebooks~\cite{perez2015project}.

Dataframes have
several characteristics
that make them an appealing
choice for data exploration:

\squishlist
\item an
intuitive data model that
embraces an implicit ordering on both rows
and columns and treats them symmetrically;
\item a query
language that bridges a variety of data
analysis modalities including
relational (e.g., filter, join),
linear algebra (e.g., transpose),
and spreadsheet-like (e.g., pivot) operators;
\item an incrementally composable query
syntax that encourages easy and rapid validation
of simple expressions,
and their iterative refinement and composition
into complex queries; and
\item native embedding in a
host language such as Python
with familiar imperative semantics.
\end{list}

\noindent
Characteristics such as these
have helped dataframes become
incredibly popular for EDA;
for instance,
the dataframe abstraction provided by pandas\xspace
within Python (\url{pandas.pydata.org}),
has, as of 2020, been downloaded
over 300 million times, served as a dependency for
over 222,000 repositories in GitHub,
and starred on GitHub more 25,000 times.
Python's own popularity
has been
attributed to the success of pandas\xspace
for data exploration and data science~\cite{python-growing-quickly,python-growth-blamed}.
Due to its ubiquity, we focus on pandas\xspace for concreteness.

Pandas\xspace
has been developed from the ground up
\rebuttal{via open-source contributions
from dozens of contributors,
each providing operators and
their implementations to the DataFrame API}
to satisfy immediate or ad-hoc needs,
spanning capabilities
that mimic
relational algebra,
linear algebra, and
spreadsheet computation.
To date,
the pandas\xspace DataFrame API has ballooned to
over 200 operators~\cite{pandas-api}.
R, which is
both more mature and more carefully curated, has only 70 operators---but this
still far more than, say, relational
and linear algebra combined~\cite{R-dataframe-api}.

While this rich API is sometimes cited as a
reason for pandas\xspace' attractiveness,
the set of operators has significant redundancies,
often with different performance implications.
These redundancies place a considerable burden
on users to select the optimal way of expressing their goal.
For example, one blog post cites five different ways to express
the same goal, with performance varying from 0.3ms to 600ms
(a 1700$\times$ increase)~\cite{optimizing-pandas};
meanwhile, the pandas\xspace documentation itself offers multiple recommendations
for how to enhance performance~\cite{enhancing-performance}.
As a result, many users eschew the bulk of the API,
relying only on a small
subset of operators~\cite{minimally-sufficient}.
The complexity of the API and evaluation semantics
also make it difficult to apply
traditional query optimization techniques.
Indeed, each operator within a pandas\xspace ``query plan''
is executed completely before subsequent operators are executed,
with limited optimization, and
no reordering of operators or pipelining
(unless explicitly done so by the user using \code{.pipe}).
Moreover, the performance of the \code{pandas.DataFrame} API
breaks down when processing
even moderate volumes
of data that do not fit in memory, as we will see
subsequently---this is especially problematic
due to pandas\xspace' eager evaluation semantics, wherein
intermediate data items often surpass main memory limits
and must be paged to disk.

\rebuttal{
To address pandas\xspace' scalability challenges,
we developed \modin (\url{github.com/modin-project/modin}),
our first attempt at a scalable dataframe system,
which employs
parallel query execution
to
enable unmodified pandas\xspace code
to run more efficiently on large dataframes.
\modin is used by over 60 downstream projects, and
has over 250 forks and 4,800 stars on GitHub\techreport{ in its first 20 months}, indicating
the impact and need for such systems.
\modin rewrites pandas\xspace API calls
into a sequence
of operators in a new, compact
dataframe algebra.
\modin then leverages simple
parallelization and a new physical
representation
to speed up the
execution of these operators,
by up to {\bf 30$\times$} in certain
cases, and is able to run to completion
on datasets {\bf 25$\times$} larger
than pandas\xspace
in others.
}

\rebuttal{
Our initial optimizations in \modin are
promising, but only scratch the surface of what's possible. Given that
first experience and the popularity of the results,
we believe
there is room for a {\bf \em broad, community
research agenda on
making dataframe systems
scalable and efficient}, with many novel research challenges.
Our original intent when developing \modin
was to adapt standard relational database techniques
to help make dataframes scalable.
However, while the principles (such as parallelism)
do apply, their instantiation in the form of specific
techniques often differ,
thanks to the differences between
the data models and algebra of dataframes and relations.
Therefore, a more principled
foundation for dataframes is needed,
comprising a formal data model
and an expressive and compact algebra.
We describe our first attempt
at such a formalization in Section~\ref{sec:definitions}.
Then, armed with our data model
and algebra,
we outline a number of
research challenges organized around
unique dataframe characteristics and
the unique ways in which they are processed.

In Section~\ref{sec:datamodel},
we describe how the dataframe data model and algebra
result in new scalability challenges.
Unlike relations, dataframes
have a flexible schema and are lazily typed,
requiring careful maintenance of metadata,
and avoidance of the overhead of type inference as
far as possible.
Dataframes treat rows and columns
as equivalent, and metadata (column/row labels) and data
as equivalent, requiring flexible ways
to keep track of metadata and orientation,
placing new metadata awareness
requirements on dataframe query planners to avoid physically transposing data where possible.
In addition, dataframes are ordered---and dataframe systems
often enforce a strict coupling between logical and physical
layout; we identify several opportunities to deal
with order in a more light-weight, decoupled, and lazy fashion.
Finally, the new space of operators---encompassing
relational, linear algebra, and spreadsheet operators---introduce
new challenges in query processing and optimization.

In Section~\ref{sec:interactivity},
we describe new challenges and opportunities
that emerge from how dataframes are used
for data exploration.
Unlike SQL which
offers an all-or-nothing query modality,
dataframe
queries are
constructed one operator
at a time, with ample think-time between query fragments.
This makes it more challenging to perform query optimization
wherein operators can be reordered for higher overall efficiency.
At the same time, the additional thinking time between steps
can be exploited to do background processing.
Users often inspect intermediate dataframe results
of query fragments, usually
for debugging, which requires a costly materialization
after each step of query processing.
However, users are only shown an ordered
prefix or suffix of this intermediate
dataframe as output, allowing
us to prioritize the execution to return
this portion quickly and defer the execution
of the rest.
Finally, users often revisit old processing steps in
an ad-hoc process of trial-and-error data exploration.
We can consider opportunities to minimize redundant computation
for operations completed previously.

\stitle{Outline and Contributions.}
In this paper,
we begin with an example dataframe workflow
capturing typical
dataframe capabilities and user behaviors.
We then
describe our experiences with \modin
(Section~\ref{sec:modin}).
We use \modin to ground our discussion of
the research challenges.
We {\bf \em (i)
provide a candidate formalism for
dataframes} and enumerate their capabilities with a new algebra
(Section~\ref{sec:definitions}).
We then outline research challenges and
opportunities
 {\bf \em to build on our formalism
and make dataframe systems more scalable,}
by optimizing
and accounting
for
{\bf \em (ii) the unique characteristics
of the new data model and algebra} (Section~\ref{sec:datamodel}),
as well as {\bf \em (iii)
the unique ways in which dataframes are used
in practice for data exploration} (Section~\ref{sec:interactivity}).
We draw on tools
and techniques from the database research literature throughout
and discuss how they might be adapted
to meet novel dataframe needs.
}

In describing the aforementioned challenges, we focus on the pandas\xspace dataframe system~\cite{pandas-api}
for concreteness.
Pandas\xspace is much more popular than other dataframe
implementations,
and is therefore well worth our effort to study and optimize.
We discuss other dataframe
implementations and related work in Section~\ref{sec:ext}.
\papertext{Many details about \modin and our dataframe data model and algebra are
omitted
and can be found in our technical report~\cite{petersohn2020towards}.}

\section{The Modin Dataframe System}\label{sec:modin}

\rebuttal{
While the pandas\xspace API is convenient and powerful,
the underlying implementation has many scalability
and performance problems.
We therefore started an effort to develop
a ``drop-in'' replacement for the pandas\xspace API, \modin,
to address these issues.
We identified that while many operations in pandas\xspace
are fast, they are limited by their
single-threaded implementation.
Therefore, our starting point for \modin
was to add multi-core capabilities and other
simple performance improvements to enable
pandas\xspace users to run their same unmodified workflows
both faster and on larger datasets.
We briefly describe the challenges we encountered
in our implementation and how we addressed them in Section~\ref{sec:optim},
followed by a preliminary case study of the performance of \modin
in Section~\ref{sec:accelerate}.
We then discuss takeaways and how that informs
our future research agenda in Section~\ref{subsec:takeaways}.
We defer detailed treatment of \modin's architecture
to our technical report
}

\rebuttal{
We started an effort to build a drop-in replacement for
the pandas\xspace API, \modin, to solve many of the
scalability and performance problems introduced by the pandas\xspace implementation.
In pandas\xspace many operations are fast, but limited by their single-threaded implementation.
As an engineering challenge, we targeted making \modin a drop-in replacement
that would add multi-core capabilities and performance improvements that pandas\xspace
users could simply plug in to their existing workflows without
requiring additional
knowledge.
We began by integrating simple parallelism
and more efficient data management.
As we started the effort, we expected to directly
integrate best practices from relational system literature.
However, we quickly discovered
that dataframes like pandas\xspace do not conform to the relational data model.
Based on these differences,
we derived a new data model from the behaviors and capabilities
of existing dataframe systems.
Armed with a new data model and algebra, we can consider the new challenges
in integrating relational database optimizations, many of
which we discuss in Sections 5 and 6, grounded in our experience building
a parallel dataframe system.
}

\moved{
\modin supports the pandas\xspace API by rewriting the API
calls into a minimal subset. This subset
became the algebra presented in Section~\ref{sec:df-algebra}.
\modin is implemented in Python using over 30,000 lines
of code and emulates all the functionality of
\code{pandas.DataFrame}, \code{pandas.Series}, and
pandas\xspace  utilities (e.g., \code{pd.\-concat}),
while also yielding substantial (30$\times$)
speedups over pandas\xspace for certain operations.
To use \modin instead of pandas\xspace, users can simply
invoke ``\code{import modin.pandas}'',
instead of ``\code{import pandas}'', and proceed
as they would with pandas\xspace.
\modin is completely open source and can be found at
\url{https://github.com/modin-project/modin}.
}
\rebuttal{
We will reserve the implementation details and architecture
of this system to another
paper, however it is important that we highlight
our experience and lessons learned with implementing
some of the more exotic components
of the \modin dataframe system and some of the challenges therein.
}

\subsection{Engineering Challenges in Dataframes}\label{sec:optim}
\rebuttal{
As we began studying the pandas\xspace implementation, we discovered many
challenges in exposing the API. In this section we discuss the engineering
challenges we have encountered that are unique to the pandas\xspace
dataframe implementation.
}

\stitle{Massive API.}
\moved{
Pandas\xspace has been developed from the ground up
via open-source contributions;
pandas\xspace DataFrame API operators
and their implementations
have been engineered
by dozens of contributors
to satisfy immediate or ad-hoc needs,
spanning capabilities
that mimic
relational algebra,
linear algebra, and
spreadsheet formula computation.
To date,
the pandas\xspace DataFrame API has ballooned to
over 240 distinct operators~\cite{pandas-api},
}
\rebuttal{
making it challenging to engineer and ensure adequate
API coverage.
}

\rebuttal{
Currently, \modin supports over 85\% of
the \code{pandas.DataFrame} API. We chose the order
of implementation based on a study we conducted on
over 1 million Jupyter notebooks, the results of
which are discussed in our tech report~\cite{techreport}.
To solve this problem, we derived a kernel of operators
that represent the pandas\xspace API, and layered the
\modin implementation to avoid duplicating logic
as much
as possible. As we developed the dataframe data model,
this kernel of operators became the
working dataframe algebra we will present
in Section~\ref{sec:df-algebra}.
}

\stitle{Parallel execution.}
Parallelization
is commonly used to improve performance
in a relational context
due to the embarrassingly parallel nature
of relational operators.
Dataframes have
\rebuttal{a different set of operators
than relational tables, supporting relational algebra,
linear algebra, and some spreadsheet operators.
We will discuss these operators in detail in Section~\ref{sec:df-algebra}.}
\rebuttal{Each of these operators represents
a class of data manipulation APIs from pandas.
We implemented different internal mechanisms for
exploiting parallelism}
depending on the
data dimensions and operations being performed.
Some operations
are embarrassingly parallel and
can be performed on each row independently.
\rebuttal{Other}
operations do not admit
row-wise parallelism
because
computation for each subsequent
row must wait for the result of the
prior row.
\rebuttal{To address the challenge of differing levels
of parallelism and support all of the operations in
existing dataframe implementations, we designed
a mechanism within \modin to be able to flexibly
move between all common partitioning schemes:}
row-based (i.e., each partition has a collection of rows),
column-based (i.e., each partition has a collection of columns),
or block-based partitioning
(i.e., each partition has a subset of rows and columns),
depending on the operation.
\rebuttal{This gives \modin the flexibility to
take advantage of many optimizations in row-based systems,
column stores, and block stores.}

\begin{figure*}[ht!]
    \centering
    \vspace{-10pt}
    \includegraphics[width=0.9\textwidth]{perf_plots.pdf}
    \vspace{-10pt}
    \caption{%
        For each function,
        we show the runtime for both \modin and pandas\xspace
        and the 95\% confidence interval.
        There are no times for transpose with pandas\xspace as
        pandas\xspace is unable to run transpose beyond 6 GB.
    }
\label{fig:performance}
\vspace{-10pt}

\end{figure*}

\stitle{Supporting billions of columns.}
\rebuttal{The majority of traditional} database systems
cannot support tables with
billions of columns;
\rebuttal{In the pandas\xspace API, however, }
it is possible to \code{TRANSPOSE} a dataframe
with billions of rows
into one with billions of columns.
In many settings, e.g., when dealing with large graph
adjacency matrices in neuroscience or genomics,
the number of rows and number of columns can both be very large.
For these reasons, \modin treats
rows and columns essentially equivalently,
\rebuttal{as we will} discuss in Section~\ref{sec:definitions}.
In particular, for transposing a large dataframe,
\modin uses block-based partitioning on the large
dataframe, where each block consists of a
subset of rows and columns.
Each of the blocks are individually transposed,
followed by a simple change of the overall metadata
tracking the new locations of each of the blocks.
The result is a transposed dataframe that does not
require any communication.

\subsection{Preliminary Case Study}\label{sec:accelerate}

\rebuttal{To study how some simple parallelism can improve the scalability of the pandas\xspace
semantics,}
we evaluated \modin's performance against that of pandas\xspace using microbenchmarks on an EC2 x1.32xlarge (128 cores and 1,952 GB RAM) node using a New York City taxicab dataset~\cite{nyc-taxi-data} that was replicated 1 to 11
times to yield a dataset size
between 20 to 250 GB with up to 1.6 billion rows.
We consider four queries:
\squishlist
\item map: check if each value in the dataframe is null, and replace it with a \code{TRUE} if so, and \code{FALSE} if not.
\item groupby ($n$):
group by the non-null ``passenger\_count'' column and count the number of
rows in each group.
\item groupby ($1$):
count the number of non-null rows in the dataframe.
\item transpose:
swap the columns and rows of the dataframe and
apply a simple (map) function across
the new rows.
\end{list}

\noindent
We highlight the difference
between group by with one group and
$n$ groups, because in a group by
with $n$ groups
\rebuttal{
data shuffling and
communication is a
factor in performance.
With groupby(1),
the communication overheads
across groups are non-existent.
}
We include transpose
to demonstrate that \modin
can handle data with
billions of columns.
This query also
shows where pandas\xspace crashed or
did not complete in more than 2 hours.

Figure~\ref{fig:performance} shows that
for the group by ($n$)
and group by ($1$) operations,
\modin yields a speedup of up to $19\times$
and $30\times$ relative to pandas\xspace, respectively.
For example, a group by ($n$) on a 250GB dataframe,
pandas\xspace takes about 359 seconds
and \modin takes 18.5 seconds, a speedup of more
than 19$\times$.
For map operations, \modin is about 12$\times$
faster than pandas\xspace.
These performance gains come from
simple parallelization of operations within \modin,
while pandas\xspace only uses a single core.
During the evaluation of transpose,
pandas\xspace was unable to transpose
even the smallest dataframe of 20 GB ($\sim$150 million rows)
after 2 hours.
Through separate testing,
we observed that pandas\xspace can only transpose
dataframes of up to 6 GB ($\sim$6 million rows) on the
hardware we used for testing.

These performance numbers are preliminary
results that demonstrate the promise of
\rebuttal{integrating simple optimizations}.
We plan to perform further analyses in support of future optimizations,
\rebuttal{the possibilities of which we discuss in later sections}.

\subsection{The Future of Dataframes}\label{subsec:takeaways}

\rebuttal{
In our experience building the \modin dataframe system, we
discovered many new challenges in integrating optimizations and
best practices from relational database literature.
Given the amount of impact that \modin has had with the relatively
basic optimizations presented in this section,
we feel that future works in developing and optimizing
dataframes will have a profound and lasting impact on the
data science community.
}

\todo{Consider moving outline here}

\subsection*{Metareview}
\com{(M1)
The description of the existing system should be reduced and rephrased
to be more of a technical background rather than
sounding like a research paper.
}

We have substantially reduced the amount of
detail in each of
Sections~\ref{sec:usecase}, \ref{sec:modin},
and \ref{sec:definitions}, and
only kept details
that are pertinent to the vision components of the paper.
We now describe in detail what was
removed or revised.

In Section~\ref{sec:usecase},
we removed portions
that were self-explanatory or easily understood.
We also replotted Figure~\ref{fig:example}
to take up less space.
Descriptions of how users
interact with a dataframe system
were moved to later sections
when describing the motivations for
improving certain interaction modalities.

In Section~\ref{sec:modin}, we substantially
reduced the amount of detail on our current implementation
of \modin.
Recognizing the purpose of this section
is to describe our experience with dataframes
thus far, and to use that to
set the stage for our future research
agenda, we moved this section
to right after Section~\ref{sec:usecase}
as our prior work.
We entirely removed any architectural
descriptions about \modin as they are not relevant
for our vision.
Since the techniques underlying \modin
thus far are straightforward, we
made their description much more concise.
Since there was also
some confusion about what had been implemented
and what was future work, we
also cleared that up by making
Section~\ref{sec:modin} the ``already implemented''
component and making
latter sections more vision-oriented to convey
that those are indeed future work.

In Section~\ref{sec:definitions}, we have made substantial
changes to all subsections.
We removed much of the detailed
discussion on the finer points of the described
data model in Section~\ref{sec:dataframedef}.
Some of this detail was moved
to Section~\ref{sec:datamodel} to motivate
some of the research challenges in dataframes,
but many details were removed entirely from the
paper if they did not add to the overall vision.
We also replaced some lengthy text with two compact
tables.
We entirely removed the workflow definitions part,
choosing to introduce some of these terms
as needed later on.
In Section~\ref{sec:df-algebra},
we made significant cuts to the explanation of
the operators.
Since this paper does not try to argue
minimality, we use
these operators more as a frame of reference
to describe the new challenges in efficiently
processing dataframes as opposed to providing
formal definitions.
We only kept the components that tie
directly to later sections of the paper
where our future research problems are described.
We have revised Section~\ref{sec:algebra-example}
to only convey one single case study on \code{pivot}
as opposed to many straightforward examples
of rewriting of pandas\xspace API operators into
the dataframe algebra.
(We also enhanced this case study to add more
detail, along with a new figure.)
Former Section 3.5 (now would be 4.5) was entirely
removed, since the extensions to the data model
does not add much to the vision portion of the paper.

While we have cut back substantially in all of
Sections~\ref{sec:usecase}, \ref{sec:modin},
and \ref{sec:definitions},
further cuts would hurt understanding
for database readers.
Specifically, we believe an important contribution
of this paper is to provide some background into
dataframes and their characteristics.
One of our reviewers remarked that they were skeptical of
any difference between dataframes and databases before they read this paper,
but this background was effective in convincing them
that they are distinct artifacts
and will require a new body of research.

\com{(M2)
The integration between the technical background and the vision needs to be improved.
Specifically, the vision focuses on the more general problems in data exploration
and does not focus on how these problems are different in dataframes
(as compared to relational settings).
}

\com{AND}

\com{(M3)
The identification of the unique challenges of dataframes needs to be better.
Additionally, the challenges of relational systems which dataframes exacerbate
and that which dataframes lessen.
}

To highlight how the discussed
challenges are specific to dataframes,
we have significantly restructured the paper to provide
a more familiar flow
and have substantially revamped
Sections~\ref{sec:datamodel} and \ref{sec:interactivity}
taking the reviewer comments into account.

Specifically, for Section~\ref{sec:datamodel},
we had originally anchored our discussion around
``layers'' of a database system architecture
to provide a familiar point of entry for a VLDB audience.
Likewise, for Section~\ref{sec:interactivity},
we had originally organized our proposed directions
around ideas (many of them stemming from general
data exploration) as opposed to unique dataframe aspects.
We also focused too much on solutions rather than the underlying problems and why they are interesting
and unique.
After reading the reviews,
however, we realized that this was not an optimal approach
for conveying our vision for scalable dataframe systems.

As such,
we have now focused these sections around
unique challenges in the dataframe
data model and algebra (Section~\ref{sec:datamodel})
and in how dataframes are manipulated over
the course of a user exploration session
(Section~\ref{sec:interactivity}).
When describing these challenges, we focused
on the key differences between operating on dataframes
and on relations.
Prior to these sections, we
set the stage for our research vision in the
substantially revised Section~\ref{sec:modin}
which describes what has been implemented,
and how that informs our future agenda.
We now explain the changes to Sections~\ref{sec:datamodel} and ~\ref{sec:interactivity}
in detail.

In Section~\ref{sec:datamodel}, we organize
our discussion around various unique properties
of dataframes, including flexible schema, lazy typing,
row-column equivalence (thanks to operators such as transpose), data-metadata equivalence (thanks to the presence of
row and column labels
and operators that allow labels to become part of data),
and the centrality of order for both rows and columns.
We ground this discussion by drawing on prior work in the
relational database community, and discuss why those
techniques would not apply to dataframes without violating
key dataframe properties. Grounding
the discussion in this manner helps us contrast the future
work needed to develop dataframe systems with existing work
on relational databases.

In Section~\ref{sec:interactivity},
we have centered our research challenges around the unique
ways in with dataframes play a role in data exploration.
Specifically, dataframes are usually manipulated interactively
over the course of a long-running user session,
with dataframe queries composed incrementally as individual \stmts,
a small number of operators at a time,
with subsequent invocations building on previous ones.
Users often revisit previous steps in their exploration,
trying out different exploration strategies in a trial-and-error fashion.
They also inspect intermediate results often with
an eye towards debugging and validation.
These characteristics are unique to how dataframes
are manipulated across data exploration sessions
typically performed in an interactive environment
such computational notebooks.

\subsection*{Reviewer 1}
\com{(A1) It is unclear as to which parts are the technical details
that are currently implemented in the system (which are less suited for a vision paper)
and which parts are the novel visionary contributions of the paper.
}

This feedback was addressed while resolving (M2/M3).

\com{(A2)
It would be nice to see more discussion
on the semantics of the group-by (resp. window) operator.
}

We thank the reviewer for this suggestion. We agree that
the semantics of dataframe \code{GROUPBY} and \code{WINDOW} deserve
special attention, particularly the ways in which they
deviate from their SQL/relational algebra counterparts.
In particular, the fact that dataframes can support
composite types per cell
means that the dataframe algebra can use a broader class of aggregation
functions, not restricted to those that result in a single atomic value. This behavior
is also reflected in pandas\xspace' \code{groupby} operator.
We have added additional
discussion in Section~\ref{sec:df-algebra}, highlighting how certain
functionality can be expressed more elegantly using the dataframe
variants of these primitives.

\com{(A3)
It would be nice to see more discussion
on the interplay between dataframes and data visualizations.
}

Visualization is indeed
an important component
of data exploration with dataframes,
and not mentioning it was an oversight.
We now have added a brief
discussion in Section~\ref{sec:interactivity}
on how the default
tabular view displayed when dataframes are printed
(a prefix/suffix of the rows and columns)
is a simple form of visualization for
debugging and validation of structure and order,
but other forms of visualization may also be
valuable.
We also have added a discussion around
how prior work on approximate
decision making with visualization for
debugging and validation may be adapted.

\com{(A4)
The visonary aspects of the paper are dissappointing.
The authors discuss standard interactive data exploration tasks rather than
discussing the specific challenges posed and opportunities created
as a result of dataframes.
}

We appreciate this comment, and have taken it to heart -- please see responses to
(M2/M3).

\com{(A5)
It is hard to print the PDF and, having gotten it printed,
the math symbols were not properly rendered.
}

We have re-rendered the Math symbols in the PDF to allow for easier printing.

\com{(A6)
It was surprising that there were no row-level schemas.
}

This is an interesting point!
Both the relational model and pandas\xspace have schemas on only one axis: columns.
For relations, this is because of the distinct semantics of rows and columns.
Perhaps in pandas\xspace this is because of the desire for a single default interpretation of a cell:
we always use the column type to interpret the bits in a cell.
One could of course have an alternative row-based interpretation
as you suggest, though. This is achieved in dataframe libraries like pandas\xspace, as well
as our algebra, by applying a transpose operator (which of course is not in SQL!)
to shift interpretation.
However your observation is intriguing. We now highlight this point in Section~\ref{sec:dataframedef},
and discuss the resulting optimization challenges (i.e. the need to transpose
just to shift one's interpretation) in Section~\ref{sec:rowcolumneq}.

\com{(A7)
In the performance figure, why was there was a spike in variance around 100GB,
which was followed by a normalization of perofmance numbers.
}

After rerunning the experiments, we concluded that the spike in variance
was due to some contention in resources. We repeated the experiments additional times and did not see the variance spike in the
updated results. The new numbers are reported in
Figure~\ref{fig:performance}.

\subsection*{Reviewer 2}
\com{(B1)
The microbenchmarks do not demonstrate the strength of the underlying data model
as it's strength is in the assembly of the operators,
which does not occur in the microbenchmarks
}

Our goal with the microbenchmarks is to
validate that simple optimizations (such as parallelism)
within \modin
can lead to substantial improvements
in scalability and performance over pandas\xspace,
which has severe issues, despite being widely used.
To clarify this point further, we have moved
the \modin section to Section~\ref{sec:modin}
as opposed to Section 4 (in the previous version),
and focused more on lessons learned from our engineering
experience with \modin, and how that guides
our future research directions.
Indeed, further experiments to test the strength of
the underlying model and rewriting rules are needed,
but we consider that as part of our future research agenda
and will do so in future work.

\com{(B2)
The paper, after the technical details of Modin,
is a grab bag of notes on existing work in databases and data science.
The discussion is somewhat direction-less and there is no true vision expressed here.
}
This feedback was addressed while resolving (M2/M3).
We have taken this feedback to heart and entirely revamped
Sections~\ref{sec:datamodel} and \ref{sec:interactivity} to be centered
on novel dataframe aspects.

\com{(B3)
Table of operator is not legible in printouts.
}

We have fixed the table to be more legible in printouts
with a larger text size.

\com{(B4)
Typo when discussion operators:
``... as well as four new operators.. We briefly describe... the three new operators.''
}

We have fixed this typo to describe the four new operators.

\com{(B5)
It is unclear whether the types of values are represented and inspectable at run time.
}

Types are inspectable at runtime, and inspecting the types
will trigger their materialization if they are already not
materialized. We have added this clarification to
Section~\ref{sec:datamodel}.

\com{(B6)
Some of the rewrites should be removed and
be replaced with fewer but more in-depth rewrites.
}

We agree with the reviewer that the number of rewrites
in Section~\ref{sec:algebra-example}
was excessive and was not adding much to the discussion.
We have instead decided to focus on \code{pivot} as a single
case study---a challenging operator for relational algebra---and
described it in more detail with a new diagram.

\com{(B7)
The statement that ``query optimization is not possible in an eager system''
is misleading because most query optimization is performed before the evaluation of the program.
}

We were not clear in our writing
and did not intend for this interpretation.
Dataframe systems, unlike relational databases,
support an incremental mode of composition of queries
where programmers can specify a \stmt
composed of one or more operators at a time (i.e., a query sub-expression),
building on the variables declared in previous \stmts.
We revised Section~\ref{sec:interactivity}
to clarify that, by ``eager'',
we mean that the query processor executes each \stmt
as soon as it is invoked by the programmer, without waiting.
By ``lazy'', we mean that the query processor waits
until the dataframe is either printed or saved before
it finds an optimized query execution plan that is
semantically equivalent
to executing each of the operators
of query sequentially,
and executes this optimized query plan.
In this context, we believe that the ``eager'' mode
makes it difficult to perform query optimization
since the query processor will need to produce
results for each intermediate sub-expression as assembled by the user.
We have reworked this entire section and
taken out the ``not possible'' part as it was confusing;
we have also added an example to illustrate this further.

\com{(B8)
The idea that lazy query processors ``recently emerged'' is flawed
as the on-demand evaluation of complex algebraic plans (e.g., Volcano)
has been the default mode of execution in query processors for decades.
}

We were not clear in our writing when stating that
``the lazy paradigm ... recently emerged.''
We revised our submission to make it clear that
we are discussing eager and lazy evaluation
in the context of other dataframe and dataframe-like systems
such as Pandas, Dask, and Spark,
and not in relational databases
which do not have
an incremental mode of composition.
In the context of dataframe systems,
eager execution, as described in the previous point,
is the canonical approach as is the approach used
in dataframe systems up until recently (e.g., Pandas and R Dataframes).
It is only recently with Spark dataframes and Dask
have dataframe or dataframe-like
systems begun operating within a lazy paradigm.
But since this point is subtle, we removed
any mention of whether the emergence was recent,
and focus more on conveying the two modes as is,
centered on dataframe and dataframe-like systems.

\com{(B9)
There should be more discussion around multi-query optimization and materialization.
Particularly, there should be more discussion on how the system would
predict which intermediate results would be more likely to be used.
What information would be necessary to drive such inferences?
}

We have added further discussion on materialization and reusing
query results to Section~\ref{sec:interactivity},
taking advantage of ample user think-time. Specifically,
we discuss the need to predict user intent based on past workloads~\cite{ucsd-dataframe-study}
and operator lineage. We discuss the challenges in materialization
of intermediate results given that we may have many query fragments
partially completed.
We also propose interesting future work on
embedding materialization decisions within the opportunistic
evaluation query planner to further accelerate the interactive user experience with speculative execution.

\com{(B10)
It may be hard to do prefix computation when considering more complex expressions
as the system may need more than k rows to be able to display a prefix of size k
after more operations have been added to the expression.
What is the approach that Modin will take to this issue?
}

We have added a deeper discussion in Section~\ref{sec:datamodel}
on the novel aspects of prefix computation
and the challenges in preserving order
with prefix computation. As the reviewer mentions, it is
not always possible to know how many
rows a given query will output, and keeping aside
only $k$ rows will not always work, especially in complex queries
with selective predicates---this question is not new to dataframe systems
but the ordering aspect is novel.
One approach, for example, would be to use operators that generate
results in order, such as index nested loop joins,
which progressively ingest more of the input dataframes until
$k$ output rows are produced.
We can also leverage parallelism to
prioritize the ingest
and processing of ``enough'' of the inputs to guarantee
the output of the first $k$ rows.
Since dataframes
must {\em guarantee} both the top $k$ and its order,
that dataframe query optimizers may need to use both
selectivity and cardinality estimates, along with
models of past user behavior to gain
insight into how many
input rows may be necessary to generate $k$ output rows.

\com{(B11)
Sections 5 and 6 should be more concrete and try to have a focused vision
that shows how the algebraic approach can be an advantage on the current
state-of-the-art (e.g., Pandas and R).
This may be the focus on query planning to defer or avoid costly
data restructuring operations or
a reversal of roles of data data and meta-data.
}

\com{AND}

\com{(B12)
There should be a connection between the technical details described in the beginning
and the vision described in the rest of the paper.
It is ok if this makes the vision of the paper becomes specific to the Modin view of dataframes.
}

This feedback was addressed while resolving (M2/M3).
We thank the reviewer for the query planning points---we have used them
when reframing our vision when centered around novel
aspects of dataframes.
We have also substantially revised the previous portions of the paper
to keep only as many technical details as is needed
to ground our discussion on the vision.

\subsection*{Reviewer 3}
\com{(C1)
Please cut out a bunch of details, we don't need a 12 page vision paper.
\squishlist{}
    \item I don't really need a 1-page example on data frames.
    \item Why do I need to know the history of data frames?
    \item Perhaps we do not need the exact formalism for the data model and all operations and
    a detailed sketch would suffice.
\end{list}{}
}

This was resolved while addressing (M1). We provide some additional
details below.

We thank the reviewer for these suggestions.
We retained the example, but substantially reduced its length
and detail as it allows database readers who are unfamiliar
with dataframes to establish a basic understanding.
We have also redrawn the figure to reduce the space taken for it.

We have reduced the length for the history of dataframes,
only emphasizing key background for the interested database reader.
Specifically, we retained the portions that
contribute a meaningful and largely unknown piece
of how dataframes
emerged to the scientific community.
This background also
gives a basis on which we can
understand how dataframes were intended to be used,
so that we can optimize
them in this context.

Finally, we have substantially reduced the length
and details
in the formalism
for the data model and algebra,
reduced the number of rewritings,
and removed the extensions.
We focus on the
components which make dataframes difficult to scale. The formalism
is important because it provides a basis upon which we can build
our research vision---and we only retain as much as is needed
to support that.
We have also clarified the intention of this section.

Given the overwhelming popularity of dataframes
and their important role in the data science ecosystem,
as well as the relative lack of awareness and understanding
from the database research community,
we believe that the length of this paper is justified.

\com{(C2)
Missing related work.
There should be explicit mention of embeddable DBMSs such as DuckDB and SQLite
and, at least, a theoretical comparison of them and the vision proposed in the paper.
Also, please cite Tukey's book on EDA.
}

Regarding embeddable DBMSs, from an architecture perspective, we now
clarify in Section~\ref{sec:modin} that Modin is a library, much like an embeddable DBMS. (This is standard for
dataframe libraries, including pandas, so we overlooked mentioning it in this environment. It's a nice
connection to make, thanks!) In Section~\ref{sec:flexschemas} we also address some of the implications that arise
for dataframes from having their storage external to the application, including some of the work in the
community (e.g. Apache Feather) to address this. Finally, with respect to theoretical issues, the bulk of the
paper focuses on distinctions (both theory and practice) that arise from the semantic distinctions
between relational databases (embedded or otherwise) and dataframes, so we hope there's sufficient discussion
of DBMSs vs. dataframes in general.

With respect to Tukey, we are big fans, and have happily added a citation to Tukey's book in the introduction.
Thanks for pointing that out -- sometimes we take our heroes for granted!

\com{(C3)
The future vision is a bit generic.
Although sections 5-7 are the more interesting parts
with a particular emphasis on section 6,
they are only 2 pages out of the entire paper.
These sections should have a higher fraction of the paper
by adding more depth to the challenges and future directions
and making them less generic would also help.
}

This feedback was addressed while resolving (M2/M3).
We have taken this feedback to heart and have substantially revised
the vision portions of this paper.

\section{The Modin Dataframe System}\label{sec:modin}

\rebuttal{
While the pandas\xspace API is convenient and powerful,
the underlying implementation has many scalability
and performance problems.
We therefore started an effort to develop
a ``drop-in'' replacement for the pandas\xspace API,
\modin\footnote{\scriptsize \modin's name is derived from the Korean
word for ``every'', as it targets every dataframe operator.},
to address these issues.
In the style of embedded database systems~\cite{sqlite2020hipp,raasveldt2019duckdb},
Modin is a library that runs in the same process as the application that
imports it.
We briefly describe the challenges we encountered
and the lessons we learned
during our implementation in Section~\ref{sec:optim},
followed by a preliminary case of \modin's performance in Section~\ref{sec:accelerate}.
\papertext{We defer detailed treatment of \modin's architecture
to our technical report~\cite{petersohn2020towards}.}
\techreport{Finally, we describe \modin's architecture
and implementation.}
}

\subsection{\rebuttal{Modin Engineering Challenges}}\label{sec:optim}
\rebuttal{
When we started our effort to make pandas\xspace
more scalable,
we identified that while many operations in pandas\xspace
are fast, they are limited by their
single-threaded implementation.
Therefore, our starting point for \modin
was to add multi-core capabilities and other
simple performance improvements to enable
pandas\xspace users to run their same unmodified workflows
both faster and on larger datasets.
However, we encountered a number of engineering
challenges.
}

\stitle{Massive API.}
\rebuttal{The pandas\xspace API
has over 240 distinct operators,
making it challenging to individually optimize
each one.
After manually trying to parallelize
each operator within \modin,
we tried a different approach.
We realized that there is a lot of redundancy
across these 240 operators.
Most of these operators can be rewritten
into an expression composed using
a much smaller set of operators.
We describe our compact set of dataframe
operators---our working dataframe algebra---in
Section~\ref{sec:df-algebra}.
Currently, \modin supports over 85\% of
the \code{pandas.DataFrame} API,
by rewriting API calls into our working algebra,
allowing us to avoid duplicating
optimization logic as much as possible.
The operators we prioritized
were based on an analysis of
over 1M Jupyter notebooks\papertext{, the results of
which are discussed in our technical report~\cite{petersohn2020towards}.}
\techreport{discussed in Section\ref{sec:usage}.}
Specifically, we targeted all the functionality in
\code{pandas.DataFrame}, \code{pandas.Series}, and
pandas\xspace  utilities (e.g., \code{pd.\-concat}).
To use \modin instead of pandas\xspace, users can simply
invoke ``\code{import modin.pandas}'',
instead of ``\code{import pandas}'', and proceed
as they would previously.
}
\techreport{
\modin is implemented in Python using over 30,000 lines
of code.
\modin is completely open source and can be found at
\url{https://github.com/modin-project/modin}.}

\stitle{Parallel execution.}
\rebuttal{Since most pandas\xspace
operators are single-threaded,
we looked towards parallelism
as a means to speed up execution.}
Parallelization
is commonly used to improve performance
in a relational context
due to the embarrassingly parallel nature
of relational operators.
Dataframes have
\rebuttal{a different set of operators
than relational tables, supporting relational algebra,
linear algebra, and spreadsheet operators,
as we saw in Section~\ref{sec:usecase}, and we
will discuss in Section~\ref{sec:definitions}.
We implemented different internal mechanisms for
exploiting parallelism}
depending on the
data dimensions and operations being performed.
\rebuttal{Some} operations
are embarrassingly parallel and
can be performed on each row independently \rebuttal{(e.g., C3 in Figure~\ref{fig:example})},
\rebuttal{while others (e.g., C2, A1, A3) cannot.}
\rebuttal{To address the challenge of differing levels
of parallelism across operations, we designed
\modin to be able to flexibly
move between common partitioning schemes:}
row-based (i.e., each partition has a collection of rows),
column-based (i.e., each partition has a collection of columns),
or block-based partitioning
(i.e., each partition has a subset of rows and columns),
depending on the operation.
\rebuttal{Each partition is then processed independently
by the execution engine, with the results communicated
across partitions as needed.}

\begin{figure*}[ht!]
    \centering
    \vspace{-10pt}
    \includegraphics[width=0.9\textwidth]{perf_plots.pdf}
    \vspace{-10pt}
    \caption{%
        \rebuttal{For each function,
        we show the runtime for both \modin and pandas\xspace
        and the 95\% confidence interval.
        There are no times for transpose with pandas\xspace as
        pandas\xspace is unable to run transpose beyond 6 GB.}
    }
\label{fig:performance}
\vspace{-15pt}

\end{figure*}

\stitle{Supporting billions of columns.}
\rebuttal{While parallelism does address
some of the scalability challenges, it fails
to address a major one: the ability to support
tables with billions of columns---something
even traditional database systems do not support.
Using the pandas\xspace API, however, it is possible
to transpose a dataframe (as in Step C2)
with billions of rows
into one with billions of columns.}
In many settings, e.g., when dealing with graph
adjacency matrices in neuroscience or genomics,
the number of rows and number of columns can both be very large.
For these reasons, \modin treats
rows and columns essentially equivalently,
\rebuttal{a property of dataframes will discuss in detail in Section~\ref{sec:definitions}}.
In particular, to transpose a large dataframe,
\modin employs block-based partitioning,
where each block consists of a
subset of rows and columns.
Each of the blocks are individually transposed,
followed by a simple change of the overall metadata
tracking the new locations of each of the blocks.
The result is a transposed dataframe that does not
require any communication.

\subsection{Preliminary Case Study}\label{sec:accelerate}

\rebuttal{
To understand how the simple optimizations discussed above
impact the scalability of dataframe operators,
we perform a small case study evaluating}
\modin's performance against
that of pandas\xspace using
microbenchmarks on an EC2 x1.32xlarge (128 cores and 1,952 GB RAM)
node using a New York City taxicab dataset~\cite{nyc-taxi-data} that was replicated 1 to 11
times to yield a dataset size
between 20 to 250 GB, with up to 1.6 billion rows.
We consider four queries:
\squishlist
\item map: check if each value in the dataframe is null, and replace it with a \code{TRUE} if so, and \code{FALSE} if not.
\item groupby ($n$):
group by the non-null ``passenger\_count'' column and count the number of
rows in each group.
\item groupby ($1$):
count the number of non-null rows in the dataframe.
\item transpose:
swap the columns and rows of the dataframe and
apply a simple (map) function across
the new rows.
\end{list}

\noindent
We highlight the difference
between group by with one group and
$n$ groups, because
with $n$ groups
\rebuttal{
data shuffling and
communication are a
factor in performance.
With groupby(1),
the communication overheads
across groups are non-existent.
}
We include transpose
to demonstrate that \modin
can handle data with
billions of columns.
\techreport{This query also
shows where pandas\xspace crashed or
did not complete in more than 2 hours.}

Figure~\ref{fig:performance} shows that
for the group by ($n$)
and group by ($1$) operations,
\modin yields a speedup of up to $19\times$
and $30\times$ relative to pandas\xspace, respectively.
For example, a group by ($n$) on a 250GB dataframe,
pandas\xspace takes about 359 seconds
and \modin takes 18.5 seconds, a speedup of more
than 19$\times$.
For map operations, \modin is about 12$\times$
faster than pandas\xspace.
These performance gains come from
simple parallelization of operations within \modin,
while pandas\xspace only uses a single core.
During the evaluation of transpose,
pandas\xspace was unable to transpose
even the smallest dataframe of 20 GB ($\sim$150 million rows)
after 2 hours.
Through separate testing,
we observed that pandas\xspace can only transpose
dataframes of up to 6 GB ($\sim$6 million rows) on the
hardware we used for testing.

\rebuttal{\stitle{Takeaways.} Our preliminary case study and our experience
with \modin
demonstrates the promise of integrating
simple optimizations to make dataframe systems scalable.
Next, we define a dataframe data model
and algebra to allow us to ground our subsequent discussion of
our research agenda, targeting the unique characteristics
of dataframes and the unique ways in which they are used.
We defer further performance analyses of \modin to  future work.}

\techreport{
\subsection{The MODIN Architecture}\label{sec:architecture}

\begin{figure}
\centering
\vspace{-5pt}
\includegraphics[width=.4\textwidth]{modin_architecture_updated.png}
\vspace{-5pt}
\caption{\modin architecture.}
\label{fig:modin-arch}
\vspace{-15pt}
\end{figure}

\modin's architecture is {\em modular}
for easy integration of new storage and execution engines, APIs, and optimizations. It consists of four layers:
the API layer, the query processing
and optimization layer,
the execution layer,
and the storage layer, shown in Figure~\ref{fig:modin-arch}.

\stitle{API layer.}
Users can leverage
\modin via a pandas\xspace-based API,
or directly via a leaner and simpler \modin API
based on the algebra in Section~\ref{sec:df-algebra}.
In either case, the API layer
translates each call into
a dataframe algebraic expression,
and passes that to the next layer for execution.
The layer isolates users from changes
to the layers below, while allowing
users to leverage the API modality they are most
comfortable with.
\techreport{Future implementations may support other user
APIs for working with dataframes,
such as SQL or relational algebra.}
Our pandas\xspace-based API currently supports
about 150 of over 200 pandas\xspace dataframe APIs,
and rewrites each of them into dataframe
algebraic expressions.

\stitle{Query processing and optimization layer.}
As shown in Figure~\ref{fig:modin-arch},
the query processing layer follows a
``narrow waist'' design,
exposing a small API based on
the dataframe algebra,
and implements the data model
from Section~\ref{sec:dataframedef}.
This layer parses, optimizes, and executes
dataframe queries with the help
of layers below.
As we will describe in Section~\ref{sec:optim},
\modin leverages parallel execution
of dataframe queries on multiple
dataframe partitions,
scheduled on execution engines
in the next layer.
This layer also keeps track of
dataframe metadata
including row labels, column labels,
and column data types.
\techreport{Recall that data types may not be specified
on dataframe creation, so }
\modin
induces types on-the-fly (using the $S$ function)
when needed for a specific operation.

\stitle{Execution layer.} \modin
supports distributed
processing of
dataframe partitions
using
two execution frameworks:
Ray~\cite{ray} and Dask~\cite{dask}.
Both Ray and Dask are task-parallel asynchronous
execution engines exposing an API that requires defining a task or function and providing data for the task to run on.
Integration of a new
execution framework is simple, often requiring
fewer than 400 lines of code.

\stitle{Storage layer.}
\modin's modular storage layer
supports both main memory and
persistent storage out-of-core (also called memory spillover),
allowing intermediate dataframes to exceed main-memory limitations
while not throwing memory errors, unlike pandas\xspace.
To maintain pandas\xspace semantics, the dataframe
partitions are freed from persistent storage once
a session ends.
}

\section{Acceleration across Statements}\label{sec:acrossstatement}

One of the most-used features of dataframes is the ability to compose longer
queries one statement at a time and save, store, or return to
intermediate results.
In a SQL database, this can be done with views,
which are selectively materialized by the query optimizer.
In a pure dataframe implementation such as pandas,
intermediate results are materialized
in memory as long as there is a pointer to it in scope.
Users rely on these intermediate result in the typical data scientists workflow,
primarily because a
significant amount of dataframe interactions follow the trial and error
programming paradigm.
Despite its usefulness from the user's perspective,
materialization of every intermediate result is expensive
and memory intensive. The cost and potential
optimizations of this behavior across
sub-queries will be discussed in Section~\ref{sec:acrossstatement}.

There is a significant missed opportunity for optimization if
we only focus on optimizing single statements. For example, taking a
reduction (e.g. \code{COUNT}) followed by a projection. If we perform
the projection first, we can significantly reduce the amount of
computation. In this section, we will discuss several ways we can apply techniques from relational database literature to speed up the execution of dataframe operations.

\subsection{Multiquery Optimization}\label{sec:mqo}
We envision that \modin will prioritize interactivity, returning
control to the user as quickly as possible by displaying
preview (head/tail) or
approximate results and defer calculation of full or exact results to background computation using techniques from Section\label{sec:singlestatement}.
As such, many operations may be queued for execution at once\dlee{not sure what this sentence is saying}. These statements may
operate over similar or even identical subsets of data. To exploit this workload, \modin will make use of multiquery optimization (MQO) techniques~\cite{sellis1988multiple}
to allow operations that share significant amounts of data to run underneath the
same scans or seeks, thereby reducing the overhead required to funnel data up
through the memory hierarchy. However, MQO presents a significant challenge when employed
in an interactive environment, where the results of the operation is displayed in-situ the coding/input environment, such as a Jupyter notebook cell. In this case, the optimizer will have to balance between maximizing operation throughput and
minimizing the latency required to compute output of the important ``to-be-displayed'' operations.

\subsection{Rewrite Rules}

Current approaches to planning queries for dataframes are either
(1) strictly imperative and do not perform any
query planning~\cite{mckinney2010data, R, dask}
or (2) declarative but do not support operations
beyond the traditional relational table operations~\cite{Armbrust:2015:SSR:2723372.2742797}.
The challenge of supporting declarative query processing across a wide range of dataframe operators is that the cost of extending rewrite rules beyond relational operations, to support spreadsheet and linear algebra operations, requires a significant development effort.
As a result, dataframe users either have to sacrifice performance, operate on a feasible subset of their data, or manually construct and profile various possible rewrite to determine the optimal approach to execute the query~\cite{optimizing-pandas}. When creating rewrite rules for dataframes, we have to consider (1) how to group the dataframe operations into queries and (2) when to rewrite the queries.

Manual query optimization on the part of the developer can be a daunting task due to the large number of possible ways to perform an operation~\cite{Wu2019}.\dlee{I don't think the example for sum is necessary, or we could simply say that there are X number of ways of performing certain operation. Add citation to Yifan's paper.}
In addition to the numerous ways of writing any given query at the API level,
the problem is further exacerbated by the fact that
there large, diverse set of operations beyond relational operators to consider when creating rewrite rules.
Traditional databases typically focus exclusively on relational
operators~\cite{???}.
Although there has been work to cover spreadsheet and linear algebra
operations~\cite{???} \william{Cite that pivot paper.} \simon{and stonebreaker scidb},
they still rely on the underlying rewrite rules made
with relational operations in mind.
Thus, there is simply too large of a space of API and functionality
to cover in comprehensively with proper rewrite rules.

In addition to the large query space to cover with rewrite rules,
we still have to consider when the query rewriting will occur.
Traditional databases operate in a declarative environment.
As a result, it is obvious that the query rewriting occurs
once the query is submitted.
However, there is no clear cut line to even differentiate separate queries for dataframes because most existing dataframe frameworks are imperative and execute operations eagerly.

\subsection{Optimizing user time}
Although there are dataframe implementations that already do query
rewriting~\cite{Armbrust:2015:SSR:2723372.2742797},
they operate within a lazy computation environment.
While laziness simultaneously solves the problem of
how to group the queries and when to rewrite the queries,
as we have already seen from Section~\ref{sec:modin}, the lazy execution model is not ideal for interactive dataframe workloads with a human-in-the-loop.

From the system's perspective, lazy evaluation seems like the best way to
conduct query optimization: the system will optimize the number of CPU
cycles it takes to get to an answer. However, from the user's
perspective, lazy evaluation removes the interactive capabilities of data frames, namely incremental query building
and checking intermediate results.
When the user checks the result of every
statement, it limits the amount of query planning possible in a system using
lazy execution.
Moreover, users are usually idle in the interactive workflow when thinking and re-writing the program.
When this happens, the CPU ends up waste cycles being
idle while the user is also idle or thinking.

Instead of focusing on minimizing the CPU cycles it takes to arrive at an answer, a more effective objective would be to minimize the overall wall clock time for an interactive
workflow.In other words, we prioritize the user's time over the CPU's time to provide a more productive environment for users. In order to be useful in a
general setting, a system that prioritizes a user's time in an interactive
environment should also be able to perform as well as the state-of-the-art
systems that prioritize a CPU's time when running in a batch environment or
in the worst case for interactive workflows.

Thus, though rewriting dataframe ``queries'' may appear to be a solved problem,
dataframes bring a unique set of problems that will require their own unique approach,
while simultaneously borrowing from approaches used in traditional databases.

\subsection{Materialization and Reusing Results}
The incremental and exploratory nature of dataframe query construction
leads to nonlinear code paths
where users revisit the same intermediate results repeatedly
to refine the query results.
Recomputing the same intermediate result repeatedly
is time-consuming and wasteful. Ignoring re-computation can also be costly for operations such as data loading, which often does not need to be re-executed
We envision the \modin optimizer to automatically materialize and reuse intermediate results
to significantly reduce execution time by removing redundant computation across statements.

To concretize the discussions of the research challenges
associated with this optimization, consider the following example.
\begin{lstlisting}
r1 = df.groupby(...).count().query("c1 > 0")
r2 = df.groupby(...).count().query("c2 <= 0")
\end{lstlisting}
Intermediate results refer to the output of any combination of operations.
In this example, the intermediate result accessed by both \code{r1} and \code{r2}
is \code{df.groupby(...).count()},
which is computed twice when executing the statement verbatim.
We could eliminate the redundant computation
by identifying this common subexpression in both statements
and substitute it with a reference to the intermediate results.
This is a common technique in compilers known as common subexpression elimination\cite{cocke1970global}. Applying these techniques to dataframes is non-trivial due to the tradeoff between storage cost and compute savings.

Formally, the objective of this optimization problem is to trade
\textit{materialization overhead}, including both the storage and the time to persist the results,
for \textit{reduced execution time} due to reuse.
As we can see from the example above, there are two components to this optimization.
First, we need to identify reusable intermediate results,
which can be accomplished using standard program analysis.
The second component is deciding whether an intermediate result should be stored and reused,
and the optimizer needs to utilize storage in a way that maximizes
saved compute---small
objects that are time-consuming to compute and reused frequently
should be prioritized over large objects that are fast to compute.
Storage can refer to either memory or disk,
depending on whether reuse takes place within a single session
or across multiple sessions.
A storage budget is often imposed, especially in the single-session case, making the problem NP-Hard (by reduction from the Knapsack problem).
Effective solutions need to adapt to variable reuse patterns.

\subsection{Cost Modeling and Optimization}

Once we have identified a set of simple rewrite rules,
we will develop a simple cost model for optimization purposes.
Since much of the data for dataframes sits in-memory, we will need
to develop a cost model that is appropriate for hierarchical
memory systems\cite{manegold2002}. However, we do not simply
want to model the cost for the CPU's time. Because of the interactive
nature of dataframes, we will want to model the cost to
both the user's and the CPU's time and prioritize the
optimization of the user's time.

For example, in a case where the user is engaged with a challenging task that requires significant think time between executed statement,
it is possible to begin processing parts of that statement immediately,
and complete the processing of the statement during
the user's think time. For exceptionally complex statements, such as  nested joins, it is possible to wait for the next
statement to see whether the user provides a filter or some
other operator that would reduce the amount of computation necessary.
This way, the system can be selectively lazy and choose when
or if to delay computation, while
optimizing for the user's valuable analysis time.

Asynchronous computing is a middle ground that will allow
us to choose whether or not to be lazy for any given
statement without placing any of this decision burden
on the user. When the user submits a statement,
the cost modeler will determine whether or not to
immediately execute that query based on the cost
model we develop to model the user's time. If the
system chooses to delay computation, when the user
submits their next statement, the cost modeler
will again determine whether to execute immediately
given the new statement from the user.

In order to develop a cost model for the user's time,
we will first have to study how users interact with the
system. Understanding what operations typically follow
others, when users pause for thinking, and how long
pauses are. This study must be conducted on a large
number of users to ensure generalizability across tasks and datasets,
and will be an important first step in
modeling users behavior when interacting with dataframes.
Modeling the user behavior is a common practice in the HCI literature \cite{Battle2019}.

\section{Introduction}
The DataFrame has become a staple component of modern data science.
It is often used to clean or filter datasets, gather summary
statistics, and to query data. The success of the DataFrame can seem
somewhat counter-intuitive because many DataFrame systems violate
fundamental database principles in their implementation and offer
additional functionality and features that traditional database
systems do not. However, DataFrame systems are popular primarily
because of the deviations from conventional wisdom in database
systems. The primary reason DataFrame systems are so popular is
because the data has an order, and an order that is preserved through
transformations, similar to the spreadsheet model. Another important
design of the DataFrame is that queries can be built one small
component at a time, and intermediate results can be checked for
validity. In a traditional DBMS using SQL, intermediate results can
only be checked by independently executing a subquery, however DataFrame
technologies allow users to check intermediate results and build queries
one statement at a time. Depending on the use-case, other features may be
important to users, e.g. interoperability between linear and relational
algebra, indexing, and virtually unbounded user defined functions. Users
who prefer DataFrame systems typically use it in an interactive
environment.

Because of these design deviations, DataFrame systems are difficult to
optimize with the best practices from traditional database query
optimization and have generated a large body of work studying how to
bridge the gap between traditional database systems and DataFrame
technologies [CITE SOME]. Unfortunately, many of the systems that attempt
to bridge this gap do not take advantage of all the work done by the
Database community in query optimization. They additionally push a
large portion of the optimization
burden onto the user, often resulting in a system that is both harder to use
and under-optimized. For example, many DataFrame systems use lazy execution to
construct a DAG of operations and only compute an answer when it is
needed. From the system's perspective, this seems like the best way to
conduct query optimization: the system will optimize the number of CPU
cycles it takes to get to an answer. However, from the user's
perspective, lazy evaluation removes two components of the DataFrame
system that make it more useful than a DBMS: incremental query building
and checking intermediate results. When the user checks the result of every
statement, it limits the amount of query planning possible in a system using
lazy execution. Users in the
interactive environment also spend a large amount of time thinking in a
typical workflow. When this happens, the CPU ends up waste cycles being
idle while the user is also idle or thinking.

Instead of focusing on minimizing the CPU cycles it takes to arrive at an answer, a more useful
metric would be to minimize the overall wall clock time for an interactive
setting. In this way, we prioritize the user's time over the CPU's time and
provide a more productive environment for users. In order to be useful in a
general setting, a system that prioritizes a user's time in an interactive
environment should also be able to perform as well as the state-of-the-art
systems that prioritize a CPU's time when running in a batch environment or
in the worst case for interactive workflows.

DataFrames are not SQL systems, but this does not mean that we should
completely throw out all of the research that has been done into optimizing
SQL when designing and building DataFrame systems. We should be borrowing
from and using SQL techniques to optimize queries in DataFrame systems. To
realize this vision, we built a system called Modin as a launchpad for
research into how to bridge the gap between DataFrame and Database systems.

\section{The origins of the DataFrame}
This section will contain the origins of the DataFrame text.

\section{Use cases and usage}
This section will contain the Use cases and usage text.

\section{Modin: Bridging DataFrames and Databases}
This section will contain the Modin research plan text.

\subsection{Current improvements over Pandas}
For example, multiprocessing.

\subsection{Query optimization}
Our plans for Query Optimization

\subsection{System level optimization}
Partitioning, Serverless, etc.

\subsection{API and other HCI}
Smaller API based on IR

\section{Conclusion}
This is the Conclusion section text.

\balance

\section{Acknowledgments}
I would like to thank the Emperor for squashing the rebellion.

\bibliographystyle{abbrv}

\section{Related work}\label{sec:ext}
While our focus on pandas\xspace is driven
by its popularity, in this section,
we discuss other existing dataframe
and dataframe-like implementations.
Table~\ref{tab:comparison} outlines the features
of these dataframe and dataframe-like implementations.
We will discuss how existing dataframe implementations fit into our framework,
thus showing how our proposed research is applicable to these systems.

\rebuttal{\stitle{Data model and algebra.}}
To the best of our knowledge,
an algebra for dataframes has never
been defined previously.
Recent work by Hutchinson et al.~\cite{lara, laradb}
proposes an algebra called Lara that combines
linear and relational algebra, exposing
only three operators:
\code{JOIN}, \code{UNION}, and \code{Ext} (also known as ``flatmap'');
however, \removed{the} \rebuttal{dataframe} metadata manipulation operators \removed{below}
\rebuttal{are not supported.}
\removed{would not be possible in Lara without
placing the metadata as part of the data.}
Other differences stem from the flexible data model
and lazily induced schema.
\removed{That said,} \rebuttal{We will draw on
Lara as we continue to refine our algebra.}

\rebuttal{\stitle{Dataframe Implementations: R.}}
As we discussed in Section~\ref{sec:dataframe-history},
the R language (and the S language before it),
both support dataframes in a manner similar to pandas\xspace
\rebuttal{and can be credited for initially popularizing
the use of dataframes for data analysis}~\cite{ihaka1996r}.
\rebuttal{R is still quite popular, especially
among the statistics community.}
An R dataframe is a
list of variables,
each represented as a column, with the same number of rows.
While both the rows and columns in an R dataframe have names,
row names have to be unique;
thus the pandas\xspace dataframe is more permissive than the R one.
As shown in Table~\ref{tab:comparison}, R supports all of the operations in our algebra.
The R dataframe fully captures our definition of a dataframe, and
thus, implementational support of R dataframes requires only conforming the R API
to our proposed algebra.
External R packages such as readr, dplyr, and ggplot2 operate on R dataframes and provide functionalities such as data loading, transformation, and visualization, similar to ones from the pandas\xspace API~\cite{tidyverse-R,tidy-data}.

\stitle{Dataframe-like Implementations.}
Some libraries provide a functional or
object-oriented programming layer
on top of relational algebra.
These libraries include SparkSQL dataframes~\cite{sparksql-func},
SQL generator libraries like QueryDSL~\cite{querydsl} and JOOQ~\cite{jooq},
and object relational-mapping systems (ORMs) such as Ruby on Rails~\cite{rubyrails}
and SQLAlchemy~\cite{sqlalchemy}.
All of these systems share some of the benefits with respect to
incremental query construction mentioned in Section~\ref{sec:interactivity}.
However, they generally do not support the richness and expressiveness
of \removed{the} dataframes \removed{data model and algebra},
including \removed{keys aspects like} ordering of rows, symmetry between rows and columns,
and operations such as transpose.

SparkSQL and Dask are scalable dataframe-like systems
that take advantage of distributed computing to handle large datasets.
However, as shown in Table~\ref{tab:comparison},
Spark and Dask do so at the cost of limiting
the supported dataframe functionalities.
For example, a dataframe in SparkSQL does not treat columns
and rows equivalently and requires a predefined schema.
As a consequence, SparkSQL does not support \code{TRANSPOSE}
and is not well optimized for dataframes
where columns substantially outnumber rows.
Thus, SparkSQL \removed{does not match our definition
of a dataframe and is much} is closer to a relation
than a dataframe.
Koalas~\cite{koalas}, a wrapper on top of the SparkSQL API,
attempts to be more dataframe-like in the API
but suffers from the same limitations\removed{as the underlying SparkSQL framework}.
\techreport{
\par \removed{On the other hand,} Dask enables distributed
processing by partitioning along the rows
and treating each partition as a separate ``dataframe'',
thus acting as a ``meta-dataframe''.
Since ordering and transpose are ill-defined for a group of dataframes,
Dask fundamentally cannot support \removed{such} operations that rely on row-ordering.
The set of operations supported \removed{in Dask
is determined by which dataframe operations}
\rebuttal{are restricted to those that}
can be combined into a single output based on the resulting,
constituent dataframes.
These include \rebuttal{embarassingly parallel} operations, such as filter, aggregation, groupby, \rebuttal{and} join.
}

\techreport{
Unlike these systems, \modin treats the dataframe data model and algebra
as first-class citizens, as opposed to a means to enable distributed processing,
addressing challenges in dataframe processing
in systems like pandas\xspace and R at scale,
while not sacrificing the convenient functionalities
that have made dataframes so popular. We advocate that our research vision around the data model proposed in this paper is a key component towards this more holistic approach for optimizing dataframe systems.
}

\begin{table}[t]
\centering
\small
\begin{tabular}{|l|l|l|l|l|l|}
\hline
{\bf Feature}         & \cellcolor{blue!25}{\bf Modin}      & \cellcolor{blue!25}{\bf Pandas\xspace}    & \cellcolor{blue!25}{\bf R}           & \cellcolor{red!25}{\bf Spark}      & \cellcolor{red!25}{\bf Dask}        \\ \hline
Ordered model   & \checkmark & \checkmark & \checkmark  & \checkmark$^\dagger$ &             \\ \hline
Eager execution & \checkmark & \checkmark & \checkmark$^+$  &            &             \\ \hline
Row/Col Equivalency & \checkmark & \checkmark & \checkmark  &            &             \\ \hline
Lazy Schema  & \checkmark & \checkmark & \checkmark  &            & \checkmark    \\ \hline
Relational Operators   & \checkmark & \checkmark & \checkmark  & \checkmark & \checkmark  \\ \hline
MAP             & \checkmark & \checkmark & \checkmark  & \checkmark & \checkmark  \\ \hline
WINDOW          & \checkmark & \checkmark & \checkmark  & \checkmark & \checkmark  \\ \hline
TRANSPOSE       & \checkmark & \checkmark & \checkmark  &            &             \\ \hline
TOLABELS       & \checkmark & \checkmark & \checkmark  &            & \checkmark* \\ \hline
FROMLABELS    & \checkmark & \checkmark & \checkmark  &            &             \\ \hline
\end{tabular}
\vspace{-5pt}
\caption{Table of comparison between dataframe and dataframe-like implementations. Blue indicates
dataframe systems, red indicates dataframe-like implementations.
$\dagger$: Spark can be treated as ordered for some operations.
$+$: R dataframe operators can be invoked lazily or eagerly.
*: Dask sorts the dataframe by the row labels after \texttt{TOLABELS}.
}\label{tab:comparison}
\vspace{-15pt}
\end{table}

\section{Single Statement Acceleration}\label{sec:singlestatement}
\devin{Renormalize to focus on the unique features of the data model that make research interesting}

Based on users' common behaviors, there are two common database optimizations we can use to accelerate the execution of individual statements in dataframes: computing partial results
(\ref{sec:pre-suffix}) and approximate computation (\ref{sec:approx}).

\subsection{Prefix or Suffix Computation}\label{sec:pre-suffix}

Dataframe users often build their query incrementally through trial-and-error. As illustrated in Section~\ref{sec:usecase},
the trial and error style typically involves printing some subset
of the rows and columns through the
\code{head}, \code{tail}, or \code{print} operation.
The \code{head} and \code{tail} commands print the first
or last \code{n} rows (5 by default), respectively.
Printing a dataframe
shows both the first and last 5 rows.
This is also another case where the user relies heavily on the
order of the data in their mental model. When a user prints
the first \code{n} rows, they expect to see the first
\code{n} rows from the actual data that was ingested,
and they expect that the system will print the same
\code{n} rows each time. The performance of displaying these first and last
\code{n} rows is important as users rely on these operations to verify the correctness of their data and query and subsequently make decisions about what to do next.

While it is possible to use strategies similar to those that optimize for the \code{LIMIT} clause in RDBMSs \cite{kim2018optimally}, additional
consideration must be made for the \code{ORDER BY} clause to ensure that the order is the same every time
time the user prints the dataframe. To avoid computing the \code{ORDER BY}
on every computation,
the first and
last \code{n} rows can be logically removed as separate tables,
and perform computation on those
tables to print the results faster. The remaining data can
computed separately following the lazy evaluation paradigm,
enabling query planning on the remaining data. In the case
that the query modifies the order of the data, the
printed rows will have to wait until the \code{ORDER BY} to
ensure that the user sees the data in the order they have
specified. In these cases, there is a limit to the amount of
query planning that can be applied because the print forces
the \code{ORDER BY}. We will discuss ways that query planning
can be used and improved for dataframes in
Section \ref{sec:acrossstatement}.

\subsection{Approximate Computation}\label{sec:approx}

Approximate computation is another way to provide users with faster query responses to facilitate interactive workflows. In some cases, the user may be content to see an approximation
rather than needing to wait for the full result. Existing RDBMS approximation
techniques for online aggregation~\cite{Fekete2018,raman2002partial,lang2014partial,viglas2002rate,rahman2017ve},
barchart, histogram, scatterplot, and map plot generation~\cite{kim2015rapid,ding2016sample+,park2016visualization},
histogram matching~\cite{macke2018adaptive}, stratified sampling~\cite{agarwal2013blinkdb}, and
error estimation~\cite{zeng2014analytical,park2018verdictdb} are directly applicable
toward accelerating individual dataframe operations. However, dataframe semantics
offer some unique opportunities for further speedups via approximation.

\dorx{We don't need to make the next two points about top/bottom $K$.
They're still applicable outside of the prefix/suffix setting.}

\devin{I think in this context the top/bottom $K$ present unique challenges
for dataframes over SQL, which is why that is the focus.}

\dlee{I agree with dorx and its also confusing since 4.1 talks about prefix/suffix issues already. The focus for this subparagraph should be the point about aggregation.}

\smacke{Agree with Dores that it's confusing in light of 4.1 (and it's my fault).
There is a fundamental difference though,
prefix / suffix section discusses accelerating exact computation of top / bottom $K$
while moving remainder to background, this section focuses on the case that
remainder cannot be moved to background for exact computation, and can only be
moved to background if we approximate top / bottom $K$. I'll work on contrasting
so that it's clear why this is a separate issue.}

\stitle{Cumulative Aggregates.}
Existing dataframe libraries like pandas\xspace display the top and bottom $K$
rows whenever an evaluation is triggered. In a typical relational model
with no notion of order, any $2K$ rows could be chosen for display, but
dataframes, which have an inherent order, must be precise in order to
satisfy the expected semantics. This can create bottlenecks when the
computation required to display the bottom $K$ rows depends on the
result of the computation for all previous rows. For example,
a cumulative sum or cumulative max must be done in order from the
top of the dataframe to the bottom, causing significant latency
before the bottom $K$ rows can be displayed.

While it is well known that an aggregate like \code{MAX}
cannot be approximated~\cite{mozafari2015handbook},
the user may be satisfied to see approximations of cumulative sums or means
in the bottom $K$ rows that
either update progressively as more data is processed, or that satisfy a
probabilistic accuracy requirement.

\stitle{Estimating Counts on Filtered Dataframes.}
Along with the top and bottom $K$ rows, dataframe libraries
like pandas\xspace typically show summary statistics like \code{COUNT}
after each operation.
If a user applies a filter on a dataframe, without prior knowledge
it is impossible to know the exact number of rows passing the filter
until the full computation has completed. One strategy is to
automatically identify such cases and adaptively estimate the
selectivity of the filter on-the-fly, again progressively updating the estimate as more tuples passes through the filter.

\stitle{Approximating Expensive Filters.}
For a filter that is both selective and expensive
(e.g., one that performs classification on
a dataframe where one of the columns contains videos), there might not be any row in the top or bottom
$K$ that satisfies the filter. As such, determining the top and bottom
$K$ rows that pass the filter can itself be a high-latency
operation, even without a complete filter application.
In this case, dataframes present a perfect use case for
{\em exploiting correlations}~\cite{joglekar2015exploiting}
between the filtering attribute
and other attributes in order to quickly approximate
the top and bottom $K$ rows that might pass the filter and
quickly display them to the user, refining as
additional filter evaluations are performed.

\stitle{Approximation and Asynchrony.}
When used in conjunction with \modin's
inherent asynchronous background execution,
exact results may be scheduled in the background for
later verification (as in~\cite{moritz2017trust}).
This may result in many exact queries getting queued in the
background as the user rapidly issues statements and achieves
immediate approximate feedback. To increase throughput of
these statements that build up in the execution queue,
we can apply {\em multiquery optimization techniques}
and to take advantage of opportunities for shared computation,
to be described in detail in Section~\ref{sec:mqo}.

Overall, we envision that the unique semantics of dataframe
operations open up a rich design space of approximation
techniques made all the more relevant by the interactive nature of dataframe usage.

redpajama_set_name: RedPajamaArXiv