costo di accesso 1

CALCOLODEL COSTODI ACCESSO

AI DATI

costo di accesso 2

Nelle lezioni precedenti• Avete visto:

– i le basi di dati relazionali ed il linguaggio SQL

– la struttura dei files– gli indici B+ tree

• questa è dedicata al calcolo del costo di accesso ai dati (tuple)

costo di accesso 3

scopo della lezione• scopo:

– valutare quale sia la migliore strategia di accesso per interrogazioni SQL sia su singola relazione sia nel caso di join

– i criteri di valutazione servono anche a prendere decisioni sull’ordinamento delle relazioni e quali indici costruire

costo di accesso 4

ottimizzatori• I criteri che vedremo sono in linea con i metodi

e le scelte utilizzati dai query-optimizer dei DBMS relazionali

• lo 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 indicicostruire

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

costo di accesso 5

decisioni

relation scan

index scan

quali indici?

Relazione di NT tuple in NB blocchi (pagine)

costo di accesso 6

utilizzo degli indici• Un indice può essere utilizzato per

eseguire una interrogazione SQL se l’attributo su cui è costruito:

• compare nella clausola WHERE• è contenuto in un FATTORE

BOOLEANO• il fattore booleano è ARGOMENTO DI

RICERCA attraverso indice• compare in un ORDER BY o GROUP BY

costo di accesso 7

utilizzo degli indici• Esempi: per la relazioneIMPIEGATI ( matr, cognome, nome, lavoro,

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

FROM impiegatiWHERE dno = 51AND salario > 2000AND (lavoro = ‘fattorino’

OR lavoro = ’guardiano’)oppure ….

costo di accesso 8

utilizzo degli indici2) la query: SELECT cognome, salario

FROM impiegatiWHERE dno = 51AND salario + straordinario > 3000AND (lavoro = ‘fattorino’

OR qualifica = 7)

costo di accesso 9

utilizzo degli indiciSeparazione della condizione WHERE in fattori booleani: un predicato è un fattore boleanose è collegato alla radice del WHERE-tree da AND

ANDAND

ORdno = 51salario > 2000

lavoro = ‘fattorino’ lavoro = ‘guardiano’

(query 1)

costo di accesso 10

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

AND AND

ORdno = 51 salario +straordinario

> 3000

lavoro = ‘fattorino’ qualifica = 7

(query 2)

costo di accesso 11

utilizzo degli indici1) per la query 1 sono fatt. bool. argomenti di

ricerca: dno = 51 , salario > 2000(lavoro = ‘fattorino’ OR lavoro = ’guardiano’)

dno lavorosalario

costo di accesso 12

utilizzo degli indici2) per la query 2 è fatt. bool. argomento di ricerca

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

qualificalavoro

si può effettuare l’unione delle liste di TID

+

costo di accesso 13

utilizzo degli indici2) per la query 2 è non è fatt. bool. argomento di

ricerca: salario + straordinario > 3000sia che il DBMS possa usare più indici per una query che uno solo :

straordinariosalario

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

?? ?

costo di accesso 14

utilizzo degli indiciper una query sono argomento di ricerca i predicati del tipo: attributo . comparatore. valore,ad es.:dno = 47 (<, < = ,> = , > , between) SIdno = $D (variabile di programma) SIdno = 47 OR dno = 32 SI(IN corrisponde ad OR ma non sempre è SI) (dno = 47) OR (qualifica = 3) SI/NO salario + straordinario > 3000 NOsalario = straordinario (stessa relazione) NO

costo di accesso 15

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

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

• il modello comunemente utilizzato (ce ne sono di molto più sofisticati e precisi) serve per previsioni di massima e si basa su:

–per la relazione : NT, NB–per ogni indice :NL (numero di foglie) –per ogni attributo :NK (cardinalità), max, min–tutti valori desumibili dai cataloghi dei DBMS–le grandezze sono uniformemente distribuite

costo di accesso 16

selettività• Un predicato è selettivo se ci si aspetta che non

tutte le tuple lo soddisfino• fattore di selettività (filtro) F di un predicato :

frazione di tuple che soddisfano il predicatont / NT = valori selezionati / NK = SK / NK

