CALCOLO DEL C OSTO COSTO DI ACCESSO

CALCOLO CALCOLO DEL COSTO DEL COSTO DI ACCESSO DI ACCESSO

AI DATI

AI DATI

Progetto di Basi di Dati Progetto di Basi di Dati – –

Dove ci troviamo?

Dove ci troviamo?

D) Prog. Concettuale (ER)

1 2 3 4 5 6 7

E) Prog. Logica e Normalizzazione

1 2 3 4

F) Prog. Fisica

ottimizzatori ottimizzatori

• I criteri che vedremo sono in linea con i metodi e le scelte utilizzati dai query optimizer dei

e le scelte utilizzati dai query-optimizer dei DBMS relazionali

• lo scopo dei query-optimizer è infatti valutarelo scopo dei query-optimizer è infatti valutare quale sia la migliore strategia di accesso

(access path) per le interrogazioni SQL degli utenti

• gli ottimizzatori non prendono decisioni

sull’ordinamento delle relazioni e su quali indici sull’ordinamento delle relazioni e su quali indici costruire

• queste decisioni sono lasciate alqueste decisioni sono lasciate al DBA che deve DBA che deve valutare sulla base del carico di lavoro

d i i i decisioni

li i di i?

index scan

quali indici?

index scan

relation scan relation scan

R l i di NT t l i NB bl hi ( i ) Relazione di NT tuple in NB blocchi (pagine)

tili d li i di i utilizzo degli indici

• Un indice può essere utilizzato per p p eseguire una interrogazione SQL se l’attributo su cui è costruito:

• compare nella clausola WHERE

• è contenuto in un FATTORE

• è contenuto in un FATTORE BOOLEANO

il fattore booleano è ARGOMENTO DI

• il fattore booleano è ARGOMENTO DI RICERCA attraverso indice

• compare in un ORDER BY o GROUP BY

tili d li i di i utilizzo degli indici

• Esempi: per la relazione

IMPIEGATI ( matr, cognome, nome, lavoro,

qualifica, salario, straordinario, dno) 1) la query: SELECT cognome, salario

FROM impiegati WHERE dno = 51 AND salario > 2000

AND (lavoro = ‘fattorino’

OR lavoro = ’guardiano’) oppure ….

tili d li i di i utilizzo degli indici

2) la query: SELECT cognome, salario FROM impiegati

WHERE dno = 51

AND salario + straordinario > 3000 AND (lavoro = ‘fattorino’

OR qualifica = 7)q )

tili d li i di i utilizzo degli indici

Separazione della condizione WHERE in

fattori booleani: un predicato è un fattore boleano se è collegato alla radice del WHERE-tree da AND

(query 1) AND

AND

(query 1) AND

dno = 51 OR

salario salario

> 2000

lavoro = ‘fattorino’ lavoro = ‘guardiano’

tili d li i di i utilizzo degli indici

un predicato è un fattore boleano se con risultato un predicato è un fattore boleano se con risultato falso determina il risultato falso per la query

(query 2)

AND AND

(query 2)

dno = 51 salario + OR straordinario

> 3000

lavoro = ‘fattorino’ qualifica = 7

tili d li i di i utilizzo degli indici

1) per la query 1 sono fatt. bool. argomenti di ricerca:

dno = 51 , salario > 2000

(lavoro = ‘fattorino’ OR lavoro = ’guardiano’)

dno salario lavoro

dno salario lavoro

tili d li i di i utilizzo degli indici

2) per la query 2 è fatt. bool. argomento di ricerca solo: dno = 51

per (lavoro = ‘fattorino’ OR qualifica = 7) se il DBMS può usare più indici per una query:

qualifica

lavoro qualifica

+

si può effettuare l’unione delle liste di TID

tili d li i di i utilizzo degli indici

2) per la query 2 è non è fatt. bool. argomento di ricerca: salario + straordinario > 3000

sia che il DBMS possa usare più indici per

h l

una query che uno solo :

straordinario salario straordinario salario

?

? ?

non si può effettuare l’unione delle liste di TID

tili d li i di i utilizzo degli indici

per una query sono argomento di ricerca i

predicati del tipo: attributo . comparatore. valore, ad es.:

dno = 47 (<, < = ,> = , > , between) SI dno = $D (variabile di programma) SI

dno = 47 OR dno = 32 SI

(IN corrisponde ad OR ma non sempre è SI) (dno = 47) OR (qualifica = 3) SI/NO salario + straordinario > 3000 NO

