Viste materializzate

(1)

Viste materializzate, A. Albano

IL PROBLEMA DELLE VISTE MATERIALIZZATE

Le viste nei DBMS relazionali

SELECT NegozioId, ProductId, SUM(Q) AS TQ

FROM Vendite

GROUP BY NegozioId, ProductId;

SELECT NegozioId, SUM(Q) AS TQ

FROM Vendite

GROUP BY NegozioId;

Vendite(ProductId, NegozioId, DataId, Q)

Utilità delle viste materializzate per l'esecuzione di interrogazioni

1

Si materializza :V

Si riscrive

SELECT NegozioId, SUM(TQ) AS TQ

FROM V

GROUP BY NegozioId;

IL PROBLEMA DELLE VISTE MATERIALIZZATE: PROBLEMI

• dato un carico di lavoro Q, quali viste materializzare

• come aggiornare le viste quando si modificano i dati (non si considera) • data un'interrogazione, come riscriverla per usare una vista materializzata

2

Viste materializzate, A. Albano APPROCCIO Interrogazioni Q Algortimo di selezione Modello dei costi Vincoli e obiettivi Viste candidate Viste materializzate selezionate

3 Viste materializzate, A. Albano

NOZIONE DI PATTERN DI AGGREGAZIONE

Il pattern (di aggregazione) P(v) di una vista v = A

!

è l'insieme A degli attributi di

raggruppamento.

Date due viste v1 e v2 e un'interrogazione q, se v1 < v2 e q << v1, allora q << v2 Diremo che q è calcolabile dalla vista v (q << v) se il risultato di q può essere trovato usando v.

• Se P(q) = A " B e P(v) = C, q << v sse A " B # C

Il pattern P(q) di un'interrogazione q = A!

$

B è l'insieme A " B

4 Le interrogazioni del carico di lavoro sono nella forma: q = A!SUM(m) AS m (per brevità q = A!)

oppure q = A!$B con A e B insiemi disgiunti di attributi e restrizioni AND di predicati (Att = c).

Viste materializzate, A. Albano IPOTESI SEMPLIFICATIVE

• le interrogazioni del carico di lavoro sono nella forma: q = A! oppure q = A!$B con A e

B insiemi disgiunti di attributi e restrizioni AND di predicati (Att = c).

5 • I dati sono statici con con n dimensioni, prive di attributi, e una misura m

• Il carico di lavoro sono le interrogazioni qi che definiscono i cuboidi diversi dalla radice F. • Le viste candidate sono i possibili cuboidi del cubo esteso (reticolo dei cuboidi = reticolo

delle possibili viste), diversi dalla radice F, definiti con espressioni tipo: A!SUM(m) AS m (F).

Gli attributi di raggruppamento del cuboide v si denotano con g(v)

• Il costo di esecuzione di q usando la vista v è |v|, il numero di record di v. Diremo che q è calcolabile dalla vista v (q << v) se il risultato di q può essere trovato usando v.

Date due viste v1 e v2 e un'interrogazione q, se v1 < v2 e q << v1, allora q << v2

Viste materializzate, A. Albano IL RETICOLO DEL DW 6 SELECT B, C SUM(M) AS M FROM R GROUP BY B, C; SELECT C SUM(M) AS M FROM R GROUP BY C; SELECT SUM(M) AS M FROM R; A B C M 0 1 1 50 1 1 1 100 2 3 1 60 4 5 1 70 6 5 2 90 A B M 0 1 50 1 1 100 2 3 60 4 5 70 6 5 90 A C M 0 1 50 1 1 100 2 1 60 4 1 70 6 2 90 B C M 1 1 150 3 1 60 5 1 70 5 2 90 M 370 A M 0 50 1 100 2 60 4 70 6 90 B M 1 150 3 60 5 160 C M 1 180 2 90

(2)

DAL RETICOLO DEI CUBOIDI AL RETICOLO DELLE VISTE

pdn 6M

pd 0.8M pn 6M dn 6M

p 0.2M d 0.1M n 0.01M

none 1 Come stimare la dimensione di una vista?

(ProdottoId, DataId, NegozioId)

(ProdottoId, DataId) (ProdottoId, NegozioId) (DataId, NegozioId)

(ProdottoId) (DataId) (NegozioId)

( )

STIMA DIMENSIONE DI UNA VISTA

vista v = A!F (R)

Stima di |v| con la formula di Cardenas (uniforme distribuzione dei dati): |v| = n – n(1 – 1/n) r

