OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

An Approach Based on Bayesian Networks for Query Selectivity Estimation

Halford, Max and Saint Pierre, Philippe and Morvan, Franck An Approach Based on Bayesian Networks for Query Selectivity Estimation. (2019) In: 24th International Conference on Database Systems for Advanced Applications (DASFAA 2019), 22 April 2019 - 25 April 2019 (Chiang Mai, Thailand).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1007/978-3-030-18579-4_1


The efficiency of a query execution plan depends on the accuracy of the selectivity estimates given to the query optimiser by the cost model. The cost model makes simplifying assumptions in order to produce said estimates in a timely manner. These assumptions lead to selectivity estimation errors that have dramatic effects on the quality of the resulting query execution plans. A convenient assumption that is ubiquitous among current cost models is to assume that attributes are independent with each other. However, it ignores potential correlations which can have a huge negative impact on the accuracy of the cost model. In this paper we attempt to relax the attribute value independence assumption without unreasonably deteriorating the accuracy of the cost model. We propose a novel approach based on a particular type of Bayesian networks called Chow-Liu trees to approximate the distribution of attribute values inside each relation of a database. Our results on the TPC-DS benchmark show that our method is an order of magnitude more precise than other approaches whilst remaining reasonably efficient in terms of time and space.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in volume 11447 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN 978-3-030-18578-7 The original PDF is available at: https://link.springer.com/chapter/10.1007/978-3-030-18579-4_1
HAL Id:hal-02493882
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Deposited On:21 Feb 2020 10:41

Repository Staff Only: item control page