1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente –...

123
1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: efficiente concorrente affidabile integra sicura (protetta) Ciascuno degli aspetti precedenti è supportato dal DBMS da specifiche componenti, che complessivamente rappresentano l’architettura del sistema

Transcript of 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente –...

Page 1: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

1

Architettura di un DBMS

Un DBMS deve garantire una gestione dei dati:– efficiente– concorrente– affidabile– integra– sicura (protetta)

Ciascuno degli aspetti precedenti è supportato dal DBMS da specifiche componenti, che complessivamente rappresentano l’architettura del sistema

Page 2: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

2

Componenti di un DBMS

Efficienza:– File system: gestisce l'allocazione dello spazio su

disco e le strutture dati usate per rappresentare le informazioni memorizzate su disco

– Buffer manager: responsabile del trasferimento delle informazioni tra disco e main memory

– Query parser: traduce i comandi del DDL e del DML in un formato interno (parse tree)

– Optimizer: trasforma una richiesta utente in una equivalente ma più efficiente

Page 3: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

3

Componenti di un DBMS

Affidabilità:– Recovery manager: assicura che il DB rimanga in uno stato

consistente a fronte di cadute del sistema Concorrenza:

– Concurrency controller: assicura che interazioni concorrenti procedano senza conflitti

Integrità:– Integrity manager: controlla che i vincoli di integrità (per esempio

le chiavi) siano verificati Sicurezza

– Authorization manager: controlla che gli utenti abbiano i diritti di accesso ai dati

Page 4: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

4

Componenti di un DBMS

Un DBMS contiene inoltre alcune strutture dati che includono:

– i file con i dati (cioè i file per memorizzare il DB stesso) – i file dei dati di sistema (che includono il dizionario dei dati e le

autorizzazioni) – indici (esempio B tree o tabelle hash) – dati statistici (esempio il numero di tuple in una relazione) che

sono usati per determinare la strategia ottima di esecuzione

Page 5: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

5

Efficienza

Finora (Basi di dati 1) abbiamo visto modelli di DBMS ad alto livello (livello logico)

Tale livello è il livello corretto per gli utenti del DB Un fattore importante nell'accettazione da parte

dell'utente è dato dalle prestazioni Le prestazioni del DBMS dipendono dall'efficienza

delle strutture dati e dall'efficienza del sistema nell'operare su tali strutture dati

Page 6: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

6

Efficienza

Esistono varie strutture alternative per implementare un modello dei dati

La scelta delle strutture più efficienti dipende dal tipo di accessi che si eseguono sui dati

Normalmente un DBMS ha le proprie strategie di implementazione di un modello dei dati

Tuttavia l'utente (esperto) può influenzare le scelte fatte dal sistema (livello fisico)

Page 7: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

7

Mapping di relazioni a file

Per DBMS di piccole dimensioni (es. per PC) una soluzione spesso adottata è di memorizzare ogni relazione in un file separato

nel caso di DBMS large-scale questa strategia di base deve essere estesa (molto spesso il DBMS deve poter allocare in modo opportuno i record ai blocchi per minimizzare le operazioni di I/O)

– una strategia frequente è di allocare per il DBMS un unico grosso file, in cui sono memorizzate tutte le relazioni

– la gestione di questo file è lasciata al DBMS

Page 8: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

8

Clustering

Si consideri la seguente interrogazione:SELECT Imp#, Nome, Sede FROM Impiegati, Dipartimenti WHERE Impiegati.Dip# = Dipartimenti.Dip#

una strategia di memorizzazione efficiente è basata sul raggruppamento (clustering) delle tuple che hanno lo stesso valore dell'attributo di join

il clustering può rendere inefficiente l'esecuzione di altre interrogazioni

– es. SELECT * FROM Dipartimenti

Page 9: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

9

Clustering

Page 10: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

10

Strutture ausiliarie di accesso

Spesso le interrogazioni accedono solo un piccolo sottoinsieme dei dati

Per risolvere efficientemente le interrogazioni può essere utile allocare delle strutture ausiliarie che permettano di determinare direttamente i record che verificano una data query (senza scandire tutti i dati)

Page 11: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

11

Strutture ausiliarie di accesso

Ogni tecnica deve essere valutata in base a: – tempo di accesso – tempo di inserzione – tempo di cancellazione – occupazione di spazio

Molto spesso è preferibile aumentare l'occupazione di spazio se questo contribuisce a migliorare le prestazioni

Si usa il termine chiave di ricerca per indicare un attributo o insieme di attributi usati per la ricerca (diverso dalla chiave primaria)

Page 12: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

12

Strutture ausiliarie di accesso

Una ricerca può essere effettuata per: – chiave primaria: il valore della chiave identifica un unico record

Es. il contribuente con codice fiscale GRRGNN69R48– chiave secondaria: il valore della chiave può identificare più

record Es. i contribuenti di Genova

– intervallo di valori (sia per chiave primaria che per secondaria) Es. i contribuenti con reddito compreso tra 60 e 90 milioni

– combinazioni delle precedenti Es. i contribuenti di Genova e La Spezia con reddito compreso tra

60 e 90 milioni

Page 13: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

13

Strutture ausiliarie di accesso

Per effettuare la ricerca in modo più efficiente si può pensare di mantenere il file ordinato secondo il valore di una chiave di ricerca

in questo caso però la ricerca su altri campi è inefficiente

Page 14: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

14

Strutture ausiliarie di accesso

Organizzazioni primarie: – impongono un criterio di allocazione dei dati

(organizzazioni ad albero o hash)

organizzazioni secondarie: – uso di indici (separati dal file dei dati) normalmente

organizzati ad albero

