2020/09/21 by Max Halford, Halford, Max, Philippe Pierre +3 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Bayesian Modeling and Causal Inference #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2009.09883
openalex publication_date 2020/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Relational query optimisers rely on cost models to choose between different\nquery execution plans. Selectivity estimates are known to be a crucial input to\nthe cost model. In practice, standard selectivity estimation procedures are\nprone to large errors. This is mostly because they rely on the so-called\nattribute value independence and join uniformity assumptions. Therefore,\nmultidimensional methods have been proposed to capture dependencies between two\nor more attributes both within and across relations. However, these methods\nrequire a large computational cost which makes them unusable in practice. We\npropose a method based on Bayesian networks that is able to capture\ncross-relation attribute value dependencies with little overhead. Our proposal\nis based on the assumption that dependencies between attributes are preserved\nwhen joins are involved. Furthermore, we introduce a parameter for trading\nbetween estimation accuracy and computational cost. We validate our work by\ncomparing it with other relevant methods on a large workload derived from the\nJOB and TPC-DS benchmarks. Our results show that our method is an order of\nmagnitude more efficient than existing methods, whilst maintaining a high level\nof accuracy.\n