Tecnologia dei data warehouse

(1)

Sistemi per DW, A. Albano

QUADRANTE MAGICO DEI DW-DBMS, 2006, GARTNER

Dimensioni di analisi:

L’abilità esecutiva è una misura della qualità del prodotto e del fornitore, del volume del fatturato, dei servizi ai clienti.

La completezza di visione è una misura della capacità dei fornitori nel rispondere ai bisogni attuali e futuri dei clienti.

1 Sistemi per DW, A. Albano QUADRANTE MAGICO Leaders Visionari Di nicchia abilità esecutiva completezza di visione Sfidanti TERADATA IBM ORACLE MICROSOFT SYBASE IQ MySQL SAND KOGNITIO DATAllegro NETEZZA 2

Sistemi per DW, A. Albano ARCHITETTURA DEI DBMS 3 DBMS MACCHINA FISICA MACCHINA LOGICA GESTORE COMANDI DDL GESTORE PIANI DI ACCESSO OTTIMIZZATORE GESTORE INTERROGAZIONI GESTORE METODI DI ACCESSO GESTORE STRUTTURE DI MEMORIZZAZIONE GESTORE BUFFER GESTORE MEMORIA PERMANENTE GESTORE TRANSAZIONI GESTORE CONCORRENZA DATI, INDICI CATALOGO, GIORNALE MEMORIA PERMANENTE COMANDI SQL GESTORE CATALOGO

DWMS: ASPETTI DA CONSIDERARE

• Tecniche di memorizzazione dei dati • Strutture di accesso (indici) • Nuovi operatori fisici per piani di accesso • Tecniche di ottimizzazione per giunzioni a stella • Estensioni dell’SQL

• Riscrittura delle interrogazioni in presenza di viste materializzate Con riferimento ai sistemi ROLAP:

4

MEMORIZZAZIONE DEI DATI Ipotesi

• dati statici,

• valori degli attributi dei record delle relazioni di dimensione uguale, • pagine dei dati di grandi dimensioni.

5

•

Memorizzazione delle tabelle per righe (partizionamento orizzontale),

soluzione standard nei prodotti che estendono i DBMS relazionali, una soluzione diversa più avanti…

Sistemi per DW, A. Albano INDICI PER DW

• Indici a BitMap • Indici di giunzione • Indici a stella

(2)

ORGANIZZAZIONE A LISTE INVERTITE: ESEMPIO

Indice IM su Matricola Indice IA su AnnoNascita 7 Tabella

Indici

RID Matricola Città AnnoNascita 1 100 MI 1972 2 101 PI 1970 3 102 PI 1971 4 104 FI 1970 5 106 MI 1970 6 107 PI 1972 Matricola RID 100 1 101 2 102 3 104 4 106 5 107 6 AnnoNascita RID 1970 2 1970 4 1970 5 1971 3 1972 1 1972 6

AnnoNascita n Lista RID 1970 3 2 4 5 1971 1 3 1972 2 1 6

Indice a liste invertite

INDICI A LISTE INVERTITE

8 E’ la soluzione usata in tutti i DBMS relazionali

• utile per attributi con Nkey alto (molto selettivi) per trovare pochi record • soluzione standard anche nei DWMS per le chiavi primarie

INDICI CON LISTE A VETTORI BINARI (BITMAP INDEX)

9 Per un attributo non chiave Asi costruisce un indice INDICE={(Vi

,Inf

i)} con le

seguenti proprietà:

•

Vi è uno dei possibili valori dell’attributo e Vi < Vi+1.

•

Infi = (vettore di N bit), con N il numero di record della tabella. L'i-esimo

bit = 1 se l'i-esimo record della tabella ha l'attributo A con valore Vi Ipotesi: Record di lunghezza uguale e costante.

E’ la soluzione usata in tutti i DBMS per DW quando un attributo è poco

selettivo (piccolo Nkey) e renderebbe inutile un indice tradizionale.

INDICI A BITMAP: ESEMPIO

10 Indice IC su Città Indice IA su AnnoNascita Tabella

Indici a bitmap

