Ottimizzazione delle interrogazioni nel modello relazionale

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• L’importanza dell’ottimizzazione delle interrogazioni in un DBMS di tipo relazionale.
• La distinzione tra ottimizzazione logica e ottimizzazione fisica.
• L’algoritmo secondo cui agisce l’ottimizzazione logica.

Prerequisiti: per comprendere pienamente il contenuto di questa nota, oltre le conoscenze minime che do per scontato che tu sappia già, ti consiglio di aver letto in precedenza queste altre note:

• Operatori derivati.

Buona lettura! ☝️🤓

---

Definizione: ottimizzazione delle interrogazioni

L’ottimizzazione delle interrogazioni è quell’insieme di tecniche che rendono l’implementazione delle interrogazioni il più veloce possibile. Si può svolgere su due tipi di risorse:

• Spazio: inteso come memoria, al giorno d’oggi non rappresenta più un problema nella maggior parte dei casi, data la mole di memoria a disposizione nei nostri dispositivi.
• Tempo: inteso come tempo di esecuzione delle istruzioni, su cui è importante concentrarsi per assicurare una risposta rapida da parte del DBMS.

In questa nota, in particolare, ci occuperemo dell’ottimizzazione delle interrogazioni nei DBMS di tipo relazionale.

1 - Perché serve l’ottimizzazione?

Un’interrogazione, solitamente, segue questo workflow:

1. Invio della richiesta: l’applicazione, salvata in memoria centrale (RAM), invia un’interrogazione al DBMS che gestisce la [base di dati](Basi di dati.md).
2. Gestione della memoria del DBMS: il DBMS controlla se il dato richiesto è già in memoria centrale o se deve essere recuperato da una periferica di archiviazione (es. SSD, HDD, CD, ecc.). La memoria centrale è molto veloce, lavora nell’ordine dei nanosecondi ($10^{-9}$ secondi).
3. Eventuale caricamento dalla periferica: se il dato voluto dal DBMS non è in RAM, bisogna leggere il dato dalla periferica di archiviazione caricando pagine (blocchi di memoria). L’accesso alle periferiche come dischi rigidi o SSD è un’operazione drasticamente più lenta, effettuata nell’ordine dei millisecondi ($10^{-3}$ secondi) per gli HDD e microsecondi ($10^{-6}$ secondi) per gli SSD.
4. Arrivo del dato nel buffer: il buffer manager del DBMS gestisce quali pagine tenere in RAM e quali eliminare quando la memoria è piena. Se il dato richiesto è ora in RAM, l’applicazione può leggerlo velocemente.
5. Uso del dato: una volta che il dato è disponibile in memoria centrale, l’app può elaborarlo molto rapidamente.

Tenendo conto che la complessità delle attività “algoritmiche” del DBMS in memoria principale è minima (in quanto il DBMS deve gestire solo cicli, confronti, copia e trasferimento di dati), ciò che davvero fa la differenza è il numero di trasferimento di pagine, ossia il numero di letture da disco: quest’operazione è un milione di volte più lenta rispetto all’acceso di un dato nella RAM.

2 - Ottimizzazione in due fasi

Tutti i DBMS realizzano l’ottimizzazione delle interrogazioni (espresse tramite l’uso dell’algebra relazionale) attraverso due fasi: l’ottimizzazione logica e l’ottimizzazione fisica.

2.1 - Ottimizzazione logica

Definizione: ottimizzazione logica

L’ottimizzazione logica consiste nel prendere in input l’albero sintattico dell’interrogazione scritta dall’utente e trasformarlo sfruttando le proprietà dell’algebra relazionale in un albero perfettamente equivalente ma ottimizzato. È indipendente dalle strutture di memorizzazione usate.

2.1.1 - L’euristica dell’ottimizzazione logica