–A = valore F = 1 / NKAdno = 24 Fdno = 1/ Nkdno , default = 1/10

–A IN (val1, val2, val3 ) F = 3 / NKAdno IN ( 24, 36) Fdno = 2/ NKdnoanalogamente per dno = 24 OR dno = 36

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

costo di accesso 17

selettività• A > valore F = SK / NKA , default f=1/3

voto > 27 Fvoto = 4/ 15se i voti vanno da 17 a 31 e supponendo che tutti siano stati assegnati almeno una voltaper salario > 2000 (range la cui cardinalità non è controllabile) si può prendere:Fsalario = (max(sal) - 2000) / (max(sal) - min(sal)) analogamente per BETWEEN 2000 AND 3500 Fsalario = (3500 - 2000) / (max(sal) - min(sal)) default f=1/4

costo di accesso 18

selettività• Predicati su attributi diversi– pred1 OR pred2 :

F = Fpred1 + Fpred2 - Fpred1 Fpred2– attributo A = attributo B

F = 1 / max(NKA, NKB)se i due domini sono sovrapposti, altrimenti F=0

- negazione : A = not valoreF = 1-1 / NKA

per ottenere maggiori precisioni molti sistemi memorizzano istogrammi semplificati

costo di accesso 19

selettività• Numero di tuple del risultato:

– E = NT × Fpred1 e –nell’ipotesi di assenza di correlazione tra i

valori degli attributi, per più predicati:E = NT × ΠiFpredi

- l’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 20

costo di accessoI casi esaminati si differenziano a seconda che:• indice clustered / unclustered• attributo unique / con ripetizione dei

valori• predicato di uguaglianza / di range / OR• uso di un solo indice / più indici

costo di accesso 21

Ipotesi di bufferSi considera, per ogni relazione o indice, che ogni cambio di riferimento a pagina referenzi una pagina fuori dal buffer di memoria centrale.E’ come se ogni relazione (o indice ) avesse una sola pagina di buffer in memoria centrale.E’ un’ipotesi pessimistica che tende a calcolare upper bounds.

costo di accesso 22

costo di accessoIl costo C è dato dalla somma :

Cindice + Crelazione

costo di accesso 23

costo di accesso• indice clustered / unclustered su attributo

unique con predicato di uguaglianza:esempio, matr = 236 (sulla relazione impiegati)

fogliaindice

bloccodati

Costo = 1 foglia + 1 blocco = 2

se l’indice è clustered o unclustered è lo stesso

costo di accesso 24

costo di accesso• indice clustered con E > 1:

matr between 236 and 312, lavoro = ‘guardiano’

Costo = F × NL + F × NB

costo di accesso 25

costo di accesso• indice unclustered / clustered :

lavoro = guardiano

Costo = (F × NL + F × NT ) con F = F valore

analogamente per il caso clustered

Costo = (F × NL + F × NB )

costo di accesso 26

costo di accesso• indice unclustered / clustered (predicato OR):

lavoro = guardiano OR portiere

Costo = 2 × (F × NL + F × NT ) con F = F valoresono 2 accessi distinti,analogamente per il caso clustered

Costo = 2 × (F × NL + F × NB )

costo di accesso 27

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

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

Costo = ΣkF k × NL k + Πk F k × NT

costo di accesso 28

costo di accessoCosto = ΣkF k × NL k + Πk F k × NT

Questa formula è molto imprecisa perché presuppone la mancanza di correlazione tra attributi

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

costo di accesso 29

costo di accessoEsempio:

SELECT * FROM IMPIEGATIWHERE lavoro = ‘fattorino’ AND salario < 1500con NT = 10000, NB = 1000,

NKsal = 100 NKlav = 50

indici: clustered su salario con NL = 160unclustered su lavoro con NL = 100

supponiamo che la selettività sia.Flav = 1 / 50 = 0.02Fsal = (1500 - min) / (max- min) = 0.1

costo di accesso 30

costo di accessocosto delle scansione sequenziale:Cseq = 1000

costo dell’indice su lavoro (unclust.):Clav = Flav × NLlav + Flav × NT =

0.02 × 100 + 0.02 × 10000 = 2 + 200 = 202

costo dell’indice su salario (clust):Csal = Fsal × NLsal + Fsal × NB =

