Valutazione costi di una QUERY

A.1A.1--Nome di tutti i Nome di tutti i fornitori che fornitori che forniscono il prodotto forniscono il prodotto P2P2

forpro

fornitoriCP=P2

Nome

fornitori (CF, Nome , Citta)prodotti(CP, NomP, Color)forpro (CF, CP, Qta)

Solo forniture prodotto P2 (CF,CP,Qta,Nome,Citt

a)

Piano della Query Piano della Query

- Espresso da un grafo- Puo’ essere ottimizzato

logicamente- Esprime una pipeline- E’ convertito in un piano di

esecuzione che puo’ essere ottimizzato rispetto al costo

Informazioni di Catalogo Informazioni di Catalogo

Sono le principali informazioni statistiche su ogni file memorizzate nel catalogo DBMS.

Riguardano parametri che possono anche variare nel tempo (es. record di una tabella)

Comando ANALYZE di Oracle

Informazioni di Catalogo Informazioni di Catalogo

T(R) Numero t-uple di RB(R) Numero blocchi di RS(R) Dimensione t-uple di RS(A,R) Dimensione attributo A di RV(A,R) Numero valori distinti di A in RMax(A,R) ; Min (A;R) K(I) Numero entrate dell’indice IL(I) Numero blocchi foglie di IH(I) Altezza indice I

La SelezioneLa Selezione

Funzioni di costo per la selezione su un Funzioni di costo per la selezione su un predicato di uguaglianza (SEL A=a in R)predicato di uguaglianza (SEL A=a in R)

Ricerca lineare C=B/2 sulla chiave altrimenti C=B

Ricerca binaria C=log2 B sulla chiave

Indice su chiave primaria C= livelli indice L(I) +1

Indice su chiave non primaria +recupero di record multipli

C= L(I)+ B/2

Funzioni di costo per la selezione in termini Funzioni di costo per la selezione in termini di blocchi acceduti in R con B(R)=Bdi blocchi acceduti in R con B(R)=B

Indice secondario (B+ tree)Selezione per uguaglianza

C=L(I)+1 se A è chiave di R

Se A non è chiave , si aggiunge il costo di ricerca sulle foglie

C= L(I)+ (V(A,R)/fattblocco indice -1)

EsempioEsempio

IMPIEGATO (matr, nome, c_Dipartimento, ……)

I 10000 Record , 2000 blocchi FB(I)= 5

Sel c_Dip =’5’ (IMPIEGATO) C=2000 non chiave

Ipotesi: un Btree+ su C_Dip con 125 valori di chiaveL(IC-Dip)=2 4 blocchi di liv. 1 ,card di selezione=10000/125=80

C= L( IC-Dip )+ selettività di C_Dip= 2+80 =82

EsempioEsempio

IMPIEGATO (matr, nome, c_Dipartimento, ……)

Ipotesi:I 10000 Record , 2000 blocchi FB(I)= 5

Sel c_Dip =’5’ and sex=‘F’ Stimo i singoli predicati

Ipotesi: su sex un indice secondario Selettività=5000

C (sex=F)= L( Isex )+selettività = 1+(5000)= 5001

EsempioEsempio

IMPIEGATO (matr, nome, c_Dipartimento, ……)

Ipotesi:I 10000 Record , 2000 blocchi FB(I)= 5

Sel c_Dip =’5’ and stip>100 and sex=‘F’

Recupero c_Dip=5 Costo (c_Dip=5)=82 Costo (Sex=F)=5001

Verifico sex= >F

METODI PER

L’IMPLEMENTAZIONE DEL JOIN

Rossi ANeri B

Bianchi B

Impiegato Reparto

Impiegati

A MoriB BruniB BruniB Bruni

Codice Capo

Reparti

Impiegati Reparto=Codice Reparti

Impiegato Reparto CapoCodiceRossi A MoriAAARossi A B BruniNeri B MoriANeri B B Bruni

Bianchi B MoriABianchi B B Bruni

Rossi A MoriAAANeri B B Bruni

Bianchi B B Bruni

Per ogni impiegato il suo capo

come opera il JOIN ?

A=B S R

inner outer

Ipotesi:

R 6000 Record , 2000 blocchiS 50 Record , 10 blocchi

NB: Il join avviene portando nel buffer di dimensione M i blocchi delle relazioni. Uno dei blocchi deve essere lasciato libero per scrivere il risultato ed uno per effettuare le elaborazioni.

Metodi per l’implementazioneMetodi per l’implementazione

Nested loop Join (forza bruta)

Single-loop Join o Index Join

Sort-Merge Join

Hash Join

Nested loop Join (forza bruta)Nested loop Join (forza bruta)

Per ogni record t in R (ciclo esterno)si confronta ogni record s in S (ciclo interno)

e si recuperano i records (le t-uple di S) che soddisfano la condizione di Join s(B)=t(A)

A=B S R

