Efficient Computation of Provenance for Query Result Exploration

Murali Mani, Naveenkumar Singaraj, Zhenyan LiuIPAW 2021 · DOI

TL;DR

This paper tackles the challenge of efficiently computing provenance (the "why" and "how" behind data) for exploring query results in databases. They introduce novel optimization techniques and a hybrid materialization approach that significantly speeds up provenance retrieval, sometimes by orders of magnitude, making interactive data exploration more practical.

What Problem Does This Paper Address?

When users interact with databases, they often ask an initial query and then want to "drill down" into the results to understand why certain data appeared. This process is called query result exploration, and it relies heavily on provenance information. Traditionally, computing provenance can be computationally expensive, especially for complex queries. The paper addresses this by proposing methods to optimize the generation of provenance queries, making the exploration process much faster and more efficient. They focus on "which-provenance," a common semantic that identifies the input data contributing to a result.

Methods

The authors build upon existing provenance research by introducing two main innovations:

  • Constraint-based Optimization: They identify and leverage "dependencies" (tuple generating dependencies) specific to the query result exploration scenario. These dependencies allow them to simplify provenance retrieval queries by reducing the number of joins required. They formalize this with a theorem and develop an algorithm (Algorithm 1) to automatically optimize provenance queries based on these constraints.
  • Hybrid Materialization: Instead of materializing all intermediate query results (which can be massive), they propose a hybrid approach. This involves materializing only a subset of intermediate data, specifically augmenting it with the keys of relevant base tables. This "materialized view" (RK) is then used to speed up provenance computations for the base tables. They also investigate how to determine which keys are most beneficial to materialize.

Datasets

The paper uses the TPC-H benchmark dataset for evaluation. They generated data at a 1GB scale and conducted experiments on a PostgreSQL 10 database server.

Key Insights and Ideas

  • Provenance Optimization is Crucial: The paper strongly demonstrates that optimizing provenance queries, even without materialization, can lead to significant performance gains.
  • Smart Materialization Pays Off: Materializing all intermediate data (the "eager" approach) can be prohibitively expensive. A targeted, "hybrid" approach that materializes only key information offers a much better cost-benefit trade-off.
  • Dependencies are Powerful: The identified dependencies are not just theoretical; they translate directly into practical query optimization, reducing join complexity.
  • Query Result Exploration is a Key Use Case: The work is specifically tailored to the interactive nature of exploring query results, where speed is paramount.

Key Results

The paper presents compelling performance improvements:

  • Algorithm 1 (Lazy Optimization): For 36.84% of the TPC-H queries, their optimization algorithm (O1) generated provenance queries with fewer joins, leading to faster execution times compared to a baseline approach (W).
  • Hybrid Approach (O2): Their hybrid materialization approach (O2) significantly outperformed the eager approach (G) for both original query computation and provenance retrieval. For Q18, G took about 420 times longer than O2 for original query computation.
  • Provenance Retrieval Speedup: O2 consistently outperformed G for provenance retrieval, even though G had a larger materialized view. This highlights the effectiveness of their targeted materialization strategy. In some cases, provenance retrieval times were reduced by orders of magnitude.

Limitations and Future Work

  • Query Language Restrictions: The current work focuses on SQL queries restricted to ASPJ (Algebraic Specification of Programs with Joins) and set semantics. They acknowledge that extending to bag semantics, unions, and outer joins is a future research direction.
  • Materialization Strategy: While their hybrid approach is effective, determining the optimal set of keys to materialize for RK is still an area for further investigation. They mention exploring more effective ways to search this space and incorporating workload information into the cost model.
  • Other Provenance Semantics: The paper focuses on "which-provenance." Future work includes investigating how to derive other provenance semantics (like "how-provenance") from their optimized provenance tables.
  • Navigation of Provenance: Exploring efficient ways to navigate the provenance information itself is also a promising avenue.

Summary updated

BibTeX
@inproceedings{mani2021efficient,
  author = {Murali Mani and Naveenkumar Singaraj and Zhenyan Liu},
  title = {{Efficient Computation of Provenance for Query Result Exploration}},
  booktitle = {IPAW},
  year = {2021},
  doi = {10.1007/978-3-030-80960-7\_8},
}
Figure