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*log2(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(n2). è 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, {A1, A2, ... Ai}): scansione e ordinamento per attributo/i

Proiezione

  • Project(R, {A1, A2, ... Ai}): proiezione senza eliminazione dei duplicati
  • Distinct(R, {A1, A2, ... Ai}): proiezione con eliminazione dei duplicati

Restrizione

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

Ordinamento

  • Sort(R, {A1, A2, ... Ai})

Raggruppamento

  • GroupBy(O, {A1, A2, ... Ai}, {f1, f2, ... fi}): f indica una funzione di aggregazione contenuta in SELECT e HAVING. L'operatore GroupBy è sempre preceduto da un Sort

Giunzione

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