Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation
Authors:
Open Access
- 27 May 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1477-1492
Abstract
Quickly and accurately estimating the selectivity of multidimensional predicates is a vital part of a modern relational query optimizer. The state-of-the art in this field are multidimensional histograms, which offer good estimation quality but are complex to construct and hard to maintain. Kernel Density Estimation (KDE) is an interesting alternative that does not suffer from these problems. However, existing KDE-based selectivity estimators can hardly compete with the estimation quality of state-of-the art methods. In this paper, we substantially expand the state-of-the-art in KDE-based selectivity estimation by improving along three dimensions: First, we demonstrate how to numerically optimize a KDE model, leading to substantially improved estimates. Second, we develop methods to continuously adapt the estimator to changes in both the database and the query workload. Finally, we show how to drastically improve the performance by pushing computations onto a GPU. We provide an implementation of our estimator and experimentally evaluate it on a variety of datasets and workloads, demonstrating that it efficiently scales up to very large model sizes, adapts itself to database changes, and typically outperforms the estimation quality of both existing Kernel Density Estimators as well as state-of-the-art multidimensional histograms.Keywords
Funding Information
- Bundesministerium für Forschung, Technologie und Raumfahrt (01IS12056)
This publication has 36 references indexed in Scilit:
- Maintaining bounded-size sample synopses of evolving datasetsThe VLDB Journal, 2007
- Consistent selectivity estimation via maximum entropyThe VLDB Journal, 2006
- Selectivity estimators for multidimensional range queries over real attributesThe VLDB Journal, 2005
- A Brief Survey of Bandwidth Selection for Density EstimationJournal of the American Statistical Association, 1996
- Cross-Validation of Multivariate DensitiesJournal of the American Statistical Association, 1994
- Comparison of Smoothing Parameterizations in Bivariate Kernel Density EstimationJournal of the American Statistical Association, 1993
- Variable Kernel Density EstimationThe Annals of Statistics, 1992
- On the propagation of errors in the size of join resultsACM SIGMOD Record, 1991
- Random sampling with a reservoirACM Transactions on Mathematical Software, 1985
- Implications of certain assumptions in database performance evauationACM Transactions on Database Systems, 1984