2026 Theses Doctoral

Fine-Grained Lineage on Analytical Engines and Their Applications

Mohammed, Haneen A.

Fine-grained lineage tracks the relationships between inputs and outputs of a query, enabling applications such as debugging, auditing, and what-if analytics. Despite its practical value, existing implementations fall short in practice. Relational approaches incur significant overhead on analytical workloads, while physical approaches are designed for row-oriented engines and do not translate to modern vectorized interpreted execution. Beyond runtime overhead, integration into mature engines requires balancing engineering cost with performance, a trade-off prior work has largely ignored. Even with fast capture, interactive applications require both fast lineage access and lineage representations designed for efficient evaluation. This dissertation addresses these challenges.

First, we show that low-overhead, tuple-level lineage capture is feasible in interpreted, vectorized engines by exploiting the equivalence between lineage and data movement. Using static data-flow analysis, we identify existing execution variables that encode lineage implicitly, and instrument DuckDB to create Smokedduck, a lineage-enabled analytical engine. On TPC-H, Smokedduck reduces lineage capture overheads by up to three orders of magnitude compared to prior approaches and supports interactive lineage queries at sub-second latency.

Second, we provide the first apples-to-apples evaluation of Query-level, Operator-level, and Function-level capture within a single analytical engine. Query-level overhead is dominated by serialization and materialization, Operator-level reduces this but adds annotation overhead for aggregations, and Function-level achieves the lowest overhead at the highest engineering cost. Our results suggest that combining Operator-level and Function-level instrumentation provides the best balance between engineering effort and runtime performance.

Third, we show how optimizing lineage access and representations enables interactive what-if analytics. What-if queries underlie many provenance-based applications, including debugging, sensitivity analysis, and hypothetical reasoning, and their response is bounded by intervention evaluation latency. By leveraging integer-based lineage rather than symbolic representations, our system accelerates intervention evaluation by up to four orders of magnitude over existing provenance-based methods, raising throughput to >1𝑀 interventions per second and making it possible to brute-force existing applications.

Together, these contributions show that fine-grained lineage can be captured with low overhead in modern vectorized engines, that engineering cost is a critical but previously unexamined dimension of lineage system design, and that lineage can be represented and evaluated efficiently enough to power interactive what-if applications at scale.