Thesis /

ROMDOC-THESIS-2016-391

Algoritmi de optimizare a interogărilor în sisteme de baze de date paralele

Odubăşteanu, Carmen Elena
2008-09-24

Abstract: Abstract Lucrarea prezintă modalităţi de optimizare a interogărilor pentru sisteme de baze de date paralele. Prezentarea este realizată într-un cadru unificat, bazat pe o abordare ierarhică, astfel încât să poată fi foarte uşor de integrat procedeele specifice fiecărui tip de paralelism. Trei tipuri de paralelism pot fi utilizate, numite astfel: paralelism intra-operator, inter-operator şi inter-interogare. În paralelismul intra-operator problema de bază este crearea sarcinilor obiectivul fiind cel de partiţionare a unui operator în sarcini astfel încât efortul să poată fi realizat de un număr dat de procesoare. Paralelismul inter-operator poate fi realizat fie prin execuţia paralelă a operatorilor independenţi fie prin procesare tip linie de asamblare (pipelining). În fiecare din cazuri, problemele cele mai importante sunt selecţia secvenţei de joncţiuni, care determină relaţiile de precedenţă dintre operatori şi structura pipeline ce poate fi exploatată, şi alocarea procesoarelor pentru fiecare operator rezultat. Pentru paralelismul interinterogare ideea de bază este tot alocarea procesoarelor, dar de data aceasta între mai multe interogări. În lucrare sunt de asemenea prezentaţi şi comparaţi mai mulţi algoritmi eficienţi (clasici, de referinţă cât şi contribuţii originale) pentru problema generării unui plan de execuţie paralel pentru un arbore de operatori de tip pipeline (în care toţi operatorii rulează în paralel utilizând paralelismul de tip inter-operator) atât pentru mediile omogene cât şi pentru mediile eterogene. Eterogenitatea resurselor a mai fost luată în considerare în contextul acestei probleme doar de A. Termehchy şi M. Ghodsi. Lucrarea este organizată după cum urmează: introducerea în domeniu (capitolul 1), în capitolul 2 sunt prezentate metodele de realizare a paralelismului de tip intra-operator în sistemele de bazele de date paralele. Capitolul 3 prezintă principalele metode de realizare a paralelismului inter-operator şi modalităţile de optimizare a interogărilor, atât în mediile centralizate cât şi în medii distribuite şi paralele; capitolul 4 prezintă cadrul general de rezolvare a problemei generării unui plan de execuţie paralel pentru paralelismul de tip pipeline şi algoritmi specifici pentru aceasta. Sunt propuşi mai mulţi algoritmi pentru sisteme omogene şi eterogene care ţin sau nu cont de anumite constrângeri de alocare a procesoarelor, precum şi optimizări ale algoritmilor descrişi. În capitolul următor, sunt evaluate performanţele (din mai multe puncte de vedere: rata medie de performanţă, rata de performanţă maximă, timpul mediu de execuţie, etc.) tuturor algoritmilor prezentaţi pentru cazul paralelismului de tip pipeline. Capitolul 6 conţine concluziile asupra lucrării şi posibilele dezvoltări ulterioare. Anexa A conţine o parte din codul sursă al aplicaţiilor implementate, iar anexa B informaţii legate de Numărul de Aur, număr ce este folosit în cazul a patru algoritmi de optimizare introduşi în această lucrare. Prin utilizarea Numărului de Aur s-a realizat o primă corelaţie între implicaţiile cunoscute ale Numărului de Aur în diverse domenii (în primul rând aceea de generare a unei armonii, a unei distribuţii echilibrate) şi aplicarea acestuia în domeniul paralelismul inter-operator, şi anume în faza de alocare a procesoarelor. This thesis presents parallel query optimization methods. The presentation is based on a hierarchical approach and a unified framework, so that the potential integration of the techniques used to address each type of parallelism can be illustrated. Three types of parallelism can be exploited, namely intra-operator, inter-operator, and inter-query parallelism. In intra-operator parallelism the major issue is task creation, and the objective is to split an operation into tasks in a manner such that the load can be spread evenly across a given number of processors. Inter-operator parallelism can be achieved either through parallel execution of independent operations or through pipelining. In either case, the major issues are the join sequence selection, which determines the precedence relations among the operations and the pipeline structures that can be exploited, and the processor allocation for each operation. For inter-query parallelism, the issue again is processor allocation, but at the query level. In this thesis are also presented and compared several efficient algorithms (classical and original contributions) for the problem of scheduling a pipelined operator tree (in which all operators run in parallel using inter-operator parallelism) for both homogeneous and heterogeneous environments. Heterogeneity of resources has been considered before in the context of the problem that we are dealing with only in by Termehchy and Ghodsi. The thesis is organized as follows: introduction (chapter 1), in chapter 2 methods for intra-operator parallelism are presented, chapter 3 presents inter-operator parallelism and query optimization for centralized, distributed and parallel environments, chapter 4 introduces the model for the problem of scheduling a pipelined operator tree and algorithms for solving this problem. Some original algorithms are proposed for both homogeneous and heterogeneous environments, with pre-allocation constraints or not; some of them optimize the classical algorithms. In the next chapter performances of algorithms introduced in previous chapter are evaluated from different points of view (medium and maximum performance ratio, execution time, etc.) Chapter 6 presents conclusions and further research. Annex A contains a part of the source code and annex B a short presentation of the Golden Number used in four original algorithms. The use of golden number, improves performances for both maximum performance ratio and its domain length. Thus, this first use of golden number in pipelined parallelism scheduling problem was a successful one and it proves that golden number implications in pipelined parallelism are alike to the implications which appears in other domains (an “harmonious distribution” for performance ratio values was obtained).

Keyword(s): Algoritmi matematici -- Teză de doctorat ; Baze de date -- Optimizare -- Teză de doctorat ; Sisteme de prelucrare (Calculatoare) -- Prelucrare în paralel (Calculatoare) -- Baze de date -- Teză de doctorat
OPAC: See record in BC-UPB Web OPAC
Full Text: see files

Notices similaires

 

Les utilisateurs qui ont vu cette page ont aussi vu:

(270)  Optimizarea conceptuală şi operaţională a instalaţiilor chimice multiscop - Voinescu, Sorin - ROMDOC-BC_UPB-THESIS-2003-000000054 (261)  Tehnologiile informării şi comunicării : suport de curs - Curta, Olimpia - ROMDOC-BOOK-2007-005 (257)  Cercetări asupra simulării în timp real a sistemelor de acţionare hidraulice şi pneumatice - Ion Guţă, Dragoş Daniel - ROMDOC-THESIS-2016-561 (255)  Contribuţii la studiul influenţei vibraţiilor sculei asupra preciziei de prelucrare a pieselor de mecanică fină - Radcenco, Luminiţa - ROMDOC-BC_UPB-THESIS-1991-000001094 (255)  THE EFFECT OF MICROWAVE RADIATION ON CATALASE EXTRACTED FROM TARAXACUM ROOTS - Popet, Laura et al - ROMDOC-BCUT-ARTICLE-2007-001

 

Évaluer ce document:

Soyez le premier à noter ce document

Discuter ce document:

Commencer la discussion sur n'importe quel aspect de ce document.