0.1 × 160 + 0.1 × 1000 = 16 +100 = 116Cseq > Clav > Csal

costo di accesso 31

costo di accessoscambiamo adesso l’ordinamento per gli indici:

costo dell’indice su lavoro (clust.):Clav = Flav × NLlav + Flav × NB =

0.02 × 100 + 0.02 × 1000 = 2 + 20 = 22

costo dell’indice su salario (unclust):Csal = Fsal × NLsal + Fsal × NT =

0.1 × 160 + 0.1 × 10000 = 16 +1000 = 1016 Csal > Cseq > Clav

costo di accesso 32

costo di accessotuple del risultato:

E = Flav × Fsal× NT = 20

• la scelta migliore per la query è avere un ordinamento su lavoro e un indice su lavoro, 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 sia di utilità per altre query l’indice unclustered su lavoro porta ad un miglioramento di 1 a 9

costo di accesso 33

uso degli indiciMiglioramento della formula di costo nel caso di ordinamento dei TIDs

Quindi in generale si ha Crelazione ≤ min(E, NB).

tids ordinati

RELAZIONE1 2 NB

array di Evalore

costo di accesso 34

cardenasCrelazione puo' essere calcolato meglio usando la

formula di CARDENAS (Comm. ACM 1975):

Φ (k,n) = n × (1-(1-1/n)k)

Crelazione = Φ (E,NB) = NB × (1-(1-1/NB)E)

La formula e' valida sotto le seguenti ipotesi: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.

costo di accesso 35

cardenasΦ(E,NB) può essere ricavata come segue:• 1/NB è la probabilità che un blocco contenga una

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

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

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

contenga almeno una delle E tuple e quindi venga visitato,

• NB ×(1-(1-1/NB)E) è il numero di blocchi che ci si aspetta contengano almeno una tupla

costo di accesso 36

andamento di ΦL'andamento generale della Φ è riportato in figura:

cardenas

NB

E

min(E,NB)

costo di accesso 37

andamento di ΦTabella con NB = 100

• La formula di Cardenas calcola in ogni caso il numero Φ di blocchi visitati (con qualsiasi successione).

• Il numero di accessi Crelazioneè calcolabile con la formula diCardenas solo se i TIDs sono in ordine.

10 1020 1830 2640 33 50 39 60 45 70 51 80 55 90 60 100 63 150 78200 87250 95300 95500 99

E Φ

costo di accesso 38

utilizzo degli indiciCaso di indice unclustered "localmente ordinato" : con i TIDs in ordine crescente per ogni valore della chiave

a b

a b a a a bbb.. .. ... .. ... .. ... .. ...

.........foglieindice

n-ple

chiave + tids

costo di accesso 39

utilizzo degli indici• Predicato : Col = valore

C = Fcol × NL + Φ(E,NB)dove E = Fcol × NT

• Predicato di tipo : valore 1< Col < valore2

C = Fcol × NL + K × Φ(E/K,NB)dove K = Fcol × NK

costo di accesso 40

utilizzo degli indici• Rivediamo i calcoli con Φ per l’esercizio

precedente con indici unclustered:

predicato: lavoro = ‘fattorino’

C = Flav × NLlav + Φ(E,NB)dove Elav = Flav × NT =200

C = Flav × NLlav + Φ(200,1000)= 2 + 182 = 184 (era 202)

costo di accesso 41

utilizzo degli indici• Predicato : salario < 1500

C = Fsal × NLsal + K × Φ(Esal/K,NB)dove K = Fsal × NKsalEsal /K = fsal × NT dove fsal è il filtro per 1 valore di salarioEsal /K = fsal × NT = 10000/100 = 100 C = 16 + 10 × Φ(100,1000) =

= 16 + 952 = 968 (era 1016)

costo di accesso 42

utilizzo degli indiciEsempio: variazione con KNL = 1.800, NR = 1.000.000, NK = 100.000, NB = 100.000

0

1

2

3

4

5

6

1 10 100 1000 10000 100000

( x 100000 )

Costi

K

con indice

scan sequenziale

costo di accesso 43

utilizzo degli indici• Le tuple del risultato vengono poi controllate

con i predicati residui:

SELECT * FROM IMPIEGATIWHERE lavoro = ‘fattorino’ AND età < 35 AND salario + straordinario >3

predicato residuo

La selettività dei predicati residui è difficile da calcolare

costo di accesso 44

uso degli indici• Perché non mettere indici su tutti gli attributi?

Il query optimizer potrebbe poi scegliere.• Gli indici devono essere mantenuti:

Costo = Nind × E’ (Nind : numero indiciE’ = E × 2)

caso DELETE: eliminazione di TID

costo di accesso 45

uso degli indici

Costo = Nind × 2 × E’ (Nind: numero indiciE’ = E × 2)

caso UPDATE: spostamento di TID

Un numero indici troppo elevato comporta un eccessivo costo di modifica della relazione

costo di accesso 46

rif. biblio.:Antonio Albano: “Costruire sistemi per basi di dati”.Addison Wesley 2001contenuti:

strutture files

struttura DBMS

recovery e concorrenza

ottimizzatori

DDBMS

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

costo di accesso 47

alcuni rif. biblio.:Validità di Φ:P.Ciaccia, D.Maio, P.Tiberio: "A unifying approach to evaluatingblock accesses in data base organizations." Information Proc. Lett.,vol 28, no. 5, 1988.

UPDATE: calcolo dei costiM.Schkolnick, P.Tiberio: "Estimating the cost of updates in arelational database". ACM Transactions on Database Systems, vol10, 2, 1985. Calcolo dei costi e scelta degli indici: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.S.Finkelstein, M.Schkolnick, P.Tiberio: "Physical database designfor relational databases". ACM Transactions on Database Systems, marzo 1988.

costo di accesso 48

proiezione• La proiezione:

SELECT DISTINCT A, C FROM REL

Si ottiene costruendo un file con solo <A, C>, facendo il sort del file e poi eliminando gli uguali (oppure costruendo un indice multicolonna su A,C)Il costo sarà:Cpj= NB + NBAC + Csort (NBAC) + NBAC + Npj

(bisogna calcolare la cardinalità della proiezione Epj e il numero di pagine che contengono il risultato Npj <NBAC <NB)

costo di accesso 49

proiezione• Le tuple risultato della proiezione sono distinte:

SELECT DISTINCT A, C FROM REL

Un calcolo approssimato del numero di tuple del risultato è il seguente:se NT sono le tuple di REL, NKA e NKC le cardinalità di A e C, NKA × NKC sono le possibili coppie (a,c) di valori distinti, quindi EA,C è calcolabile con la formula di Cardenas:

E A,C = Φ( NT, NKA × NKC)

costo di accesso 50

proiezione• Nel caso di query con selezione e proiezione:

SELECT DISTINCT C FROM RELWHERE B = 10

NT/ NKB sono le tuple di REL che soddisfano il predicato, ciascuna di queste può assumere uno dei NKC valori di C, quindi EC è calcolabile con la formula di Cardenas:

E C = Φ( NT/NKB , NKC)

costo di accesso 51

uso degli indici

• Gli indici servono per il controllo di unicità della chiave primaria.

• Gli indici clustered possono servire per l’inserimento di tuple:

– se c’è l’indice clustered, seguendo l’indice, alcuni DBMS cercano di inserire la nuova tupla in modo da mantenere l’ordine, se non c’è spazio nella pagina appropriata allora la tupla va in overflow; periodicamente la relazione viene riordinata e gli indici ricostruiti.

– in altri sistemi le nuove tuple vengono sempre aggiunte di seguito alle altre, degradando l’ordinamento; periodicamente la relazione viene riordinata e gli indici ricostruiti.

costo di accesso 52

Se la colonna ha un indice, i valori distinti vengono contati con esattezza.

Se non c’è l’indice il conteggio comporta un tempo di calcolo paragonabile alla costruzione di un indice (bisogna costruirlo o fare la proiezione).

In entrambi i casi il calcolo va effettuato per ogni colonna

SI PUO' USARE UN CONTEGGIO STATISTICO APPROSSIMATO

METODI PER IL CALCOLO DEL NUMERO DIVALORI DISTINTI IN UN ATTRIBUTO DI UN FILE

costo di accesso 53

CONTEGGIO STATISTICO APPROSSIMATO

