  Relational query optimisers rely on cost models to choose between different
query execution plans. Selectivity estimates are known to be a crucial input to
the cost model. In practice, standard selectivity estimation procedures are
prone to large errors. This is mostly because they rely on the so-called
attribute value independence and join uniformity assumptions. Therefore,
multidimensional methods have been proposed to capture dependencies between two
or more attributes both within and across relations. However, these methods
require a large computational cost which makes them unusable in practice. We
propose a method based on Bayesian networks that is able to capture
cross-relation attribute value dependencies with little overhead. Our proposal
is based on the assumption that dependencies between attributes are preserved
when joins are involved. Furthermore, we introduce a parameter for trading
between estimation accuracy and computational cost. We validate our work by
comparing it with other relevant methods on a large workload derived from the
JOB and TPC-DS benchmarks. Our results show that our method is an order of
magnitude more efficient than existing methods, whilst maintaining a high level
of accuracy.

Databases