Selectivity estimation for range predicates using lightweight models
Authors:
Top Cited Papers
Open Access
- 1 May 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 12 (9) , 1044-1057
Abstract
Query optimizers depend on selectivity estimates of query predicates to produce a good execution plan. When a query contains multiple predicates, today's optimizers use a variety of assumptions, such as independence between predicates, to estimate selectivity. While such techniques have the benefit of fast estimation and small memory footprint, they often incur large selectivity estimation errors. In this work, we reconsider selectivity estimation as a regression problem. We explore application of neural networks and tree-based ensembles to the important problem of selectivity estimation of multi-dimensional range predicates. While their straightforward application does not outperform even simple baselines, we propose two simple yet effective design choices, i.e., regression label transformation and feature engineering, motivated by the selectivity estimation context. Through extensive empirical evaluation across a variety of datasets, we show that the proposed models deliver both highly accurate estimates as well as fast estimation.Keywords
This publication has 23 references indexed in Scilit:
- Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation2015
- Efficiently adapting graphical models for selectivity estimationThe VLDB Journal, 2012
- Synopses for Massive Data: Samples, Histograms, Wavelets, SketchesFoundations and Trends® in Databases, 2011
- Preventing bad plans by bounding the impact of cardinality estimation errorsProceedings of the VLDB Endowment, 2009
- A pay-as-you-go framework for query execution feedbackProceedings of the VLDB Endowment, 2008
- Consistent selectivity estimation via maximum entropyThe VLDB Journal, 2006
- Selectivity estimators for multidimensional range queries over real attributesThe VLDB Journal, 2005
- STHoles2001
- Selectivity estimation using probabilistic models2001
- Self-tuning histograms1999