# An Approach Based on Bayesian Networks for Query Selectivity Estimation

arXiv: https://arxiv.org/abs/1907.06295 · HTML: https://mlsanity.com/paper/1907.06295/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2019.

## Built on by (most cited first, 6 of 6)

- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [FactorJoin: A New Cardinality Estimation Framework for Join Queries](https://mlsanity.com/paper/2212.05526/) (2022)
- [Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks](https://mlsanity.com/paper/2303.01140/) (2023)
- [ACE: A Cardinality Estimator for Set-Valued Queries](https://mlsanity.com/paper/2503.14929/) (2025)
- [A Lightweight Learned Cardinality Estimation Model](https://mlsanity.com/paper/2508.09602/) (2025)

## Abstract (arXiv)

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.