RID Matricola Città AnnoNascita 1 100 MI 1972 2 101 PI 1970 3 102 PI 1971 4 104 FI 1970 5 106 MI 1970 6 107 PI 1972 FI 0 0 0 1 0 0 Città Bitmap MI 1 0 0 0 1 0 PI 0 1 1 0 0 1 1970 0 1 0 1 1 0 AnnoNascita Bitmap 1971 0 0 1 0 0 0 1972 1 0 0 0 0 1 Indici a liste invertite

AnnoNascita n Lista RID 1970 3 2 4 5 1971 1 3 1972 2 1 6 FI 1 4 MI 2 1 5 PI 3 2 3 6 Città n Lista RID

VANTAGGI DEGLI INDICI CON BITMAP

• Riduzione dello spazio richiesto per l’indice per attributi poco selettivi • Utilizzo degli operatori efficienti su bit per operazioni logiche su bitmap • Ottimi per interrogazioni che non comportano l'accesso ai dati • Si prestano a compressione

Q: Quanti sono gli studenti pisani del 1972?

11 FI 0 0 0 1 0 0 Città Bitmap MI 1 0 0 0 1 0 PI 0 1 1 0 0 1 1970 0 1 0 1 1 0 AnnoNascita Bitmap 1971 0 0 1 0 0 0 1972 1 0 0 0 0 1

MEMORIA INDICI TRADIZIONALI-INDICI BITMAP

INDICI BITMAP

Nleaf = (Nkey * Lk + Nkey * Nrec / 8 )/ Dpag ! Nkey * Nrec / (Dpag * 8)

Nleaf

Nkey B+ BM

Nkey = 8 * LRID Ipotesi: nodi pieni

INDICI TRADIZIONALI

Nleaf = (Nkey * Lk + Nrec * LRID ) / Dpag ! Nrec * LRID / Dpag

12 Oracle: con la compressione gli indici a bitmap convengono se Nkey < Nrec/2

(3)

ESEMPI DI OPERATORI FISICI SU INDICI CON RID O CON BITMAP

• BMAnd(OE, OI), BMOr(OE, OI), BMMinus(OE, OI), BMNot(O) per fare operazioni logiche sui bitmap OE, OI

• BMCount(O, Ide) per contare gli 1 di un bitmap (ritorna {Ide = N di 1}) • BMToRid(O), BMFromRid(O) per passare da insiemi di RID a bitmap e viceversa • BMMerge(O) per fare l’OR dell’insieme di bitmap in O

• IndexFilter (R, Idx,!): restrizione dei record di R con indice:

• RidIndexFilter(R, Idx, !): per recuperare i RID dei record di R in Idx • TableAccess(O, R), per recuperare i record di R usando i RID in O;

13 Sistemi per DW, A. Albano

ESEMPI DI OPERATORI FISICI (cont)

• RidIndexScan(R, Idx) per trovare i RID dei record di R in Idx • RidIndexFilter(R, Idx, !) per trovare i RID dei record di R in Idx che

soddisfano !

• BMIndexFilter(R, Idx, !) per trovare l’OR dei bitmap dei record di R in Idx che soddisfano !

• BMKeyIteration(OE, OI) dove OI è un indice a bitmap su A e OE un insieme ordinato di valori di A. L’operatore ritorna un insieme di bitmap, uno per ogni valore di A in OE

14

ESEMPI DI PIANI DI ACCESSO

SELECT A FROM R

WHERE B = 10 AND C = 5;

Sia R(A, B, C) una relazione,

BMIndexFilter (R, IdxB, B = 10) BMIndexFilter (R, IdxC, C = 5) BMAnd BMToRid TableAccess (R) Project ({A}) 15 con indici su B e C.

con indici a bitmap su B e C.

IndexFilter (R, IdxB, B=10) Project ({A}) Filter (C=5)

ESEMPI DI PIANI DI ACCESSO

SELECT COUNT(*) AS N FROM R

WHERE B = 10 AND C = 5;

Sia R(A, B, C) una relazione,

16 con indici su B e C.

con indici a bitmap su B e C.

IndexFilter (R, IdxB, B=10) Project ({COUNT(*) AS N}) Filter (C=5) GroupBy ({ }, {COUNT(*)}) BMIndexFilter (R, IdxB, B = 10) BMIndexFilter (R, IdxC, C = 5) BMAnd BMCount (N)

ESEMPIO SCHEMA A STELLA