salario = straordinario (stessa relazione) NO

d ll di t modello di costo

• Un indice è utile per una query solo se il costo

di l’i di è < t d ll’

di accesso con l’indice è < costo dell’accesso sequenziale cioè < NB ( NB/2 se attributo

unique)q )

• il modello comunemente utilizzato (ce ne sono di molto più sofisticati e precisi) serve per

i i i di i i b

previsioni di massima e si basa su:

–per la relazione : NT, NB

per ogni indice :NF (numero di foglie) –per ogni indice :NF (numero di foglie)

–per ogni attributo :NK (cardinalità), max, min –tutti valori desumibili dai cataloghi dei DBMS –tutti valori desumibili dai cataloghi dei DBMS –le grandezze sono uniformemente distribuite

selettività selettività

• Un predicato è selettivo se ci si aspetta che non t tte le t ple lo soddisfino

tutte le tuple lo soddisfino

• fattore di selettività (filtro) F di un predicato : frazione di tuple che soddisfano il predicato frazione di tuple che soddisfano il predicato

nt / NT = valori selezionati / NK = SK / NK

–A = valore F = 1 / NK_A

dno = 24 F = 1/ Nk default = 1/10

dno = 24 F_dno = 1/ Nk_dno , default = 1/10

–A IN (val1, val2, val3 ) F = 3 / NK_A

d IN ( 24 36) F 2/ NK

dno IN ( 24, 36) F_dno = 2/ NK_dno analogamente per dno = 24 OR dno = 36

i l F l i/ NK d f l 1/2

in generale F= numero valori/ NK_A , default = 1/2

l tti ità selettività

• A > valore F = SK / NK_A , default f=1/3

voto > 27 F_voto = 4/ 15

se i voti vanno da 17 a 31 e supponendo che se i voti vanno da 17 a 31 e supponendo che tutti siano stati assegnati almeno una volta