Nell’ottimizzazione logica, l’ottimizzatore è guidato da un semplice principio euristico: se l’interrogazione da un punto di vista logico può arrivare a coinvolgere una massa di tupla notevole (pensiamo, al prodotto cartesiano, usato nelle operazioni di theta-join e suoi derivati, che coinvolge tutti i record delle due relazioni su cui si sta effettuando l’operazione), allora il suo obiettivo deve essere quello di ridurre il più drasticamente possibile il numero di tuple coinvolte dall’interrogazione.

Si è dimostrato nei fatti che quando l’ottimizzatore fisico deve lavorare sui dati, produce risultati migliori (dal punto di vista dell’efficienza temporale) se riceve in input un albero sintattico che ha ridotto il numero di tuple concettualmente coinvolte dall’interrogazione. L’influenza positiva dell’ottimizzazione logica si riscontra nelle grandi applicazioni gestionali dei sistemi informativi (la maggioranza delle applicazioni su basi di dati. In generale, però, l’euristica non è necessariamente sempre valida.

2.1.2 - L’importanza degli operatori di selezione e proiezione

Quasi tutte le operazioni principali dei sistemi informativi che usiamo quotidianamente sono mirate a lavorare su pochissimi dati, in particolare su una determinata porzione che ci interessa dell’intera base di dati su cui poggia il sistema a cui ci interfacciamo.

Ecco quindi che entra il gioco l’operatore della selezione: grazie ad esso, infatti, è possibile porre l’attenzione su un numero limitato di record, diminuendo quelli coinvolti nelle operazioni e aumentando l’efficienza dell’interrogazione.

Ricordiamo che la selezione gode della proprietà distributiva rispetto alla proiezione, all’unione, all’intersezione, alla differenza, al prodotto cartesiano e al theta join: ciò significa che, in ogni interrogazione in cui viene usato, possiamo spostare il momento in cui lo applichiamo a nostro piacimento e quindi, in questo caso, all’inizio dell’albero sintattico per ridurre fin da subito il numero di tuple coinvolte nelle operazioni.

Allo stesso modo, si può fare lo stesso identico discorso per quanto riguarda l’operatore della proiezione, che ci permette di ridurre il numero di attributi su cui lavorare.

2.1.3 - Algoritmo di ottimizzazione logica

Algoritmo di ottimizzazione logica

1. Usare la proprietà associativa della selezione multipla per decomporre selezioni singole in selezioni multiple.
2. Usare le proprietà distributive della selezione per trasferire le selezioni verso le foglie dell’albero sintattico.
3. Usare le proprietà distributive della proiezione per trasferire le proiezioni verso le foglie dell’albero sintattico.
4. Usare la proprietà associativa della selezione multipla per ricomporre le selezioni multiple in selezioni singole.
5. Ricondurre le combinazioni di selezioni e prodotti cartesiani a theta-join.
6. Usare la proprietà associativa della proiezione multipla per ricomporre le proiezioni singole in proiezioni multiple.
7. Scegliere la variante dell’albero sintattico di costo minimo tra quelle che si possono ottenere dall’applicazione delle proprietà associative delle operazioni.

Osservazione: spiegazione del passo 1 dell'algoritmo di ottimizzazione logica

Analizziamo il passo 1 dell’algoritmo di ottimizzazione logica:

1. Usare la proprietà associativa della selezione multipla per decomporre selezioni singole in selezioni multiple.

Ci serve compiere questo passo perché la proprietà distributiva della selezione rispetto al theta-join è valida solo se gli attributi su cui è definito il predicato della selezione sono contenuti nello schema della relazione su cui viene applicata. Per esempio, su una relazione

$$\text{STUDENTI}(\underline{\text{Matricola}},\text{Cognome},\text{Nome},\text{AnnoDiNascita})$$

si può applicare la selezione

$${\sigma }_{\text{AnnoDiNascita > 2004}}$$

ma non la selezione

$${\sigma }_{\text{CorsoDiStudi = "Matematica"}}$$

perché l’attributo $\text{CorsoDiStudi}$ non fa parte dello schema di $\text{STUDENTI}$.

Ciò implica che, a una selezione con un predicato definito su più relazioni, difficilmente può essere applicata la proprietà distributiva rispetto al theta-join. Tuttavia, se spezzo la selezione in selezioni multiple, è più facile che i singoli predicati soddisfino la condizione necessaria all’applicazione della proprietà distributiva.

Osservazione: spiegazione del passo 4 dell'algoritmo di ottimizzazione logica

Analizziamo il passo 4 dell’algoritmo di ottimizzazione logica:

4. Usare la proprietà associativa della selezione multipla per ricomporre le selezioni multiple in selezioni singole.

Questo passo ci risulta utile all’ottimizzazione perché, a forza di trasferire le selezioni verso le foglie dell’albero sintattico, esse si accumulano in cascata, quindi l’ottimizzatore ricompone insieme le selezioni multiple, applicando una sola selezione con un predicato formato da una congiunzione di confronti.

Osservazione: spiegazione del passo 5 dell'algoritmo di ottimizzazione logica

Analizziamo il passo 5 dell’algoritmo di ottimizzazione logica:

5. Ricondurre le combinazioni di selezioni e prodotti cartesiani a theta-join.

È Importante svolgere questa operazione perché tutti i DBMS hanno algoritmi ottimizzati per l’esecuzione delle operazioni di theta-join in modo molto più efficiente rispetto all’esecuzione separata di una selezione su un prodotto cartesiano.

Osservazione: spiegazione del passo 7 dell'algoritmo di ottimizzazione logica

Analizziamo il passo 7 dell’algoritmo di ottimizzazione logica:

7. Scegliere la variante dell’albero sintattico di costo minimo tra quelle che si possono ottenere dall’applicazione delle proprietà associative delle operazioni.

Il passo 7 consiste essenzialmente nella ricerca di parentesizzazioni alternative dell’albero sintattico per ridurre il costo causato dalle operazioni di theta-join (e suoi derivati come l’equi-join e il natural-join). Questo passo ha delle difficoltà computazionali non indifferenti. Per esempio, con una sequenza di $n$ theta-join, le $k$ configurazioni possibili crescono esponenzialmente:

$$k=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{2(n-1)}{n-1}\right)$$