17 RID fk1 fk2 M 1 v1 z1 150 2 v2 z1 300 3 v3 z2 400 4 v2 z2 200 5 v1 z2 90 F RID pk1 A1 ... 1 v1 a1 ... 2 v2 a2 ... 3 v3 a2 ... D1 RID pk2 B1 ... 1 z1 b1 ... 2 z2 b2 ... 3 z3 b2 ... D2

JOIN INDEX FRA DUE TABELLE

Nell'indice di giunzione ci sono tutte le coppie di RID di record delle due tabelle che soddisfano la condizione di giunzione: F.fk1 = D1.pk1.

18 RID fk1 fk2 M 1 v1 z1 150 2 v2 z1 300 3 v3 z2 400 4 v2 z2 200 5 v1 z2 90 F RID pk1 A1 ... 1 v1 a1 ... 2 v2 a2 ... 3 v3 a2 ... D1 D1 F 1 1 1 5 2 2 2 4 3 3 JoinIndex-F-D1

(4)

Sistemi per DW, A. Albano STAR JOIN INDEX

L'indice di giunzione a stella è utile per il calcolo delle giunzioni su schemi a stella (star join), ma essendo definito su una lista ordinata di attributi, esso è utile quando si usano tutti gli attributi, o quelli iniziali. Per questa ragione si preferisce usare solo indici di giunzione binari.

19 L'idea dell'indice di giunzione si estende in modo ovvio a giunzioni fra N tabelle.

D1 D2 F 1 1 1 1 2 5 2 1 2 2 2 4 3 2 3 JoinIndex-F-D1-D2

VARIANTI DEL JOIN INDEX V1: Bitmapped Join Index

20 D1 F 1 1 1 5 2 2 2 4 3 3 JoinIndex-F-D1 D1 Bitmap per F 1 10001... 2 01010... 3 00100... BMJoinIndex-F-D1 RID fk1 fk2 M 1 v1 z1 150 2 v2 z1 300 3 v3 z2 400 4 v2 z2 200 5 v1 z2 90 F RID pk1 A1 ... 1 v1 a1 ... 2 v2 a2 ... 3 v3 a2 ... D1

VARIANTI DEL JOIN INDEX (cont) V2: Foreign Column Join Index

Bitmapped FC join index (detti anche Bitmap Join Index!): Gli elementi <p,q>

dell'indice si rappresentano nella forma <p, bitmap dei record in giunzione> 21 RID fk1 fk2 M 1 v1 z1 150 2 v2 z1 300 3 v3 z2 400 4 v2 z2 200 5 v1 z2 90 F RID pk1 A1 ... 1 v1 a1 ... 2 v2 a2 ... 3 v3 a2 ... D1 D1.A1 RID-F a1 1 a1 5 a2 2 a2 4 a3 3 FCJI-D1-F

ESEMPI DI OPERATORI FISICI SU INDICI DI GIUNZIONE

• BMFCJIndexFilter(F, Idx, !), per trovare l'OR dei bitmap dei record di una relazione F usando il Foreign Column Join Index Idx con una ! sull'attributo A;

• BMJIndexFilter(F, JIdx, !) per trovare il bitmap dei record di una relazione F, usando il Bitmapped Join Index JIdx con una ! sull'attributo Di;

22 • StarIndexScan(Idx), per trovare i record di una giunzione a stella usando uno Star

Index;

• StarIndexFilter(Idx, !), per trovare i record di una giunzione a stella usando uno Star Index e una condizione sui RID di un prefisso delle dimensioni;

ESEMPIO DI USO DI BITMAPPED FC JOIN INDEX SELECT COUNT(*) AS N

FROM F, D1, D2

WHERE F.fk1= D1.pk1 AND F.fk2 = D2.pk2 AND D1.A1=10 AND D2.B1 = 20;

BMFCJIndexFilter (F, IdxD1F, D1.A1 = 10) BMFCJIndexFilter (F, IdxD2F, D2.B1 = 20) BMAnd 23 BMCount(N) Project ({COUNT(*) AS N}) GroupBy ({ }, {COUNT(*)}) IndexFilter (F, IdxFk1, fk1 = pk1) IndexNestedLoop (D1.pk1 = F.fk1) IndexFilter (D1, IdxA1, A1 = 10) IndexNestedLoop (F.fk2 = D2.pk2) IndexFilter (D2, IdxPk2, pk2 = fk2) Filter (D2.B2 = 20) Indici tradizionali Indici BMFC JoinIndex

