# Compression and In-Situ Query Processing for Fine-Grained Array Lineage

JinJin Zhao, Sanjay Krishnan
ChiData, University of Chicago<EMAIL_ADDRESS>

###### Abstract

Tracking data lineage is important for data integrity, reproducibility, and
debugging data science workflows. However, fine-grained lineage (i.e., at a
cell level) is challenging to store, even for the smallest datasets. This
paper introduces DSLog, a storage system that efficiently stores, indexes, and
queries array data lineage, agnostic to capture methodology. A main
contribution is our new compression algorithm, named ProvRC, that compresses
captured lineage relationships. Using ProvRC for lineage compression result in
a significant storage reduction over functions with simple spatial regularity,
beating alternative columnar-store baselines by up to 2000x. We also show that
ProvRC facilitates in-situ query processing that allows forward and backward
lineage queries without decompression - in the optimal case, surpassing
baselines by 20x in query latency on random numpy pipelines.

##  I Introduction

As data scientists work with ever more complex data workflows, data lineage is
a vital tool to ensure the reproducibility and reliability of results. Data
lineage systems represent input-to-output data relationships caused by
applying some data manipulation operation on one or more datasets. After a
series of operations, forward queries in a lineage system identify all final
output data influenced by some initial input, and backward queries identify
all initial input data relevant to some final output. However, answering such
queries in a purely posthoc way can be as expensive as running the original
program — consider running a lineage query on an overnight reporting job in a
data warehouse. Thus, most practical lineage systems construct some form of a
_lineage materialization_ to improve performance [32]. This materialization
captures key input-to-output relationships to speed up future forward and
backward queries.

For fine-grained lineage, these materializations quickly hit a problem of
scale. An uncompressed materialization for a point-wise summation of two
matrices of 1M cells each can be 10s of MBs (see Section VII). In other words,
the stored lineage may often be larger than the data itself. Fortunately, this
data is often highly structured and repetitive. The critical insight of this
paper is that particular lineage structures can be exploited to build storage-
efficient compressed lineage tables and fast query strategies over these
tables that do not require decompression. While it might be obvious that
lineage materializations can be effectively compressed, building compressed
lineage tables that can be queried in situ is an open technical challenge
addressed in this paper. We contribute DSLog: a system that facilitates the
efficient storage, query, and reuse of fine-grained array-like lineage. DSLog
is an indexing service that stores lineage relationships captured by lineage
capture frameworks. Its API ingests lineage for data science workflows in
which the data is structured in multidimensional arrays (or data types
resembling arrays). Integer-indexed multidimensional arrays are a universal
interface in data science that can represent data frames, documents, time
series, and images. Over the relationship captured in DSLog, users can
efficiently make two types of queries across multiple workflow steps: forward
queries that find all output data contributed to by an input and backward
queries that find all input data contributing to an output.

Several architectural insights are contributed here: (1) individual lineage
relationships are automatically encoded in a novel compressed representation;
(2) the query processing of forward and backward queries is in situ over the
compressed representation, and (3) the captured lineage is stored in a
normalized relational format with “index reshaping” that can be reused for
future calls to the same operation. The basis of these architectural insights
is the ProvRC lineage compression algorithm. This algorithm is used in DSLog
to exploit the high degree of spatial coherence between input and output
indices of common data science operations, using a novel combination of multi-
attribute range encoding and relative indexing techniques.

In the implementation, we integrate DSLog with the Python data science stack.
We demonstrate experiments where the prototype captures fine-grained lineage
capture with arrays of up to a million cells. The ProvRC algorithm achieves a
considerable storage reduction over operations with simple spatial regularity.
It achieves an approximately 0.3% storage ratio over raw storage and beats
alternative columnar-store baselines by up to 1400x, with minimal overhead. We
also demonstrate significant performance improvements in the downstream query
processing, performing queries over 100,000 input cells in $<1$ second in the
optimal case, beating the same baselines by up to 1500x. Finally, we show that
the lineage reuse capability enabled by this compressed representation has
high coverage over the numpy library, achieving input-independent reuse on 99
of the 136 evaluated numpy operations.

##  II Background

First, we motivate our problem setting and describe the related work.

###  II-A Problem Setting and Scope

An _array_ of data is a rectangular data collection indexed by tuples of
positive integers. Each value in an array is called a _cell_. The cells can be
fully indexed by their position along each array _axis_. The length of the
tuples indexing an array defines its _shape_. Arrays can represent any ordered
data structure and act as a useful universal data type for data science
operations.

  * •

A dataset of machine learning examples can be represented as a 2D array of
feature vectors, with each cell represented by a floating point number.

  * •

An image can be represented as a 3D array of RGB pixels, each represented by
an unsigned integer 0-255.

  * •

A document can be represented as a 1D array of strings.

  * •

A relational table can be represented as a 2D array where the rows and
attributes are organized in canonical order.

An array program is simply an operation that takes as input a set of input
arrays and outputs another array. For example,

⬇

Y = foo(X1,...,XN)

the operation foo applies to arrays $X^{1},...,X^{N}$ and outputs another
array $Y$.

_Fine-grained lineage_ for a single operation refers to contribution
relationships between input and output cells in such operation: which elements
in the input array contribute to the values of each output element. For any
individual operation, we assume that we have a capture method where, given a
cell in an output array of an operation, we can find all the cells from the
input arrays that “contributed” to that output cell. Many pre-existing
prototype systems capture and generate some form of lineage for data science
[39, 40, 41, 45, 36, 34, 37, 47, 29, 24, 9]. DSLog allows for the
incorporation of this lineage regardless of capture methodology. In Section
VII, we present our implementation of different types of these systems to
generate such lineage for evaluation of DSLog. DSLog work perpendicular to
individual operation lineage capture to efficiently store, query, and reuse
lineage across multiple operations.

###  II-B Architecture

Next, we describe the high-level architecture of DSLog and where it sits on
the data science lineage workflow. When users create array-based data science
pipelines, fine-grained lineage is captured based on the specified capture
techniques. While DSLog does not provide a complete solution for capture, it
does support capture in cases where the lineage can be reused. Captured
lineage is stored in a compressed format within DSLog using ProvRC, and users
can issue forward and backward queries over this to get information about
their workflow across multiple operations. DSLog responds to the queries with
an in-situ algorithm over the stored compressed lineage. In this way, storage
and queries are fully supported.

##  III DSLog: An Efficient Lineage Management System

(A) Python Code Representation
---
⬇ A = numpy.array([[0,3],[1,5],[2,1]]) B = numpy.sum(A,axis=1)

(B) Relational Representation
---
$b_{1}$ | $a_{1}$ | $a_{2}$
1 | 1 | 1
1 | 1 | 2
2 | 2 | 1
2 | 2 | 2
3 | 3 | 1
3 | 3 | 2

(C) Lineage of First Row of Relational Representation
---

Figure 1: We present a typical operation that sums over the second axis of an
array (A), the relational representation of such operation (B), and an array
visualization of the lineage relation described by the first row of the
relational representation (C).

DSLog is a system that indexes input-to-output lineage relationships. We
describe the API and the basic data model in this section.

###  III-A DSLog API

First, we present the basic API that allows an application developer to
connect a lineage system with DSLog.

Defining Tracked Arrays.  DSLog allows users to define named Arrays with a
specified shape. These are the arrays that are tracked through a data science
workflow.

⬇

Array(name: String, shape: Integer[])

//defines an array with the specified shape

Defining Lineage.  We can capture the lineage of these Arrays with a lineage
object.

⬇

Lineage(arr1: String, arr2: String, capture: Object)

//defines the lineage relationship between two arrays

//capture(i: Long[]) returns cells in arr2 that are linked to the cell in arr1
at index i

The user specifies a capture method to record lineage between arr1 and arr2. A
capture method generates an iterator where, for each cell in the output array,
we can retrieve the spatial indices (of the cells) in the input array with a
contribution relationship. The user’s desired capture method will be called
internally to populate the lineage object in the storage manager.

DSLog enables efficient lineage capture for multiple arrays operated over one
operation.

⬇

register_operation(op_name: String, in_arrs: String[], out_arrs: String[],
capture: Object[], op_args: Any[], reuse: Optional Boolean)

//registers an operation where provenance is captured between input and output
arrays

This is implemented with an operation registration API consolidating lineage
within an executed data science operation. This method internally creates
lineage between linked input and output array pairs of op_name and registers a
record between those lineage tables and the operation metadata.

The API enables automatic capture with index reshaping when ”reuse” is
enabled. In that case, the system tries to generate lineage solely based on
previous registrations without requiring a pre-defined capture methodology in
future API calls with the same operation name. Since lineage capture is
usually expensive, this can significantly reduce the cost of lineage in data
science overall.

Queries Over lineage.  The user can issue forward and backward queries to the
storage manager over Arrays. These queries can be expressed in a single query
interface.

⬇