in generale si hanno a disposizione più modalità (cammini) di accesso ai dati

Page 15: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

15

Strutture ausiliarie di accesso

Page 16: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

16

Indici

Idea base: associare al file dei dati una “tabella'’ nella quale l'entrata i esima memorizza una coppia (ki ,ri ) dove: – ki è un valore di chiave del campo su cui l'indice è

costruito – ri è un riferimento al record (ai record) con valore di

chiave ki il riferimento può essere un indirizzo (logico o fisico) di

record o di blocco

Page 17: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

17

Indici: esempio

File dei dati: chiavi c5 c2 c11 c7 c4 indirizzi 0 8 16 32 48

indice: chiave ki indirizzo ri

c2 8 c4 48 c5 0 c7 32 c11 16

Page 18: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

18

Indici

Le diverse tecniche differiscono nel modo in cui organizzano l'insieme di coppie (ki ,ri )

vantaggio nell'uso di un indice: – la chiave è solo parte dell'informazione contenuta in

un record, quindi l'indice occupa meno spazio del file dei dati

un indice può comunque raggiungere notevoli dimensioni che determinano problemi di gestione simili a quelli del file dei dati

Page 19: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

19

Indici

Esempio: – Indice per un file di 50k record, in cui i valori di

chiave sono stringhe di 20 byte e i puntatori sono di 4 byte, richiede circa 1,2Mb

ogni entrata nell’indice: 20 + 4 byte numero max entrate: 50 k totale: 24 * 50 K = 1,2 Mb

Page 20: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

20

Tipi di indice

Gli indici possono essere classificati rispetto a diverse dimensioni:– unicità valori chiave di ricerca– ordinamento dei record nel file di dati– numero di entrate nell’indice– numero di livelli

Page 21: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

21

Unicità dei valori di chiave

Indice su chiave primaria:– indice su un attributo che è chiave primaria per la