COME RICONOSCERE UN DWMS?

24

SELECT AttributiRaggruppamento, Aggregazioni FROM TabellaFatti, TabelleDimensioni WHERE PredicatiDiGiunzione AND PredicatiRestrizioni GROUP BY AttributiRaggruppamento

HAVING RestrizioniHaving;

Si creare un DW a stella con molti record in F (qualche milione).

Si analizzano i Piani Fisici per vedere

a) come si trovano i record della tabella dei fatti in giunzione con i record delle dimensioni, b) quando si calcola il raggruppamento.

(5)

STRUTTURA DEI PIANI FISICI

25 OperatoriFisiciDiGiunzione (PredicatiDiGiunzione) GROUPBY (AttributiRaggruppamento, Aggregazioni) FILTER (RestrizioneHaving) PROJECT (AttributiRaggruppamento, Aggregazioni)

Calcolo dei RID dei record della tabella dei fatti che partecipano alla giunzione a stella

TabellaFatti TabelleDimensioni TableAccess (TabellaDeiFatti) TabelleDimensioni Sotto Piano RID dei record TabellaDeiFatti AccessiERestrizioni (TabellaDeiFatti) AccessiERestrizioni (TabelleDimensioni) OperatoriFisiciDiGiunzione (PredicatiDiGiunzione) GROUPBY (AttributiRaggruppamento, Aggregazioni) FILTER (RestrizioneHaving) PROJECT (AttributiRaggruppamento, Aggregazioni) DWMS DBMS

SELECT AttributiRaggruppamento, Aggregazioni FROM TabellaFatti, TabelleDimensioni WHERE PredicatiDiGiunzione AND PredicatiRestrizioni GROUP BY AttributiRaggruppamento

HAVING RestrizioniHaving;

DBMS: ESEMPIO DI PIANO DI ACCESSO

Ipotesi indici a liste invertite sulle chiavi esterne in F, sulle chiavi primarie delle tabelle delle dimensioni e sugli attributi D1.A1 e D2.B2 SELECT M, A11, B22 FROM F, D1, D2 WHERE fk1 = pk1 AND fk2 = pk2 AND A1 = 10 AND B2 = 20; IndexFilter (D1, IdxA1, A1 = 10) IndexFilter (F, IdxFk1, fk1 = pk1) IndexNestedLoop (fk1 = pk1) IndexNestedLoop (fk2 = pk2) Project ({M, A11, B22}) IndexFilter (D2, IdxPk2, pk2 = fk2) Filter (B2 = 20) 26

DWMS: ESEMPIO DI PIANI DI

Ipotesi indici BM Foreign Column Join Index fra le tabelle delle dimensioni ed F sugli attributi D1.A1 e D2.B2, indici a liste invertite sulle chiavi primarie di D1 e D2.

SELECT F.M, D1.A11, D2.B22 FROM F, D1, D2

WHERE F.fk1 = D1.pk1 AND F.fk2 = D2.pk2 AND D1.A1 = 10 AND D2.B2 = 20;

BMFCJIndexFilter (F, IdxD1F, A1 = 10) BMFCJIndexFilter (F, IdxD2F, B2 = 20) BMAnd BMToRid IndexNestedLoop (fk2 = pk2) IndexFilter (D2, IdxPk2, pk2 = fk2) IndexNestedLoop (fk1 = pk1) IndexFilter (D1, IdxPk1, pk1 = fk1) TableAccess (F) Project ({M, A11, B22}) 27 Se mancano?

Sistemi per DW, A. Albano SADAS: UN DBMS PER DW

28 Università di Pisa

Università di Benevento

Advanced Systems, Casalnuovo di Napoli

Risultato di un progetto finanziato nel 2002 dal Ministero dell’Università e della Ricerca (MIUR)

Obiettivo: realizzare un DBMS per DW, con dati memorizzati per colonne,

per interrogazioni OLAP read-only.

I sistemi per BD non sono adatti per fare BI su grandi quantità di dati:

One Size Does Not Fit All !

Sistemi per DW, A. Albano APPROCCIO

Si cambia un’ipotesi fondamentale dei sistemi tradizionali