per salario > 2000 (range la cui cardinalità non per salario > 2000 (range la cui cardinalità non è controllabile) si può prendere:

F _{l i} = (max(sal) - 2000) / (max(sal) - min(sal)) F_salario = (max(sal) - 2000) / (max(sal) - min(sal)) analogamente per BETWEEN 2000 AND 3500

F = (3500 2000) / (max(sal) min(sal)) F_salario = (3500 - 2000) / (max(sal) - min(sal))

default f=1/4

selettività selettività

• Predicati su attributi diversi – pred1 OR pred2 :

F = F_pred1pred1 + F_pred2pred2 - F_pred1pred1 pred2F_pred2 – attributo A = attributo B

F = 1 / max(NK NK ) F = 1 / max(NK_A, NK_B)

se i due domini sono sovrapposti, altrimenti F=0

i A t l

- negazione : A = not valore

F = 1-1 / NK_A

per ottenere maggiori precisioni molti sistemi memorizzano istogrammi semplificati

selettività selettività

• Numero di tuple del risultato:

– E = NT × F_pred1 e

–nell’ipotesi di assenza di correlazione tra i p valori degli attributi, per più predicati:

E = NT × Π_{ii predi}F_predi

- l’ipotesi non è sempre verificata, bisognerebbe rilevarel ipotesi non è sempre verificata, bisognerebbe rilevare un fattore di correlazione o di clustering relativo tra valori di attributi differenti:

. tipo di lavoro, data di nascita: incorrelati . qualifica, dipartimento: correlati

costo di accesso costo di accesso

I casi esaminati si differenziano a seconda I casi esaminati si differenziano a seconda che:

• indice clustered / unclustered

• indice clustered / unclustered

• attributo unique / con ripetizione dei valori

• predicato di uguaglianza / di range / OR predicato di uguaglianza / di range / OR

• uso di un solo indice / più indici

Ipotesi di buffer Ipotesi di buffer

Si considera per ogni relazione o indice Si considera, per ogni relazione o indice, che ogni cambio di riferimento a pagina referenzi una pagina fuori dal buffer di referenzi una pagina fuori dal buffer di memoria centrale.

E’ i l i ( i di )

E’ come se ogni relazione (o indice ) avesse una sola pagina di buffer in

i t l

memoria centrale.

E’ un’ipotesi pessimistica che tende a p p

calcolare upper bound.

costo di accesso costo di accesso

Il costo C è dato dalla somma : Il costo C è dato dalla somma :

C

+ C

costo di accesso costo di accesso

• indice clustered / unclustered su attributo unique con predicato di uguaglianza:

esempio, matr = 236 (sulla relazione impiegati) foglia

indice Costo = 1 foglia + 1 blocco = 2 blocco

d ti

Costo 1 foglia 1 blocco 2

dati

se l’indice è clustered o unclustered è lo stesso

costo di accesso costo di accesso

• indice clustered con E > 1:

matr between 236 and 312, lavoro = ‘guardiano’

Costo = ⎡F × NF⎤ + ⎡ F × NB ⎤

costo di accesso costo di accesso

• indice unclustered / clustered :

l di

lavoro = guardiano

Costo = (⎡F × NF⎤ + ⎡ F × NT ⎤) con F = F _valorevalore analogamente per il caso clustered

Costo = (⎡F × NF⎤ + ⎡ F × NB ⎤)

costo di accesso costo di accesso

• indice unclustered / clustered (predicato OR):

l di OR ti

lavoro = guardiano OR portiere

Costo = 2 × (⎡F × NF⎤ + ⎡ F × NT ⎤) con F = F _valorevalore sono 2 accessi distinti,

analogamente per il caso clustered Costo = 2 × (⎡F × NF⎤ + ⎡ F × NB ⎤)

costo di accesso costo di accesso

• Uso di più indici unclustered con E > 1:

i i / i d i TID i d li i di i

intersezione /unione dei TID estratti dagli indici matr between 236 and 312, lavoro = guardiano

Costo = Σ_k⎡F _k × NF _k ⎤ + ⎡ Π_k F _k × NT ⎤

costo di accesso costo di accesso

Costo = Σ ⎡F × NF ⎤ + ⎡ Π F × NT ⎤ Costo = Σ_k⎡F_k × NF _k ⎤ + ⎡ Π_k F_k × NT ⎤ Questa formula è molto imprecisa perché Questa formula è molto imprecisa perché

presuppone la mancanza di correlazione tra attributi Questo metodo può essere migliorato aggiungendo Questo metodo può essere migliorato aggiungendo indici k solo se portano un vantaggio di selettività

al secondo termine superiore allo svantaggio introdotto nella sommatoria del primo

nella sommatoria del primo

costo di accesso costo di accesso

Esempio:p

SELECT * FROM IMPIEGATI

WHERE lavoro = ‘fattorino’ AND salario < 1500 WHERE lavoro fattorino AND salario 1500 con NT = 10000, NB = 1000,

NK_sal = 100 NK_lav = 50 NK_sal 100 NK_lav 50

indici: clustered su salario con NF = 160 unclustered su lavoro con NF = 100 unclustered su lavoro con NF = 100 supponiamo che la selettività sia.

F_lavlav = 1 / 50 = 0.02

F_sal = (1500 - min) / (max- min) = 0.1

costo di accesso costo di accesso

costo delle scansione sequenziale:

C_seq = 1000

costo dell’indice su lavoro (unclust.):

C_lav = ⎡F_lav × NF_lav⎤ + ⎡ F_lav × NT ⎤ =

0.02 × 100 + 0.02 × 10000 = 2 + 200 = 202 costo dell’indice su salario (clust):

C = ⎡F × NF ⎤ + ⎡ F × NB ⎤ = C_sal = ⎡F_sal × NF_sal⎤ + ⎡ F_sal × NB ⎤ =

0.1 × 160 + 0.1 × 1000 = 16 +100 = 116 C_seq > C_lav > C_sal

costo di accesso costo di accesso

scambiamo adesso l’ordinamento per gli indici:

costo dell’indice su lavoro (clust.):

C_lavlav = ⎡F_lavlav × NF_lavlav⎤ + ⎡ F_lavlav × NB ⎤ =

0.02 × 100 + 0.02 × 1000 = 2 + 20 = 22 t d ll’i di l i ( l t)

costo dell’indice su salario (unclust):

C_sal = ⎡F_sal × NF_sal⎤ + ⎡ F_sal × NT ⎤ =

0 1 160 0 1 10000 16 1000 1016 0.1 × 160 + 0.1 × 10000 = 16 +1000 = 1016 C_sal > C_seq > C_lav

costo di accesso costo di accesso

tuple del risultato:p E = F_lav × F_sal× NT = 20

l lt i li l è

• la scelta migliore per la query è avere un

ordinamento su lavoro e un indice su lavoro, mentre l’indice su salario non deve essere

mentre l indice su salario non deve essere costruito

• il miglioramento che si ottiene rispetto

all’assenza di indici e ordinamenti è di 1 a 45

• nel caso in cui l’ordinamento su salario si di

tilità lt l’i di l t d

utilità per altre query l’indice unclustered su lavoro porta ad un miglioramento di 1 a 9

uso degli indici uso degli indici

Miglioramento della formula di costo nel caso di ordinamento dei TIDs

tids ordinati array di E

valore

RELAZIONE

1 2 NB

RELAZIONE

d

cardenas

C _relazione relazione

Φ (k n) = ⎡ n × (1 (1 1/n)^k) ⎤ Φ (k,n) = ⎡ n × (1-(1-1/n)^k) ⎤

C _relazione

C _relazione

a) tutti i record sono equiprobabili,