prov_query(X: String[], query_cells: Integer[[]])

//retrieves lineage between cells in query_cells of the first Array and the
cells in the last Array along the path X

Based on a query path, $X$, the method prov_query retrieves the cells in the
last Array linked to specified cells, query_cells, of the first Array. This
query path is expressed as a sequence of Arrays, $X:[X^{1},\dots X^{n}]$. For
example, consider the operations Y = foo(X) and Z = bar(Y). One possible query
path is $[X,Y,Z]$, representing a forward path from the cells of $X$ to that
of $Z$. Another possible query path is $[Z,Y,X]$, representing a backward path
from the cells in $Z$ to those of $X$. If we query along these paths, we can
return fine-grained lineage between the cells in $Z$ and the cells in $X$.

###  III-B Relational Data Model

DSLog captures lineage in a relational data model. Every contribution lineage
relationship is a mapping between input and output array cells [10, 27, 21,
42]. Such a mapping is elegantly represented as a relation. Let $A$ be an
m-dimensional input array whose axes are denoted with $a_{1},a_{2},...,a_{m}$.
Similarly, the output array, $B$, is an l-dimensional array with axes denoted
with $b_{1},b_{2},...,b_{l}$. The lineage relationships between $A$ and $B$
can be represented in a relation over the dimensions
$R(b_{1},b_{2},...,b_{l},a_{1},a_{2},...,a_{m})$. Each row in the relation
corresponds to a single output lineage $B[b_{1},b_{2},...,b_{l}]\leftarrow
A[a_{1},a_{2},...,a_{m}]$.

As a concrete example, let us consider a simple array operation over an array
with shape 3x2: B $=$ numpy.sum(A, axis = 1), as shown in Figure 1. This
operation uses the numpy syntax and sums over one of the axes of the array
(A). A table representation of the lineage of this operation can be made with
DSLog (B). Each attribute of the table represents an axis of the input or
array, and each value of the table represents an index on that axis.
Therefore, each row defines two cells using the axis indices - one in the
input array and one in the output array. The rows represent lineage
relationships between input and output cells. For example, the first row shows
that the element at index (1,1) in the input contributes to the element at
index $1$ in the output (C).

This format allows for compositional forward and backward queries that span
multiple operations. The lineage relationship over multiple operations can be
reconstructed from these tables with a natural join operation [21]. For
example, given $R^{1}$ is the lineage of the operation $A\xrightarrow{}B$ and
$R^{2}$ is the lineage of $B\xrightarrow{}C$, we can find the lineage of
$A\xrightarrow[]{}C$ from $R^{1}\bowtie R^{2}$. With relational tables, we
achieve data independence; a user can still request forward and backward
lineage queries across multiple tables independent of exactly how the data are
organized within those tables.

##  IV Compression Algorithm

DSLog stores a collection of ingested input-and-output lineage relationships
in a compressed format that exploits contiguous runs of integer indices. We
will be using the lineage table from Table 1 (B) as the running example for
each step of this algorithm.

Notation.

  * •

$R$ denotes a table storing the lineage (as described in Section III.B) for a
relationship between arrays $A\to B$.

  * •

Lower case $r$ will be used to denote a row from $R$.

  * •

$R$ has attributes

$\Omega_{R}=\Omega_{A}\cup\Omega_{B}=\\{b_{1},b_{2},...,b_{l},a_{1},a_{2},...,a_{m}\\}.$

  * •

The . notation is used to reference a particular attribute.

###  IV-A Lineage Compression Algorithm

The ProvRC algorithm has two main subroutines:

  * •

Multi-Attribute Range Encoding. Express the relation as a union of
multidimensional “ranges”.

  * •

Relative Value Transformation. Expresses an input attribute numerically
relative to an output attribute.

#### Step 1. Multi-Attribute Range Encoding over Inputs

The first step compresses rectangular ranges over the attributes corresponding
to the input array cells. This step automatically compresses lineage that
match the pattern (1). We use a generalized range encoding form over the input
axis columns. Range encoding has been used in previous compression techniques
[30]. The basic idea is, given a set of integers, one can represent the set as
a union of ranges, e.g.,

$\textsf{range}(\\{1,2,3,4,9,12,13,14,15\\})=\\{[1,4],[9],[12,15]\\}.$

We extend this basic principle to the multi-attribute setting. We iteratively
encode each attribute in $R$ into ranges. This algorithm compresses
rectangular ranges over attributes of array $A$. Figure 2 demonstrates this
method over a simple array operation that aggregates a 4x4 array into a 1x1
array (A). With multi-attribute range encoding, the input array’s indices can
be represented as ranges, and we can encode the relationship between those
ranges and the output array (B).

(A) Lineage of an Aggregate Operation
---

(B) Multi-Attribute Range Encoding Reduction
---

Figure 2: This figure shows an example of multi-attribute range encoding,
where the all-to-all relationship between four cells in one array and one cell
(A) in another array can be represented succinctly with ranges (B).

First, $R$ is sorted in numeric order over attributes in order of
$b_{1},b_{2},...,b_{l},a_{1},a_{2},...,a_{m}$. We then first apply the multi-
attribute range encoding for input attributes. For each input attribute
$a_{i}\in\\{a_{m},\dots a_{1}\\}$ and $r\in R$, we add the row into a range,
$S$, and then merge the set:

  * •

If $S=\emptyset$, set $S:\\{r\\}$.

  * •

Else if $S\cup\\{r\\}$ is contiguous on $a_{i}$, set $S:S\cup\\{r\\}$.

  * •

Else, replace all rows in $R$ that are contained in $S$ with one row
$r^{\prime}$, s. t. $r^{\prime}.\omega=r.\omega$ for
$\omega\in\Omega_{R}\setminus\\{a_{i}\\}$ and $r^{\prime}.a_{i}=[low,high]$.
Then, set $S:\emptyset$.

We state that a set of rows, $S$, form a rectangular range, $[low,high]$ on
input attribute $a_{i}\in\Omega_{A}$, if, all attributes
$\Omega_{R}\setminus\\{a_{i}\\}$ have the same value and the set of
$\\{s.a_{i}|s\in S\\}$ is equivalent to the range of integers spanning
$\\{low,...,high\\}$ (inclusive on both ends). Table I shows the example
output of this step over our example lineage table. Notice how this step
efficiently reduces the number of rows in the lineage table.

$b_{1}$ | $a_{1}$ | $a_{2}$
---|---|---
1 | 1 | 1
1 | 1 | 2
2 | 2 | 1
2 | 2 | 2
3 | 3 | 1
3 | 3 | 2

$\rightarrow$ $b_{1}$ $a_{1}$ $a_{2}$ 1 1 [1, 2] 2 2 [1, 2] 3 3 [1, 2]

TABLE I: Example Output of Multi-Attribute Range Compression

#### Step 2. Relative Value Transformation and Output Range Encoding

In the second step, we apply a relative value transformation between the input
and output attributes and then execute the multi-attribute range encoding on
the output attributes. This step automatically compresses lineage that matches
both patterns (2) and (3).

The relative transformation exploits the cases in lineage relations where, for
a set of rows, $S$, and some input and output attributes, $a_{i}$, $b_{j}$,
for all $s\in S$, we have:

$s.a_{i}=s.b_{j}-\delta$ $\delta=s.b_{j}-s.a_{i}$

, for some constant $\delta$. This is observed in many lineage relations -
e.g., convolutions, one-to-one operations, matrix multiplication, and
rotations. Figure 3 demonstrates this method over a simple one-to-one array
operation over a 2x1 array (A). With relative value transformation, the input
array’s indices are considered relative to the output array’s indices (B).
This introduces new opportunities for range encoding over the output indices
(C).

(A) Lineage of a One-to-One Operation
---

(B) Relative Transformation
---

(C) New Range Encoding Opportunities
---

Figure 3: This is an example of relative transformation and output range
encoding, where, given the one-to-one relationship between two 2x1 arrays (A),
we can perform a relative indices transformation on the first array (B),
introducing new range compression opportunities for efficient encoding (C).

We perform this algorithm as follows. For every input attribute,
$a_{i}\in\Omega_{A}$, and output attribute, $b_{j}\in\Omega_{B}$, we append a
new column to $S$ named $a_{i}b_{j}$ that contains the value $b_{j}-a_{i}$. If
$b_{j}$ is a range, we subtract $a_{i}$ from both range values. Our insight is
that, for any row $r\in R$ and input attribute, $a_{i}$, given that we know
the output attributes, only one of the values in $a_{i},a_{i}b_{1},\dots
a_{i}b_{l}$ is needed to determine the value of $a_{i}$.

