Metoda analizy głównych składowych w szacowaniu selektywności zapytań

• Autorzy: Augustyn D.

Warianty tytułu

EN

Principal component analysis in query selecivity estimation

• Języki publikacji: PL

Abstrakty

PL

Selektywność zapytania jest parametrem pozwalającym określić spodziewany rozmiar wyniku zapytania. Oszacowanie selektywności wymagane jest do wyznaczania optymalnego sposobu realizacji zapytania. Zadaniem tym zajmuje się moduł optymalizatora SZBD. Obliczanie selektywności jest szczególnie utrudnione w zapytaniach z warunkami wieloatrybutowymi, gdzie potrzebny jest nieparametryczny estymator wielowymiarowego rozkładu wartości atrybutów. Zastosowanie wielowymiarowego histogramu w takiej roli może być zbyt kosztowne pod względem zajętości pamięci, szczególnie w przypadku wysokiej wymiarowości zagadnienia. W takiej sytuacji użyteczne może być podejście wykorzystujące metodę analizy składowych głównych, redukujące wymiarowość. Dodatkowo można zastosować metodę mnożenia selektywności, wyznaczonych niezależnie z jednowymiarowych rozkładów brzegowych, określonych w zredukowanej przestrzeni. Upraszcza to i przyspiesza przedstawioną w artykule metodę szacowania selektywności. W artykule opisano również sposób implementacji zaproponowanego rozwiązania w SZBD Oracle, z wykorzystaniem modułu rozszerzającego działanie optymalizatora zapytań – Oracle Data Cartridge Interface Statistics.

EN

Query selectivity allows to estimate the size of query results. It is required for obtaining the optimal method of query execution. This is a main goal of a query optimizer activities. Selectivity calculations for queries with a complex multi-attribute selection condition require a non-parametric estimator of multi-dimensional probability density function of distribution of table attribute values. Using a multi-dimensional histogram as a representation of multi-dimensional distribution is very space-consuming for high dimensions. The approach based on Principal Component Analysis allows to reduce dimensionality and makes the representation space efficient. Additionally the attribute value independence rule (with multiplicity of simple selectivities) may be used in a dimensions-reduced space so the method of the PCA-based selectivity estimation becomes simpler and more effective. The paper also presents the implementation of the proposed solution in DBMS Oracle as the extension of the query optimizer by using Oracle Data Cartridge Interface Statistics module.

Słowa kluczowe

PL

optymalizator zapytań; PCA; selektywność zapytań; Oracle ODCIStats; histogram

EN

query optimizer; PCA; query selectivity; Oracle ODCIStats; histogram

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2011
• Tom: Vol. 32, nr 2A
• Strony: 21--36
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Augustyn D.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice,

Bibliografia

• 1. Krzanowski W. J.: Principles of Multivariate Analysis: A User's Perspective. Oxford University Press, 2000.
• 2. Possala V., Ioannidis Y. E.: Selectivity Estimation without the Attribute Value Independence Assumption. Proc. of the 23rd Int. Conf. on Very Large Databases, The VLDB Journal, Athens 1997.
• 3. Gunopulos D., Kollios G., Tsotras V. J.: Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes. ACM SIGMOD 2000, Dallas 2000.
• 4. Lee. J., Deok-Hwan K., Chin-Wan Ch.: Multi-dimensional Selectivity Estimation Using Compressed Histogram Estimation Information. Proc. of ACM SIGMOD Int. Conf. on Management of Data. ACM, Philadelphia 1999.
• 5. Chakrabarti K., Garofalakis M., Rastogi R., Shim K.: Approximate Query Processing Using Wavelets. VLDB Journal. vol. 10, no. 2-3, Springer-Verlag, New York 2001.
• 6. Bruno N., Chaudhuri S., Gravano L.: STHoles: a multidimensional workload-aware histogram. Proc. of ACM SIGMOD Int. Conf. on Management of Data 30(2). ACM, New York 2001.
• 7. Getoor L., Taskar B., Koller D.: Selectivity estimation using probabilistic modes. Proc. Of ACM SIGMOD Int. Conf. on Management of Data. ACM, New York 2001.
• 8. Augustyn. D. R.: Applying advanced methods of query selectivity estimation in Oracle DBMS. Advances in Soft Computing. Man-Machine Interactions. Springer-Verlag, Berlin Heidelberg 2009.
• 9. Augustyn. D. R., Warchał Ł.Ś Zastosowanie sieci Bayesa w szacowaniu selektywności zapyta1 w optymalizatorze zapyta1 serwera bazy danych Oracle. Studia Informatica, Vol. 32, No. 1A (94), Gliwice 2011.
• 10. Oracle 10g. Using extensible optimizer (2010). http://download.oracle.com/docs/cd/B14117 01/appdev.101/b10800/dciextopt.htm.
• 11. Oracle Database SQL Reference. Analyze (2011). http//download.oracle.com/docs/cd/B19306_01/server.102/b14200/statements_4005.htm.