Spiegazione degli indici SQL, pt. 2

Nella prima lezione di SQL Indexes Explained , abbiamo imparato a utilizzare l'ordinamento per accelerare il recupero dei dati. Mentre l'esecuzione della nostra query è più veloce dopo che le righe sono state ordinate, l'ordinamento comporta la lettura di ogni riga almeno una volta e il loro spostamento. Ciò rende il metodo più lento e meno efficiente rispetto alla semplice lettura dell'intera tabella in sequenza.

La conclusione logica sembra essere che dovremmo mantenere le copie ordinate, che chiameremo ufficialmente indici SQL, con il prefisso IX_ , di una determinata tabella. Gli algoritmi di recupero del primo articolo sarebbero quindi applicabili e non avremmo bisogno di ordinare la tabella prima di iniziare.

L'indice come copia ordinata della tabella

Diamo un'occhiata all'implementazione letterale di quell'idea, sempre utilizzando Fogli Google. Il nostro foglio di calcolo delle prenotazioni diventa una raccolta di cinque fogli contenenti gli stessi dati. Ogni foglio è ordinato in base a diversi insiemi di colonne.

Gli esercizi qui devono essere meno precisi rispetto al precedente articolo dell'esercitazione sull'indice SQL: possono essere eseguiti più in base al tatto che in base al timer e al conteggio delle righe. Alcuni esercizi sembreranno molto simili, ma questa volta stiamo esplorando:

1. Come recuperare i dati in modo più efficiente quando si utilizzano indici separati anziché tabelle primarie ordinate
2. Come mantenere l'ordine in ogni indice e tabella durante la modifica dei dati

Il tutorial precedente si concentrava sulle letture, ma in molte dinamiche di dati comuni nel mondo reale, incluse le nostre prenotazioni alberghiere, dobbiamo tenere conto degli effetti dell'indicizzazione sulle prestazioni di scrittura, sia per l'inserimento di nuovi dati che per l'aggiornamento di quelli esistenti.

Esercizio preliminare: annullare una prenotazione

Per avere un'idea delle prestazioni dell'indice SQL utilizzando la strategia della tabella ordinata, il tuo compito è eliminare una prenotazione per il Cliente 12, dal 22 agosto 2020, in Hotel 4. Tieni presente che devi rimuovere una riga da tutte le copie di la tabella e mantenere il corretto ordinamento.

Fatto? Dovrebbe essere chiaro che l'idea di mantenere più copie ordinate della tabella non è buona come sembrava. Se hai ancora dei dubbi, puoi anche provare a reinserire la prenotazione che hai appena cancellato o modificare la data di una prenotazione esistente.

Mentre le copie ordinate della tabella consentono un recupero più rapido, come abbiamo appena appreso, la modifica dei dati è un incubo. Ogni volta che dobbiamo aggiungere, eliminare o aggiornare una riga esistente, dovremo recuperare tutte le copie della tabella, trovare una riga e/o il punto in cui dovrebbe essere aggiunta o spostata e infine spostare blocchi di dati.

Indici SQL che utilizzano indirizzi di riga

Questo foglio di calcolo contiene indici che utilizzano un approccio diverso. Le righe dell'indice sono ancora ordinate in base a criteri specifici, ma non conserviamo tutte le altre informazioni nella riga dell'indice. Invece, manteniamo solo l'"indirizzo di riga", l'indirizzo della riga nel foglio Prenotazioni, che rappresenta la tabella stessa, nella colonna H.

Tutte le implementazioni RDBMS utilizzano una capacità a livello di sistema operativo per trovare rapidamente il blocco sul disco utilizzando un indirizzo fisico. Gli indirizzi di riga sono in genere costituiti da un indirizzo di blocco più la posizione della riga all'interno del blocco.

Facciamo alcuni esercizi per imparare come funziona questo design dell'indice.

Esercizio 1: Tutte le prenotazioni di un cliente

Come nel primo articolo, simulerà l'esecuzione della seguente query SQL:

 SELECT * FROM Reservations WHERE ClientID = 12;

Ancora una volta, ci sono due approcci ragionevoli. Il primo è semplicemente leggere tutte le righe dalla tabella Prenotazioni e recuperare solo le righe che corrispondono ai criteri:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

