Organizzazione fisica dei database

Organizzazione fisica dei file

Heap: inserisco i dati a caso. È il metodo utilizzato di default nel filesystem. Può andare bene per pochi dati o accessi sempre su tutti i dati.

Sequenziale: inserisco i dati in ordine, con un ordine scelto a priori. Con un ordinamento sequenziale il costo dell'accesso a un dato è di N*log₂(N).

L'ordinamento tipico di ordinamento nei database che memorizzano i dati in modo sequenziale è merge sort. MS si presta bene al calcolo in parallelo su più processori.

L'ordinamento può essere effettuato tramite hash o tramite albero, e può essere statico (le informazioni, una volta inserite, non cambiano) o dinamico.

Nell'hash si trasforma una hash in un indirizzo di pagina. Bisogna gestire le eccezioni (collisioni) e la possibilità che i dati aumentino o diminuiscano molto. L'hash è estremamente efficiente. L'hash si presta molto poco alla ricerca su intervallo.

La struttura ad albero permette sia un accesso diretto a un dato sia a un intervallo con un tempo di esecuzione molto soddisfacente. L'organizzazione ad albero B⁺ può essere applicato sia al dato sia a un indice.

Inoltre la struttura ad albero restituisce insiemi di dati già ordinati.

Gli indici devono essere usati con parsimonia e buon senso, perché la loro aggiunta selvaggia compromette i tempi delle operazioni di inserimento e la concorrenza nell'accesso ai dati.

La chiave primaria è corredata automaticamente di un indice, perché permette di verificare velocemente se esiste già una chiave uguale o meno.

Operazioni

Proiezione

π e π⁺ sono le due operazioni algebriche che rappresentano rispettivamente SELECT DISTINCT e SELECT.
π⁺ ha un'esecuzione banale: si eliminano i campi non interessanti e si scrive il risultato.
π invece esclude i duplicati, e funziona:

1. riscrive una copia della tabella con i soli campi che interessano
2. ordina per tutti gli attributi
3. elimina duplicati
4. scrive il risultato

L'operazione di π si indica con due operazioni (SORT + DISTINCT), a indicare che l'operazione di eliminazione dei duplicati agisce in due fasi diverse.

Restrizione

σ è l'operazione algebrica corrispondente alla clausola WHERE (HAVING).

L'operazione funziona in modi diversi se esiste un indice sugli attributi ricercati o se non esiste.

Se non esiste, occorre leggere tutta la tabella e scartare i record non corrispondenti.

Se  esiste, il costo è dato dalla somma del costo per l'accesso all'indice e per l'accesso al dato. Il motore decide quale alternativa è migliore; in generale l'indice conviene quando la restrizione è molto selettiva (estrae pochi record).

Aggregazione

L'aggregazione senza GROUP BY legge i record e applica la funzione di aggregazione.

Con GROUP BY bisogna prima raggruppare i dati e successivamente calcolare l'aggregazione.

In particolare, si ordinano i record sull'attributo di ordinamento e poi si calcolano le funzioni di aggregazione.

Anche in questo caso le operazioni sono SORT + GROUP BY.

Giunzione

Gli algoritmi possibili sono:

• Nested loop: leggo un record alla volta della prima relazione (i), leggo un record della seconda relazione (j) e restituisco il record se gli attributi sono uguali. Il tempo di esecuzione è O(n²). è comodo se la seconda relazione è molto piccola e la prima grande.
• Nested loop a pagine
• Indexed nested loop: usa un indice per fare il confronto (necessita di un indice sul campo di join)
• Merge join: quando entrambe le tabelle sono ordinate sull'attributo di join, l'algoritmo confronta solo i record finché l'attributo non cambia in entrambe le tabelle

Operatori

Lettura dei dati

• TableScan(R): scansione su una tabella
• IndexScan(R, Idx): scansione sull'indice di una tabella
• SortScan(R, {A₁, A₂, ... A_i}): scansione e ordinamento per attributo/i

Proiezione

• Project(R, {A₁, A₂, ... A_i}): proiezione senza eliminazione dei duplicati
• Distinct(R, {A₁, A₂, ... A_i}): proiezione con eliminazione dei duplicati

Restrizione

• Filter(O, ψ)
• IndexFilter(R, Idx, ψ)

Ordinamento

• Sort(R, {A₁, A₂, ... A_i})

Raggruppamento

• GroupBy(O, {A₁, A₂, ... A_i}, {f₁, f₂, ... f_i}): f indica una funzione di aggregazione contenuta in SELECT e HAVING. L'operatore GroupBy è sempre preceduto da un Sort

Giunzione

• NestedLoop(O_E, O_I, ψ_J)
• PageNestedLoop(O_E, O_I, ψ_J)
• IndexNestedLoop(O_E, O_I, ψ_J): O_E rappresenta il risultato di un'operazione di IndexFilter
• MergeJoin(O_E, O_I, ψ_J): O_E e O_I rappresentano due relazioni già ordinate per gli attributi di join