Indexes driven mechanism for grouped SQL queries

eng Artykuł w języku angielskim DOI:

wyślij Radosław Boroński , Grzegorz Bocewicz Politechnika Koszalińska - Wydział Elektroniki i Informatyki - Katedra Podstaw Informatyki i Zarządzania

Pobierz Artykuł

Abstract

This paper discusses the problem of automatic minimization of a response time for a database workload by a proper choice of indexes on production systems. The main objective of our contribution is to illustrate the database queries as a group and search for good indexes for the group instead of an individual query. We present queries block relation conditions for applying the concept of grouped queries index selection. We also introduce genetic algorithm that we use in experimental test. Numerical results are presented to show quality of the recommended approach.

Keywords

database, genetic algorithms, grouped queries, index

Mechanizm wyznaczania indeksów dla grupy zapytań SQL

Streszczenie

Autorzy podejmują się problemu automatycznej minimalizacji czasu odpowiedzi bazy danych na zadaną grupę zapytań SQL poprzez poprawny dobór indeksów dla systemów produkcyjnych. Głównym naszym celem jest traktowanie zapytań jako grupy i szukanie odpowiednich indeksów dla całej grupy a nie dla pojedynczego zapytania. Przedstawiamy warunki które musi spełniać grupa zapytań. Proponujemy użycie algorytmu genetycznego do poszukiwania indeksów w testach doświadczalnych. Prezentujemy wyniki testów eksperymentalnych jako uzasadnienie użycia proponowanego podejścia.

Słowa kluczowe

algorytm genetyczny, baza danych, grupa indeksów, indeks

Bibliografia

  1. Agrawal S.. Chaudhuri S.. Kollar L.. Marathe A., Narasayya V., and Syamala M.. Database Tuning Advisor for Microsoft SQL Server 2005, [in:] Proceedings of the 30th International Conference on Very Large Databases, 2004.
  2. Back T., Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press Oxford, UK, 1996.
  3. Bruno N., Chandhnri S., Automatic physical database-tuning: a relaxation-based approach, [in:] Proceedings of the 2005 ACM SIGMOD international conference on Management of Data, ACM New York, NY, USA, 2005, 227-238.
  4. Chandhnri S.. Narasayya V., An efficient Cost-Driven Index Selection Tool for MS SQL Server, Very Large Data Bases Endowment Inc. 1997.
  5. Comers D., The Ubiquitous B-Tree, “Computing Surveys”, 11 (2), DOI:10.1145/356770.356776, 123-137.
  6. Dageville B.. Das D., Dias K.. Yagoub K., Zait M., Ziauddin M.. Automatic SQL Tuning in Oracle 10g. Proceedings of the 30th International Conference on Very Large Databases, 2004.
  7. Dawes C, Bryla B., Johnson J., Weishan M., OCA Oracle 10g Administration I, Sybex, 2005, 173.
  8. Finkelstein S., Schkolnick M., Tiberio P., Physical database design for relational databases. ACM Trans. Database Syst. 13(1), (1988), 91-128.
  9. Frank M., Omiecinski M., Adaptive and Automated Index Selection in RDBMS, Proceedings of EDBT. 1992.
  10. Gupta H., Harinarayan V., Rajaraman A., Ullman J.D., Index Selection for OLAP. In Proceedings of the Internatoinal Conference on Data Engineering. Birmingham, U.K., April 1997, 208-219.
  11. Knuth D., The Art of Computer Programming. Vol. 3, Sorting and Searching. Addison-Wesley, Reading, Mass., 1973.
  12. Knuth D., Sorting and Searching. The Art of Computer Programming. Vol. 3 (Second ed.), Addison-Wesley.
  13. Kołaczkowski P.. Rybiński H., Automatic Index Selection in RDBMS by Exploring Query Execution Plan Space. Studies in Computational Intelligence. Vol. 223, Springer, 2009, 3-24
  14. Kratica J., Ljubic I., Tosic D., A Genetic Algorithm for the Index Selection Problem. EvoVVorkshops’03. Proceedings of the 2003 International Conference on Applications of Evolutionary Computing, 2003.
  15. Lehman P.L.. Efficient locking for concurrent operations on B-trccs, ACM Transactions on Database Systems (TODS), Vol. 6, Iss. 4, Dec. 1981. G50 G70.
  16. Maggie Y., Ip L., Saxton LV., Vijay V. Raghavan, On the Selection of an Optimal Set of Indexes, IEEE Transactions on Software Engineering, 9(2), March 1983, 135-143.
  17. Schkolnick M., The Optimal Selection of Indices for Files, “Information Systems”, Vol.1. 1975.
  18. Schnaitter K., On-line Index Selection for Physical Database Tuning, ProQuest, UMI Dissertation Publishing. 2011.
  19. [http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html] - Tatham S., Counted B-Trees.
  20. Wedekind H.. On the selection of access paths in a data base system. In Data Base Management Klimbie J.W., Koffeman K.L.. Eds. North-Holland, Amsterdam, 1974. 385 397.
  21. [http://www.oracle.com/us/technologies/java/overview/index.html].