Nested loop Join (forza bruta)Nested loop Join (forza bruta)

Per ogni record t in R (ciclo esterno)si confronta ogni record s in S (ciclo interno)

e si recuperano i records (le t-uple di S) che soddisfano la condizione di Join s(B)=t(A)

A=B S R

Nested loop Join (esempio)Nested loop Join (esempio)

Query: Nome degli studenti che hanno sostenuto BD

STUDENTE (matr, nome, residenza, ……)

EsameBD (matr, semestre)

Porto in memoria ESAMEBD e per ogni record cerco la matricola corrispondente in STUDENTE e scrivo il nome nel buffer dei risultati

Nested loop Join - CostoNested loop Join - Costo

Costo = B(R) + B(R)* B(S)

Blocchi di R Blocchi di S

N.B. Formula che vale i buffer sono abbastanza da contenere sia R che S che i risultati

Nested loop Join - CostoNested loop Join - Costo

Costo = B(R) + B(R)* B(S)

Conviene portare in memoria centrale il maggior numero di blocchi del ciclo esternoPer poi leggere i blocchi del ciclo interno

Blocchi di R Blocchi di S

Influenza del bufferInfluenza del buffer

Costo = B(R) + ( B(R)/(NB-2) *B(S) )

Blocchi di R Buffer MemoriaCentrale NB

Ogni blocco di R viene letto una volta Ciascun blocco di S viene letto una volta per ognuna delle letture degli (NB-2) blocchi di R

Blocchi di S

Nested loop Join - CostoNested loop Join - Costo

Costo = B(R) + B(R)* B(S) / (NB-2)

Blocchi di R Blocchi di S

N.B. Formula che vale se ho NB buffers

Nested loop Join - CostoNested loop Join - Costo

Costo = B(R) + B(R)* B(S) / (NB-2)

Blocchi di R Blocchi di S

N.B. IN ALCUNI TESTI PUO’ TROVARSI IL VALORE 1 PERCHE’ SI DA’ PER SCONTATO CHE UN BUFFER SIA LASCIATO A DISPOSIZIONE PER I RISULTATI

Nested loop Join – Costo (esempio)Nested loop Join – Costo (esempio)IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

NB=12 sono disponibili 10I 6000 Record , 2000 blocchiD 50 Record , 10 blocchi

Costo = B(R) + B(R)* B(S) / (NB-2)

Costo = B(I) + B(I)* B(D) / (NB-2)=2000+2000*10/10=4000

Costo = B(D) + B(D)* B(I) / (NB-2)=10+10*2000/10=2010

Single loop Join Single loop Join

Esiste un indice su uno dei due attributi di Join (es. B in S).

Per ogni record t in R (ciclo esterno)si utilizza l’indice per recuperare da S tutti i records s che soddisfano la condizione di Join s(B)=t(A)

A=B S R

Single loop Join - CostoSingle loop Join - Costo

Costo = B(R) + V(B,S) * C(IB,S)

Blocchi di R

Numero valoriDistinti di B in S

Costo percorrenza indice

Costo percorrenza indice Costo percorrenza indice Influenzato dal fattore di selezione del Join rispetto al predicato P.

F(P) = numero tuple che soddisfano P numero totale di tuple

Indica la percentuale di t-uple che partecipano al join

Costo percorrenza indiceCosto percorrenza indiceEsempio:

A) se ho un B-Tree su chiave primaria :Percorro l’indice e poi accedo al dato

B) se ho un B-Tree su chiave secondaria :Percorro l’indice e poi percorro le foglie . Il costo di percorrenza delle foglie è proporzionale al numero di chiavi che soddisfano la condizione di join, cioè F(P).

Single loop Join - CostoSingle loop Join - Costo

Costo = B(R) + V(B,S) * C(IB,S)

Blocchi di R

Numero valoriDistinti di B in S

Costo percorrenza indice

Nel dettaglio rispetto all’indice ….

Single loop Join con Costo IndiceSingle loop Join con Costo Indice

Costo = B(R) + T(R) * (L(IB) +1)

T-UPLE di RLivelloindice

INDICE PRIMARIO (chiave) SU B

Single loop Join con Costo indiceSingle loop Join con Costo indice

Costo = B(R) + T(R) * (F(P) * L (IB,S) )

T-UPLE di R

Numero valoriDistinti di S che partecipano al JOIN

LIVELLOindice

INDICE SECONDARIO SU B

Se non conosco F(P) …….Se non conosco F(P) …….

Costo = B(R) + T(R) * (V(B,S)/F(IB))

T-UPLE di R

Numero valoriDistinti di B in S

Fattore di bloccoindice

INDICE SPARSO (cluster) SU B

Single loop Join – Costo (esempio)Single loop Join – Costo (esempio)IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

FK: direttore matr

Molti impiegati non dirigono un dipartimento e non partecipano al join.

Se Dipartimento ha 50 recordse Impiegato ne ha 6000

