M2HSE - metoda estymacji selektywności pewnej klasy zapytań zakresowych oparta na wielowymiarowym rozkładzie wartości atrybutów oraz rozkładach brzegowych

Selektywność jest parametrem wyznaczanym przez bazodanowy optymalizator zapytań w celu wczesnego oszacowania rozmiaru danych spełniających warunek zapytania. Jest to czynność niezbędna do znalezienia optymalnego planu wykonania zapytania. Selektywność jest na ogół oszacowywana na podstawie histogramów, które są nieparametrycznymi estymatorami rozkładów wartości atrybutów. Wyznaczanie selektywności dla zapytań z warunkiem selekcji opartym na kilku atrybutach wymaga wykorzystania wielowymiarowego histogramu estymującego łączny rozkład wartości atrybutów. Dokładność histogramów wielowymiarowych spada wraz ze wzrostem liczby wymiarów, co jest powszechnie znane pod nazwą problemu przekleństwa wymiarowości. Natomiast jednowymiarowe histogramy zbudowane dla pojedynczych atrybutów, które charakteryzują rozkład brzegowy, opisują ten jednowymiarowy rozkład dokładniej, ale oczywiście nie opisują zależności pomiędzy atrybutami. W niniejszym artykule zaproponowano metodę wyznaczania selektywności, opartą na histogramach opisujących zarówno rozkład łączny, jak i rozkłady brzegowe. Zaproponowana metoda (nazwana M2HSE) dotyczy pewnej klasy zapytań, w których zakresowy warunek selekcji oparty jest na wielu atrybutach. Dla takich zapytań przedstawiona metoda może pozwolić na wyznaczenie dokładniejszych przybliżeń wartości selektywności niż klasyczne metody, wykorzystujące histogramy opisujące tylko rozkład łączny albo tylko rozkłady brzegowe (gdzie zastosowane jest założenie o niezależności atrybutów).

---

Selectivity is a parameter obtained by database query optimizer for early estimation of size of data that satisfying a query condition. This is needed for finding the optimal query execution plan. Commonly, selectivity is estimated using histograms that are non-parametric estimators of attribute values distribution. Obtaining a selectivity for a query with a selection condition bases on a few attributes requires a multimensional histogram estimating joint distribution. Accuracy of multidimensional histograms decreases for high dimensions. It is well-known as the curse of dimensionality problem. One-dimensional histograms describing marginal distributions are more accurate, but they do not describe dependency between attributes. In this paper we propose a method of selectivity estimation based on both types of histograms describing either a multidimensional joint distribution or marginal ones. The method (named M2HSE) may be used for some kind of queries with a range selection condition based on many attributes. For such kind of queries, this method may give more accurate selectivity estimations than classical methods based on multidimensional histogram only or marginal histograms only (where the AVI rule is assumed).