Gli ottimizzatori, ovviamente, non esplorano tutte le possibili configurazioni (es. con $n=10$, si otterrebbero $4862$ possibili configurazioni, troppe da poter essere esplorate una per una), ma cercano una configurazione subottimale.

La scelta dell’ottimizzatore, quindi, è quella di anticipare il prima possibile i theta-join tra relazione con cardinalità bassa, anche perché il theta-join può lavorare su una massa di tuple enorme, ma solitamente, in uscita, produce un numero di tuple limitato (grazie alla selezione di cui è composto).

[!esercizio] Esercizio

Dato lo schema R1(AB), R2(CDE), R3(FGH), disegnare l’albero sintattico della seguente query e ottimizzarlo logicamente limitandosi agli aspetti non quantitativi.

$${\pi }_{A,D,H}({\sigma }_{B=C\wedge E=F\wedge A>20\wedge G=10}(R_1\times R_3\times R_2))$$

Questa domanda non ha una valutazione automatica. Puoi scrivere la risposta su un foglio e confrontarla in seguito con la risposta giusta.

[!esercizio] Esercizio dalla prova d’esame 17/12/24

Con riferimento alla base di dati “Titoli” e i seguenti dati quantitativi:

• CARD(SQUADRA) = 500
• CARD(CONQUISTA) = 1000
• MIN(AnnoConquista, CONQUISTA) = 1900
• MAX(AnnoConquista, CONQUISTA) = 2020

disegnare gli alberi sintattici prima e dopo l’ottimizzazione logica e calcolare il numero di tuple “mosse” prima e dopo l’ottimizzazione logica della seguente query:

$$\begin{array}{rl}& {\sigma }_{\text{AnnoConquista}>1960\wedge \text{Genere}=\text{"Femminile"}\wedge \text{NomeSquadra}=\text{"Torino F.C."}}(\\ & \text{SQUADRA}{\bowtie }_{\text{SQUADRA.NomeSquadra}=\text{CONQUISTA.NomeSquadra}\wedge \text{SQUADRA.Genere}=\text{CONQUISTA.Genere}}\text{CONQUISTA}\\ & )\end{array}$$

