Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: estymacja selektywności zapytań

Sortuj według:

Ogranicz wyniki do:

Zastosowanie predykcji rozkładu wartości atrybutu w celu poprawy dokładności estymacji selektywności zapytań

Augustyn D.

Studia Informatica

2013

Vol. 34, nr 2A

23--42

Parametr selektywności jest wykorzystywany w procesie optymalizacji zapytań. Uzyskanie selektywności wymaga nieparametrycznego estymatora rozkładu wartości atrybutu, tj. histogramu. Histogramy są tworzone w ramach procesu aktualizacji statystyk. Dla dużych baz danych aktualizacja statystyk jest wykonywana raczej rzadko, np. tylko w momentach małego obciążenia systemu. To powoduje, że histogramy nie opisują aktualnego rozkładu danych. Aby uzyskać bardziej aktualne histogramy, powinno się zastosować mechanizm predykcji rozkładu. Pozwoli to na bardziej dokładną estymację selektywności. W niniejszym artykule zaproponowano metodę ekstrapolacji rozkładu wartości atrybutów. Metoda ta dokonuje predykcji momentów szukanego, ekstrapolowanego rozkładu. W celu jego wyznaczenia opisywana metoda wykorzystuje zasadę maksimum entropii z uwzględnieniem wartości momentów znalezionych w ramach procedury predykcji.

A selectivity parameter is needed in query optimization process. Obtaining the query selectivity requires a non-parametric estimator of attribute value distribution, i.e. a histogram. Histograms are produced during update statistics process. For large databases the update statistics process is performed rather seldom, e.g. only during time of low workload of a system. This results that histograms do not describe actual data distribution. To obtain a more accurate histogram, a prediction mechanism should be introduced. This results obtaining a more accurate estimation of selectivity. 24 D. R. Augustyn The method of extrapolation of attribute value distribution is proposed in this paper. This method predicts moments of the extrapolated distribution. It uses the maximum entropy principle for obtaining the extrapolated distribution subject to the predicted values of the distribution moments.

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

Augustyn D.

Studia Informatica

2013

Vol. 34, nr 2A

43--56

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).