Reproduce “Efficient Row-Level Lineage Leveraging Predicate Pushdown” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Yin Lin, Cong Yan

PredTrace introduces a lazy inference method for row-level data lineage that leverages predicate pushdown to efficiently trace complex data pipelines, including those with non-relational operators and user-defined functions. It achieves an average lineage query time of 226.6 ms for TPC-H, up to 98x faster than previous lazy systems, and supports all 70 evaluated real-world Pandas data science pipelines.

Key insights

  • Predicate pushdown, traditionally a query optimization technique, can be effectively repurposed for efficient row-level lineage inference by translating output row identities into upstream selection conditions.
  • Strategically materializing minimal intermediate results only when precise predicate pushdown is insufficient drastically reduces lineage query time and storage overhead without requiring full pipeline re-execution.
  • An iterative refinement process combining predicate pushdown and pushup can significantly reduce the false positive rate of lineage supersets, providing useful provenance even without saving intermediate data.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.