QUADRANTE MAGICO DEI DW-DBMS, 2006, GARTNER …baioletti/didattica/bddm/albano/9.Tecnologia...

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

VisionariDi nicchia

ab

ilit

à e

se

cu

tiv

a

completezza di visione

Sfidanti

TERADATA

IBM

ORACLE

MICROSOFT

SYBASE IQ

MySQL

SAND

KOGNITIO

DATAllegro

NETEZZA

2


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…


INDICI PER DW

• Indici a BitMap

• Indici di giunzione

• Indici a stella

6


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 A si costruisce un indice INDICE={(Vi ,Infi)} 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


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;


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 AFROM RWHERE 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 NFROM RWHERE 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

FRID pk1 A1 ...

1 v1 a1 ...

2 v2 a2 ...

3 v3 a2 ...

D1D1 F

1 1

1 5

2 2

2 4

3 3

JoinIndex-F-D1


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

FRID 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

FRID 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 NFROM 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, AggregazioniFROM TabellaFatti, TabelleDimensioniWHERE PredicatiDiGiunzione AND PredicatiRestrizioniGROUP BY AttributiRaggruppamentoHAVING 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.

Si esegue una query a stella con GROUP BY.


STRUTTURA DEI PIANI FISICI

25

OperatoriFisiciDiGiunzione(PredicatiDiGiunzione)

GROUPBY(AttributiRaggruppamento, Aggregazioni)

FILTER(RestrizioneHaving)

PROJECT(AttributiRaggruppamento, Aggregazioni)

⎨⎧⎩

Calcolo dei RID dei recorddella tabella dei fatti

che partecipano alla giunzione a stella

TabellaFatti TabelleDimensioni

TableAccess(TabellaDeiFatti)

TabelleDimensioni

SottoPiano

RID dei record TabellaDeiFatti

AccessiERestrizioni(TabellaDeiFatti)

AccessiERestrizioni(TabelleDimensioni)

OperatoriFisiciDiGiunzione(PredicatiDiGiunzione)

GROUPBY(AttributiRaggruppamento, Aggregazioni)

FILTER(RestrizioneHaving)

PROJECT(AttributiRaggruppamento, Aggregazioni)

DWMSDBMS

SELECT AttributiRaggruppamento, AggregazioniFROM TabellaFatti, TabelleDimensioniWHERE PredicatiDiGiunzione AND PredicatiRestrizioniGROUP BY AttributiRaggruppamentoHAVING 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, B22FROM F, D1, D2WHERE 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.B22FROM F, D1, D2WHERE 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


IndexNestedLoop

(fk1 = pk1)

IndexFilter


TableAccess

(F)

Project

({M, A11, B22})

27

Se mancano?


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 !


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

NomeC1

C2

C3

CittàK1

K2

K3

Pk

Q1

Q2

Q3

Q4

QtyP1

P2

P3

P4

PriceCK1

CK2

CK3

CK3

Fk

ColonneClienti ColonneVendite

29

N1N2N3

NomeC1C2C3

CittàK1K2K3

PkQ1Q2Q3Q4

QtP1P2P3P4

PrezzoCK1CK2CK3CK3

Fk

Clienti Vendite


STRUTTURE DI MEMORIZZAZIONE

A.CLN

LT

NA

NA

TO

TO

LT

CE

CE

Index on A

TO

NA

LT

CE1

2

3

4

A.CLI

2

3

3

4

4

2

1

1

30


STRUTTURE DI MEMORIZZAZIONE: INDICI MULTI ATTRIBUTI

1

2

3

4

5 4 4

3 3

32

1 2

11

2

1

2

2

1

B C n

BC.GDOB.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


STRUTTURE DI MEMORIZZAZIONE: JOIN INDEX

N1

N2

N3

NomeC1

C2

C3

CittàK1

K2

K3

Pk

Q1

Q2

Q3

Q4

QtyP1

P2

P3

P4

PriceCK1

CK2

CK3

CK3

Fk

ColonneClienti ColonneVendite

RID1

RID2

RID3

RID3

VtoC

JoinIndex

32


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”


DW DI TEST

LineItemOrders 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.





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-giunzioniTableAccess

(TabellaFatti)TabelleDimensioni

OperatoreGiunzione

(PredicatoDiGiunzione)

GROUPBY

(AttributiRaggruppamento, Aggregazioni)

FILTER

(PredicatiAggregazioni)

PROJECT

(Attributi, Aggregazioni)

Finale

Raggruppamento

36


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 restriction, aggr. with 3 GBY col.





QUADRANTE MAGICO DEI DW-DBMS, 2006, GARTNER …baioletti/didattica/bddm/albano/9.Tecnologia...

Documents

Transcript of QUADRANTE MAGICO DEI DW-DBMS, 2006, GARTNER …baioletti/didattica/bddm/albano/9.Tecnologia...