Si predispone un buffer di lunghezza fissa con nposizioni di m bytes.

Si sceglie una funzione hash per trasformare la chiave in m bytes.

Si predispone una maschera di m*8 bitsinizialmente tutti a 0 (ad esempio).

Si leggono tutti i valori della chiave, si trasformano con la funzione hash e si inseriscono nel buffer se non già presenti.

Quando il buffer si riempie si escludono tutti i valori che contengono un valore diverso da quello della maschera nel bit meno significativo; ciò consente di eliminare circa la metà dei valori presenti.

costo di accesso 54

CONTEGGIO STATISTICO APPROSSIMATO

L’ algoritmo riparte non facendo entrare nel buffer i valori con il 10 bit diverso da quello della mascheramentre fa entrare tutti gli altri.

Quando nuovamente il buffer è pieno si eliminano i valori che hanno il 20 bit diverso da quello della maschera. etc..Algoritmo:

si predispone un buffer b vuoto per n valori di mbytes; si sceglie la funzione hash per trasformare ciscunvalore in m bytes.

costo di accesso 55

CONTEGGIO STATISTICO APPROSSIMATO

mult ← 1, nvalb ← 0repeat leggi il prossimo record

VH ← hash (valore nella colonna)IF mult > 1 THEN escludi VH se ≠ dalla maschera

per i valori da mult-1 ad 1;IF VH non è già in b THEN inserisci vH in b,

nvalb ← nvalb +1;IF b e' pieno THEN si escludono da b tutti i

valori il cui bit in posizionemult e' ≠ dal corrispondente bit della maschera, si compatta be si conta nvalb, mult← mult+1;

until fine del filenval← nvalb * 2 mult - 1 .

nvalb : valori diversi contenuti nel buffer,mult : fattore moltiplicativo,nval : stima del numero di valori diversi.

costo di accesso 56

CONTEGGIO STATISTICO APPROSSIMATO

vvalore

HASH

scartato

MASCHERA

?

BUFFER

scartato se gia' nel buffer

se il buffer e' pienoallora scarta i valori e modifica mult

mult

FILE

CAMPO

costo di accesso 57

CONTEGGIO STATISTICO APPROSSIMATO

La funzione hash è essenziale perché agisce darandomizzatore dei valori e rende giustificata l'ipotesi che ad ogni riempimento del buffer il controllo del valore 0/1 effettivamente elimini metà dei valori.

Questo metodo può commettere in qualche caso errori grandi ma mediamente l'errore è, confinato tra il 10% ed il 5%. la stima è sufficiente per i calcoli di prima approssimazione.

Un errore è anche introdotto dal fatto che le funzioni hashnon sono perfette ma introducono collisioni per valori diversi.

costo di accesso 58

Metodo linear counting

Date N tuple, calcolare gli nval valori diversi contenuti in una colonna. La funzione hash questa volta pone ad 1 un bit in un array di m bit (con m molto grande).Alla fine del processo si conta il numero di zeri nz nell'array che rapportato ad m dà :

p = nz/m = (1-1/m)nval

( 1/m è la probabilità che uno degli m bits corrisnda ad uno degli nval valori ≠, 1-1/m è la prob. che il bit non corrisponda ad uno degli nval valori, p è la prob. che il bit non corrisponda ad alcuno degli nval valori)

il numero di valori distinti è :

nval = loge p/ loge(1-1/m)

costo di accesso 59

Metodo linear counting

FILE

colonna

valori HASH

bit array

1 1 1001.. ..0100.. 10000..10..

costo di accesso 60

Metodo linear counting

Criteri di scelta di m: si usa una tabellaN m

100 80200 106500 172

1000 2685000 948

10000 170950000 6909

100000 12744500000 53848

1000000 10088010000000 83180950000000 3699768

Esistono tabelleprecalcolate che dato Ndicono quanto deve esserela dimensione mdel bit array peravere un erroreminore del 10%.

costo di accesso 61

Metodo linear counting

algoritmo linear counting

inizializza la bitarray a 0repeat

leggi una tupla;vh ← hash(valore);bitarray [vh] ← 1;

until fine del file

nz ← numero di 0 in bitarray; p ← nz/mnval ← loge p/ log e(1 - 1/m)