We apply the same multi-attribute range encoding algorithm over the output
attributes $b_{j}\in[b_{l},\dots b_{1}]$, with simple modifications that
account for the above insight. We define that set of rows, $S$, form a range
on attribute $b_{j}\in\Omega_{B}$ if all attributes
$\Omega_{B}\setminus\\{b_{j}\\}$ have the same value, and, for all
$a_{i}\in\Omega_{A}$, there exists a non-empty subset of
$\\{a_{i},a_{i}b_{1},\dots a_{i}b_{l}\\}$ where all the attributes have the
same value and the set of $\\{s.b_{j}|s\in S\\}$ can be represented as a
range. When we compress over output attributes by replacing $S$ with a
singular row in the multi-attribute range encoding algorithm, we only preserve
the values in the non-empty subset rather than every value in
$\\{a_{i},a_{i}b_{1},\dots a_{i}b_{l}\\}$. If the absolute value is preserved,
the lineage matches pattern (2); otherwise, it matches pattern (3).

Let us see an example of how this works over the range-encoded example table
from the first step (Table I). In Table II, the values in $a_{1}$ are the same
as $b_{1}$ for each row. Adding the column $a_{1}b_{1}$ introduces an
attribute match in $a_{1}$ for the multi-attribute range encoding algorithm
that did not exist before. We can now compress the previous results to an even
more concise representation.

$b_{1}$ | $a_{1}$ | $a_{2}$ |
---|---|---|---
1 | 1 | [1, 2] |
2 | 2 | [1, 2] |
3 | 3 | [1, 2] |

$\rightarrow$ $b_{1}$ $a_{1}$ $a_{1}b_{1}$ $a_{2}$ $a_{2}b_{1}$ 1 1 0 [1, 2]
[0, 1] 2 2 0 [1, 2] [-1, 0] 3 3 0 [1, 2] [-2, -1] $\rightarrow$ $b_{1}$
$a_{1}$ $a_{1}b_{1}$ $a_{2}$ $a_{2}b_{1}$ [1,3] - 0 [1, 2] -

TABLE II: Output Relative Value Transformation Improving Opportunities for
Multi-Attribute Range Encoding

###  IV-B Proof of Correctness [Sketch]

We will prove that ProvRC is a lossless compression algorithm. The basic proof
strategy is to show that every step of this algorithm is lossless and fully
reversible, and thus, by induction, the algorithm is also lossless.

Union of Cartesian Products.  Let $R$ be a relational instance with set
semantics over the attributes $Y$. Every such instance can be expressed as a
“union of Cartesian products” (UCP). For example consider the set of 2-tuples
$\\{(^{\prime}a^{\prime},1),(^{\prime}a^{\prime},2),(^{\prime}b^{\prime},3)\\}$,
one can express this set as
$\\{\\{^{\prime}a^{\prime}\\}\times\\{1,2\\}\cup\\{^{\prime}b^{\prime}\\}\times\\{3\\}\\}$.
The Cartesian product generates the columns, and the union combines the rows.
This representation is identical to the $\mathcal{T}$ representation in the
worst-case optimal join literature [13]. This representation is fully lossless
where:

$\\{(^{\prime}a^{\prime},1),(^{\prime}a^{\prime},2),(^{\prime}b^{\prime},3)\\}\equiv\\{\\{^{\prime}a^{\prime}\\}\times\\{1,2\\}\cup\\{^{\prime}b^{\prime}\\}\times\\{3\\}\\}.$

Note that “set semantics” is important here; this approach is lossless when
every row in the lineage relation is unique (which is true in DSLog).

Multi-Attribute Range Encoding as a UCP. Every step of Multi-Attribute Range
Encoding produces a valid UCP representation of the instance. For example,
table I shows the algorithm’s output for an example table. In UCP notation,

$\\{\\{1\\}\times\\{1\\}\times\\{1,2\\}\cup\\{2\\}\times\\{2\\}\times\\{1,2\\}\cup\\{3\\}\times\\{3\\}\times\\{1,2\\}\\}$

This is because we only replace contiguous ranges where ALL other attributes
match on equality.

Relative Transformation.  The results above hold for any integer-valued
dataset. Thus, we can always choose how to encode these integers as long as
that encoding is reversible. The relative transformation simply encodes
certain columns as a delta rather than an absolute number (output-to-input).

###  IV-C Asymmetry in Representation

Our lineage representation is asymmetrical - input attributes can have
relative indices, but output attributes are absolute. While not relevant for
correctness (lossless compression), it does have an impact on query
processing. We can push down predicates only on absolutely indexed columns.
This is easily resolved by materializing a different version of the compressed
tables with the inverse property when necessary - a version where output
attributes can have relative indices, but input attributes are absolute.
Either both versions can be stored on one version depending on the
distribution of forward and reverse queries.

In Table III, we show the forward query table of our running example. This
table encodes the same information as the previous representation but has
absolute values on attributes $a_{1},\dots,a_{m}$.

$a_{1}$ | $a_{2}$ | $b_{1}$ | $b_{1}a_{1}$ | $b_{1}a_{2}$
---|---|---|---|---
[1,3] | [1,2] | - | 0 | -
TABLE III: Alternative Compression Representation to Enable Forward Queries

##  V In Situ Query Processing

We now describe the algorithm for directly answering backward and forward
queries over the compressed lineage index.

Recall the user calls the method prov_query to query the lineage between two
Array along some path represented by chained Arrays
$X^{1}\xrightarrow{}X^{2}\dots\xrightarrow{}X^{n}$. This query returns the
cells in $X^{n}$ that contribute to particular cells in $X^{1}$. The user
specifies the interested cells with $Q$, a table with attributes
$\Omega_{X^{1}}$ (which correspond to array indices of $X^{1}$) that contain
the interested cell indices. Such a query is answerable if a chain of
operations connects the given path, and the lineage of these operations is
stored in DSLog.

###  V-A Basic Query Processing

Suppose the uncompressed lineage relation between array $X^{i}$ and $X^{i+1}$
is stored as a full lineage table $R^{i}$. To materialize the lineage
relationship along the chain of operations, we join these tables with a
natural join:

$R^{1}\bowtie...\bowtie R^{n-1}$

In forward and backward queries, the query is simply a predicate over $R^{1}$,
specifically over the attributes corresponding to $X^{1}$. This can be
elegantly expressed as another join:

$Q\bowtie R^{1}\bowtie...\bowtie R^{n-1}$

###  V-B In-Situ Join Algorithm

Instead of working with the original relations, we now work with compressed
relations. We assume that each $R_{1}^{i}$ table is appropriately constructed
from the full lineage table $R^{i}$ using the ProvRC compression algorithm.
Now, we can perform a similar query over the compressed tables _but replace
the equality joins with custom $\theta$-joins over intervals_. These
$\theta$-joins account for the range-encoding and relative value
transformations of ProvRC.

$Q^{\prime}\bowtie_{\theta}R_{1}^{1}\bowtie_{\theta}...\bowtie_{\theta}R_{1}^{n-1}$

The query, $Q^{\prime}$, is encoded from $Q$ in the same format as the
compressed relational lineage tables with multi-attribute range encoding. This
encoding is typical with other in-situ query processing algorithms, e.g.,
dictionary coding [5].

There are two subroutines within a $\theta$-join:

  * •

Range Join. Perform a range join on the range intervals in the compressed
tables [3]. Recall, after compression, values in the table can be ranges. We
want to join on ranges that have any overlap. This is simply a range join,
where the join condition is $range_{1}\cap range_{2}\neq\emptyset$.

  * •

De-Relativize Indices. Convert the relative attributes of the resulting table
into absolute attributes.

We will now describe the $\theta$-join over tables $Q^{\prime}$ and
$R_{1}^{1}$:

$Q^{\prime}\bowtie_{\theta}R^{1}_{1}(X^{1},X^{2})$

Using our running example, we also demonstrate how a query is processed with a
$\theta$-join. Assume that Table II, $R_{exp}$ is stored in our system. Let us
generate a query over the path $B\to A$ (i.e., a backward query) with the cell
specification table, $Q_{exp}$, as shown in Table IV. This specifies that we
are interested in the cells with indices $b_{1}=1,2$.

$b_{1}$
---
[1,2]
TABLE IV: Example Query for Stored Lineage Table

####  V-B1 Step 1. Range Join

As the first step of the $\theta$-join, a range join is performed over $Q$ and
$R^{1}$. Given columns that describe intervals in two tables, a range join
joins on the intersection between those intervals. For example, we have a
range join over $\alpha$ and $\beta$ columns as:

$\alpha$
---
$[1,3]$
$[4,8]$

$\bowtie_{\text{Range}}$ $\beta$ $[0,2]$ $[10,12]$ $\rightarrow$ $\alpha$
$\beta$ $\alpha\beta\text{(Intersect)}$ $[1,3]$ $[0,2]$ $[1,2]$

In our case, this join takes the joint intersection of ranges over all common
attributes of $\Omega_{X^{1}}$ between the two tables. We now use the critical
insight that each row in $R^{1}$ describes an all-to-all relationship between
input and output attributes. This is true even in the case of relative
attributes; however, in this case, the all-to-all relationship is in the
relative space. Using this insight, we can observe that a range join between
$Q$ and $R^{1}$ preserves the lineage relationships described in $R^{1}$ for
the relevant cells given by $Q$.

