metode de optimizare a organizării bazelor de date
DESCRIPTION
Îndrumător ştiinţific:Doctorand: Prof. Dr. Leon TâmbuleaDaniel Stuparu. Metode de optimizare a organizării bazelor de date. 2. Metode clasice de proiectare a bazelor de date Top-Down şi Buttom-Up Problema fragmentării şi a alocării fragmentelor în noduri - PowerPoint PPT PresentationTRANSCRIPT
Îndrumător ştiinţific:Doctorand:Prof. Dr. Leon Tâmbulea Daniel Stuparu
2
2. Metode clasice de proiectare a bazelor de date Top-Down şi Buttom-Up Problema fragmentării şi a alocării fragmentelor în
noduri3. Abordări ale proiectării bazelor de date
Workload-ul privit ca o secvenţă de instrucţiuni Definirea problemei Algoritmul
4. Reducerea complexităţii algoritmilor Tehnica reducerii bazate pe cost Tehnica explorării secvenţelor disjuncte Tehnica Greedy
5. Concluzii şi direcţii viitoare
1. CUPRINS
3
2. Metode clasice de proiectare a bazelor de date Top-Down şi Buttom-Up Problema fragmentării şi a alocării fragmentelor în
noduri3. Abordări ale proiectării bazelor de date
Workload-ul privit ca o secvenţă de instrucţiuni Definirea problemei Algoritmul
4. Reducerea complexităţii algoritmilor Tehnica reducerii bazate pe cost Tehnica explorării secvenţelor disjuncte Tehnica Greedy
5. Concluzii şi direcţii viitoare
1. CUPRINS
4
2. Metode clasice de proiectare a bazelor de date Top-Down şi Buttom-Up Problema fragmentării şi a alocării fragmentelor în
noduri3. Abordări ale proiectării bazelor de date
Workload-ul privit ca o secvenţă de instrucţiuni Definirea problemei Algoritmul
4. Reducerea complexităţii algoritmilor Tehnica reducerii bazate pe cost Tehnica explorării secvenţelor disjuncte Tehnica Greedy
5. Concluzii şi direcţii viitoare
1. CUPRINS
5
2. Metode clasice de proiectare a bazelor de date Top-Down şi Buttom-Up Problema fragmentării şi a alocării fragmentelor în
noduri3. Abordări ale proiectării bazelor de date
Workload-ul privit ca o secvenţă de instrucţiuni Definirea problemei Algoritmul
4. Reducerea complexităţii algoritmilor Tehnica reducerii bazate pe cost Tehnica explorării secvenţelor disjuncte Tehnica Greedy
5. Concluzii şi direcţii viitoare
1. CUPRINS
6
Proiectarea BD distribuite se reduce la: Fragmentarea datelor; Alocarea şi optimizarea la nivel local.
Metode de proiectare: Top-Down Buttom-Up
Problema fragmentării Informaţii relative la BD, la aplicaţii, la reţeaua de comincare, la
caracteristicile nodurilor; Tipurile: orizontală, verticală, mixtă
Alocarea fragmentelor în noduri Tipuri de baze de date: partiţionată, complet replicată,
parţial replicată.
2. METODE CLASICE DE PROIECTARE A BAZELOR DE DATE
7
Workload – definiţie (o secvenţă de instrucţiuni) Scenariul 1. “Query by day, update by night” Scenariul 2. Tabele temporare Scenariul 3. Dinamicitate pe servere de producţie
[AgNaYa04] - “Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design” la conferinta VLDB 2004
Structură fizică de design – definiţie Configuraţie – definiţie Enunţ problemă
Dată fiind o bază de date D, un workload W, şi o limită de spaţiu S, să se găsească o configuraţie P a cărei cerinţe de stocare să nu depăşească S iar COST(Q,P) să fie minim.
3. ABORDĂRI ALE PROIECTĂRII BAZELOR DE DATE
8
[AgChuNa06] – “Automatic Physical Design Tuning: Workload as a Sequence” – la conferinta VLDB 2006
Funcţii introduse: COST(S,C) şi TRANSITION-COST(C1,C2)
SEC (costul executiei secvenţei)
Enunţ problemă Dată fiind o bază de date D, un workload definit ca şi
secvenţă W=[S1,S2,…,Sn], având o configuraţie iniţială C0 şi o limită de stocare M, să se găsească configuraţiile C1,C2,…,Cn+1 astfel încât cerinţa de stocare a configuraţiei Ci(1<=i<=N+1) să nu depăşească M, iar costul de execuţie al secvenţei SEC[C1,S1,…,Cn,Sn,Cn+1] să fie minim.
),(],,,...,,,,[ 112211 NNNNN CCCOSTTRANSITIONCSCSCSCSEC
N
kkkkk CCCOSTTRANSITIONCSCOST
11 )),(),((
3. ABORDĂRI ALE PROIECTĂRII BAZELOR DE DATE
9
Algoritm Input:
Secvenţă cu N instrucţiuni SQL Mulţime de structuri candidat – index I
Output: N+1 configuraţii (C1,C2, ... CN+1)
Graful folosit pentru ==> calculul drumului minim
Se observă propoziţiile: Propoziţie 1. Costul nodurilor şi cel al arcelor nu poate fi negativ Propoziţie 2. Drumul minim în graf poate fi calculat folosind tehnica drumului minim
într-un graf cu un singur nod sursă având complexitate liniară .
{}
{} {} {}
{}
{I} {I} {I}
SURSĂ DESTINAŢIE
S1 S2 SN
0
0
0
0
IcIc
Id
Id
3. ABORDĂRI ALE PROIECTĂRII BAZELOR DE DATE
10
Tehnici de reducere a complexităţii - pornesc de la costurile fiecărui nod sau de la numărul de coloane folosite de către
instrucţiunile din workload
1. Tehnica reducerii bazată pe cost
2. Tehnica explorării secvenţelor disjuncte
3. Tehnica GREEDY
4. REDUCEREA COMPLEXITĂŢII ALGORITMILOR
11
4. 1. TEHNICA REDUCERII BAZATĂ PE COST
Optimizarea soluţiei prin reducerea configuraţiilor din graf. Calcularea unei margini inferioare a costurilor unei instrucţiuni
pe o anumită configuraţie Rezultă un graf cu un număr redus de configuraţii
Ex: fie o secv de intrare cu 4 instrucţiuni Iar pentru Si indexul Ii este singurul relevant, COST (Id) = 0
Algoritmul principal graf cu 24 = 16 configuraţii posibile
Fol. Tehnica cost-prunning graf cu 5 configuraţii
],,,[ 4321 SSSS
12
4. 1. TEHNICA REDUCERII BAZATĂ PE COST
Eficienţa – acurateţea şi eficienţa determinării marginii inferioare de cost Dificilă pentru că nu se doreşte parcurgerea tuturor
configuraţiilor; O margine trivială este cel mai mic cost al
execuţiei unei interogări la nivelul orcărui design fizic; Folosirea unor configuraţii atomice [ChNa97]
pentru o margine mai eficient aleasa; Se pot folosi instrumentele de optimizare ale SGBD; Costul INSERT, UPDATE sau DELETE se gestionează
prin tehnica de “splitting” pe părţi, identificănd tuplurile participante.
13
Tehnici de reducere a complexităţii - pornesc de la costurile fiecărui nod sau de la numărul de coloane folosite de către
instrucţiunile din workload
1. Tehnica reducerii bazată pe cost
2. Tehnica explorării secvenţelor disjuncte
3. Tehnica GREEDY
4. REDUCEREA COMPLEXITĂŢII ALGORITMILOR
14
4.2. Tehnica explorării secvenţelor disjuncte
Se aplică pe workload-uri mari Se bazează pe faptul ca un workload se poate
împărţi în grupuri de instrucţiuni ce accesează părţi de date reduce spaţiul de soluţii
Definiţie. X şi Y secvenţe disjuncte dacă: Nu au instrucţiuni comune; Fie s structură fizică de design, toate instrucţiunile lui s
aparţin DOAR intr-una din secvenţe. Tehnica are 2 operatori principali:
1. SPLIT. Pentru o secv de intrare şi o mulţime de structuri împarte secvenţa într-o mulţime de secvenţe disjuncte;
2. MERGE. Are ca intrare mulţimea de secvenţe disjuncte şi soluţiile acestora şi le combină pentru generarea unei soluţii valide.
15
4.2. Tehnica explorării secvenţelor disjuncte
16
Tehnici de reducere a complexităţii - pornesc de la costurile fiecărui nod sau de la numărul de coloane folosite de către
instrucţiunile din workload
1. Tehnica reducerii bazată pe cost
2. Tehnica explorării secvenţelor disjuncte
3. Tehnica GREEDY
4. REDUCEREA COMPLEXITĂŢII ALGORITMILOR
17
4.3. Tehnica GREEDY Numărul configuraţiilor (nodurilor şi arcelor din
grafic ) este exponenţial cu numărul structurilor candidat din workload; Algoritmul principal nu este fezabil în cazul
workload-urilor cu un număr mare de structuri candidat;
La baza tehnicii GREEDY de reducere a numărului de configuraţii este algoritmul GREEDY: Dacă workload-ul este considerat o secvenţă
algoritmul se numeşte GREEDY-SEQ Algortmul GREEDY-SEQ foloseşte o funcţie UnionPair
18
Funcţia UnionPair Primeşte 2 soluţii p1= [a1, S1,..., aN, SN, aN+1] şi p2= [b1, S1,..., bN, SN, bN+1]
pentru secvenţa [S1,...,SN]; Generează o soluţie nouă pentru aceeaşi secvenţă; La fiecare etapă k sunt generate configuraţii suplimentare plecând
de la configuraţiile ak şi bk care sunt adăugate în graf; Ieşirea este cel mai scurt drum în graful generat.
4.3. Tehnica GREEDY
19
Algoritmul GREEDY-SEQ
Pas 1. Pentru fiecare structură din S= {s1, s2,..., sM}se găseşte soluţia optimă folosind
algoritmul principal. Există o mulţime de soluţii P pentru structuri individuale.
Fie P={p1,..., pM} şi pi= [ai1, S1,..., SN, aiN+1];Pas 2. Fie C mulţimea tuturor configuraţiilor peste toate structurile individuale;Pas 3. Pe mulţimea P se rulează căutarea greedy.
Pas 3a. Fie r = [c1, S1,...,cN, SN, cN+1] soluţie din P unde COST(r) minim. P=P-{r}.
Fie C=C U {c1,..., cN+1};Pas 3b. Aleg s din P pentru care t=UnionPair(r,s) are costul execuţiei minim între toate elementele din P, iar COST(t) < COST(r). Dacă s nu există goto Pas 4. P=P-{s}, P=PU{t} goto Pas 3a.
Pas 4. Se generează graful cu toate configuraţiile din C în respectiva etapă. Se rulează algoritmul de drum minim şi se întoarce soluţia.
4.3. Tehnica GREEDY
20
5. Concluzii şi direcţii viitoare de cercetare
Concluzii abordări diferite ale proiectării bazelor de date Definirea unor soluţii scalabile de design Workload-ul – o secvenţă de instrucţiuni Algoritmi şi tehnici de reducere a complexităţii la
nivelul bazelor de date centralizate
Directii de viitor Soluţii de design la nivelul BDD Transpunerea algoritmilor pe BDD Noi abordări în cazul BDD