QuickSel: Quick Selectivity Learning with Mixture Models

Yongjoo Park, Shucheng Zhong, Barzan Mozafari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Estimating the selectivity of a query is a key step in almost any cost-based query optimizer. Most of today's databases rely on histograms or samples that are periodically refreshed by re-scanning the data as the underlying data changes. Since frequent scans are costly, these statistics are often stale and lead to poor selectivity estimates. As an alternative to scans, query-driven histograms have been proposed, which refine the histograms based on the actual selectivities of the observed queries. Unfortunately, these approaches are either too costly to use in practice - -i.e., require an exponential number of buckets - -or quickly lose their advantage as they observe more queries. In this paper, we propose a selectivity learning framework, called QuickSel, which falls into the query-driven paradigm but does not use histograms. Instead, it builds an internal model of the underlying data, which can be refined significantly faster (e.g., only 1.9 milliseconds for 300 queries). This fast refinement allows QuickSel to continuously learn from each query and yield increasingly more accurate selectivity estimates over time. Unlike query-driven histograms, QuickSel relies on a mixture model and a new optimization algorithm for training its model. Our extensive experiments on two real-world datasets confirm that, given the same target accuracy, QuickSel is 34.0x - 179.4x faster than state-of-the-art query-driven histograms, including ISOMER and STHoles. Further, given the same space budget, QuickSel is 26.8% - 91.8% more accurate than periodically-updated histograms and samples, respectively.

Original languageEnglish (US)
Title of host publicationSIGMOD 2020 - Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
PublisherAssociation for Computing Machinery
Pages1017-1033
Number of pages17
ISBN (Electronic)9781450367356
DOIs
StatePublished - Jun 14 2020
Externally publishedYes
Event2020 ACM SIGMOD International Conference on Management of Data, SIGMOD 2020 - Portland, United States
Duration: Jun 14 2020Jun 19 2020

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Conference

Conference2020 ACM SIGMOD International Conference on Management of Data, SIGMOD 2020
CountryUnited States
CityPortland
Period6/14/206/19/20

Keywords

  • approximate query processing
  • cardinality estimation
  • database learning
  • selectivity estimation
  • selectivity learning

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'QuickSel: Quick Selectivity Learning with Mixture Models'. Together they form a unique fingerprint.

Cite this