Il secondo approccio prevede la lettura dei dati dal foglio IX_ClientID e, per qualsiasi elemento che soddisfa i criteri, la ricerca di una riga nella tabella Prenotazione in base al valore rowAddress:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Qui, l'espressione Get first row from è implementata da un ciclo simile a quelli visti nell'articolo precedente:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Puoi trovare una riga con un determinato rowAddress scorrendo verso il basso fino a trovare una riga o utilizzando un filtro nella colonna rowAddress.

Se ci fossero solo una manciata di prenotazioni da restituire, l'approccio che utilizza l'indice sarebbe migliore. Tuttavia, con centinaia, o talvolta anche solo decine, di righe da restituire, il semplice utilizzo della tabella Prenotazioni direttamente può essere più veloce.

Il volume delle letture dipende dal valore di ClientID. Per il valore più grande, devi leggere l'intero indice, mentre per il valore più basso, è all'inizio dell'indice. Il valore medio è la metà del numero di righe.

Torneremo su quella parte più tardi e presenteremo una soluzione efficiente. Per ora, concentriamoci sulla parte dopo aver trovato la prima riga che corrisponde ai nostri criteri.

Esercizio 2: Il numero di prenotazioni a partire da una determinata data

Il compito è contare il numero di check-in il 16 agosto 2020, utilizzando il nuovo design dell'indice.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

L'approccio dell'utilizzo dell'indice appropriato per il conteggio è superiore alla scansione di una tabella, indipendentemente dal numero di righe coinvolte. Il motivo è che non dobbiamo affatto accedere alla tabella Prenotazioni: abbiamo tutte le informazioni di cui abbiamo bisogno nell'indice stesso:

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

L'algoritmo è sostanzialmente lo stesso di quello che utilizza le tabelle ordinate. Tuttavia, la riga dell'indice è molto più corta della riga della tabella, quindi il nostro RDBMS dovrebbe leggere meno blocchi di dati dal disco.

Esercizio 3: Indagine penale (elenco degli ospiti dato hotel e intervallo di date)

Prepariamo una lista degli ospiti arrivati ​​all'Hotel 3 il 13 e 14 agosto 2020.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Possiamo leggere tutte le righe dalla tabella Prenotazioni o utilizzare uno degli indici disponibili. Dopo aver eseguito lo stesso esercizio con una tabella ordinata secondo criteri specifici, abbiamo scoperto che l'indice IX_HotelID_DateFrom è il più efficiente.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Possiamo progettare un indice ancora più efficiente?

Accediamo alla tabella a causa del valore ClientID , l'unica informazione di cui abbiamo bisogno per l'elenco degli ospiti che stiamo segnalando. Se includiamo quel valore nell'indice SQL, non dobbiamo affatto accedere alla tabella. Prova a preparare un elenco leggendo solo da un tale indice, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Quando l'indice contiene tutte le informazioni necessarie per l'esecuzione della query, diciamo che l'indice copre la query.

Esercizio 4: Elenco dei nomi degli ospiti invece degli ID

Un elenco di ID ospiti sarebbe inutile per un agente di polizia che indaga su un crimine. Dobbiamo fornire i nomi:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Per fornire un elenco, oltre ai dati della tabella Reservations , abbiamo bisogno anche di una tabella Clients contenente le informazioni sugli ospiti, che possono essere trovate in questo foglio di Google.

Questo esercizio è simile al precedente, così come l'approccio.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

L'espressione Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID può essere implementata tramite la scansione della tabella o utilizzando il nostro indice. Se utilizziamo una scansione della tabella, per ogni ClientID del ciclo While , dovremmo leggere in media la metà delle righe dalla tabella Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

L'implementazione dell'indice che abbiamo considerato finora, chiamiamola implementazione dell'indice "piatta", non sarebbe molto utile. Dovremmo leggere lo stesso numero di righe (anche se più piccole) dall'indice, quindi passare alla riga in Clients using RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Nota: qui, PK si riferisce a "chiave primaria", un termine che esploreremo più avanti nella serie.

C'è un modo per farlo senza dover leggere così tante righe? Sì, questo è esattamente a cosa servono gli indici B-tree.

Indici Balanced Tree (B-tree).

