Rappresentazione ed ottimizzazione delle query

La rappresentazione ed ottimizzazione delle query è un compito fondamentale del DBMS. È svolto dal gestore delle interrogazioni e consiste nel trasformare una query SQL in un codice eseguibile che svolga le azioni richieste. Possiamo suddividere le operazioni in due componenti, la fase di parsing e la fase di ottimizzazione.

Dopo la compilazione della query SQL, essa può essere memorizzata per future esecuzioni (compile-and-store) oppure eseguita immediatamente senza essere salvata (compile-and-go).

Parsing

Il parser deve verificare dapprima la correttezza lessicale e sintattica della query SQL per poi successivamente controllare la correttezza semantica. Quest'ultima consiste anche nel verificare che gli oggetti (nomi di tabelle, nomi di colonne, ecc.ecc.) esistano effettivamente nella base di dati. La risoluzione dei simboli avviene utilizzando il dizionario (o catalogo) contenuto nel DBMS.

Ora, accertata la validità della query, questa può essere trasformata in una rappresentazione interna del database, solitamente una rappresentazione ad albero, così da poter utilizzare le regole dell'algebra relazionale. L'albero costruito ha le seguenti caratteristiche:

• Ogni foglia rappresenta o un nodo, o una tabella o un indice;
• Ogni nodo non foglia rappresenta un'operazione sui dati di basso livello, come scansione di tabelle, ordinamenti, accessi agli indici, ecc.

Il DBMS conserva alcune informazioni (profili delle relazioni) in apposite tabelle interne, che contengono alcune informazioni di servizio, per esempio:

• il numero di tuple di ciascuna tabella
• la dimensione di ciascun attributo di ogni tabella
• il numero di valori duplicati per ogni attributo
• il minimo e il massimo per ogni attributo

Questi dati vengono calcolati periodicamente o dopo alcune azioni. Questi dati sono utilizzati per ottimizzare le query, come descritto nella sezione successiva. Ogni DBMS commerciale possiede differenti profili e li utilizza/aggiorna con differenti modalità.

Operazioni

Vengono presentate qui brevemente alcune operazioni presenti nei nodi intermedi dell'albero generato dalla fase di parsing.

Scansione sequenziale

Detta sequential scan in inglese, esegue un accesso a tutte le tuple di una tabella (o meglio di una relazione, perché può essere il frutto di una elaborazione precedente) eseguendo contemporaneamente delle operazioni, per esempio:

• proiezione di una lista di attributi;
• selezione di un predicato;
• inserimenti, cancellazione e modifiche di tuple.

Ordinamento

Detta sort in inglese, ordina i valori per uno o più campi (clausola ORDER BY in SQL). L'ordinamento può avvenire in memoria centrale oppure in memoria secondaria, nel caso in cui i dati non possano essere trasferiti a causa della loro dimensione. In quest'ultimo caso i dati devono essere suddividi e ordinati a blocchi in memoria centrale e ricomposti successivamente in memoria secondaria.

Gli algoritmi di ordinamento utilizzati variano in base al DBMS scelto e al tipo di ordinamento (ad esempio, se sono già presenti indici o meno).

Accesso agli indici

Detto indexed access oppure direct access, quando l'operazione può leggere o scrivere su un record senza recuperare l'intero file dalla memoria secondaria (effettuando una scansione sequenziale per selezionare il record richiesto). Per fare ciò si utilizzano gli indici. Essi possono essere usati solo se abbiamo predicati puntuali (es: A = 5) oppure predicati a intervallo (es: 5<A<19), in tal caso il predicato è detto valutabile.

Più predicati possono essere valutabili, quindi si può avere il caso di predicati a congiunzione o predicati a disgiunzione. Nel primo caso si seleziona il predicato più restrittivo dei due, mentre per i disgiunzione il DBMS può scegliere se eseguirne uno solo, entrambi eliminando i duplicati o nessuno dei due.

Join

L'operazione di join è la più comune utilizzata nelle query, ma anche la più dispendiosa in termini di costo di esecuzione, in quanto può portare a dover eseguire un prodotto cartesiano tra due relazioni nel caso in cui i valori non siano chiave.

Esistono tre tecniche principali per eseguire le join:

• nested loop: la tecnica più semplice, viene eseguito un ciclo su tutti i valori della prima tabella e per ogni record si cerca il corrispondente attributo di join sull'altra tabella utilizzando un'altra scansione o gli indici se essi sono presenti;
• merge scan: se le tabelle sono già ordinate sugli attributi di join oppure presentano indici su essi, è possibile scorrere le tabelle in modo parallelo eseguendo uno dei classici algoritmi di merge;
• hash-based: si esegue una funzione di hash con bassa dimensione del digest (in modo da avere volutamente collisioni) sugli attributi coinvolti nel join su ciascuna tabella. Le tabelle sono ora divise in partizioni ed ora diventa molto più semplice eseguire nested loop oppure merge scan sulle piccole partizioni generate.

Ottimizzazione

L'ottimizzazione è eseguita dall'optimizer e si divide principalmente in tre fasi:

• inizialmente viene svolta un'ottimizzazione di tipo algebrico, eseguendo tutte le operazioni ovvie sempre convenienti;
• successivamente in base al modello dei costi scelto e dal DBMS, viene eseguita ottimizzazione dei metodi di accesso;
• infine il codice finale viene generato.

L'ottimizzazione di una query può diventare molto complessa nel caso di sistemi distribuiti.

Ottimizzazione cost-based

È una delle ultime ottimizzazioni prima della generazione del codice ed è un punto critico sulle prestazioni del codice generato: può avere grandi benefici, ma può richiedere troppo tempo computazionale per essere generata (soprattutto nel caso compile-and-go). Il problema consiste nell'effettuare alcune scelte scegliendo tra diverse alternative. Solitamente una soluzione ottima al problema non è sempre raggiungibile perché troppo onerosa, quindi si utilizza una funzione di costo e un albero delle decisioni in cui ogni percorso radice-foglia rappresenta un modo per eseguire l'operazione. L'algoritmo per trovare il miglior percorso è solitamente di tipo branch and bound.

Il costo è solitamente calcolato con la formula:

$C=C_{CPU}\cdot n_{CPU}+C_{I/O}\cdot n_{I/O}$

dove $C_{CPU}$ e $C_{I/O}$ sono parametri costanti.

Esempi di alternative che l'ottimizzatore deve scegliere sono:

• l'ordine in cui eseguire le azioni;
• quali metodi di accesso utilizzare;
• il tipo di metodo da utilizzare (es. il tipo di join);
• eventuale parallelelismo e pipelining;
• se eseguire o meno l'ordinamento preventivo, oppure al termine delle operazioni.

Bibliografia

• Paolo Atzeni, Basi di dati - Architetture e linee di evoluzione, McGraw-Hill, 2007, ISBN 978-88-386-6370-3.
• Ottimizzazione delle interrogazioni, Angelo Montanari, Università di Udine