Database Learning
Authors:
Open Access
- 9 May 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 587-602
Abstract
In today's databases, previous query answers rarely benefit answering future queries. For the first time, to the best of our knowledge, we change this paradigm in an approximate query processing (AQP) context. We make the following observation: the answer to each query reveals some degree of knowledge about the answer to another query because their answers stem from the same underlying distribution that has produced the entire dataset. Exploiting and refining this knowledge should allow us to answer queries more analytically, rather than by reading enormous amounts of raw data. Also, processing more queries should continuously enhance our knowledge of the underlying distribution, and hence lead to increasingly faster response times for future queries. We call this novel idea---learning from past query answers---Database Learning. We exploit the principle of maximum entropy to produce answers, which are in expectation guaranteed to be more accurate than existing sample-based approximations. Empowered by this idea, we build a query engine on top of Spark SQL, called Verdict. We conduct extensive experiments on real-world query traces from a large customer of a major database vendor. Our results demonstrate that database learning supports 73.7% of these queries, speeding them up by up to 23.0x for the same accuracy level compared to existing AQP systems.Keywords
All Related Versions
Funding Information
- National Science Foundation (1629397, 1553169, 1544844)
This publication has 56 references indexed in Scilit:
- Approximating query answering on RDF databasesWorld Wide Web, 2011
- StatAdvisorProceedings of the VLDB Endowment, 2009
- General Database Statistics Using Entropy MaximizationLecture Notes in Computer Science, 2009
- Confidence bounds for sampling-based group by estimatesACM Transactions on Database Systems, 2008
- Sampling-based estimators for subset-based queriesThe VLDB Journal, 2008
- Optimized stratified sampling for approximate query processingACM Transactions on Database Systems, 2007
- Answering queries using views: A surveyThe VLDB Journal, 2001
- Join synopses for approximate query answeringACM SIGMOD Record, 1999
- Online aggregationACM SIGMOD Record, 1997
- An Overview of Machine Learning1983