Dividiamo le righe di Clients_PK_Flat in blocchi di quattro righe e creiamo un elenco contenente il valore dell'ultimo ClientID del blocco e l'indirizzo di inizio del blocco (colonna IndexRowAddress ). La struttura dei dati dell'indice del database risultante: puoi trovarla nel foglio Clients_PK_2Levels. Prova come la nuova struttura ti aiuta a trovare un cliente con un ClientID di 28. L'algoritmo dovrebbe assomigliare a questo:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Probabilmente hai capito che possiamo aggiungere un altro livello. Il livello 1 è composto da quattro righe, come puoi vedere nella scheda IX_Clients_PK. Per trovare il nome dell'ospite con un ClientID di 28, devi leggere tre blocchi (nodi) di dati, uno per livello, dalla struttura della chiave primaria e infine passare alla riga Clienti con l'indirizzo 42.

La struttura di questo indice SQL è chiamata albero bilanciato. L'albero è bilanciato quando il percorso dal nodo radice a ciascun nodo a livello di foglia ha la stessa lunghezza, la sua cosiddetta profondità dell'albero B. Nel nostro caso, la profondità è tre.

D'ora in poi, considereremo ogni indice come struttura ad albero B, anche se i nostri fogli di calcolo contengono solo voci a livello di foglia. I fatti più importanti da sapere su B-tree sono:

• La struttura dell'indice B-tree è l'indice più comunemente utilizzato da tutti i principali RDBMS sul mercato.
• Tutti i livelli di un albero bilanciato sono ordinati in base ai valori delle colonne chiave.
• I dati vengono letti dal disco in blocchi.
• Un nodo B-tree contiene uno o più blocchi.
• Il fattore più importante che influisce sulle prestazioni delle query è il numero di blocchi letti dal disco.
• Il numero di elementi in ogni nuovo livello dell'albero B, a partire dalla radice, fino al livello foglia, aumenta in modo esponenziale.

Esercizio 5: Indagine penale, parte II

Ora, l'ispettore di polizia sta cercando un elenco dei nomi degli ospiti corrispondenti, delle date di arrivo e dei nomi degli hotel di tutti gli hotel della città A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Approccio 1

Se utilizziamo l'indice IX_DateFrom_HotelID_ClientID , per ogni riga dell'intervallo di date, dovremmo accedere alla tabella Hotels e verificare se l'hotel è della città A. Se lo è, dovremmo accedere anche alla tabella Clienti per leggere il nome del cliente.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Approccio 2

L'utilizzo IX_HotelID_DateFrom_ClientID ci offre un piano di esecuzione più efficiente.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Dalla tabella Hotels , troviamo tutti gli hotel della città A. Conoscendo l'ID di questi hotel, possiamo leggere le voci successive dell'indice IX_HotelID_DateFrom_ClientID . In questo modo, dopo aver trovato la prima riga nel livello foglia dell'albero B per ogni hotel e data, non leggiamo le prenotazioni degli hotel fuori città A.

Qui possiamo vedere che quando abbiamo un indice di database appropriato per i nostri obiettivi, un join aggiuntivo può effettivamente rendere una query più veloce.

La struttura dell'albero B e il modo in cui viene aggiornata ogni volta che una riga viene inserita, aggiornata o eliminata verrà affrontata in modo più dettagliato quando spiego la motivazione del partizionamento e il suo impatto. Il punto è che possiamo considerare questa operazione rapida ogni volta che utilizziamo un indice.

La query sull'indice in SQL: i dettagli fanno la differenza

Quando si tratta di indici e database, lavorare a livello di linguaggio SQL nasconde in una certa misura i dettagli di implementazione. Questi esercizi hanno lo scopo di aiutarti a farti un'idea di come funzionano i piani di esecuzione quando si utilizzano indici SQL diversi. Dopo aver letto l'articolo, spero che sarai in grado di indovinare il miglior piano di esecuzione dati gli indici disponibili e gli indici di progettazione che renderebbero una query il più veloce ed efficiente possibile.

Nella parte successiva di questa serie, utilizzeremo ed espanderemo le competenze appena acquisite per indagare e comprendere le best practices e gli anti-pattern più comuni nell'uso degli indici in SQL. Ho un elenco di buone e migliori pratiche che voglio affrontare nella prossima parte, ma per rendere il prossimo articolo più pertinente alle tue esigenze ed esperienze, non esitare a pubblicare le tue domande a cui vorresti vedere risposta .

Nella parte finale di SQL Indexes Explained , impareremo anche il partizionamento di tabelle e indici, le motivazioni giuste e sbagliate per usarlo e il suo impatto sulle prestazioni delle query e sulla manutenzione del database.