b) tutti i blocchi contengono lo stesso numero di tuple, c) come conseguenza di a) e b) tutti i blocchi sono

equiprobabili.

cardenas cardenas

Φ(E,NB) può essere ricavata come segue:

• 1/NB è la probabilità che un blocco contenga una data tupla estratta dagli E,g

• 1-1/NB è la probabilità che un blocco non contenga una data tupla estratta dagli E

• (1-1/NB)E^E è la probabilità che un blocco non contenga nessuna delle E tuple

1 (1 1/NB) ^E è l b bilità h bl

• 1-(1-1/NB) ^E è la probabilità che un blocco

contenga almeno una delle E tuple e quindi venga visitato

visitato,

• NB

×

d t di Φ

andamento di Φ

L' d t l d ll è i t t i fi

L'andamento generale della Φ è riportato in figura:

andamento di Φ

Tabella con NB = 100

L f l di C d l l ^{10 10}

E ⎡ Φ ⎤

• La formula di Cardenas calcola in ogni caso il numero

Φ

bl hi i it ti ( l i i

10 10 20 18 30 26

blocchi visitati (con qualsiasi successione).

40 33 50 39 60 45

• Il numero di accessi C_relazione è calcolabile con la formula di

C d l i TID

60 5

70 51 80 55

90 60

Cardenas solo se i TIDs sono in ordine.

90 60 100 63 150 78

200 87

200 87 250 95

tili d li i di i utilizzo degli indici

C di i di l t d "l l t Caso di indice unclustered "localmente

ordinato" : con i TIDs in ordine crescente per ogni valore della chiave

ogni valore della chiave

foglie chiave + tids

a b ...

....

foglie indice

a b a b b a a b

a b a b b a a b

.. .. ... .. ... .. ... .. ...

n-ple

tili d li i di i utilizzo degli indici

• Predicato : Col = valore

C = ⎡F

NF⎤ + ⎡Φ(E,NB)⎤

dove E = F_col × NT

• Predicato di tipo : valore1< Col < valore2

⎡ ⎤ ⎡ ⎤

C = ⎡F

NF⎤ + ⎡K

Φ(E/K,NB)⎤

dove K = F_col × NK

tili d li i di i utilizzo degli indici

• Rivediamo i calcoli con

Φ

predicato: lavoro = ‘fattorino’

predicato: lavoro = fattorino

C = ⎡F

NF

⎤ + ⎡Φ(E,NB)⎤

dove E_lav = F_lav × NT =200

C = ⎡F

NF

⎤ + ⎡Φ(200,1000)⎤

= 2 + 182 = 184 (era 202)

= 2 + 182 = 184 (era 202)

tili d li i di i utilizzo degli indici

• Predicato : salario < 1500

C = ⎡F

NF

⎤ + ⎡K

Φ(E

/K,NB)⎤

dove K = F_sal × NK_sal

E

/K =

E

/K =

C = 16 + ⎡10

Φ(100,1000)⎤ =

= 16 + 952 = 968

= 16 + 952 = 968

tili d li i di i utilizzo degli indici

Esempio: variazione con Kp

NF = 1^.800, NT = 1^.000^.000, NK = 100^.000, NB = 100^.000

5

6 Costi

con indice

3 4

5 ( x 100000 ) con indice

1 2 3

scan sequenziale

0 1

1 10 100 1000 10000 100000

K

tili d li i di i utilizzo degli indici

• Le tuple del risultato vengono poi controllateLe tuple del risultato vengono poi controllate con i predicati residui:

SELECT * FROM IMPIEGATI SELECT * FROM IMPIEGATI WHERE lavoro = ‘fattorino’

AND tà 35 AND età < 35

AND salario + straordinario >3

predicato residuo La selettività dei predicati residui è difficile

uso degli indici uso degli indici

• Perché non mettere indici su tutti gli attributi?

Il query optimizer potrebbe poi scegliere Il query optimizer potrebbe poi scegliere.

• Gli indici devono essere mantenuti:

caso DELETE: eliminazione di TID caso DELETE: eliminazione di TID

Costo = N_ind × E’ (N_ind : numero indici E’ E 2) E’ = E × 2)

