A Session-Based Approach to Fast-But-Approximate Interactive Data Cube Exploration

With the proliferation of large datasets, sampling has become pervasive in data analysis. Sampling has numerous benefits—from reducing the computation time and cost to increasing the scope of interactive analysis. A popular task in data science, well-suited toward sampling, is the computation of fast-but-approximate aggregations over sampled data. Aggregation is a foundational block of data analysis, with data cube being its primary construct. We observe that such aggregation queries are typically issued in an ad-hoc, interactive setting. In contrast to one-off queries, a typical query session consists of a series of quick queries, interspersed with the user inspecting the results and formulating the next query. The similarity between session queries opens up opportunities for reusing computation of not just query results, but also error estimates. Error estimates need to be provided alongside sampled results for the results to be meaningful. We propose Sesame, a rewrite and caching framework that accelerates the entire interactive <underline>ses</underline>sion of aggregation queries over <underline>sam</underline>pl<underline>e</underline>d data. We focus on two unique and computationally expensive aspects of this use case: query speculation in the presence of sampling, and error computation, and provide novel strategies for result and error reuse. We demonstrate that our approach outperforms conventional sampled aggregation techniques by at least an order of magnitude, without modifying the underlying database.