relazione (a ogni entrata dell'indice corrisponde un solo record)

Indice su chiave secondaria: – indice su un attributo che non è chiave primaria per

la relazione (ad ogni entrata dell'indice possono corrispondere più record)

Page 22: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

22

Ordinamento dei record nel file dei dati

Indice clusterizzato (o indice primario):– indice sull'attributo secondo i cui valori il file dei dati

è mantenuto ordinato

indice non clusterizzato (o indice secondario): – indice su un attributo secondo i cui valori il file dei

dati non è mantenuto ordinato

Page 23: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

23

Numero di coppie nell’indice

Indice denso– indice il cui numero di entrate (ki, ri) è pari al

numero di valori di ki

Indice sparso– indice il cui numero di entrate (ki, ri) è minore del

numero di valori di ki

Page 24: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

24

Numero di livelli

Indice a singolo livello– indice organizzato su un singolo livello

Indice multilivello– indice organizzato su più livelli

Page 25: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

25

Indici densi e sparsi

Indice denso: l'indice contiene un'entrata per ogni valore della chiave di ricerca nel file

– Ricerca: scansione per trovare il record con valore chiave uguale al valore cercato

– recupero dati fino a che il valore non cambia

Indice sparso: le entrate dell'indice sono create solo per alcuni valori della chiave.

– Ricerca: scansione fino a trovare il record con il più alto valore della chiave che sia minore o uguale al valore cercato

– scansione sequenziale del file dei dati fino a trovare il record cercato

Page 26: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

26

Indice denso

Page 27: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

27

Indice sparso

Page 28: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

28

Indici densi e sparsi

Un indice denso consente una ricerca più veloce, ma impone maggiori costi di aggiornamento

Un indice sparso è meno efficiente ma impone minori costi di aggiornamento

Poiché molto spesso la strategia è di minimizzare il numero di blocchi trasferiti, un compromesso spesso adottato consiste nell'avere una entrata nell'indice per ogni blocco

Page 29: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

29

Indici multilivello

Un indice anche se sparso può essere di dimensioni notevoli

Esempio: file di 100000 record, con 10 record per blocco, richiede

un indice con 10000 entrate se ogni blocco contiene 100 entrate dell’indice: 100 blocchi

Page 30: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

30

Indici multilivello

Se l’indice è piccolo, può essere tenuto in memoria principale

molto spesso, però, è necessario tenerlo su disco e la scansione dell’indice può richiedere parecchi trasferimenti di blocchi – circa 7 nel nostro esempio, se si utilizza ricerca binaria

Soluzione:– si tratta l’indice come un file e si alloca un indice sparso

sull’indice stesso– si parla di indice sparso a due livelli

Page 31: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

31

Indici multilivello

se l’indice esterno è mantenuto in memoria principale basta accedere un solo blocco di indice

Page 32: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

32

Tecniche di indicizzazione

Le strutture per MS differiscono da quelle per MM perché si cerca di minimizzare il numero di blocchi acceduti (che determina il costo della ricerca) – basate su alberi (B-tree e varianti)– basate su tabelle hash

Page 33: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

33

B-Alberi

i B-alberi sono organizzazioni ad albero bilanciato, utilizzate come strutture di indicizzazione per dati in memoria secondaria

requisiti fondamentali per indici per memoria secondaria:– bilanciamento: l’indice deve essere bilanciato rispetto ai blocchi e non

ai singoli nodi (è il numero di blocchi acceduti a determinare il costo I/O di una ricerca)

– occupazione minima: è importante che si possa stabilire un limite inferiore all’utilizzazione dei blocchi, per evitare una sotto-utilizzazione della memoria

– efficienza di aggiornamento: le operazioni di aggiornamento devono avere costo limitato

Page 34: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

34

B-alberi

garantiscono un’occupazione di memoria almeno del 50% (almeno metà di ogni pagina allocata è effettivamente occupata)

consentono di effettuare l’operazione di ricerca con costo, nel caso peggiore, logaritmico nella cardinalità dell’indice (cioè nel numero di valori distinti della chiave di ricerca)

in un B-albero ogni nodo ha al più m figli, dove m è l’unico parametro dipendente dalle caratteristiche della memoria, cioè dalla dimensione del blocco

Page 35: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

35

B-alberi

Un B-albero di ordine m (m 3) è un albero bilanciato che soddisfa le seguenti proprietà:

– ogni nodo contiene al più m - 1 elementi– ogni nodo contiene almeno elementi,– la radice può contenere anche un solo elemento

ogni nodo non foglia contenente j elementi ha j +1 figli ogni nodo ha una struttura del tipo:

p0(k1, r1)p1(k2, r2)p2 . . . pj-1(kj, rj)pj

dove j è il numero degli elementi del nodo

12/ m

Page 36: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

36

B-alberi

In ogni nodo

p0(k1, r1)p1 (k2, r2)p2 . . . pj-1(kj, rj)pj

k1, ... , kj sono chiavi ordinate, cioè k1 < k2 < ... < kj

nel nodo sono presenti j + 1 riferimenti ai nodi figli p0,..., pj e j riferimenti al file dei dati r1, ... , rj

per ogni nodo non foglia, detto K(pi) (i = 1, ... , j) l’insieme delle chiavi memorizzate nel sottoalbero di radice pi, si ha: y K(p0), y < k1

y K(pi), ki < y < ki+1, i = 1, ... , j - 1

y K(pj), y > kj

Page 37: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

37

B-alberi

Formato di un nodo di un B-albero

Page 38: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

38

B-alberi

Esempio di B-albero di ordine 5

Page 39: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

39

B+-alberi

Un B-albero è molto efficiente per la ricerca e la modifica dei singoli record

– ad esempio, con m = 100 e N = 1000000 la ricerca di una chiave comporta al massimo 4 accessi a disco

un B-albero non è però particolarmente adatto per elaborazioni di tipo sequenziale nell’ordine dei valori di chiave, né per la ricerca dei valori di chiave compresi in un certo intervallo

– la ricerca del successore di un valore di chiave può comportare la scansione di molti nodi

per ovviare a questo problema è stata proposta una variante dei B-alberi, nota come B+-alberi

Page 40: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

40

B+-alberi

Idea principale: in un B-albero, i valori di chiave svolgono una duplice funzione:

– separatori: per determinare il cammino da seguire nella ricerca– valori di chiave: permettono di accedere all’informazione ad

essi associata

nei B+-alberi queste funzioni sono mantenute separate:– le foglie contengono tutti i valori di chiave– i nodi interni (organizzati a B-albero) memorizzano dei

separatori la cui sola funzione è determinare il giusto cammino nella ricerca di una chiave

Page 41: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

41

B+-alberi

i nodi foglia sono inoltre collegati a lista, per facilitare ricerche per intervalli di chiavi o sequenziali (+ puntatore alla testa di tale lista, per accedere velocemente al valore di chiave minimo)

parziale duplicazione delle chiavi– le entrate dell’indice (chiavi e riferimenti ai dati) sono

solo nelle foglie – la ricerca di una chiave deve individuare una foglia

Page 42: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

42

B+-alberi

il sottoalbero sinistro di un separatore contiene valori di chiave minori del separatore, quello destro valori di chiave maggiori od uguali al separatore

nel caso di chiavi alfanumeriche facendo uso di separatori di lunghezza ridotta si risparmia spazio

Page 43: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

43

B+-alberi

Un B+-albero di ordine m (m 3) è un albero bilanciato che soddisfa le seguenti proprietà:– ogni nodo contiene al più m - 1 elementi– ogni nodo, tranne la radice, contiene almeno

elementi, la radice può contenere anche un solo elemento

– ogni nodo non foglia contenente j elementi ha j +1 figli

12/ m

Page 44: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

44

B+-alberi

ogni nodo foglia ha una struttura del tipo:

(k1, r1)(k2, r2) . . . (kj, rj)

dove:– j è il numero degli elementi del nodo– k1, ... , kj sono chiavi ordinate, cioè k1 < k2 < ... < kj

– r1, ... , rj sono j riferimenti al file dei dati

ogni nodo foglia ha un puntatore al nodo foglia precedente e successivo

Page 45: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

45

B+-alberi

ogni nodo non foglia ha una struttura del tipo:

p0k1p1k2p2 . . . pj-1kjpj

dove:– j è il numero degli elementi del nodo– k1, ... , kj sono chiavi ordinate, cioè k1 < k2 < ... < kj

– p0, … , pj sono j+1 riferimenti ai nodi figli

Page 46: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

46

B+-alberi

per ogni nodo non foglia, detto K(pi) (i = 0, ... , j) l’insieme delle chiavi memorizzate nel sottoalbero di radice pi, si ha: y K(p0), y < k1

y K(pi), ki y < ki+1, i = 1, . . . , j - 1

y K(pj), y kj

– ogni ki, per i = 1, . . . , j è l’elemento minimo di K(pi)

Page 47: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

47

B+-alberi

Page 48: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

48

B+-alberi

Esempio di B+-albero di ordine 5

Page 49: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

49

B+-alberi: confronto con B-alberi

HP: parità di dimensione dei nodi la ricerca di una singola chiave è più costosa in media in un

B+-albero (si deve necessariamente raggiungere sempre la foglia per ottenere il puntatore ai dati)

per operazioni che richiedono il reperimento dei record ordinati in base al valore della chiave o per intervalli di chiave i B+- alberi sono da preferirsi (il collegamento a lista delle foglie elimina la necessità di accedere ai nodi ad altri livelli)

il B-albero è più conveniente per quanto riguarda l’occupazione di memoria (le chiavi sono memorizzate una volta sola)

Page 50: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

50

Organizzazioni hash

Le organizzazioni hash sono usate principalmente per l’organizzazione primaria dei dati

l’uso di indici ha lo svantaggio che è necessario eseguire la scansione di una struttura dati per localizzare i dati

questo perché l’associazione(chiave, indirizzo)

è mantenuta in forma esplicita un’organizzazione hash utilizza una funzione hash H che

trasforma ogni valore di chiave in un indirizzo per effettuare la ricerca, data una chiave k, si calcola

semplicemente H(k)

Page 51: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

51

Organizzazioni hash

Ogni indirizzo generato dalla funzione hash individua una pagina logica, o bucket

il numero di elementi che possono essere allocati nello stesso bucket determina la capacità c dei bucket

se una chiave viene assegnata a un bucket che già contiene c chiavi si ha un trabocco (overflow)

la presenza di overflow può richiedere l’uso di un’area di memoria separata, detta area di overflow

l’area di memoria costituita dai bucket indirizzabili dalla funzione hash è detta area primaria

Page 52: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

52

Organizzazioni hash

012

M-1

hkey

h(key) mod M ……

area primaria area di overflow

c

c

Page 53: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

53

Organizzazioni hash

Una funzione hash genera M indirizzi (0, . . . ,M - 1) tanti quanti sono i bucket dell’area primaria

organizzazione statica: il valore di M è costante (il dimensionamento dell’area primaria è parte integrante del progetto dell’organizzazione)

organizzazione dinamica: l’area primaria si espande e contrae, per adattarsi al volume effettivo dei dati (si usano più funzioni hash)

– Hash lineare (non lo vediamo)– Hash estensibile

Page 54: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

54

Hashing estensibile

l’hashing estensibile fa uso di una struttura ausiliaria, detta direttorio

il direttorio è un insieme di 2p celle, con indirizzi da 0 a 2p-1, con p >= 0 profondità del direttorio

l’espansione dell’area dati avviene aggiungendo una nuova pagina ogni volta che si tenta di inserire un record in una pagina satura

Page 55: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

55

Hashing estensibile

idea: fare uso di una funzione hash che, dato un valore di chiave ki, restituisce non un indirizzo di bucket, ma una stringa binaria di opportuna lunghezza (ad esempio, 32 bit) detta pseudochiave

la funzione hash associa ad ogni chiave una pseudochiave di cui si considerano i primi p bit per accedere direttamente ad una delle 2p celle, ognuna contenente un puntatore ad un bucket

Page 56: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

56

Hashing estensibile: esempio

Page 57: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

57

Hashing estensibile

ogni bucket ha una profondità locale p’<=p (mantenuta nel bucket) che indica il numero effettivo di bit usati per allocare le chiavi nel bucket stesso

una cella del direttorio contiene il riferimento ad una pagina dell’area dati contenente tutte e sole le registrazioni con pseudochiavi con lo stesso prefisso di lunghezza p’

Page 58: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

58

Hashing estensibile: esempio

p=3

Page 59: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

59

Hashing estensibile

per effettuare la ricerca di un record:– si estraggono i primi p bit dalla pseudochiave– si accede l’entrata dell’indice che corrisponde alla

stringa di p bit– dall’entrata si determina l’indirizzo della pagina del

file che contiene il record cercato

Page 60: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

60

Hashing estensibile

per effettuare l’inserimento di un record:– inizialmente si ha un solo bucket e p = p’ = 0– quando si deve inserire un record in una pagina

satura di profondità p’, se p = p’ innanzitutto si raddoppia il direttorio e si incrementa p di 1, copiando i valori dei puntatori nelle nuove celle corrispondenti

Page 61: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

61

Hashing estensibile

– sia nel caso p = p’ che nel caso p’ < p, si alloca un nuovo bucket e si distribuiscono le chiavi tra i due bucket (quello saturo e quello appena allocato) facendo uso del p’+1-esimo bit delle pseudochiavi

– per i due bucket si pone a p’+1 la profondità locale e si aggiorna il direttorio facendo in modo che una sua cella contenga un riferimento al nuovo bucket

Page 62: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

62

Esempio 1

Page 63: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

63

Esempio 2

Page 64: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

64

Esempio 2 – cont.

Page 65: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

65

Esempio 3

Page 66: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

66

Confronto tra indici e hashing

se la maggior parte delle interrogazioni ha la forma

SELECT A1,A2,......An FROM R WHERE Ai=C

la tecnica hash è preferibile infatti:

– la scansione di un indice ha un costo proporzionale al logaritmo del numero di valori in R per Ai

– in una struttura hash il tempo di ricerca è indipendente dalla dimensione della base di dati

Page 67: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

67

Confronto tra indici e hashing

gli alberi sono preferibili se le interrogazioni usano condizioni di range

SELECT A1,A2,......An FROM R

WHERE C1 < Ai < C2

è infatti difficile determinare funzioni hash che mantengono l’ordine

Page 68: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

68

Definizione di cluster e indici in SQL

la maggior parte dei DBMS relazionali fornisce varie primitive che permettono al progettista della base di dati di definire la configurazione fisica dei dati

queste primitive sono rese disponibili all’utente come comandi del linguaggio SQL

non esiste uno standard, ma la sintassi non differisce molto nei vari sistemi per quanto riguarda i comandi principali

Page 69: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

69

Definizione di cluster e indici in SQL

i comandi più importanti sono il comando per la creazione di indici, su una o più colonne di una relazione, e il comando per la creazione di cluster

un cluster permette di memorizzare fisicamente contigue le tuple di una o più relazioni che hanno lo stesso valore per una o più colonne, dette colonne del cluster

Page 70: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

70

Definizione di cluster e indici in SQL

il comando per la creazione di un indice in SQL ha il seguente formato:

CREATE INDEX Nome Indice

ON Nome Relazione(Lista Nomi Colonne) |

Nome Cluster

[ASC | DESC];

dove– Nome Indice è il nome dell’indice che si crea– la clausola ON specifica l’oggetto su cui è allocato

l’indice

Page 71: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

71

Definizione di cluster e indici in SQL

Tale oggetto può essere:– una relazione: si devono specificare i nomi delle colonne su cui l’indice è

allocato– un cluster: l’indice viene allocato automaticamente su tutte le colonne del

cluster l’indice può essere allocato su più colonne

– i valori della chiave sono ottenuti come concatenazione di tutti i valori di tali colonne, normalmente esiste un limite al numero di colonne (es. in Oracle 16)

le opzioni ASC e DESC specificano se i valori della chiave dell’indice devono essere ordinati in modo crescente o decrescente

– ASC è il default

Page 72: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

72

Definizione di cluster e indici in SQL - Esempio

L’indice creato è in genere un B+-tree o una sua variante

Per allocare un indice sulla colonna stipendio della relazione Impiegati

CREATE INDEX idxstipendio

ON Impiegati (stipendio);

Page 73: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

73

Definizione di cluster e indici in SQL

Definizione di indici clusterizzati (DB2):CREATE INDEX Nome Indice

ON Nome Relazione(Lista Nomi Colonne)

CLUSTER;

una tabella può avere un solo indice clusterizzato se la tabella è non vuota quando si crea l’indice

clusterizzato i dati non vengono automaticamente raggruppati (è necessario usare una speciale utility REORG)

Page 74: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

74

Definizione di cluster e indici in SQL

Comando per la creazione di un cluster:CREATE CLUSTER NomeCluster

(NomeCol1 Dominio_1, . . ,NomeColn Dominio_n)

[INDEX | HASH IS Expr |

HASHKEYS Intero];

NomeCluster è il nome del cluster che si definisce (NomeCol1 Dominio_1, . . ., NomeColn Dominio_n),

con n >= 1, è la specifica delle colonne del cluster– tale insieme di colonne è detto chiave del cluster

Page 75: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

75

Definizione di cluster e indici in SQL

Ogni cluster è sempre associato ad una struttura di accesso ausiliaria

– Index: vengono clusterizzate tuple con lo stesso valore per la chiave del

cluster e indicizzate tramite un indice di tipo B+-albero (default) conviene se si hanno frequenti interrogazioni di tipo range sulla chiave

del cluster o se le relazioni possono aumentare di dimensione in modo impredicibile

cluster di tipo index– Hash:

vengono clusterizzate le tuple con lo stesso valore di hash per la chiave del cluster e indicizzate tramite una funzione hash

conviene se si hanno frequenti interrogazioni con predicati di uguaglianza su tutte le colonne e se le relazioni sono statiche

cluster di tipo hash

Page 76: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

76

Definizione di cluster e indici in SQL - cluster di tipo hash

Il DBMS fornisce sempre una funzione hash interna che viene usata come default (spesso basata sul metodo della divisione)

l’opzione HASHKEYS permette di specificare il numero di valori della funzione hash

questo valore (se non è un numero primo) viene arrotondato dal sistema al primo numero primo maggiore

tale valore viene usato come argomento dell’operazione di modulo usata dal sistema per generare i valori della funzione hash

Page 77: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

77

Definizione di cluster e indici in SQL - Esempio

Cluster di tipo indice:CREATE CLUSTER Personale(D# NUMBER);

CREATE INDEX idxpersonnel

ON CLUSTER Personale;

Cluster di tipo hash:CREATE CLUSTER Personale

(D# NUMBER) HASHKEYS 10;

dato che l’opzione HASHKEYS ha valore 10, il numero di valori generati dalla funzione hash è 11 (primo numero primo > 10)

Page 78: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

78

Definizione di cluster e indici in SQL - cluster di tipo hash

È possibile cambiare la funzione hash da utilizzare tramite l’opzione HASH IS

questa opzione può tuttavia essere usata solo se:– la chiave del cluster è composta da campi di tipo intero– l’espressione deve restituire valori positivi– + altre condizioni

Page 79: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

79

Definizione di cluster e indici in SQL - cluster di tipo index

se il cluster è di tipo index, prima di poter eseguire interrogazioni o modifiche è necessario creare un indice sul cluster tramite il comando di CREATE INDEX

un cluster può includere una o più relazioni– singola relazione: il cluster è usato per raggruppare le tuple della

relazione aventi lo stesso valore per le colonne che sono chiavi del cluster

– più relazioni: il cluster viene usato per raggruppare le tuple di tutte le relazioni aventi lo stesso valore per la chiave del cluster (join efficienti su colonne che sono parte della chiave del cluster)

una relazione deve essere inserita nel cluster al momento della creazione

Page 80: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

80

Definizione di cluster e indici in SQL - Esempio

per inserire nel cluster Personale le relazioni Impiegati e Dipartimenti

CREATE TABLE Impiegati

(Imp# Decimal(4) NOT NULL,

Dip# Decimal(2))

CLUSTER personale (Dip#);

CREATE TABLE Dipartimenti

(Dip# Decimal(4) NOT NULL)

CLUSTER personale (Dip#);

Page 81: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

81

Definizione di cluster e indici in SQL - Esempio

i nomi delle colonne delle relazioni su cui si esegue il clustering non devono necessariamente avere lo stesso nome della colonna del cluster, devono però avere lo stesso tipo

Page 82: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

82

Ottimizzazione delle interrogazioni

Page 83: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

83

Ottimizzazione di interrogazioni

abbiamo visto finora come organizzare i dati in un DB normalmente le decisioni sulle strutture da allocare sono

determinate durante la progettazione fisica della base di dati

la modifica di tali strutture in seguito può essere costosa quindi quando una interrogazione è presentata al

sistema occorre determinare il modo più efficiente per eseguirla usando le strutture disponibili

Page 84: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

84

Ottimizzazione di interrogazioni

nell’elaborazione di interrogazioni si trasforma quindi una query in un query plan

Esempio:

SELECT B,D

FROM R,S

WHERE R.A = “c” S.E = 2 R.C=S.C

Page 85: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

85

Ottimizzazione di interrogazioni

R A B C S C D E

a 1 10 10 x 2

b 1 20 20 y 2

c 2 10 30 z 2

d 2 35 40 x 1

e 3 45 50 y 3

Page 86: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

86

Ottimizzazione di interrogazioni

Risposta:

B D2 x

Come eseguiamo tale interrogazione? Una possibile strategia è:

– fare il prodotto Cartesiano– selezionare le tuple– effettuare la proiezione

Page 87: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

87

Ottimizzazione di interrogazioni

RXS R.A R.B R.C S.C S.D S.E

a 1 10 10 x 2

a 1 10 20 y 2

. .

C 2 10 10 x 2 . .

Page 88: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

88

Ottimizzazione di interrogazioni

I piani di esecuzione possono essere descritti per mezzo dell’algebra relazionale

il piano descritto è

B,D [ R.A=“c” S.E=2 R.C = S.C (RXS)]

Piano I B,D

R.A=“c” S.E=2 R.C=S.C

XR S

Page 89: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

89

Ottimizzazione di interrogazioni

Altra possibile strategia

Piano II B,D

R.A = “c” S.E = 2

R S

natural join

Page 90: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

90

Ottimizzazione di interrogazioni R S

A B C (R) (S) C D E

a 1 10 A B C C D E 10 x 2

b 1 20 c 2 10 10 x 2 20 y 2

c 2 10 20 y 2 30 z 2

d 2 35 30 z 2 40 x 1

e 3 45 50 y 3

Page 91: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

91

Ottimizzazione di interrogazioni

Piano III si utilizzano gli indici R.A e S.C

– si usa l’indice R.A per selezionare le tuple di R con R.A = “c”

– per ogni valore di R.C trovato si usa l’indice su S.C per trovare le tuple che matchano

– si eliminano le tuple di S tali che S.E 2– si concatenano le tuple di R e S risultanti,

proiettando su B e D

Page 92: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

92

Ottimizzazione di interrogazioni

R S

A B C C D E

a 1 10 10 x 2

b 1 20 20 y 2

c 2 10 30 z 2

d 2 35 40 x 1

e 3 45 50 y 3

A CI1 I2

=“c”

<c,2,10> <10,x,2>

check=2?

output: <2,x>

tupla successiva:<c,7,15>

Page 93: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

93

Ottimizzazione di interrogazioni

per interrogazioni complesse esistono più strategie possibili

il costo di determinare la strategia ottima può essere elevato

il vantaggio in termini di tempo di esecuzione che se ne ricava è tuttavia tale da rendere preferibile eseguire l'ottimizzazione

Page 94: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

94

Ottimizzazione di interrogazioni

Esempio Consideriamo le relazioni

Studenti(MatrS,Nome,Ind,AltreInfo) Esami(Corso,MatrS,Voto,Data)

Supponiamo di voler trovare il nome degli studenti e la data degli esami per gli studenti che hanno sostenuto BD con 30

SELECT Nome,Data FROM Studenti NATURAL JOIN Esami WHERE Corso ='BD' AND Voto =30

Page 95: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

95

Ottimizzazione di interrogazioni

Consideriamo un database con 2.000 studenti e 20.000 esami, di cui 500 di BD e di questi solo 50 con 30 (consideriamo solo la scansione sequenziale delle relazioni)

Se si fa il prodotto cartesiano delle due relazioni, si ottiene una relazione temporanea con 40.000.000 tuple, da queste si estraggono poi le 50 tuple desiderate (costo proporzionale a 120.000.000 accessi)

Se si selezionano i 50 esami di BD con 30 e poi si fa il join di questa relazione temporanea con Studenti si ha un costo proporzionale a 120.050

Page 96: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

96

Passi nell’esecuzione di un’interrogazione

Parsing – Viene controllata la correttezza sintattica della query e ne

viene generata una rappresentazione interna (parse tree)

Trasformazioni algebriche – La query viene trasformata in una query equivalente ma più

efficiente da eseguire (ci si basa sulle proprietà dell'algebra relazionale)

– Esempi: eseguire le operazioni di selezione prima possibile evitare join che rappresentano prodotti Cartesiani

Page 97: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

97

Efficienza - Passi nell’esecuzione di un’interrogazione

Selezione della strategia – si determina in modo preciso come la query sarà eseguita

(per esempio si determina che indici si useranno) – la scelta della strategia è fatta principalmente in base al

numero di accessi a disco Esecuzione della strategia scelta

– è possibile eseguire alcuni dei passi a tempo di compilazione del programma (DB2 e System R usano questa strategia) o a tempo di esecuzione (Oracle usa questa strategia)

Page 98: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

98

Passi nell’esecuzione di un’interrogazione

parse

convert

apply laws

estimate result sizes

consider physical plans estimate costs

pick best

execute

{(P1,C1),(P2,C2)...}

Pi

answer

SQL queryparse tree

logical query plan

“improved” l.q.p.

l.q.p. +sizes

statistics

{P1, P2, …}

Page 99: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

99

Passi nell’esecuzione di un’interrogazione

Esempio: query SQLSELECT titleFROM StarsInWHERE starName IN (

SELECT nameFROM MovieStarWHERE birthdate LIKE ‘%1960’);

Trovare i film in cui hanno recitato attori nati nel 1960

Schema:StarsIn(title,year,starName)MovieStar(name, address, gender,birthdate)

Page 100: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

100

Passi nell’esecuzione di un’interrogazione - parse tree

<Query>

<SFW>

SELECT <SelList> FROM <FromList> WHERE <Condition>

<Attribute> <RelName> <Tuple> IN <Query>

title StarsIn <Attribute> ( <Query> )

starName <SFW>

SELECT <SelList> FROM <FromList> WHERE <Condition>

<Attribute> <RelName> <Attribute> LIKE <Pattern>

name MovieStar birthDate ‘%1960’

Page 101: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

101

Passi nell’esecuzione di un’interrogazione - algebra

title

StarsIn <condition>

<tuple> IN name

<attribute> birthdate LIKE ‘%1960’

starName MovieStar

Page 102: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

102

Passi nell’esecuzione di un’interrogazione: logical query plan

title

starName=name

StarsIn name

birthdate LIKE ‘%1960’

MovieStar

Page 103: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

103

Passi nell’esecuzione di un’interrogazione: improved logical query plan

title

starName=name

StarsIn name

birthdate LIKE ‘%1960’

MovieStar

Page 104: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

104

Passi nell’esecuzione di un’interrogazione: stima della dimensione del risultato

necessità di determinare

la dimensione

StarsIn

MovieStar

Page 105: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

105

Passi nell’esecuzione di un’interrogazione: physical plan

Parametri: ordine di esecuzione dei join,

dimensione della memoria, attributi su cui si proietta,...

Hash join

SEQ scan index scan Parametri:condizione di selezione,...

StarsIn MovieStar

Page 106: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

106

Passi nell’esecuzione di un’interrogazione: stima dei costi

L.Q.P.

P1 P2 …. Pn

C1 C2 …. Cn

Scelta del piano di esecuzione migliore

Page 107: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

107

Ottimizzazione di interrogazioni

Un piano di esecuzione di un’interrogazione consiste quindi in:

– un ordine di esecuzione delle varie operazioni relazionali– una strategia per l’esecuzione di ogni operazione

Page 108: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

108

Progettazione fisica

Page 109: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

109

Progettazione fisica

Dopo la progettazione concettuale e logica dello schema con le metodologie viste, e la definizione del livello esterno (viste) abbiamo gli schemi logico e esterno della base di dati

bisogna però ancora scegliere gli indici e decidere le strategie di memorizzazione delle relazioni

inoltre gli schemi logici ed esterni ottenuti dalla progettazione possono dover essere rivisti per esigenze legate alle prestazioni

Page 110: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

110

Progettazione fisica

il primo passo per effettuare questa fase di progettazione è capire il workload:– quali sono le query più importanti e con che frequenza

vengono eseguite– quali sono gli aggiornamenti più importanti e con che

frequenza vengono eseguiti– le prestazioni desiderate/necessarie per tali

interrogazioni e aggiornamenti

Page 111: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

111

Progettazione fisica

Per ogni query nel workload bisogna chiedersi:– a quali relazioni accede?– quali attributi ritrova?– quali attributi sono coinvolti in condizioni di selezione/join?

quanto selettive saranno queste condizioni?

Per ogni update nel workload bisogna chiedersi:– quali attributi sono coinvolti in condizioni di selezione/join?

quanto selettive saranno queste condizioni? – il tipo di update (INSERT/DELETE/UPDATE) e gli attributi che

saranno coinvolti nell’aggiornamento

Page 112: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

112

Progettazione fisica

Decisioni da prendere quali indici creare

– quali relazioni devono avere indici– su quali attributi– più di un indice per relazione

per ogni indice, di che tipo deve essere– clusterizzato? hash/tree? denso/sparso?

Page 113: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

113

Progettazione fisica

Decisioni da prendere bisogna modificare lo schema? (tuning schema logico)

– si può decidere di scegliere uno schema in 3NF piuttosto che in BCNF

– il workload può influenzare le scelte fatte nello scomporre una relazione in 3NF o BCNF (seguire schemi di normalizzazione alternativi)

– si può scomporre ulteriormente uno schema BCNF

– si può denormalizzare (cioè disfare un passo di normalizzazione), o si possono aggiungere campi ad una relazione

– si può effettuare una scomposizione orizzontale

Page 114: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

114

Progettazione fisica

Decisioni da prendere Bisogna modificare le interrogazioni? (tuning delle interrogazioni) se un’interrogazione è più lenta di quel che ci si aspetta bisogna

controllare se le statistiche sono troppo vecchie a volte più succedere che il DBMS non stia eseguendo il piano che

si pensa - tipicamente questo succede per:– selezioni che coinvolgono valori nulli– selezioni che coinvolgono espressioni aritmetiche o su stringhe– selezioni che coinvolgono condizioni in OR – mancanza di caratteristiche quali strategie index-only o alcuni metodi di

join o stima inesatta delle dimensioni si deve controllare quale piano viene effettivamente utilizzato e

aggiustare la scelta degli indici o riscrivere l’interrogazione

Page 115: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

115

Progettazione fisica

Scelta degli indici Un possibile approccio è:

– si considerano una alla volta le query più importanti– si considera il piano di esecuzione migliore utilizzando gli

indici attualmente disponibili– se con un indice addizionale si avrebbe un piano di

esecuzione migliore, lo si aggiunge prima di creare un indice, però, bisogna anche considerare

l’impatto degli aggiornamenti sul workload! trade-off:

– gli indici possono velocizzare le query ma rallentare gli aggiornamenti– inoltre richiedono spazio su disco

Page 116: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

116

Progettazione fisica

Scelta degli indici gli attributi che appaiono in una clausola WHERE sono

candidati come chiavi per un indice– se la condizione è di uguaglianza può essere meglio un indice hash – se la condizione è di tipo range si preferisce un indice ad albero – la clusterizzazione su tale attributo è particolarmente utile in caso di

query tipo range, ma può essere utile anche per l’uguaglianza se ci sono duplicati

bisogna cercare di scegliere indici che siano utilizzabili nel maggior numero possibili di query

un solo indice per relazione può essere clusterizzato, per sceglierlo ci si basa sulle interrogazioni importanti che trarrebbero maggior vantaggio dalla clusterizzazione

Page 117: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

117

Progettazione fisica

Scelta degli indici se la clausola WHERE di un’interrogazione importante

contiene diverse condizioni si considerano anche indici con chiave multi-attributo– se si hanno selezioni di tipo range, l’ordine degli

attributi deve essere scelto attentamente in modo da corrispondere a quello del range

– si noti anche che questo tipo di indici a volte permettono strategie index-only per query importanti

si noti anche che per le strategie index-only, il clustering non è importante!

Page 118: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

118

Progettazione fisica

Esempio un indice hash su D.dname permette la selezione di ‘Toy’

– non serve quindi un indice su D.dno un indice hash su E.dno permette di ritrovare le tuple di

Emp che matchano per ogni tupla di Dept selezionata se la clausola WHERE includesse: “... AND E.age=25”?

– si potrebbero ritrovare le tuple di Emp usando l’indice su E.age, e poi effettuare il join cercando le tuple di Dept che soddisfano la condizione su dname (analogo alla strategia utilizzando l’indice su E.dno)

– se si ha già un indice su E.age, questa query non motiva l’aggiunta di un indice su E.dno

SELECT E.ename, D.mgrFROM Emp E, Dept DWHERE D.dname=‘Toy’ AND E.dno=D.dno

Page 119: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

119

Progettazione fisica

Esempio Visto che le selezioni sono su Emp, si parte da li a valutare

l’interrogazione – potrebbe essere utile un indice hash su D.dno

che indici si dovrebbero costruire su Emp?– si potrebbe usare un indice di tipo B+ tree su E.sal O un indice su E.hobby – uno solo di tali indici è necessario e qual è meglio dipende dalla selettività

delle condizioni in generale (ma non è detto!), le selezioni con uguaglianza sono più selettive di

quelle di tipo range si noti come la scelta degli indici sia guidata dai piani che ci aspettiamo

che l’ottimizzatore considerà per la query bisogna avere chiaro come funzionano gli ottimizzatori!

SELECT E.ename, D.mgrFROM Emp E, Dept DWHERE E.sal BETWEEN 10000 AND 20000 AND E.hobby=‘Stamps’ AND E.dno=D.dno

Page 120: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

120

Progettazione fisica

Clustering si può usare un indice di tipo B+

tree su E.age– quanto selettiva è la condizione?– l’indice è clusterizzato?

interrogazione con GROUP BY– se molte tuple hanno E.age > 10, l’uso

dell’indice su E.age seguito dall’ordinamento delle tuple ritrovate può essere costoso

– un indice clusterizzato su E.dno può essere meglio

query di uguaglianza con duplicati:– è vantaggioso clusterizzare su

E.hobby

SELECT E.dnoFROM Emp EWHERE E.age>40

SELECT E.dno, COUNT (*)FROM Emp EWHERE E.age>10GROUP BY E.dno

SELECT E.dnoFROM Emp EWHERE E.hobby=Stamps

Page 121: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

121

Progettazione fisica

Indici multi-attributo per ritrovare record di Emp con age=30 AND sal=4000, un

indice su <age,sal> è meglio di un indice su age o un indice su sal

– tali indici sono anche detti indici compositi o concatenati– la scelta della chiave dell’indice è ortogonale al clustering etc.

se la condizione è: 20<age<30 AND 3000<sal<5000: – indici ad albero clusterizzati su <age,sal> o <sal,age> sono la

soluzione migliore se la condizione è: age=30 AND 3000<sal<5000:

– un indice clusterizzato su <age,sal> è molto meglio di un indice <sal,age>

gli indici compositi sono però più grossi e vengono aggiornati più spesso

Page 122: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

122

Progettazione fisica

Piani Index-Only un certo numero

di query può essere risolto senza ritrovare tuple da una o più delle relazioni coinvolte se è disponibile un indice opportuno

SELECT D.mgrFROM Dept D, Emp EWHERE D.dno=E.dno

SELECT E.dno, COUNT(*)FROM Emp EGROUP BY E.dno

<E.dno>

<E.dno>

SELECT E.dno, MIN(E.sal)FROM Emp EGROUP BY E.dno

SELECT AVG(E.sal)FROM Emp EWHERE E.age=25 AND E.sal BETWEEN 3000 AND 5000

<E.dno,E.sal>(ad albero)

<E. age,E.sal> o<E.sal, E.age>(ad albero)

Page 123: 1 Architettura di un DBMS Un DBMS deve garantire una gestione dei dati: – efficiente – concorrente – affidabile – integra – sicura (protetta) Ciascuno.

123

Riferimenti

Raghu Ramakrishnan, Johannes Gehrke “Database Management Systems - Second Edition” McGraw Hill, 2000

Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom “Database System Implementation” Prentice Hall, 2000