F(direttore=matr)= 50/6000 circa 8%.

Single loop Join – Costo (esempio)Single loop Join – Costo (esempio)IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

FK: direttore matr

A volte ogni relazione ha un indice.Come scegliere quale indice utilizzare ????

Esempio: Cerco i nomi dei direttori

Single loop Join – Costo (esempio)Single loop Join – Costo (esempio)IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

FK: direttore matr

Ipotesi:I 6000 Record , 2000 blocchiD 50 Record , 10 blocchi

esistono 2 indici secondari :-- su matr a 4 livelli-- su direttore a 2 livelli

IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

FK: direttore matr

1) Accedo a impiegato e uso I(direttore)

OPPURE

2)Accedo a Direttore e uso I(matr)

IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

FK: direttore matr

Costo1) = B(I) + NRec(I) * (liv(Idirettore)+1) =2000+(6000*3)= 20.000

1) Accedo a impiegato e uso I(direttore) a 2 livelli

I 6000 Record , 2000 blocchiD 50 Record , 10 blocchi

Indice su campo chiave.

IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

FK: direttore matr

Costo2)= B(D) + NRec(D)*(liv(Imatr)+1)=50+(50*5)= 260

2)Accedo a Direttore e uso I(matr) a 4 livelli su chiave primaria

I 6000 Record , 2000 blocchiD 50 Record , 10 blocchi

Conviene portare nel buffer DIPARTIMENTO

Sort Merge Join Sort Merge Join

R ed S sono ordinati secondo A e B (se non lo sono si ordinano)

Files scanditi ordinatamente in modo concorrente

Coppie di blocchi copiate in ordine sul buffer

Record di R scanditi una sola volta rispetto a S.

A=B S R

Sort Merge Join - CostoSort Merge Join - Costo

C1 = B(R) + B(S)

Blocchi di R Blocchi di S

C2 = C1+(B(R) * log2 (B(R)) + (B(S) *log2 (B(S))

Ordinamento R

Ordinamento S

Sort Join: Precisazione Sort Join: Precisazione

I costi sono calcolati ipotizzando di portare nel buffer il prodotto cartesiano delle relazioni R e S Se ho M buffer deve essere:

B(R) +B (S) <=M2.

Altrimenti il costo deve essere espresso in log di base M-1 e non in base 2

Sort Join - CostoSort Join - Costo

C1 =3( B(R) + B(S) )

Blocchi di R Blocchi di S

Questo costo vale se il valore del log in base 2 è pari a 1.Cioè se l’ampiezza del prodotto cartesiano è pari alNumero dei blocchi di R + numero blocchi di S

Hash Join Hash Join

1) Fase di partizionamento

Una stessa funzione di hash su A e B mappa R in R1,R2,…RM buckets (prima iterazione) S in S1,S2,..SM buckets (seconda iterazione)

Per ogni bucket, un solo buffer che viene scaricato quando è pieno

A=B S R

IMPIEGATO (matr, nome, dipartimento, ……)DIPARTIMENTO (nomeDip, direttore)

FK: direttore matr

Esempio potrei fare su entrambe le relazioniUn hashing modulo 7 sul campo matricola

Avrei M=8 buckets corrispondenti per relazione

1 R e S2 R e S……….8 R e S

Hash Join Hash Join

1) Fase di joining o probing

Servono M iterazioni.All’iterazione i si esegue il join di Ri con Si.

Join nested loop la piu’ piccola partizione portata in memoria e confrontata con le altre.

A=B S R

Hash Join - CostoHash Join - Costo

C1 = 3 *( B(R) + B(S) )

Blocchi di R Blocchi di S

Hash Join Hash Join

Se la piu’ piccola R sta tutta in memoria:

1) Si porta R in memoria organizzata da hashing

2) Ogni blocco di S viene portato in memoria, sottoposto ad hashing e confrontato con R.

C = B(R) + B(S)

Hash Join Ibrido Hash Join Ibrido Obiettivo: eseguire il join durante il

partizionamento.1) Si partiziona R in M partizioni2) Si porta in memoria R1 (le altre su disco3) Si partiziona S portando tutti i record S1

in memoria4) Si esegue il join R1 S15) Si effettua il join sulle M-1 partizioni

rimaste

Se ho NB buffer si puo’ fare solo se:

B(R) <=NB2.

Hash Join Ibrido- CostoHash Join Ibrido- Costo

C1 = (3-2*NB/ min(B(R),B(S)) * (B(R)+ B(S) )

N.B. Qualunque sia la tipologia di JOIN va considerato un costo aggiuntivo per la scrittura del risultato

A=B S R

La DIMENSIONE del risultato dipende da V(A,R) Numero valori distinti di A in RV(B,S) Numero valori distinti di B in S

X=

T(X) = T(R)*T(S) / max (V(A,R) V(B,S))

Utile nel caso di join multipli