6.6 Ottimizzazione operazione di raggruppamento
6.6.3 Terzo Caso: aggregazione su attributi dimensionali
nali
La prossima proposizione considera il caso denominato foreign relation aggre- gate in [CS94] e eager count in [YL95], quando R non soddisfa né la proprietà del raggruppamento invariante (seconda condizione della Proposizione 1) né la proprietà del raggruppamento parziale (seconda condizione della Defini- zione 1), in quanto le funzioni di aggregazione utilizzano attributi non in R, come nella seguente interrogazione:
SELECT PS_Partkey, PS_Suppkey, SUM(PS_Supplycost) AS C FROM Lineitem, Partsupp
WHERE L_Partkey = PS_Partkey AND L_Suppkey = PS_Suppkey AND L_Returnflag = ‘R’ AND PS_Supplycost = 100 GROUP BY PS_Partkey, PS_Suppkey;
dove l’attributo di aggregazionePS_Supplycostnon è attributo della tabella dei
fattiLineitem, ma della tabella dimensionalePastsupp. La chiave primaria della
tabelle dimensionalePartsuppè formata dagli attributiPS_PartkeyePS_Suppkey.
Per effettuare l’anticipazione delGROUP BYsulla tabella dei fatti in questo
tipo di interrogazioni, l’idea consiste nel rivedere il calcolo delle funzioni di aggregazione, derivando i valori del risultato delle funzioni di aggregazione
dal numero di elementi delle partizioni generate dall’anticipazione del GROUP BY.
Proposizione 3 Se R non ha la proprietà del raggruppamento invariante perché ci sono funzioni di aggregazioni decomponibili in G ⊆ F che usano attributi di S (la condizione 2 della Proposizione 1 non è soddisfatta), allora
AγF(R ⊲⊳Cj S) ≡ πbA∪(F −G)∪X((A∪α(Cj)−α(S)γ(F −G)∪{COU N T (∗) AS GBCount}(R)) ⊲⊳CjS)
dove X è un insieme di espressioni tale che (si assume che una funzione di aggregazione f è rinominata con f AS Ide):
• ai × GBCount AS Idej ∈ X, se f(ai) ∈ G è SUM(ai) AS Idej;
• Idej ∈ X, se f(ai) ∈ G è MIN(ai) AS Idej, MAX (ai) AS Idej, AVG
(ai) AS Idej;
• GBCount AS Idej ∈ X, se f(ai) ∈ G è COUNT(ai) AS Idej.
Esempio
Si consideri lo schema a stella in Figura 6.6 e l’interrogazione
SELECT PS_Partkey, PS_Suppkey, SUM(PS_Supplycost) AS C FROM Lineitem, Partsupp
WHERE L_Partkey = PS_Partkey AND L_Suppkey = PS_Suppkey AND L_Returnflag = ‘R’ AND PS_Supplycost = 100 GROUP BY PS_Partkey, PS_Suppkey;
Si mostra in Figura 6.14 l’albero logico che produce un tradizionale ottimizzatore.
L’ottimizzatore può effettuare l’anticipazione del GROUP BY dato che l’interrogazione rientra nel caso dell’aggregazione relazione esterna, ot- tenendo l’albero logico mostrato in Figura 6.15. Il relativo piano di ac- cesso fisico con gli operatori fisici di SADAS è mostrato in Figura 6.16.
6.6 Ottimizzazione operazione di raggruppamento SADAS
PS_Partkey,PS_Suppkey
γ
SUM(PS_Supplycost) AS C⊲⊳
L_Partkey = PS_Partkey, L_Suppkey = PS_Suppkey
σ
L_Returnflag=‘R′σ
PS_Supplycost=100Lineitem Partsupp
Figura 6.14: Albero logico senza l’utilizzo dell’aggregazione su attributi dimensionali
π
bPS_Partkey, PS_Suppkey, PS_Supplycost × GBCount AS C⊲⊳
L_Partkey = PS_Partkey, L_Suppkey = PS_Suppkey
σ
PS_Supplycost=100Partsupp
L_Partkey,L_Suppkey
γ
COUNT(∗) AS GBCountσ
L_Returnflag=‘R′Lineitem
Figura 6.15: Albero logico con l’utilizzo dell’aggregazione su attributi
dimensionali
IndexGByJoinFromBM
({L_Partkey, L_Suppkey}, {PS_Partkey, PS_Suppkey, PS_Supplycost},
{PS_Partkey, PS_Suppkey, PS_Supplycost × GBCount AS C}, {COUNT(*) AS GBCount})
BMJoinIndex (JILineitem−Partsupp)
BMIndexFilter
(L_Returnflag = ‘R’) (PS_Supplycost = 100)BMIndexFilter
6.7
Esperimenti e analisi prestazioni
Gli autori confrontano le prestazioni del sistema SADAS con un commercia- le DBMS relazionale con memorizzazione per righe, che implementa indici a bitmap, indici di giunzione e alcune tecniche di ottimizzazione per l’esecu- zione delle interrogazioni a stella. La base di dati per l’esperimento è stata creata utilizzando le specifiche del benchmark TPC-H con fattore di scala 10 e con dati creati dal generatore fornito da TPC, che genera valori casua- li con distribuzione uniforme. Mentre l’insieme delle interrogazioni eseguite per la valutazione delle prestazioni risulta essere una versione semplificata dell’insieme delle interrogazioni proposte dal benchmark [TPC99].8
I risultati riportati in [ARG+06b] dimostrano che SADAS, rispetto al
DBMS relazionale per righe di riferimento, ha prestazioni nettamente supe- riori, dove le interrogazioni vengono eseguite con una velocità di media 40 volte superiore rispetto al DBMS relazionale per righe, oltre a occupare uno spazio di memorizzazione nettamente inferiore.
L’ottimizzazione delle interrogazioni tramite l’anticipazione delGROUP BY
mostrato nella Sezione 6.6 in generale risulta efficace nell’aumentare la ve- locità di esecuzione delle interrogazioni con raggruppamento e calcolo delle funzioni di aggregazione, anche se ci sono casi in cui questo tipo di ottimiz- zazione non consente di determinare la migliore soluzione, soprattutto nel caso del doppio raggruppamento descritto in Sezione 6.6.2. Comunque le dif- ferenze in questo caso non sono state molto significative e dato che la stima dei costi di alternativi piani di accesso non è molto precisa, è stato deciso di utilizzare sempre la tecnica di ottimizzazione con l’anticipazione del GROUP BY.
8
Per le caratteristiche sulla piattaforma hardware e software sui cui sono stati fatti gli esperimenti e su altri dettagli si faccia riferimento alla documentazione [ARG+06b].
6.8 Conclusioni SADAS
6.8
Conclusioni
In questo capitolo sono state descritte le caratteristiche del sistema SADAS, un DWMS basato sulla memorizzazione per colonne con piano di accesso ottimizzato per eseguire le interrogazioni a stella attraverso l’utilizzo di indici a liste invertite, indici multiattributo a liste invertite, colonne con le codifiche, bitmap e indici di giunzione, senza tecniche di ordinamento.
In particolare è stato presentato un approccio per generare piani di accesso ottimizzati per interrogazioni con raggruppamento e con calcolo di funzioni di aggregazioni, cercando di anticipare queste operazioni prima delle operazioni di giunzione per diminuire la dimensione degli elementi che partecipano alla giunzione, in quanto la giunzione viene considerata l’operazione più costosa per eseguire un’interrogazione.
Gli esperimenti degli autori confermano che l’approccio della memorizza- zione delle tabelle per colonne piuttosto che per righe, aumenta la velocità di esecuzione delle complesse interrogazioni di analisi di dati presenti in ambienti di supporto alle decisioni.
C-STORE
Si presentano le caratteristiche del modulo RS (Read optimized Store) de- dicato alla gestione di dati statici memorizzati con l’approccio per colonne [SAB+05, AMDM07, Fer05, AMF06, HBND06].1 C-Store è un progetto di
ricerca, di varie università, in fase di sviluppo e prevede altri moduli e fun- zionalità non ancora supportate. L’attuale implementazione utilizza Berke- leyDB di Sleepycat per la memorizzazione dei dati [Ora], acquisito da Oracle nel febbraio 2006, con largo uso della compressione.
7.1
Strutture di memorizzazione dei dati
C-Store non memorizza per colonne gli attributi delle tabelle di uno schema a stella, ma gli attributi di un insieme di proiezioni della tabella dei fatti, delle tabelle dimensionali o di giunzioni della tabella dei fatti con tabelle dimensionali. Le proiezioni sono particolari tipi di viste materializzate dello schema a stella. Ogni proiezione contiene generalmente più di un attributo della schema e uno stesso attributo può appartenere a più di una proiezione [SAB+05].
1
Il modulo WS per la modifica dei dati (Writable Store) non viene trattato e inoltre non risulta ancora implementato.
7.1 Strutture di memorizzazione dei dati C-STORE
La i-esima proiezione di una tabella T viene rappresentata con uno sche- ma di relazione con nome T i. Nella proiezione vengono inseriti gli attributi di interesse di T e di un insieme di tabelle {D} in associazione con T , preceduti in questo caso eventualmente dal nome di D per distinguere gli attributi.
Ad esempio un possibile insieme completo di proiezioni derivato dallo schema a stella proposto in Figura 7.1 è:
Orders O_Orderkey O_Custkey O_Orderdate Lineitem L_Orderkey * L_Partkey * L_Suppkey * L_Linenumber L_Quantity L_Extendedprice L_Returnflag L_Shipdate Partsupp PS_Partkey PS_Suppkey PS_Availqty PS_Supplycost
Figura 7.1: Schema relazionale di riferimento
Lineitem1(L_Orderkey, L_Partkey, L_Suppkey)
Lineitem2(L_Linenumber, L_Quantity, L_Extendedprice, O_Orderdate)
Lineitem3(L_Orderkey, L_Linenumber, L_Returnflag, L_Shipdate)
Partsupp1(L_Orderkey, PS_Partkey, PS_Suppkey, PS_Availqty)
Partsupp2(PS_Partkey, PS_Suppkey, PS_Supplycost)
Per poter eseguire le interrogazioni sullo schema a stella, ogni attributo di una tabella dello schema deve far parte di almeno una proiezione. La scelta di duplicare un attributo in proiezioni diverse produce una ridondanza dei dati, ma consente all’ottimizzatore delle interrogazioni di scegliere la proiezione più adatta tra quelle disponibili per produrre un piano di accesso migliore.
Gli elementi di ciascuna colonna di una proiezione sono identificati per posizione, che ne permette la corrispondenza logica. Risulta quindi immediato ricostruire la proiezione partendo dai singoli attributi memorizzati in colonne distinte.2
7.2
Strutture dati ausiliarie
C-Store fa largo uso dell’ordinamento dei dati e implementa vari tipi di indici in base all’ordinamento della colonna.
7.2.1
Ordinamento
Le proiezioni sono ordinate su alcuni attributi che definiscono la chiave di ordinamento (sort key), specificata nella proiezione dopo una barra verticale [SAB+05]. Ad esempio, considerando l’insieme delle proiezioni definite nella
precedente sezione otteniamo:
Lineitem1(L_Orderkey, L_Partkey, L_Suppkey | L_Orderkey)
Lineitem2(L_Linenumber, L_Quantity, L_Extendedprice, O_Orderdate | L_Quantity, O_Orderdate)
Lineitem3(L_Orderkey, L_Linenumber, L_Returnflag, L_Shipdate | L_Linenumber)
Partsupp1(L_Orderkey, PS_Partkey, PS_Suppkey, PS_Availqty | L_Orderkey, PS_Availqty)
2
Gli autori utilizzano il termine storage key per riferirsi alla posizione. Inoltre l’ar- chitettura di C-Store prevede un partizionamento orizzontale in segmenti e quindi ogni elemento è identificato dalla coppia <segmento, posizione nel segmento>. Per brevità questa possibilità non viene considerata.
7.2 Strutture dati ausiliarie C-STORE
Partsupp2(PS_Partkey, PS_Suppkey, PS_Supplycost | PS_Partkey, PS_Suppkey)
Orders1(O_Orderkey, O_Custkey | O_Custkey)
Orders2(O_Orderkey, O_Orderdate | O_Orderdate)
Ovviamente una colonna della proiezione è ordinata solo se coincide con il primo attributo della chiave di ordinamento. Se invece la colonna coincide con uno degli altri attributi della chiave di ordinamento, risulta essere ordinata a gruppi di valori (run).