Model-based Approximate Query Processing
  Interactive visualizations are arguably the most important tool to explore,
understand and convey facts about data. In the past years, the database
community has been working on different techniques for Approximate Query
Processing (AQP) that aim to deliver an approximate query result given a fixed
time bound to support interactive visualizations better. However, classical AQP
approaches suffer from various problems that limit the applicability to support
the ad-hoc exploration of a new data set: (1) Classical AQP approaches that
perform online sampling can support ad-hoc exploration queries but yield low
quality if executed over rare subpopulations. (2) Classical AQP approaches that
rely on offline sampling can use some form of biased sampling to mitigate these
problems but require a priori knowledge of the workload, which is often not
realistic if users want to explore a new database. In this paper, we present a
new approach to AQP called Model-based AQP that leverages generative models
learned over the complete database to answer SQL queries at interactive speeds.
Different from classical AQP approaches, generative models allow us to compute
responses to ad-hoc queries and deliver high-quality estimates also over rare
subpopulations at the same time. In our experiments with real and synthetic
data sets, we show that Model-based AQP can in many scenarios return more
accurate results in a shorter runtime. Furthermore, we think that our
techniques of using generative models presented in this paper can not only be
used for AQP in databases but also has applications for other database problems
including Query Optimization as well as Data Cleaning.