uso degli indici uso degli indici

caso UPDATE: spostamento di TID caso U sposta e to d

Costo = N_ind × 2 × E’ (N_ind: numero indici E’ = E × 2) E = E × 2) Un numero indici troppo elevato comporta un eccessivo costo di modifica della relazione

eccessivo costo di modifica della relazione

rif biblio : rif. biblio.:

Antonio Albano:

“Costruire sistemi per basi di dati”.

Addison Wesley 2001y contenuti:

strutture files strutture files struttura DBMS

recovery e concorrenza ottimizzatori

DDBMS

riferimenti: oracle sybase informix DB2 SQl server riferimenti: oracle, sybase, informix, DB2, SQl server

rif biblio : rif. biblio.:

Fabio Grandi:

“Esercizi di Basi di Dati”.

Progetto Leonardo, Bologna, 2007g , g , contenuti:

Esercizi risolti e ampiamente commentati di:

Esercizi risolti e ampiamente commentati di:

• interrogazione e manipolazione SQL

• ottimizzazione piani di accesso

alcuni rif biblio : alcuni rif. biblio.:

Validità di Φ:

P Ciaccia D Maio P Tiberio: "A unifying approach to evaluating P.Ciaccia, D.Maio, P.Tiberio: "A unifying approach to evaluating block accesses in data base organizations." Information Proc. Lett., vol 28, no. 5, 1988.

UPDATE: calcolo dei costi

M.Schkolnick, P.Tiberio: "Estimating the cost of updates in a relational database" ACM Transactions on Database Systems vol relational database". ACM Transactions on Database Systems, vol 10, 2, 1985.

Calcolo dei costi e scelta degli indici:g

R.Bonanno, D.Maio, P.Tiberio: "An approximation algorithm for secondary index selection in relational database physical design".

The Computer Journal vol 28 4 1985 The Computer Journal, vol. 28, 4, 1985.

S.Finkelstein, M.Schkolnick, P.Tiberio: "Physical database design for relational databases". ACM Transactions on Database Systems, marzo 1988

marzo 1988.

Formulario

Formulario

Costo di accesso Costo d accesso

• E = ⎡Π_iF_i * NT⎤

F: default

• K = ⎡Π_iF_i * NK⎤

F: default

A = val 1 / NK_A <= 1/10

A IN (val( ₁₁, val, ₂₂ ... val_nn ) (OR)) ( ) n / NK_AA <= 1/2 A > val (max_A-val) / (max_A-min_A) <= 1/3

A < val (val min ) / (max min ) <= 1/3

A < val (val-min_A) / (max_A-min_A) <= 1/3 A BETWEEN val₁ AND val₂ (val₁-val₂) / (max_A-min_A) <= 1/4

A = NOT val 1-1 / NK_A

A = B 1 / max(NK_A, NK_B)

pred1 OR pred2 F_pred1+ F_pred2 -F_pred1F_pred2

Costo di accesso Costo d accesso

• C_A = 1 foglia + 1 blocco = 2 E=1

indice clustered / unclustered indice clustered / unclustered

• C_A = ⎡F * NF⎤ + ⎡F * NB⎤ E>1 indice clustered indice clustered

• C_A = ⎡F * NF⎤ + ⎡F * NT⎤ E>1

indice unclustered (TID disordinati) indice unclustered (TID disordinati)

• C_A = Σ_k ⎡F_k * NF_k⎤ + ⎡Π_k F_k * NT⎤ E>1

più indici unclustered (unione TID) (!)

p ( ) ( )

• C_A = ⎡F * NF⎤ + ⎡Φ(E,NB) ⎤ E>1 K=1

indice unclustered (TID ordinati)

• C_A = ⎡F * NF⎤ + ⎡K * Φ(E/K,NB)⎤ E>1 K>1