Si riconsiderano le soluzioni per le strutture di memorizzazione e l’ottimizzazione delle interrogazioni

N1 N2 N3 Nome C1 C2 C3 Città K1 K2 K3 Pk Q1 Q2 Q3 Q4 Qty P1 P2 P3 P4 Price CK1 CK2 CK3 CK3 Fk ColonneClienti ColonneVendite 29 N1 N2 N3 Nome C1 C2 C3 Città K1 K2 K3 Pk Q1 Q2 Q3 Q4 Qt P1 P2 P3 P4 Prezzo CK1 CK2 CK3 CK3 Fk Clienti Vendite

STRUTTURE DI MEMORIZZAZIONE A.CLN LT NA NA TO TO LT CE CE Index on A TO NA LT CE 1 2 3 4 A.CLI 2 3 3 4 4 2 1 1 30

(6)

STRUTTURE DI MEMORIZZAZIONE: INDICI MULTI ATTRIBUTI

1 2 3 4 5 4 4 3 3 3 2 1 2 1 1 2 1 2 2 1 B C n BC.GDO B.CLI 1 3 2 4 4 2 1 1 C.CLI 2 3 3 4 4 3 1 2 BC.GDI 2 4 3 5 5 3 1 2

31 Sistemi per DW, A. Albano

STRUTTURE DI MEMORIZZAZIONE: JOIN INDEX

N1 N2 N3 Nome C1 C2 C3 Città K1 K2 K3 Pk Q1 Q2 Q3 Q4 Qty P1 P2 P3 P4 Price CK1 CK2 CK3 CK3 Fk ColonneClienti ColonneVendite RID1 RID2 RID3 RID3 VtoC JoinIndex 32

Sistemi per DW, A. Albano VALIDITA’ DEL PROGETTO

33 M. Stonebraker e altri, nel lavoro One Size Fits All? (2007), dicevano:

“We define “dramatically outperform” to mean at least a factor of 10 advantage on the same (or comparable) hardware.

For example, a factor of 10 is the difference between response time of 1 minute and response time of 6 seconds”

Sistemi per DW, A. Albano DW DI TEST LineItem Orders PartSupp # of Records 15 000 000 59 986 052 8 000 000 Size 1683 MB 7473 MB 1156 MB 34

Calcolatore: Windows NT, 2800 MHz Pentium, 1 GB RAM

SADAS: PRESTAZIONI (sec)

SADAS è in media 42 volte più veloce 1 table, 2 restrictions

1 table, 2 restrictions 2-way join, 3 restrictions

1 table, 2 restrictions, aggr. with 2 GBY col. 2-way join, 3 restrictions, aggr. with 1 GBY col. 2-way join, 3 restriction, aggr. with 3 GBY col. 2-way join, 0 restrictions, aggr. with 2 GBY col. 2-way join, 1 restrictions, aggr. with 2 GBY col. 3-way join, 2 restrictions, aggr. with 1 GBY col. 3-way join, 3 restrictions, aggr. with 3 GBY col.

35 0 375 750 1,125 1,500 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10

Row store SADAS

10 sec invece di 7 minuti Sistemi per DW, A. Albano

STRUTTURA PIANI DI ACCESSO PER INTERROGAZIONI A STELLA

RID dei record delle F!D Accessi TabellaFatti & Ri-giunzioni TableAccess (TabellaFatti) TabelleDimensioni OperatoreGiunzione (PredicatoDiGiunzione) GROUPBY (AttributiRaggruppamento, Aggregazioni) FILTER (PredicatiAggregazioni) PROJECT (Attributi, Aggregazioni) Finale Raggruppamento 36

(7)

UTILITA’ DELL’ANTICIPAZIONE DEL GROUPBY

37 0 _{37.5 75.0 112.5 150.0} Q4 Q5 Q6 Q7 Q8 Q9 Q10 NO YES

1 table, 2 restrictions, aggr. with 2 GBY col. 2-way join, 3 restrictions, aggr. with 1 GBY col. 2-way join, 3 restriction, aggr. with 3 GBY col. 2-way join, 0 restrictions, aggr. with 2 GBY col. 2-way join, 1 restrictions, aggr. with 2 GBY col. 3-way join, 2 restrictions, aggr. with 1 GBY col. 3-way join, 3 restrictions, aggr. with 3 GBY col.