(A) Compressed lineage of an All-to-All Operation
---

(B) Intersection with [1,2] Query
---

(C) Get Full Range of First Array
---

Figure 4: This is an example of a range join preserves lineage, where, given a
lineage table compressed with ProvRC (A), we can identify the intersections
between the query and the table (B) and then get the full lineage of those
intersecting intervals (C).

Figure 4 demonstrates an example of this insight, given a compressed array
lineage relationship between array attribute intervals:
$[1,2]\rightarrow[1,3]$ (A). Suppose we query for the backward lineage of the
second array at indices (1,2). We are only interested in the lineage
relationships described by the intersection between the query and the lineage
table (on the second array’s attributes) (B). Due to the all-to-all
relationship, we want the full range of the first array’s attributes
corresponding to those intervals (C). This is elegantly represented with a
range join.

After performing the range join over tables $Q_{exp}$ and $R_{exp}$ from our
running example, we get the table shown in Table V. Note that, over the
intersection of ranges, the lineage relationships captured by full lineage
table $R_{exp}$ are preserved, but only over the cells specified by the query
$Q_{exp}$.

$b_{1}$ (Intersect) | $a_{1}$ | $a_{1}b_{1}$ | $a_{2}$ | $a_{2}b_{1}$
---|---|---|---|---
[1,2] | - | 0 | [1, 2] | -
TABLE V: Range Joins Preserve the Lineage Relationships of Queried Cells

####  V-B2 Step 2. De-Relativize Attributes

Let the output table of the range join over $Q$ and $R^{1}$ be represented as
$T$. The table $T$ may have relative attributes; however, we would like the
$\theta$-join operation to return a table with only absolute attributes for
future $\theta$-joins or for displaying the query result. As the second step
of the $\theta$-join, we shall now demonstrate how to convert the relative
attributes in $T$ back into absolute attributes.

(A) Compressed Lineage of an One-to-One Operation
---

(B) Range Join with [1,2] Query
---

(C) Convert into Absolute Indices
---

Figure 5: We have an example of how we can find absolute indices from relative
range intervals, where, given a lineage table compressed with ProvRC (A), we
can perform a range join with a query (B), and then calculate the absolute
indices from the resulting table (while breaking the all-to-all relationship)
(C).

The relative attributes can be combined with the absolute attributes they
reference to generate the original absolute values. We first give an intuition
for this process with the example shown in Figure 5. This example shows a
lineage relationship between two array index intervals where the first index
is _relative_ : $[0,1]\rightarrow[1,3]$ (A). Given a query for the backward
lineage of the second array at index (1,2), we can calculate the relevant
lineage relationships with a range join (B). Now, we can calculate the
absolute indices captured in these relationships by reversing the relative
operation (C). This breaks the all-to-all lineage relationship (as shown with
a dashed arrow) but still gives the correct lineage cells for the queried
intervals. Note that this calculation is made without expanding any intervals
into full representations, and _the absolute interval values remain in
compressed range encoding_. By working through the transformations of ProvRC,
it can be shown that for any arbitrary ranges $t.x,r.x,t.xy$, the original
absolute indices captured by the ranges are exactly contained in the output of
$rel\\_for$ or $rel\\_back$.

We can generalize this process to create a reversal algorithm for any row
$t\in T$. To formalize this, for attribute $y\in\Omega_{X^{2}}$, we perform
the following algorithm:

  * •

If $t.y$ is not empty, do nothing.

  * •

Else, find a non-empty $t.xy$ for some $x\in\Omega_{X^{1}}$,

    * –

If the table is a backward representation,
set $t.y:=rel\\_back(t.x,t.xy)$

    * –

If the table is a forward representation,
set $t.y:=rel\\_for(t.x,r.x,t.xy)$

    * –

Set $t.xy:=\emptyset$

We compute the absolute interval values using the methods $rel_{for}$ and
$rel_{back}$, for forward and backward tables, respectively:

$rel\\_back(t.x,t.xy):=[t.x[1]+t.xy[1],t.x[2]+t.xy[2]]$
$rel\\_for(t.x,r.x,t.xy):=$ $[\max(t.x[1]-t.xy[2],r.x[1]-t.xy[2]),$
$\min(t.x[2]-t.xy[1],r.x[1]-t.xy[2])]$

For forward queries, the method $rel\\_for$ also needs the values of row $r\in
R^{1}_{1}$ from which $t$ is derived.

In the running example, we can apply this calculation to the single row in
Table V to retrieve only absolute attributes. This final table is shown in
Table VI. This final table shows the cells in $A$ that contributed to the
cells in $B$ with indices $b_{1}=1,2$. Since the example query only has one
step in the lineage path, query_cells returns $(a_{1}:[1,2],a_{2}:[1,2])$. For
a general query, we repeat the $\theta$-join for
$T\bowtie_{\theta}R^{2}(X^{2},X^{3})$ and so on. Each join returns the
relevant indices of the following array in the path until we reach the final
array.

$b_{1}$ | $a_{1}$ | $a_{2}$
---|---|---
[1,2] | [1,2] | [1, 2]
TABLE VI: Final Table Contains Only Absolute Values

####  V-B3 Query Plan and Optimizations

We process these joins in a left-to-right query plan, i.e., we process the
joins in the order that they appear in the path specified by the user. To
optimize performance, DSLog apply projection and row-reduction operations on
the output of the $\theta$-join, $T$, before the next join. First, DSLog finds
the projection $T^{\prime}:\Pi_{\\{y\in\Omega_{X_{2}}\\}}(T)$ (since the query
now only requires $X_{2}$ attributes). Second, any rows in $T^{\prime}$
describing cell indices with adjacent intervals are merged into a singular
row, using an algorithm similar to the multi-attribute range encoding step in
ProvRC. This minimizes the total number of rows in $T^{\prime}$, reducing the
cost of the next join.

##  VI Lineage Reuse

When the same operations are repeatedly called on different input arrays, the
lineage from one call can populate the lineage from another. For example, if
the same featurization function is used on a training dataset and then a
testing dataset, we may find the lineage of that function on the testing
dataset without explicit capture.

This section describes how previously captured lineage can be reused during
repeated operation calls in DSLog. Our core contribution here is allowing the
reuse of lineage from operations with differently shaped array inputs through
“index reshaping”. This reshaping is explicitly enabled by extending our
compression algorithm, ProvRC.

###  VI-A Basic Design

An operation signature is associated with each call of register_operation. The
operation signature is defined by the name of the array operation, op_name,
the set of input arrays, in_arrs, and other input arguments, op_args. Users
specify the relevant input arguments in op_args. We require that they define
the lineage pattern of the operation for given array inputs up to pseudo-
randomness.

DSLog can internally map this operation signature with the associated lineage
tables of its input and output arrays:

⬇

base_sig(op_name: String, in_arrs: String [], op_args: Any[]) = {R}

In subsequent calls to register_operation with the same signature, calls to
the capture object can be bypassed by the previous lineage tables. This basic
strategy has been employed in systems like Lima [29]. However, it requires
recording and matching on the entire input array and generally has limited
reuse capabilities. As we will see in the following section, our system goes a
few steps further regarding reuse by defining more general signature mappings.

###  VI-B Lineage Extrapolation

In several scenarios, the lineage depends only on the shape of the input
arrays and not the actual input arrays themselves. For example, the lineage
for linear algebra operations or a forward evaluation of a neural network on a
different mini-batch of data fits this criterion.

In those cases, we can store a more general mapping between operation
signatures and the lineage table:

⬇

dim_sig(op_name:String, in_shapes:Tuple[], op_args:Any[]) = {R}

, where in_shapes is the shape of arrays in in_arrs of the operation
signature. Similar to the previous case, in subsequent calls to
register_operation, we can directly reuse the lineage registered above if
there is a match on the operation signature. However, a match only needs the
same input array shapes rather than the same input arrays.

Finally, it is also possible to extrapolate lineage in some scenarios without
matching on shape. For example, consider an image smoothing operation with a
convolutional filter. The user runs this program twice, and for the second
time, the image is down-sampled beforehand. In this case, the lineage relation
from the second run is simply a fraction of the relation of the first run. We
have found that this pattern is relatively common in data science workflows.

In DSLog, we can generate the lineage table to any input array shape for this
lineage pattern by “index reshaping” the original compressed lineage table
into a generalized representation. Now, DSLog can map operation signatures to
lineage tables without requiring any matches on the input array shapes:

⬇

gen_sig(op_name:String, op_args:Any[]) = {R’}’

, where $R^{\prime}$ is a modified table that enables index reshaping. We can
generate $R^{\prime}$ directly because of DSLog’s compressed representation of
lineage tables.

