OneProvenance: Efficient Extraction of Dynamic Coarse-Grained Provenance from Database Logs

Fotis Psallidas, Ashvin Agrawal, Chandru Sugunan, Khaled Ibrahim, Konstantinos Karanasos, Jesús Camacho-Rodríguez, Avrilia Floratou, Carlo Curino, Raghu Ramakrishnan

Abstract

In modern data governance, tracking the lineage of data—its origin, movement, and transformations—is essential for auditing and observability. Traditional methods for provenance extraction often face a trade-off between the speed of static analysis and the completeness of dynamic execution plan analysis. OneProvenance bridges this gap by shifting the focus from heavy physical query plans to lightweight database event logs. By utilizing a novel tree-based dependency model called the QQTree and aggressive noise-filtering techniques, OneProvenance achieves up to an 18x improvement in storage efficiency over state-of-the-art methods while maintaining a negligible performance footprint on the source database.

Introduction

As data ecosystems grow in complexity, knowing the "provenance" of data is critical. Static extraction tools analyze code and schemas but often miss "hidden" logic like triggers or dynamic SQL. Conversely, dynamic extraction tools that rely on physical query plans introduce significant design overheads, slowing down databases by up to 18x and generating massive logs. Furthermore, these tools often treat every system query as equally important, burying meaningful business logic under a mountain of irrelevant data and failing to capture the context of nested dependencies, such as stored procedures.

System Architecture

OneProvenance introduces a shift in strategy by analyzing query event logs (such as Azure SQL’s xEvents) instead of execution plans. The system architecture is designed to process these logs through several specialized stages to extract meaningful lineage information.

The OneProvenance system architecture, showing the flow from database events to the final data catalog.

The workflow begins with the Activity Collector, which groups related events into "activities." These activities are then processed by the Runtime Information Extractor and the Provenance Extractor. The Stitcher serves as the system's core, merging runtime metadata (e.g., CPU usage, user identity) with structural provenance (table and column-level dependencies). Finally, the Uploader pushes the enriched entities and relationships to a data catalog.

The QQTree and Dependency Modeling

A central innovation of OneProvenance is the QQTree (Query-Query Tree). Instead of viewing queries in isolation, the system builds a hierarchical model that explicitly maps parent-child relationships. This allows the system to capture dependencies where a stored procedure might trigger a sequence of nested queries or statements.

The construction of a QQTree: (a) shows the sequence of events with parent guides, and (b) shows the resulting hierarchical tree structure.

This hierarchical approach enables "loop compression." If a stored procedure executes a query 1,000 times in a loop, OneProvenance can compress these iterations, logging only the most relevant data to save space and reduce noise. This allows users to either look at the high-level lineage of an entire procedure or "drill down" into specific internal queries.

Key Results and Performance

The authors evaluated OneProvenance using industry-standard benchmarks, including TPC-H and TPC-DS for analytical workloads, TPC-C for transactional stress testing, and SQL-ProcBench for complex procedural logic.

  • Efficiency: OneProvenance requires approximately 18x less storage for logs compared to plan-based extraction methods.
  • Minimal Overhead: In TPC-C stress tests, the performance impact on the source database was nearly indistinguishable from a database with no logging enabled. In contrast, plan-based logging caused transaction rates to drop by a factor of three.
  • Noise Reduction: Through filtering and loop compression, the system reduced the size of resulting provenance graphs by orders of magnitude without losing critical lineage information.

Conclusion

OneProvenance demonstrates that physical execution plans are often overkill for coarse-grained (table/column level) provenance. By leveraging query text and schema metadata, the system provides a production-ready solution that is currently deployed at scale within Microsoft Purview. Future work will focus on handling extreme load scenarios where event logs might be dropped and developing more sophisticated semantic filters to automatically distinguish business-critical queries from system noise.

Summary updated

BibTeX
@article{psallidas2023oneprovenance,
  author = {Fotis Psallidas and Ashvin Agrawal and Chandru Sugunan and Khaled Ibrahim and Konstantinos Karanasos and Jesús Camacho-Rodríguez and Avrilia Floratou and Carlo Curino and Raghu Ramakrishnan},
  title = {{OneProvenance: Efficient Extraction of Dynamic Coarse-Grained Provenance from Database Logs}},
  journal = {Proc. VLDB Endow.},
  year = {2023},
  doi = {10.14778/3611540.3611555},
}
Figure