Query templates identified using data provenance patterns
Data Provenance Aggregation and Structural Descriptors for Query-Template Identification
DatabasesMachine Learning
Summary
Finding similar database queries helps people understand patterns and catch problems, but current methods miss how data flows through queries. The authors propose a new way to compare queries based on the detailed history of data used and created during execution. They build summaries that capture the structure and frequency of this data flow, enabling better matching of queries even when using large numbers of examples. Their approach improves accuracy over time and works efficiently with limited past data.
What this means in practice
- •For database administrators: Identify recurring query patterns for workload management and auditing from historical data flows within query results.
- •For data engineering teams: Improve debugging and anomaly detection by recognizing query behavior based on actual data dependencies rather than text or plans.
Authors
Paulo Pintor, Rogério Costa, José Moreira
Abstract
Runtime query similarity identification supports several activities, including workload analysis, identifying recurring behaviour, auditing, debugging, and anomaly detection. Existing methods for evaluating query similarity mostly rely on SQL text, execution plans, or result values but do not account for input data or how results are derived during query execution. This paper proposes a novel approach using data provenance for query-template identification. We construct query-level profiles that capture explicit data dependencies, occurrence frequencies, and structural properties by aggregating tuple-level Lineage and Why-provenance across entire query results. We also derive Provenance Structural Descriptors (PSD), which summarise these profiles using a small set of numerical features. We evaluate our proposals using these profiles to identify query templates over \(12{,}500\) distinct query instances generated from parametrised TPC-DS query templates. The experimental evaluation shows that query templates can be identified solely from their provenance footprints, and that accuracy improves as more historical data becomes available. It also shows that PSD achieve high classification accuracy with limited training history and low test-processing cost.