To create $R^{\prime}$ given a compressed relational table, $R$, for $d_{i}\in
dim(X)$, we identify all intervals equal to $[1,d_{i}]$ in $R$ and replace
them with the generalized interval $[1,D_{i}]$, where $D_{i}$ is an indicator
of that attribute. Suppose those intervals are the only ones dependent on the
shape of the input arrays, and there is no data dependence. In that case, a
generalized representation is formed independent of the input array shape. The
symbolic interval is used to extrapolate the lineage for calls of the same
function but with differently shaped data.

(A) Compressed Lineage of an Aggregate Operation for a 1-D Array with
$d_{1}=2$
---

(B) Generalize Representation of Lineage from (A)
---

(C) Converted Lineage from (B) for a 1-D Array with $d_{1}=4$
---

Figure 6: This figure shows how compressed lineage tables can be leveraged for
reuse with index reshaping. The compressed lineage of an aggregate operation
for a two-cell array (A) can be converted to a generalized representation (B),
which can be used to find lineage for downstream operation calls with
different array shapes (C).

Figure 6 shows an example of index reshaping. Given an aggregation operation
that captures an all-to-all relationship and outputs a 1-cell array, and a 1-D
input array with $d_{1}=2$, DSLog can generate a compressed lineage table with
ProvRC (A). For the generalized representation, the interval in this
compressed lineage is converted to $[1,D_{i}]$ based on the algorithm above
(B). In a subsequent call to the same aggregation operation with an input
array with $d_{1}=4$, DSLog can set $D_{1}=4$ to capture that call’s
compressed lineage without additional tracking (C).

###  VI-C Automatic Reuse Prediction

Understanding when reuse is possible requires knowledge of the exact lineage
pattern of an operation and how that lineage pattern is stored. This can be
time-intensive and error-prone for end-users. Instead of requiring users to
enable reuse, DSLog can try to automatically predict when dim_sig and gen_sig
signatures can be generated. This is based on simple heuristics that
extrapolate lineage based on the past behavior of that operation signature.

When register_operation is called, DSLog internally stores _temporary_ dim_sig
and gen_sig mappings. In the subsequent $m$ calls to register_operation that
match on either partial operation signature, DSLog checks if the stored
lineage tables in these mappings match the new lineage tables. We set the
mapping relations as permanent if a match occurs after $m$ calls. Otherwise,
we mark that partial signature key as not reusable. For the gen_sig matches,
we also require that the $m$ calls have different array shape values. In our
current implementation, we set $m=1$.

##  VII Experiments

We performed experiments to evaluate each component of DSLog. Our performance
experiments were performed on Chameleon, a large-scale computer science
research platform [14], with an Intel Xeon Gold 6126 Processor, an RTX6000
GPU, and 192 GiB of RAM.

###  VII-A Prototype Capture Algorithms

In DSLog, we include several prototype capture methods for different types of
operations in the Python data science ecosystem. These are included to
demonstrate our system but are not meant to represent what is required to
capture lineage for entire array workflows. We view the difficult task of
lineage capture in data science as perpendicular work to this paper.

####  VII-A1 Cell-Level Tracking in numpy

The numpy array is a popular array framework in Python. Using annotations, we
have implemented a data type tracked_cell that automatically tracks the
lineage of every cell within a numpy array during low-level operations. Under
the hood, this capture technique is similar in semantics to taint tracking
[49]. With efficient memory management, tracked_cell performs 300x over the
equivalent Python implementation and can scale to (and over) arrays with 1
billion cells. The lineage history of each cell in the output array can be
used as the capture argument in a Lineage object. Detailed capture performance
experiments and further descriptions will be included in the Appendix of the
technical report.

####  VII-A2 Explainable AI Tracking

DSLog also allows lineage capture with lineage derived from model explanation
algorithms. We assume that the model operations take the form
$y=\texttt{model}(x)$, where $x$ is an input example a (vector, 1-d array) and
y is the predicted label (a vector, 1-d array). Under this assumption, DSLog
can apply explainable AI techniques - i.e., LIME or D-RISE - over the model
[35, 28]. Both explainable AI techniques generate a bipartite weighted
contribution relationship between the cells in $x$ and the cells in $y$.
Direct contributions are filtered from this graph based on a significance
threshold.

####  VII-A3 Custom Tracking Functions

Finally, we have implemented custom ‘group-by’ and ‘inner-join’ operations
that record the lineage history of individual cells upon execution. This
demonstrates the integration of DSLog with traditional relational operations.

###  VII-B DPSM Baselines and Implementation

We have implemented alternative storage formats and physical designs to
evaluate the compression and query components of DSLog. For most baselines,
the query interface is served by the DuckDB system [33]. We additionally
evaluated one array-based baseline, where the query is completed with array
operations. All storage formats (except the array-based one) are designed to
be transparently queried from DuckDB; however, some baselines might require
explicit decompression before querying.

Raw. The captured lineage tuples are stored in a row-oriented format without
data compression. This format is similar to the design principles of Ground
[20], but with an implementation in DuckDB so we could compare to baselines
111We referred to the table design in https://github.com/ground-
context/ground.

Array. The captured lineage tuples are stored as a numpy array.

Parquet. The captured lineage tuples are stored directly in Apache Parquet
files, a columnar file format that different query processing engines can
parse. We use default encoding and row-group partitioning settings.

Parquet-GZip. The captured lineage tuples are stored in a GZIP compressed
Parquet file, as suggested by industry practice [1].

Turbo-RC. We designed a custom columnar format that applies state-of-the-art
integer compression over each column. This compression included run-length
encoding combined with integer entropy coding [17].

We compared these baselines to ProvRC and ProvRC-GZip, a version of ProvRC
where GZip is applied to the results of the main algorithm, similar to
Parquet-GZip. The GZip compression had minimal performance impact on our
system, with significant storage benefits for unstructured lineage. In
practice, DSLog uses the ProvRC-GZip algorithm for optimal storage across all
operations.

Name | Raw | Array | Parquet | Parquet-GZip | Turbo-RC | ProvRC |  ProvRC\- GZip
---|---|---|---|---|---|---|---
| Abs | Abs | Rel | Abs | Rel | Abs | Rel | Abs | Rel | Abs | Rel | Abs | Rel
| (MB) | (MB) | (%) | (MB) | (%) | (MB) | (%) | (MB) | (%) | (MB) | (%) | (MB) | (%)
Negative | 22.66 | 32.00 | 141 | 5.05 | 22.31 | 4.33 | 19.10 | 5.11 | 22.58 | 0.00978 | 0.0431 | 0.0103 | 0.0457
Addition | 45.33 | 64.00 | 141 | 10.11 | 22.31 | 8.66 | 19.10 | 10.23 | 22.58 | 0.0195 | 0.0431 | 0.0207 | 0.0457
Aggregate | 20.55 | 32.00 | 155 | 0.131 | 0.639 | 0.0255 | 0.124 | 3.73 | 18.17 | 0.00978 | 0.0475 | 0.0103 | 0.0504
Repetition | 98.22 | 128.0 | 130 | 25.20 | 25.65 | 14.52 | 14.78 | 22.03 | 22.43 | 0.00983 | 0.0100 | 0.0103 | 0.0105
Matrix*Vector | 39.22 | 64.00 | 163 | 0.254 | 0.649 | 0.048 | 0.122 | 6.77 | 17.25 | 0.0195 | 0.0498 | 0.0207 | 0.0528
Matrix*Matrix | 40127 | 64000 | 159 | 254.8 | 0.635 | 48.06 | 48.06 | 0.119 | 6770. | 0.0198 | 4.95$\times 10^{-5}$ | 0.0210 | 5.23$\times 10^{-5}$
Sort | 22.66 | 32.00 | 141 | 3.38 | 14.92 | 2.76 | 12.19 | 6.10 | 26.91 | 3.43 | 15.15 | 2.79 | 12.33
ImgFilter | 4.288 | 5.632 | 131 | 1.96 | 45.93 | 1.06 | 24.73 | 1.05 | 24.64 | 0.00999 | 0.233 | 0.0104 | 0.244
Lime | 24.09 | 29.63 | 123 | 0.529 | 2.19 | 0.123 | 0.513 | 5.97 | 24.78 | 0.0123 | 0.0511 | 0.0121 | 0.0502
DRISE | 8.82 | 11.07 | 125 | 0.0898 | 1.01 | 8.242 | 0.271 | 2.19 | 24.91 | 0.0106 | 0.120 | 0.0108 | 0.123
Group By | 183.43 | 251.00 | 136 | 32.62 | 17.78 | 13.56 | 7.39 | 35.97 | 19.61 | 29.45 | 16.05 | 13.62 | 7.42
Inner Join | 2330 | 2612.13 | 111 | 195.44 | 8.36 | 53.44 | 2.28 | 584.98 | 25.02 | 14.13 | 0.604 | 6.36 | 0.272
TABLE VII: Comparison of Compression Ratio for Different Algorithms Against
ProvRC