[!soluzione] Soluzione

Ottimizzazione dell’albero sintattico:

1. Dividiamo le selezioni singole in selezioni multiple

$$\begin{array}{rl}& {\sigma }_{\text{AnnoConquista}>1960}(\\ & {\sigma }_{\text{Genere}=\text{"Femminile"}}(\\ & {\sigma }_{\text{NomeSquadra}=\text{"Torino F.C."}}(\\ & \text{SQUADRA}{\bowtie }_{\text{SQUADRA.NomeSquadra}=\text{CONQUISTA.NomeSquadra}\wedge \text{SQUADRA.Genere}=\text{CONQUISTA.Genere}}\text{CONQUISTA}\\ & )\\ & )\\ & )\end{array}$$

2. Spostiamo le selezioni verso le foglie:

$$\begin{array}{rl}& {\sigma }_{\text{Genere}=\text{"Femminile"}}({\sigma }_{\text{NomeSquadra}=\text{"Torino F.C."}}(\text{SQUADRA}))\\ & {\bowtie }_{\text{SQUADRA.NomeSquadra}=\text{CONQUISTA.NomeSquadra}\wedge \text{SQUADRA.Genere}=\text{CONQUISTA.Genere}}\\ & {\sigma }_{\text{AnnoConquista}>1960}(\text{CONQUISTA})\end{array}$$

3. Spostiamo le proiezioni
4. Riaccorpiamo le selezioni singole in selezioni multiple:

$$\begin{array}{rl}& {\sigma }_{\text{Genere}=\text{"Femminile"}\wedge \text{NomeSquadra}=\text{"Torino F.C."}}(\text{SQUADRA})\\ & {\bowtie }_{\text{SQUADRA.NomeSquadra}=\text{CONQUISTA.NomeSquadra}\wedge \text{SQUADRA.Genere}=\text{CONQUISTA.Genere}}\\ & {\sigma }_{\text{AnnoConquista}>1960}(\text{CONQUISTA})\end{array}$$

5. Ricostituire i theta-join
6. Riaccorpare le proiezioni
7. Scegliere variante di costo minore

Ora calcoliamo il costo delle due query. Query originale:

$$\begin{array}{rl}{f}_s(q_{\text{orig}})=& f_s({\sigma }_{\text{AnnoConquista}>1960\wedge \text{Genere}=\text{"Femminile"}\wedge \text{NomeSquadra}=\text{"Torino F.C."}}(\\ & \text{SQUADRA}{\bowtie }_{\text{SQUADRA.NomeSquadra}=\text{CONQUISTA.NomeSquadra}\wedge \text{SQUADRA.Genere}=\text{CONQUISTA.Genere}}\text{CONQUISTA}\\ & ))\\ =& f_s(\text{SQUADRA}{\bowtie }_{\text{SQUADRA.NomeSquadra}=\text{CONQUISTA.NomeSquadra}\wedge \text{SQUADRA.Genere}=\text{CONQUISTA.Genere}}\text{CONQUISTA})\\ & +\max (\text{card(SQUADRA), card(CONQUISTA)})\\ =& (\text{card(SQUADRA)}\cdot \text{card(CONQUISTA)})\\ & +\text{max}(500,1000)\\ =& (500\cdot 1000)+1000\\ =& 500000+1000\\ =& 501000\end{array}$$

Query ottimizzata:

$$\begin{array}{rl}{f}_s(q_{\text{ott}})=& f_s({\sigma }_{\text{Genere}=\text{"Femminile"}\wedge \text{NomeSquadra}=\text{"Torino F.C."}}(\text{SQUADRA})\\ & {\bowtie }_{\text{SQUADRA.NomeSquadra}=\text{CONQUISTA.NomeSquadra}\wedge \text{SQUADRA.Genere}=\text{CONQUISTA.Genere}}\\ & {\sigma }_{\text{AnnoConquista}>1960}(\text{CONQUISTA}))\\ =& f_s({\sigma }_{\text{Genere}=\text{"Femminile"}\wedge \text{NomeSquadra}=\text{"Torino F.C."}}(\text{SQUADRA}))\\ & +(\text{card}({\sigma }_{\text{Genere}=\text{"Femminile"}\wedge \text{NomeSquadra}=\text{"Torino F.C."}}(\text{SQUADRA}))\cdot \text{card}({\sigma }_{\text{AnnoConquista}>1960}(\text{CONQUISTA}))))\\ & +f_s({\sigma }_{\text{AnnoConquista}>1960}(\text{CONQUISTA})))\\ =& \text{card(SQUADRA)}\\ & +(1\cdot 1000)\\ & +\frac{\max (\text{AnnoConquista, CONQUISTA})-1960}{\max (\text{AnnoConquista, CONQUISTA})-\min (\text{AnnoConquista, CONQUISTA})}\cdot \text{card(CONQUISTA)}\\ =& 500+1000+\frac{2020-1960}{2020-1900}\cdot 1000\\ =& 2000\end{array}$$

2.1.4 - Stima del costo della selezione e fattore di selettività

L’analisi quantitativa dell’interrogazione permette di predire ex ante la cardinalità della relazione del risultato senza eseguirla. In particolare, data una relazione $R$ possiamo provare a predire la cardinalità del risultato della selezione ${\sigma }_{\Theta }(R)$ attraverso un fattore di selettività $f_s$ che prende come argomento il predicato $\Theta$:

$$|{\sigma }_{\Theta }(R)|=f_s(\Theta )\cdot |R|$$

Il fattore di selettività $f_s$ è legato al solo predicato $\Theta$ ed è un valore decimale che varia tra $0$ e $1$ interpretabile come la probabilità che un record in $R$ soddisfi il predicato $\Theta$, ovvero la stima della percentuale di record che soddisfano il predicato di selezione.

I DBMS mantengono in memoria una serie di informazioni di tipo statistico su ogni relazione $R(A)$ con istanza $r$. In particolare calcolano e salvano in memoria:

• $\text{card}(R)$: la cardinalità $|R|$ della relazione $R$.
• $\text{size}(t)$: l’ampiezza dei record $t\in r$ in byte.
• $\text{val}(A_i,R)$: il numero di valori distinti che appaiono nell’attributo $A_i\in A$ all’interno della relazione $R$.
• $\min (A_i,R)$: il valore minimo dell’attributo $A_i\in A$ all’interno della relazione $R$.
• $\max (A_i,R)$: il valore massimo dell’attributo $A_i\in A$ all’interno della relazione $R$.

I DBMS hanno a disposizione un formulario molto avanzato per il calcolo del fattore di selettività, però noi per comodità forniremo una versione più grossolana, ma sufficiente ai nostri scopi. Considereremo quindi una distribuzione uniforme dei valori all’interno dei vari attributi. Ecco una tabella per calcolare approssimativamente il fattore di selettività secondo la struttura del predicato $\Theta$ che confronta i valori di ogni tupla in corrispondenza di un determinato attributo $A_i\in A$ rispetto a un valore $v$ (o una coppia ordinata $⟨v_1,v_2⟩$ con $v_1\le v_2$):

Predicato $\Theta$	Valore di $f_s(\Theta )$
$A_i=v$	$\frac{1}{\text{val}(A_i,R)}$
$A_i\le v$	$\frac{v-\min (A_i,R)}{\max (A_i,R)-\min (A_i,R)}$
$A_i\ge v$	$\frac{\max (A_i,R)}{\max (A_i,R)-\min (A_i,R)}$
$v_1\le A_i\le v_2$	$\frac{v_2-v_1}{\max (A_i,R)-\min (A_i,R)}$

La seguente tabella, invece, permette di stimare il fattore di selettività su uno o più predicati ${\Theta }_1,{\Theta }_2,\dots ,{\Theta }_n$ combinati con gli operatori logici:

