Ottimizzazione delle query nei sistemi centralizzati

Una volta derivati ​​i percorsi di accesso alternativi per il calcolo di un'espressione di algebra relazionale, viene determinato il percorso di accesso ottimale. In questo capitolo esamineremo l'ottimizzazione delle query in un sistema centralizzato mentre nel prossimo capitolo studieremo l'ottimizzazione delle query in un sistema distribuito.

In un sistema centralizzato, l'elaborazione delle query viene eseguita con il seguente obiettivo:

  • Minimizzazione del tempo di risposta della query (tempo impiegato per produrre i risultati alla query dell'utente).

  • Massimizza la velocità effettiva del sistema (il numero di richieste elaborate in un determinato periodo di tempo).

  • Riduci la quantità di memoria e archiviazione necessaria per l'elaborazione.

  • Aumenta il parallelismo.

Analisi e traduzione delle query

Inizialmente, viene eseguita la scansione della query SQL. Quindi viene analizzato per cercare errori sintattici e correttezza dei tipi di dati. Se la query supera questo passaggio, la query viene scomposta in blocchi di query più piccoli. Ogni blocco viene quindi tradotto in un'espressione di algebra relazionale equivalente.

Passaggi per l'ottimizzazione delle query

L'ottimizzazione delle query prevede tre passaggi, ovvero la generazione dell'albero di query, la generazione del piano e la generazione del codice del piano di query.

Step 1 − Query Tree Generation

Un albero di query è una struttura di dati ad albero che rappresenta un'espressione di algebra relazionale. Le tabelle della query sono rappresentate come nodi foglia. Le operazioni di algebra relazionale sono rappresentate come nodi interni. La radice rappresenta la query nel suo insieme.

Durante l'esecuzione, un nodo interno viene eseguito ogni volta che le sue tabelle di operandi sono disponibili. Il nodo viene quindi sostituito dalla tabella dei risultati. Questo processo continua per tutti i nodi interni fino a quando il nodo radice non viene eseguito e sostituito dalla tabella dei risultati.

Ad esempio, consideriamo i seguenti schemi:

DIPENDENTE

EmpID EName Stipendio DeptNo DateOfJoining

DIPARTIMENTO

DNo DName Posizione

Esempio 1

Consideriamo la query come la seguente.

$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(EMPLOYEE)}) $$

L'albero della query corrispondente sarà:

Esempio 2

Consideriamo un'altra query che coinvolge un join.

$ \ pi_ {EName, Salary} (\ sigma_ {DName = \ small "Marketing"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $

Di seguito è riportato l'albero delle query per la query precedente.

Step 2 − Query Plan Generation

Dopo la generazione della struttura ad albero della query, viene creato un piano di query. Un piano di query è un albero di query esteso che include percorsi di accesso per tutte le operazioni nell'albero di query. I percorsi di accesso specificano come devono essere eseguite le operazioni relazionali nell'albero. Ad esempio, un'operazione di selezione può avere un percorso di accesso che fornisce dettagli sull'uso dell'indice dell'albero B + per la selezione.

Inoltre, un piano di query stabilisce anche come le tabelle intermedie dovrebbero essere passate da un operatore al successivo, come dovrebbero essere usate le tabelle temporanee e come le operazioni dovrebbero essere pipeline / combinate.

Step 3− Code Generation

La generazione del codice è il passaggio finale dell'ottimizzazione delle query. È la forma eseguibile della query, la cui forma dipende dal tipo di sistema operativo sottostante. Una volta generato il codice della query, Execution Manager lo esegue e produce i risultati.

Approcci all'ottimizzazione delle query

Tra gli approcci per l'ottimizzazione delle query, vengono utilizzati principalmente la ricerca esaustiva e gli algoritmi basati sull'euristica.

Ottimizzazione della ricerca esaustiva

In queste tecniche, per una query, vengono inizialmente generati tutti i possibili piani di query e quindi viene selezionato il piano migliore. Sebbene queste tecniche forniscano la soluzione migliore, hanno una complessità temporale e spaziale esponenziale a causa dell'ampio spazio della soluzione. Ad esempio, tecnica di programmazione dinamica.

Ottimizzazione basata su euristica

L'ottimizzazione basata su euristica utilizza approcci di ottimizzazione basati su regole per l'ottimizzazione delle query. Questi algoritmi hanno una complessità temporale e spaziale polinomiale, che è inferiore alla complessità esponenziale di algoritmi basati sulla ricerca esaustiva. Tuttavia, questi algoritmi non producono necessariamente il miglior piano di query.

Alcune delle regole euristiche comuni sono:

  • Eseguire le operazioni di selezione e progetto prima delle operazioni di unione. Questo viene fatto spostando le operazioni di selezione e progetto in basso nella struttura della query. Ciò riduce il numero di tuple disponibili per l'unione.

  • Eseguire le operazioni di selezione / progetto più restrittive prima delle altre operazioni.

  • Evitare il funzionamento tra prodotti poiché si traducono in tabelle intermedie di dimensioni molto grandi.