###  VII-C Compression

####  VII-C1 Lineage Capture Storage Size

We compare the size on disk of the different compression formats for tables
within our lineage index. Each baseline, ProvRC and ProvRC-GZip, were applied
to compress the lineage of selected operations.

Twelve individual data science operations were constructed to capture a full
range of individual array operations. This workload can be broken down into
the following categories:

  1. 1.

Eight of those operations are numpy operations [2]: for five of the operations
(Negative, Addition, Aggregate, Repetition, Matrix*Vector, Matrix*Matrix), the
lineage is independent of the data values, and for two of the operations, the
lineage is value-dependent (Sort, ImgFiter). The lineages are tracked with
low-level array tracking. Note that “Sort” is the worst case for ProvRC, where
no continuous patterns exist in the lineage.

  2. 2.

Two of these operations are explainable AI. A frame was chosen from VIRAT
[26], a surveillance camera dataset, and YOLOv4 object detection was applied
over that frame to detect a ’car’ object. On this model and data, lineage was
captured with LIME and DRISE.

  3. 3.

The final two operations are relational operations, and the stored lineage is
captured with custom functions [12]. These operations are applied to the full
IMDB dataset tables[4]. Note that the ’tconst’ and ’startYear’ columns are
sorted in the original tables, but ’isAdult’ is unsorted.

Table VII shows the size of the lineage file on disk for each compression
algorithm and relative compression ratios to the raw file. The Array baseline
is uncompressed and has a similar storage size to Raw. Across all operations,
Turbo-RC has the most consistent performance - suggesting that its compression
algorithm did not exploit specific underlying lineage patterns. We can observe
that Parquet and Parquet-GZip are exceptionally efficient in compressing
aggregation patterns - compressing significantly on “Aggregate” and
“Matrix*Vector ” - but are still less optimal in those operations than ProvRC
and ProvRC-GZip.

Over operations that explicitly matched the patterns described in Section IV
(“Negative”, “Addition”, “Aggregate”, “Repetition”, “Matrix*Vector”,
“Matrix*Matrix”), ProvRC is the most efficient compression algorithm,
achieving a compression ratio of $5\times 10^{-5}\%$ and beating the closest
baseline by up to 2000x. Even over operations with only partially structured
lineage (“ImgFilter”, “Lime”, “DRISE”, and “Inner Join”), ProvRC performs
exceptionally well, with a compression ratio of $<0.3\%$, beating the closest
baselines by up to 400x. We attribute this result to the algorithm’s ability
to compress more complex multi-columnar patterns and efficiently represent
range intervals.

ProvRC-GZip performs slightly worse than ProvRC over the most structured
lineages due to the slight overhead of the GZip compression. However, for
partially structured lineage, it was better than ProvRC in two cases (‘Lime”
and “Inner Join”). The benefit of ProvRC-GZip is over unstructured lineage,
significantly improving the lineage storage size of two unstructured
operations (“Group-By”, ”Sort). In both cases, it was within 0.5% of the
optimal compression algorithm. These experiments show that applying ProvRC-
GZip to array lineage tables captured within DSLog is feasible and generally
the most optimal solution.

We only materialize the ProvRC and ProvRC-GZip representation for backward
queries. Since the backward and forward queries store the same information,
only one must be stored in long-term storage. We measured the file size of the
database files that were ultimately served to DuckDB.

####  VII-C2 Compression Latency

Next, we evaluated the compression latency of the different baselines and
ProvRC-GZip. This latency considers the entire read, format-conversion,
compression, and flush latency time it takes to write the compression lineage
tables to disk. We measured the latency of table compression for the two
extreme lineage types: one-to-one element-wise operations and one-axis
aggregation operations. This latency is measured over a range of array sizes.

Figure 7: (A) and (B) benchmark the compression algorithms in terms of their
latency as a function of input size.

Figure 7 shows the latency of the different compression algorithms. We note
that the latency between different compression algorithms is within an order
of magnitude of each other and increases as the input array shape increases.
ProvRC-GZip is very efficient on smaller tables for aggregation patterns;
however, it is consistently less efficient in other cases and is relatively
slow in compressing larger element-wise lineage tables compared to baselines.
Given that the current implementation is written in Python for simplicity, and
the baselines are written in C++ and are from mature/public codebases, we find
this performance reasonable. ProvRC is also highly parallelizable, so we
expect significant performance gains from a multi-threaded implementation.

###  VII-D Query Processing

Figure 8: These graphs show the evaluation of query latency on (A) image
machine learning, (B) relational and (C) ResNet workflows.

Figure 9: These graphs show the evaluation of average query latency on random numpy workflows with (A) five and (B) ten operations. | Image Pipeline | Relational Pipeline
---|---|---
1 | Resize to (416,416) | Inner Join on ’tconst’
2 | Increase Luminosity | Filter Columns with NaN Value
3 |  Rotate $90^{o}$ | Add Two Columns
4 | Horizontal Flip | One-Hot Encode on ”genres”
5 | Evaluate Lime on YOLOv4 | Add Constant to One Column
TABLE VIII: Summary of Image and Relational Workflows

We orchestrated five experiments on different workflows to evaluate query
latency - two on hand-generated workflows, one on a ResNet block [18] and two
on randomly generated numpy workflows. The wall-clock latency time to the
query result is measured, i.e., the time delay between the users issuing a
query to DSLog and receiving a response. Each query_cells value is a randomly
selected fixed-sized cell range. For cells within query_cells, we query for
the forward lineage through the full workflow pipeline. For brevity, backward
query experiments are not shown in the paper - those results have similar
trends as the forward query results since the algorithm applied are identical.

The first two experiments are over hand-generated workflows to match task-
specific cases: one for computer vision model debugging and another for
relational data pre-processing. Each of these workflows has five steps,
including a mix of data-dependent and data-independent operations, as
summarized in Table VIII. The Resnet workflow contains seven steps of a ResNet
block during machine learning inference. The image and ResNet workflow is
performed over a frame of the VIRAT dataset, and the relational workflow is
performed over the full table of the IMDB title.basics and title.episode
tables. These are identical to data tables used in the compression storage
experiments.

For the two randomly-generated experiments, numpy operations are randomly
selected from an initial list of 76 numpy operations[2]. This list includes
selected operations from Section IX that can intake and output a single
float_64 arrays. Twenty workflows are generated using this list for each
experiment with five and ten chained operations, respectively. The workflows
operate on an initial array with randomly generated values and 100,000 cells.
We use tracked_cells to annotate the contribution lineage.

For each experiment, the query latency time of our compression table and query
algorithm in DSLog is compared with the Parquet, Parquet-GZip, and Turbo-RC
compressed tables and basic join queries, as well as vectorized numpy
operations over the Array table. For the latter, we evaluated the equality
condition (==) between the Array tables and the requested query (in array
format). We batched the query with a batch size of 1000 to avoid out-of-memory
issues. For completeness, we included two additional baselines in the randomly
generated workflows with five operations - the uncompressed table (Raw) and a
version of our query algorithm where the final merge step is skipped (DSLog-
NoMerge). The maximize time to complete each query was set to 3 hours (10800
seconds).

Figure 8 shows the result of latency query experiments over the two hand-
generated and ResNet workflows. We define query selectivity by the percentage
of cells from the initial dataset. The main observation is that DSLog
performed better than baselines over all queries except the most selective
ones over the image workflow, achieving up to 1500x less latency than the
following best baseline. The main reason for this improvement is that fewer
rows are queried due to the optimizations on our compression and query
algorithms.The Array baseline performed the worst of all baselines and did not
complete for less selective queries and queries over the relational workflow.
This suggests the vectorized operation does not scale well with data and query
size. Turbo-RC has significant overhead because of decompression, making it
highly unsuitable for more selective queries. Parquet and Parquet-GZip
performed similarly; latency time increased with the selectivity. The most
significant benefit of DSLog is on queries with low selectivity, with latency
time increasing slower as the number of initial cells increased. Lastly, DSLog
had the lowest latency on the ResNet workflow, primarily because the structure
of operations in the machine learning inference operations are extremely
regular, and ProvRC could compress such structures very efficiently.

Figure 9 shows the result of latency query experiments over the numpy
workflows. Minimum and maximum latency times are shown with an interval bar.
In general, the trends of the previous experiments hold, with DSLog performing
close to or better than baselines. Array’s relative performance improved on
more selective queries. We suspect that the smaller overhead of ingesting the
array accounted for this difference on those queries. The latency time of
DSLog was relatively higher, with only up to 20x improvement over the
following best baseline. Again, this is accounted for by how much ProvRC can
compress each operation’s lineage. All compression algorithms demonstrated a
considerable variation in latency. The minimum/maximum query latency times
were two orders of magnitude smaller/larger than the average time, showing
that the specific operations captured significantly impacted query latency.