Predicati	Valore di $f_s$
${\Theta }_1\wedge {\Theta }_2\wedge \dots \wedge {\Theta }_n$	$f_s({\Theta }_1)\cdot f_s({\Theta }_2)\cdot \dots \cdot f_s({\Theta }_n)$
${\Theta }_1\vee {\Theta }_2\vee \dots \vee {\Theta }_n$	$1-(1-f_s({\Theta }_1))\cdot (1-f_s({\Theta }_2))\cdot \dots \cdot (1-f_s({\Theta }_n))$
$\neg \Theta$	$1-f_s(\Theta )$

Esempio: stima del costo dell'equi-join

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e due attributi $A_i\in A$ e $B_j\in B$, stimiamo il costo dell’equi-join tra questi:

$$f_s(R{\bowtie }_{A_i=B_j}S)$$

Sappiamo già che, nel caso specifico in cui $A_i$ è una chiave primaria con vincolo di integrità referenziale su $B_j$, la cardinalità dell’operazione è:

$$|R{\bowtie }_{A_i=B_j}S|=|R|$$

Tralasciando però questo caso specifico, consideriamo che l’equi-join associa a ogni tupla $t$ in $R$ con valore $v$ (ossia $t[A_i]=v$) una o più tuple $u$ in $S$ con valore $v$ ($u[B_j]=v$). Secondo la tabella del calcolo del fattore di selettività, abbiamo la seguente stima:

$$f_s(u[B_j]=v)=\frac{1}{\text{val}(B_j)}\cdot |S|$$

Estendendo questo calcolo da ogni singola tupla $t$ a tutta la relazione $R$, otteniamo:

$$f_s(R{\bowtie }_{A_i=B_j}S)=\frac{1}{\text{val}(B_j)}\cdot |S|\cdot |R|$$

Viceversa, se consideriamo le associazioni di ogni tupla $u$ in $S$ con valore $v$ (ossia $u[B_j]=v$) a una o più tuple $t$ in $R$ con valore $v$ ($t[A_i]=v$), otteniamo la stima:

$$f_s(t[A_i]=v)=\frac{1}{\text{val}(A_i)}\cdot |R|$$

E, estendendo il calcolo da ogni singola tupla $u$ a tutta la relazione $S$, otteniamo:

$$f_s(R{\bowtie }_{A_i=B_j}S)=\frac{1}{\text{val}(A_i)}\cdot |R|\cdot |S|$$

Tra le due opzioni, nel risultato finale cambia solo il valore ottenuto dal fattore di selettività: quale dei due dobbiamo scegliere?

Se consideriamo che entrambe sono delle sovrastime, possiamo considerare il valore minimo tra i due. Quindi possiamo stabilire che la cardinalità del risultato di una equi-join si può stimare come:

$$|R{\bowtie }_{A_i=B_j}S|=\min \left\{\frac{1}{\text{val}(A_i)},\frac{1}{\text{val}(B_j)}\right\}\cdot |R|\cdot |S|$$

2.2 - Ottimizzazione fisica

Definizione: ottimizzazione fisica

L’ottimizzazione fisica consiste nel migliorare l’efficienza dell’interrogazione attraverso l’analisi delle strutture dati in cui è memorizzata la base di dati. Nell’ottimizzazione fisica si prende in input il risultato dell’ottimizzazione logica e si analizza ogni operatore all’interno dell’albero sintattico per vedere quali relazioni coinvolge e, di conseguenza, scegliere quale algoritmo applicare per rendere ottimale l’esecuzione di ogni operazione.

---

Approfondimento

Fonti:

• 🏫 Lezioni e slide del Prof. Pensa Ruggero Gaetano del corso di Basi di Dati (canale B), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2024-25:
  • 5. L’ottimizzazione del DBMS.
• 🏫 Appunti di Luca Barra del corso di Basi di Dati, Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2022-23 (caricati sul repository GitHub del Team Studentesco Informatica).