dove n è il numero di possibili valori di A e r = |R|.

8 Esempio. Sia R(B,C,D), con Nrec(R), Nkey(B) eNkey(C).

La stima di una vista v raggruppando R su (B, C) si ottiene ponendo n = Nkey(B) * Nkey(C)

r = Nrec(R)

PERCHE' MATERIALIZZARE LE VISTE

Query: totale delle vendite raggruppate per ProdottoId

Caso 3: vista materializzata (p) = 0.2M Caso 2: vista materializzata (pd) = 0.8M Caso 1: dati (pdn) = 6M

pdn 6M

pd 0.8M pn 6M dn 6M

p 0.2M d 0.1M n 0.01M

none 1

PERCHE' NON MATERIALIZZARE TUTTE LE VISTE?

Completa materializzazione: ~19M record Meglio parziale:

- includere: pdm, il DW - escludere: pn, dn

totale: ~ 7M, a pari prestazioni pdn 6M

pd 0.8M pn 6M dn 6M

p 0.2M d 0.1M n 0.01M

none 1

10

SCELTA DELLE VISTE DA MATERIALIZZARE

Sia C(qi, M) il costo di esecuzione dell'interrogazione qi usando le viste materializzate M.

L'obiettivo è di selezionare il sottoinsieme M delle viste candidate V che minimizzi il costo complessivo di esecuzione delle interrogazioni Q: %(V, M) =

&

i = 1.. |Q|C(qi, M)

rispettando un vincolo che verrà specificato più avanti.

Il problema di ottimizzazione è NP-completo. Pertanto si cerca una soluzione approssimata con un algoritmo di tipo greedy che procede selezionando una dopo l'altra la vista che produce il massimo beneficio, finché le viste selezionate non superano un vincolo prefissato.

11 Viste materializzate, A. Albano BENEFICIO DI UNA VISTA

1. Per ogni vista w discendente di v (w ' v):

a) Sia u la vista di costo minimo in M tale che w ' u b) Se C(v) < C(u), allora Bw = C(u) – C(v), altrimenti Bw = 0.

2. Si pone B(v, M) = & w ' v Bw

Informalmente, il beneficio di una vista è la riduzione del costo di esecuzione del carico di lavoro che produce.

Dato un insieme M di viste materializzate, per ogni vista v del reticolo, il beneficio B(v, M) di v rispetto ad M è definito da:

12 n 100 ( ) 1 pn 1000 pdn 1000 dn 700 p 200 d 150 pd 500

(3)

Viste materializzate, A. Albano ALGORITMO BASE

Vincolo: numero k di viste da materializzare fra le V candidate

13

Algoritmo HRU(k)

1. M = {Top};

2. A = V – M;

3. for i = 1 to k do

3.1. v = la vista in A, tale che B(v, M) è massimo

3.2. M = M " {v}; 3.3. A = A – {v};

4. return M;

Viste materializzate, A. Albano ESEMPIO Prima scelta 0 500 ! 4 = 2000 999 850 ! 2 = 1700 900 ! 2 = 1800 800 ! 2 = 1600 300 ! 4 = 1200 Seconda scelta 0 300 ! 2 = 600 300 ! 2 = 600 900 + 400 = 1300 499 350 ! 2 = 700 Terza scelta 0 300 300 99 350 Soluzione M = {pdn, pd, n, d} n 100 ( ) 1 pn 1000 pdn 1000 dn 700 p 200 d 150 pd 500 14 ( ) d n p dn pd pn

1. Per ogni vista w discendente di v (w ' v):

a) Sia u la vista di costo minimo in M tale che w ' u b) Se C(v) < C(u), allora Bw = C(u) – C(v), altrimenti Bw = 0.

2. Si pone B(v, M) = & w ' v Bw

HRU NON TROVA LA MIGLIORE SOLUZIONE

A 200 B 100 C 99 D 100 20 NODI 20 NODI 20 NODI 20 NODI K = 2 Greedy M = {A, C, B} B(M) = 6241 15 D = C = B = Prima scelta D = 100 + 40*100 = 4100 C = 101 + 40*101 = 4141 B = 100+ 40*100 = 4100 Prima scelta D = B = Seconda scelta D = 100+20*100 = 2100 B = 100+20*100 = 2100 Seconda scelta Ottimo M = {A, B, D} B(M) = 200 + (200 - 100) * 80 = 8200 6241/8200 = 0,76

Viste materializzate, A. Albano PRESTAZIONI