The Raw queries were worse on very selective queries but were on par with
Parquet and Parquet-GZip on less selective ones. DSLog-NoMerge was worse than
DSLog over all queries, showing that the merge step significantly improves
query performance with minimal overhead. There is an average of about a 4x
increase in latency time on the pipelines with ten operations compared to the
ones with five operations. The non-proportional increase is due to the
complexity of the pipeline at ten operations. Despite this increase, the
average query time is still significantly shorter using DSLog.

###  VII-E Reuse and Compression Over numpy API

Op. | Tot. | ProvRC | dim_sig | gen_sig | Error
---|---|---|---|---|---
|  | Abs | % | Abs | % | Abs | % | Abs
element | 75 | 75 | 100 | 75 | 100 | 75 | 100 | 0
complex | 61 | 55 | 90.1 | 51 | 83.6 | 24 | 39.3 | 1
total | 136 | 130 | 95.5 | 126 | 92.6 | 99 | 72.7 | 1
TABLE IX: numpy API Operations Covered by Compression and Reuse

We quantitatively evaluate the coverage of DSLog’s optimization over 136
different operations in numpy. These optimizations include ProvRC and
automatic reuse prediction.

The operations consist of all functions in numpy’s API that meets the criteria
of currently supported operation signatures in tracked_cells: they (1) can
intake and output float_64 arrays, and (2) can intake scalar-only arguments
outside of float_64 arrays. They represent a diverse range of typical array
manipulations and are a super-set of the operations used in the numpy query
experiments in Section VII-D [2].

DSLog evaluated compression and reuse over 20 runs of each operation. The
generated lineage is automatically compressed with ProvRC, and the automatic
reuse prediction algorithm is applied. For compression, we tallied the number
of operations that were compressed to $<0.5$ of the original raw CSV file. For
reuse, we evaluate the number of operations where DSLog successfully discovers
and stores shape-based and generalized mappings.

We divided the numpy operations into two categories - element-wise operation
and other more complex patterns. Table IX summarizes the results of our
evaluation for both categories. This table shows that the coverage of ProvRC
compression is significant, and 95.5% of all operations are compressed. This
is because numpy operations are generally structured and value-independent.
Our compression covered any operation covered by reuse and four additional
operations. These results show that traditional array manipulation workflows
are highly suited to lineage compression in DSLog.

Automatic reuse prediction had less coverage than compression but performed
exceptionally well over the numpy library. As the table shows, over half of
our results are over element-wise operations. These operations were well-
suited for reuse; DSLog was able to generate shape-based and generalized
mapping over all of those lineage tables. Mapping coverage over complex
operations was slightly lower but still significant; shape and generalized
reuse were generated for 86.8% and 39.3% of operations, respectively. This
represents a significant reduction of capture latency compared to not using a
lineage index such as DSLog since retrieving each mapping has negligible
latency. In contrast, naive lineage capture can be extremely costly.

One reuse misprediction error occurred, where DSLog generated a wrong
generalized mapping for the operation cross. This is because cross has
different lineage patterns depending on the size of the second dimension.
Mispredictions are the downside of setting $m$ as a low value in our
prediction algorithm.

###  VII-F Compression over Data Science Workflows

Dataset | Total Op. | Compressible Op. | Longest Chain
---|---|---|---
|  | Abs | (%) |
Flight |  54.9 $\pm$ 38.8 |  40.5 $\pm$ 27.6 |  76.3 $\pm$ 11.0 |  16.4 $\pm$ 13.3
Netflix |  58.3 $\pm$ 36.3 |  40 $\pm$ 27.2 |  66.9 $\pm$ 9.2 |  14.2 $\pm$ 9.0
Total |  56.6 $\pm$ 36.6 |  40.25 $\pm$ 26.7 |  71.6 $\pm$ 11.0 |  15.3 $\pm$ 11.12
TABLE X: Qualitative Estimate of Compressible Operations and Longest Operation
Chain in Kaggle Workflows

A very typical application of array operations is in data science workflows.
We evaluated the coverage of ProvRC over these workflows to ground the
applicability of a lineage index in real-world scenarios. However,
characterizing these workflows is difficult [23], and to the best of our
knowledge, there is currently no method to capture lineage over these
workflows completely.

Instead of quantitative evaluation, 20 data science Jupyter notebooks were
manually evaluated for coverage [2]. These notebooks were selected from the
“Trending” code page for two popular Kaggle datasets: 2015 Flight Delays and
Cancellations [25] and Netflix Movies and TV Shows [8]. The Flight dataset
contains 31 attributes and 5819079 rows and records flight data within the USA
in 2015. The Netflix dataset contains 12 attributes and 8807 rows and records
all content available on Netflix as of mid-2021. Notebooks were selected to
span the spectrum between data exploration and machine learning predictions.

Coverage is evaluated as follows. Each operation with an input and output
array is checked; visualization and plotting operations were excluded for
simplicity. We considered an operation compressible if its estimated lineage
matches one of the three patterns defined in Section IV, i.e., if its lineage
contains continuous rectangular ranges in input cells, absolute output cells,
or output cells after a relative transformation. Operations that did not
explicitly match these patterns may still be compressible but were not
counted. Operations appearing in for-loops over array indices were only
considered once since they all were observed to have simple equivalence to
similar operations that do not need such control structures.

The summary results of this experiment are shown in Table X. Qualitatively, we
found that workflows that focused more on data exploration had higher
operation counts, lower compressible operations, and shorter chains than
machine learning workflows. We estimate that the distribution of data
exploration and machine learning workflows accounted for the difference in
results between the two datasets rather than the specific dataset properties.

The most significant result is the high coverage of compressible operations
over these workflows(76.3$\pm$ 11.0% on the Flight dataset and 66.9$\pm$ 9.2%
on the Netflix dataset). This suggests that the lineage of these operations
would be significantly compressed with ProvRC-GZip, achieving significant
storage and query cost reduction when ingested into DSLog. Most incompressible
operations were value-filter operations, which do not have simple exploitable
lineage patterns.

During the inspection, each workflow’s longest chained operation length was
counted. The summary results of this count are in Table X. Across both
datasets, we found that this length has less variation between workflows than
the total number of operations and is not directly correlated with workflow
length. The average length is 15.3$\pm$ 11.12, giving us an estimate of the
upper bound of joins for lineage queries in tabular data workflows.

##  VIII Related Work

To our knowledge, automatic compression has yet to be integrated into existing
lineage systems for data science. For example, the Ground [20] system uses a
Postgres SQL engine with a row-oriented data organization. Similarly, Smoke
uses an in-memory data structure to store and index lineage for visualization
applications [32].

Prior work has been done on provenance compression of non-array structures,
mainly in graph representation [16, 19]. Multiple works explore identifying
and combining common nodes in a provenance graph [44, 43, 10]. Anand et al.
introduces range and subsequence reduction [7]. Compression has also been
studied in network lineages [11, 48]. Finally, algorithms have been presented
for lossy compression of provenance through sampling [22] and minimizing graph
distance [6]. Previous approaches do not exploit the numerical regularity of
array indices in typical array-programming applications. We also leverage
existing ideas from columnar compression (our baseline) [5] and in-situ query
processing [31] to build our query processing framework.

Since our focus is on array programs, there is also a tangentially related
field of machine learning workflow management. Initial prototypes such as
HELIX [45], Alpine Meadow [38], MLFlow [46], and the Collaborative Optimizer
[15] rely on coarse-grained lineage tracing at the level of entire machine
learning programs. Such systems are helpful in versioning and dataset
discovery. However, they do not track contribution lineage and fail to give
fine-grained information about how individual data values, i.e., individual
array elements, contribute to final results.

