Deletion based view maintenance is a building block in many query explanation and analytics applications, such as sensitivity analysis, what-if analysis, data cleaning, and probabilistic databases, which require exploring how a query's output result changes when excluding (deleting) subsets of input relations (referred to as “deletion interventions”). These applications' ability to remain interactive is limited by how fast they can recompute output results, especially over complex queries and large data. A critical limitation in existing engines is their performance. To remain interactive, existing approaches either restrict the types of aggregation functions, require explanations to be pre-specified, or apply sampling and approximation. We show how to build an interactive deletion intervention evaluation engine for SPJA queries, by Ieveraging recent advances in fast fine-grained provenance that captures input/output relationship for each physical operator in a denormalized compact pointer-free format. We use provenance to propagate the deletion status of tuples per operator, in a tight loop that leads to improvement in instruction and data locality. In addition, this representation is amenable to a variety of physical optimizations, such as dictionary-encoding, bit-packing, vectorization, and parallelization. Operators' output tuples can be evenly split across threads, and their deletion status can be computed independently. Our preliminary results show that on the TPC-H workload, our engine takes on average 9ms to evaluate 1K deletion interventions at a time, achieving on average wins of 3 orders of magnitude over DBToaster, a state-of-the art IVM based engine, and wins of 4 orders of magnitude against existing provenance based approaches. Utilizing tight loops and a cache-friendly provenance and intervention representation enable us to evaluate thousands of deletion interventions at interactive speed, and enable interactive time query explanations over more complex queries and data than previously possible.

What-if queries are the building blocks for many explanation and analytics applications—sensitivity analysis, hypothetical reasoning, data cleaning, probabilistic databases—that explore how a query's output changes due to input data changes. Their response time is bounded by intervention evaluation latency, which can be in the minute or hours for complex queries and large datasets. FaDE is a compilation engine that uses provenance to evaluate hypothetical deletion and scaling interventions at low latency and high throughput. FaDE forgoes conventional provenance representations as symbolic expressions and leverages their underlying relational structure. This accelerates intervention evaluation on average by 1000× against IVM and 10,000× against prior provenance-based approaches. In addition, FaDE develops a suite of optimizations (e.g., compilation, parallelization, incremental evaluation, sparse representations) that collectively raise evaluation throughput to >1 million interventions per sec—a rate that can brute-force existing applications within 1 s.

Interactive data visualization and exploration (DVE) applications, such as the one in Figure 1, have rapidly grown in popularity with use cases in numerous sectors [2, 4, 9, 11, 15]. Like typical web services, DVE applications may be run on heterogeneous client devices and networks, with users expecting fast response times under 100 ms [12]. However, the resource demands of DVE applications are magnified and highly unpredictable, making it difficult to achieve such interactivity.