• In generale l'algoritmo non trova la soluzione ottima, ma è stato dimostrato che esso fornisce buoni risultati e vale la seguente proprietà:

Per ogni reticolo, sia Bgreedy il beneficio di k viste scelte con l'algoritmo

greedy e Bopt il beneficio di un insieme ottimo di k viste, allora Bgreedy non

è inferiore a 0,63 * Bopt.

• Complessità di tempo O(kn2_{), dove k è il numero di viste selezionate e n il}

numero delle viste del reticolo.

16

Viste materializzate, A. Albano VARIANTE 1

• Algoritmo HRU ha complessità di tempo polinomiale nel numero delle viste n, ma esponenziale nel numero delle dimensioni d ! O(kn2_{) = O(k2}2d₎

Con n = 10, il reticolo ha 1024 nodi e HRU sceglie 120 viste in un’ora!

Nel 2002 è stato proposto un algoritmo Polynomial Greedy Algorithm (PGA) di complessità polinomiale nelle dimensioni.

La complessità esponenziale dipende da due scelte:

Ad ogni iterazione si calcola il beneficio di tutte le viste non materializzate A ogni iterazione si considerano tutti i discendenti di una vista

Viste materializzate, A. Albano PGA: ESEMPIO

Candidate di prima nomina = {pd}, {d}, {}

Prima scelta: {pd} m 100 ( ) 1 pm 1000 pdm 1000 dm 700 p 200 d 150 pd 500

fase di nomina: si scelgono le viste più promettenti, fra quelle non ancora

prese in considerazione, che si aggiungono all'insieme delle viste candidate, inizialmente vuoto. Le viste promettenti sono le più piccole di ogni famiglia.

fase di scelta: si sceglie la vista v fra quelle candidate

(4)

Viste materializzate, A. Albano PGA: ESEMPIO

Candidate di prima nomina = {pd}, {d}, {} Prima scelta: {pd} Candidate di seconda nomina = {dm}, {d}, {m}, {} Seconda scelta: {m} Candidate di terza nomina = {dm}, {pm}, {d}, {p}, {} Terza scelta: {dm}

La soluzione in questo caso è diversa da HRU, ma all’aumentare delle dimensioni di solito è la stessa.

m 100 ( ) 1 pm 1000 pdm 1000 dm 700 p 200 d 150 pd 500

19 Viste materializzate, A. Albano VARIANTE 2

Carico di lavoro con interrogazioni non equiprobabili

Invece di fissare il numero k di viste da materializzare, si impone il vincolo che l'insieme M non occupi più di un certo spazio S.

20

ALGORITMO CON VINCOLO DI SPAZIO BPUS

Algoritmo BPUS(S)

1. M = {Top}; 2. A = V – M; 3. while (S > 0) do

3.1. v = vista in A con max Bs; 3.2. if (S – S(v) > 0) then {S = S – S(v); M = M " {v}; A = A – {v} }; else S = 0; 4. return M;

Beneficio per unità di spazio Bs(v, M) = B(v, M)/S(v) =& _{w ' v}Bw /S(v)

ALGORITMO CON VINCOLO DI SPAZIO PBS (Pick By Size)

Algoritmo PBS(S) 1. M = {Top}; 2. A = V – M; 3. while (S > 0) do

3.1. v = la vista più piccola in A; 3.2. if (S – S(v) > 0) then {S = S – S(v); M = M " {v}; A = A – {v} }; else S = 0; 4. return M;

Si comporta come PBUS per reticoli Size Restricted: per ogni vista v con k figli e per ogni suo genitore z,

|z| ! (1+k) |v|, quando |z| " |Top|

Risultati sperimentali mostrano che il risultato trovato è buono anche se il reticolo non è Size Restricted.

22

Viste materializzate, A. Albano VARIANTE 3

Il carico di lavoro è un particolare insieme di interrogazioni Q.

1000 v1

{ProdottoId, NegozioId, DataId}

500 v3 {ProdottoId, DataId} 100 v6 {NegozioId} 1 v8 { } 200 v5 {ProdottoId} 1000 v2 {ProdottoId, NegozioId} 700 v4 {NegozioId, DataId} 150 v7 {DataId} q1 q2 q3 q4 q5 q6 23 Ogni q si associa alla minima vista v che ne consente il calcolo.

Viste materializzate, A. Albano VISTE CANDIDATE

V2 ?

1000 v1

{ProdottoId, NegozioId, DataId}

500 v3 {ProdottoId, DataId} 100 v6 {NegozioId} 1 v8 { } 200 v5 {ProdottoId} 1000 v2 {ProdottoId, NegozioId} 700 v4 {NegozioId, DataId} 150 v7 {DataId} q1 q2 q3 q4 q5 q6 NO 24 Sono le v con associata almeno una q ...

(5)

CRITERIO PER STABILIRE SE UNA VISTA E’ CANDIDATA

• Dato uno schema di DW e un carico di lavoro Q, una vista v è detta candidata se soddisfa una delle seguenti condizioni:

•( esiste un’interrogazione q ) Q tale che g(q) = g(v),

•( esiste una coppia di viste candidate vi e vj tali che g(v) = g(vi) * g(vj), con *

estremo superiore

ALGORITMO PER TROVARE LE VISTE CANDIDATE

• Algoritmo BPT(Q)

Candidate = insieme dei g(v) tali che g(v)=g(q), per ogni q ) Q; while (Candidate cambia) do

for (g(vi) ) Candidate with g(vi) ! Top) do

for (g(vj) ) Candidate with (g(vj) ! Top) and

(g(vi) + g(vj)) and (g(vj) * g(vj) , Candidate))

do

Candidate = Candidate " (g(vj) * g(vj));

return Candidate;

26

ALGORITMO DI SCELTA DELLE VISTE CON CARICO DI LAVORO

• Da Q si trova l’insieme delle possibile viste “naturali” • Si determina l’insieme delle viste candidate V

• Si trova l’insieme delle viste da materializzare con uno degli algoritmi visti in precedenza

DIMENSIONI CON ATTRIBUTI

d a c b 28 dabc dbc abc dab da db ab dac dc ac bc d a b c {} Ipotetico da a db bc d c b {} dc dbc Ridotto

Ipotetico: come se si partisse dai dati della giunzione di F con tutte le D. Si puo’ semplificare:

- come radice basta F

- se a –> b una vista su a ha gli stessi gruppi di una su ab.

DIMENSIONI CON GERARCHIE

d a c b da a db bc d c b {} dc dbc d a c b da a b d c {} dc db

MODIFICA DELLE VISTE CANDIDATE IN PRESENZA DI GERARCHIE

In una vista v si sostituisce un attributo più generale (Provincia) con uno più specifico (Città) se si ottiene una vista v' di "poco" più grande: -S(v') < S(v). E' stato mostrato sperimentalmente che, con - = 0.95, si ottiene una sensibile riduzione del numero delle viste. ProdottoId NegozioId Provincia Città ProdottoId, NegozioId NegozioId ProdottoId, Provincia ProdottoId, Città Q3 Q2 Q1 ProdottoId, NegozioId NegozioId ProdottoId, Città Q3 Q2 Q1

(6)

Viste materializzate, A. Albano CONCLUSIONI

• Occorre un buon algoritmo approssimato per trovare le viste da materializzare, a partire dal carico di lavoro e rispettando i vincoli • In presenza di gerarchie, occorre ridurre la cardinalità dell'insieme delle

viste candidate.

GLI INDICI SU VISTE MATERIALIZZATE

• Utilità degli indici: si consideri l'interrogazione q = $b sulla vista v con attributi

(a, b).

Su una vista con attributi (a, b) si possono definire 4 indici: Ia, Ib Iab o Iba Gli

indici definiti su tutti gli attributi di una vista (Iab o Iba ) sono detti completi.

In assenza di indici il costo di esecuzione di q dipende da |v|.

Se esiste l'indice Ib il costo di esecuzione si stima con quello di accesso ai dati:

CD = |v(a,b)| / Nkey(Ib) = |v(a,b)| / |v(b)|

32

SCELTA DEGLI INDICI SU VISTE MATERIALIZZATE

Due diverse strategie per risolvere il problema

Carico di lavoro Q Selezione viste materializzate M Selezione indici da memorizzare I Viste e indici M ! I Carico di lavoro Q Selezione viste materializzate M e indici I Viste e indici M ! I

33 Viste materializzate, A. Albano APPROCCIO CONSIDERATO Carico di lavoro Q Algoritmo di selezione Viste M e Indici I Vincoli e Obiettivi Modello dei costi Indici candidati IndiciC Viste candidate V 34

Viste materializzate, A. Albano REGOLE DI BUON SENSO

• Costruire un indice sugli attributi della vista usati nelle restrizioni e che sono molto selettivi.

• Costruire un indice sugli attributi della vista che sono chiave esterna della tabella sulla quale è definita la vista.