## References

  * [1] Athena compression support.
  * [2] Detailed coverage experiment results.  https://github.com/j2zhao/DSLog-Coverage, journal=Github, year=2023, month=May.
  * [3] Range join optimization.  https://docs.databricks.com/optimizations/range-join.html.
  * [4] Imdb non-commercial datasets.  https://developer.imdb.com/non-commercial-datasets/, 2022.
  * [5] D. Abadi, S. Madden, and M. Ferreira.  Integrating compression and execution in column-oriented database systems.  In Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 671–682, 2006.
  * [6] E. Ainy, P. Bourhis, S. B. Davidson, D. Deutch, and T. Milo.  Approximated summarization of data provenance.  In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM ’15, page 483–492, New York, NY, USA, 2015. Association for Computing Machinery.
  * [7] M. Anand, S. Bowers, T. McPhillips, and B. Ludäscher.  Efficient provenance storage over nested data collections.  In Proceedings of the 12th International Conference on Extending Database Technology, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT’09, pages 958–969, 2009.  Copyright: Copyright 2009 Elsevier B.V., All rights reserved.; 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT’09 ; Conference date: 24-03-2009 Through 26-03-2009.
  * [8] S. Bansal.  Netflix movies and tv shows.  https://www.kaggle.com/datasets/shivamb/netflix-shows, Sep 2021.
  * [9] M. Boehm, M. W. Dusenberry, D. Eriksson, A. V. Evfimievski, F. M. Manshadi, N. Pansare, B. Reinwald, F. R. Reiss, P. Sen, A. C. Surve, et al.  Systemml: Declarative machine learning on spark.  Proceedings of the VLDB Endowment, 9(13):1425–1436, 2016.
  * [10] A. P. Chapman, H. V. Jagadish, and P. Ramanan.  Efficient provenance storage.  In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 993–1006, 2008.
  * [11] C. Chen, H. T. Lehri, L. Kuan Loh, A. Alur, L. Jia, B. T. Loo, and W. Zhou.  Distributed provenance compression.  In Proceedings of the 2017 ACM International Conference on Management of Data, pages 203–218, 2017.
  * [12] J. Cheney, L. Chiticariu, and W.-C. Tan.  Provenance in databases: Why, how, and where.  Now Publishers Inc, 2009.
  * [13] R. Ciucanu and D. Olteanu.  Worst-case optimal join at a time.  Technical report, Technical report, Oxford, 2015.
  * [14] C. Cloud.  A configurable experimental environment for large-scale cloud research. chameleoncloud. org. retrieved, 2022.
  * [15] B. Derakhshan, A. Rezaei Mahdiraji, Z. Abedjan, T. Rabl, and V. Markl.  Optimizing machine learning workloads in collaborative environments.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1701–1716, 2020.
  * [16] D. Deutch, Y. Moskovitch, and N. Rinetzky.  Hypothetical reasoning via provenance abstraction, 2020.
  * [17] L. Hanzo, T. H. Liew, and B. L. Yeap.  Turbo coding, turbo equalisation and space-time coding.  John Wiley & Sons, 2002.
  * [18] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  CoRR, abs/1512.03385, 2015.
  * [19] T. Heinis and G. Alonso.  Efficient lineage tracking for scientific workflows.  In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD ’08, page 1007–1018, New York, NY, USA, 2008. Association for Computing Machinery.
  * [20] J. M. Hellerstein, V. Sreekanti, J. E. Gonzalez, J. Dalton, A. Dey, S. Nag, K. Ramachandran, S. Arora, A. Bhattacharyya, S. Das, et al.  Ground: A data context service.  In CIDR. Citeseer, 2017.
  * [21] M. Interlandi, K. Shah, S. D. Tetali, M. A. Gulzar, S. Yoo, M. Kim, T. Millstein, and T. Condie.  Titian: Data provenance support in spark.  In Proceedings of the VLDB Endowment International Conference on Very Large Data Bases, volume 9, page 216. NIH Public Access, 2015.
  * [22] S. Lee, B. Ludäscher, and B. Glavic.  Approximate summaries for why and why-not provenance (extended version).  CoRR, abs/2002.00084, 2020.
  * [23] M. H. Namaki, A. Floratou, F. Psallidas, S. Krishnan, A. Agrawal, and Y. Wu.  Vamsa: Tracking provenance in data science scripts.  CoRR, abs/2001.01861, 2020.
  * [24] M. Nikolic, M. Elseidy, and C. Koch.  Linview: incremental view maintenance for complex analytical queries.  In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 253–264, 2014.
  * [25] D. of Transportation.  2015 flight delays and cancellations.  https://www.kaggle.com/datasets/usdot/flight-delays, Feb 2017.
  * [26] S. Oh, A. Hoogs, A. Perera, N. Cuntoor, C.-C. Chen, J. T. Lee, S. Mukherjee, J. Aggarwal, H. Lee, L. Davis, et al.  A large-scale benchmark dataset for event recognition in surveillance video.  In CVPR 2011, pages 3153–3160. IEEE, 2011.
  * [27] D. Olteanu.  On factorisation of provenance polynomials.  In In TaPP. Citeseer, 2011.
  * [28] V. Petsiuk, R. Jain, V. Manjunatha, V. I. Morariu, A. Mehra, V. Ordonez, and K. Saenko.  Black-box explanation of object detectors via saliency maps.  In Computer Vision and Pattern Recognition (CVPR), 2021.
  * [29] A. Phani, B. Rath, and M. Boehm.  Lima: Fine-grained lineage tracing and reuse in machine learning systems.  In Proceedings of the 2021 International Conference on Management of Data, pages 1426–1439, 2021.
  * [30] G. E. Pibiri and R. Venturini.  Techniques for inverted index compression.  ACM Computing Surveys (CSUR), 53(6):1–36, 2020.
  * [31] N. Potti and J. M. Patel.  Daq: a new paradigm for approximate query processing.  Proceedings of the VLDB Endowment, 8(9):898–909, 2015.
  * [32] F. Psallidas and E. Wu.  Smoke: Fine-grained lineage at interactive speed.  arXiv preprint arXiv:1801.07237, 2018.
  * [33] M. Raasveldt and H. Mühleisen.  Duckdb: an embeddable analytical database.  In Proceedings of the 2019 International Conference on Management of Data, pages 1981–1984, 2019.
  * [34] E. K. Rezig, L. Cao, G. Simonini, M. Schoemans, S. Madden, N. Tang, M. Ouzzani, and M. Stonebraker.  Dagger: a data (not code) debugger.  In CIDR 2020, 10th Conference on Innovative Data Systems Research, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings, 2020.
  * [35] M. T. Ribeiro, S. Singh, and C. Guestrin.  ” why should i trust you?” explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144, 2016.
  * [36] T. Sellam, K. Lin, I. Huang, M. Yang, C. Vondrick, and E. Wu.  Deepbase: Deep inspection of neural networks.  In Proceedings of the 2019 International Conference on Management of Data, pages 1117–1134, 2019.
  * [37] Z. Shang, E. Zgraggen, B. Buratti, F. Kossmann, P. Eichmann, Y. Chung, C. Binnig, E. Upfal, and T. Kraska.  Democratizing data science through interactive curation of ml pipelines.  In Proceedings of the 2019 international conference on management of data, pages 1171–1188, 2019.
  * [38] Z. Shang, E. Zgraggen, and T. Kraska.  Alpine meadow: A system for interactive automl.
  * [39] G. E. Suh, J. W. Lee, D. Zhang, and S. Devadas.  Secure program execution via dynamic information flow tracking.  ACM Sigplan Notices, 39(11):85–96, 2004.
  * [40] M. Tiwari, H. M. Wassel, B. Mazloom, S. Mysore, F. T. Chong, and T. Sherwood.  Complete information flow tracking from the gates up.  In Proceedings of the 14th international conference on Architectural support for programming languages and operating systems, pages 109–120, 2009.
  * [41] M. Vartak, J. M. F. da Trindade, S. Madden, and M. Zaharia.  Mistique: A system to store and query model intermediates for model diagnosis.  In Proceedings of the 2018 International Conference on Management of Data, pages 1285–1300, 2018.
  * [42] J. Widom.  Trio: A system for integrated management of data, accuracy, and lineage.  Technical report, Stanford InfoLab, 2004.
  * [43] Y. Xie, D. Feng, Z. Tan, L. Chen, K.-K. Muniswamy-Reddy, Y. Li, and D. D. Long.  A hybrid approach for efficient provenance storage.  In Proceedings of the 21st ACM international conference on Information and knowledge management, pages 1752–1756, 2012.
  * [44] Y. Xie, K.-K. Muniswamy-Reddy, D. D. Long, A. Amer, D. Feng, and Z. Tan.  Compressing provenance graphs.  In 3rd USENIX Workshop on the Theory and Practice of Provenance (TaPP 11), 2011.
  * [45] D. Xin, S. Macke, L. Ma, J. Liu, S. Song, and A. Parameswaran.  Helix: Holistic optimization for accelerating iterative machine learning.  arXiv preprint arXiv:1812.05762, 2018.
  * [46] M. Zaharia, A. Chen, A. Davidson, A. Ghodsi, S. A. Hong, A. Konwinski, S. Murching, T. Nykodym, P. Ogilvie, M. Parkhe, et al.  Accelerating the machine learning lifecycle with mlflow.  IEEE Data Eng. Bull., 41(4):39–45, 2018.
  * [47] Z. Zhang, E. R. Sparks, and M. J. Franklin.  Diagnosing machine learning pipelines with fine-grained lineage.  In Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing, pages 143–153, 2017.
  * [48] W. Zhou, S. Mapara, Y. Ren, Y. Li, A. Haeberlen, Z. Ives, B. T. Loo, and M. Sherr.  Distributed time-aware provenance.  Proceedings of the VLDB Endowment, 6(2):49–60, 2012.
  * [49] D. Zhu, J. Jung, D. Song, T. Kohno, and D. Wetherall.  Tainteraser: Protecting sensitive data leaks using application-level taint tracking.  ACM SIGOPS Operating Systems Review, 45(1):142–154, 2011.