Metode de optimizare a organizării bazelor de date

Î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






1. CUPRINS

4






1. CUPRINS

5






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 )),(),((


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


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





3. Tehnica GREEDY


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





3. Tehnica GREEDY


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

Metode de optimizare a organizării bazelor de date

Documents

Transcript of Metode de optimizare a organizării bazelor de date