Risolvere i colli di bottiglia con indici SQL e partizioni

Nella prima lezione di Spiegazione degli indici SQL, abbiamo appreso che le query SELECT sono più veloci quando i dati sono già ordinati in base ai valori di colonne specifiche.

Nella seconda lezione, abbiamo appreso la struttura di base degli indici B-tree e come utilizzarli per ridurre il volume di dati a cui accediamo durante l'esecuzione di una query. Abbiamo anche scoperto come implementare query che uniscono più tabelle e come gli indici possono accelerare tali query.

Abbiamo anche evidenziato due scenari in cui l'uso degli indici in SQL è utile. Quando gli indici coprono gli indici, contenenti tutte le colonne della query, dalle condizioni WHERE , dalle condizioni JOIN e dall'elenco SELECT , evitiamo di leggere completamente la tabella corrispondente. In alternativa, gli indici possono aiutare quando riducono il numero di blocchi di dati a cui si accede a una piccola frazione della dimensione della tabella.

In caso contrario, è più efficiente eseguire la scansione dell'intera tabella piuttosto che leggere da un indice e saltare in modo casuale avanti e indietro alle righe della tabella corrispondenti.

Query sull'intervallo SQL

Le query che possono sfruttare gli indici in genere includono condizioni che riducono notevolmente l'intervallo di valori possibili che una o più colonne possono assumere. Le query di intervallo limitano i dati in base a condizioni come "il valore della colonna A deve essere compreso tra X e Y".

Un buon esempio di ciò è la query dell'Esercizio 4 della seconda lezione:

 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;

Qui abbiamo due gamme. Il primo è l'intervallo di date, il periodo compreso tra il 13 agosto 2020 e il 14 agosto 2020. Il secondo è l'intervallo numerico più piccolo possibile. La condizione è equivalente a r.HotelID BETWEEN 3 AND 3 .

Esercizio 1: Periodi (Query su data e intervallo di tempo)

Aggiungiamo una colonna chiamata CheckInTime alla tabella Reservations . Puoi vedere dati di esempio in questo foglio di lavoro. Si noti che esiste un unico indice che copre sia CheckInTime che ClientId .

Scrivi una query che restituisca i nomi dei clienti che hanno effettuato il check-in il 15 agosto 2020.

Gli sviluppatori SQL inesperti di solito scrivono la seguente query:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE TO_DATE(r.CheckInTime, 'YYYY-MM-DD') = '2020-08-15';

Presumono che l'esecuzione della query sia simile a questa:

 Get first row from IX_CheckInTime_ClientID where TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' While found and TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

Il problema è che non un singolo RDBMS al momento in cui scriviamo è in grado di generare un tale piano di esecuzione. Vedono TO_DATE (sintassi Oracle) come una funzione che trasforma il valore della colonna CheckInTime in qualcosa di non indicizzato. Quindi, i piani di esecuzione che tendono a generare sono simili a questo:

 For each row from IX_CheckInTime_ClientID If TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' then Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName

L'esecuzione sarebbe più veloce della lettura di tutte le righe dalla tabella Reservations perché la riga dell'indice è più stretta della riga della tabella. Una riga più piccola significa che è necessario accedere a meno blocchi dal disco.

Tuttavia, sappiamo che il primo piano di esecuzione sarebbe molto più efficiente. Per convincere il nostro RDBMS a utilizzare questo approccio, dobbiamo riscrivere la query:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.CheckInTime >= TO_DATE('2020-08-15 00:00:00', 'YYYY-MM-DD HH:MI:SS') AND r.CheckInTime < TO_DATE('2020-08-16 00:00:00', 'YYYY-MM-DD HH:MI:SS');

Questa è una query di intervallo corretta, comprensibile da ogni buon RDBMS. Il nostro RDBMS rileva che desideriamo dati dalla tabella Reservations in cui il valore di CheckInTime non qualcosa che ne deriva, appartiene all'intervallo ben definito. Il piano di esecuzione che genera sarebbe più simile a:

 Get first row from IX_CheckInTime_ClientID where CheckInTime >= '2020-08-15 00:00:00' While found and CheckInTime < '2020-08-16 00:00:00' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

Questo è ciò che vogliamo davvero: sfruttare non solo l'indice stesso, ma anche il fatto che è ordinato.

Esercizio 2: LIKE con un carattere jolly all'inizio

Questa volta il nostro detective arriva in albergo con vaghe informazioni sul sospetto: solo che il cognome finisce con "-figlio". Il detective vuole il nome e il cognome di tutti questi ospiti:

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE '%son';

Per la tabella Clients e un indice su LastName , utilizzeremo questo foglio di calcolo. Annotare i risultati che la query restituirebbe. Pensa ai diversi approcci che puoi applicare.

Approccio alla scansione della tabella

La strategia più semplice è leggere tutti i dati dalla tabella e annotare i nomi degli ospiti quando il loro cognome termina con "-son":

 For each row from Clients If LastName like '%son' then write down FirstName, LastName

Qui, dovremmo leggere l'intera tabella in sequenza.

Utilizzo di un indice

Proviamo a sfruttare l'indice sulla colonna LastName . Vai al foglio IX_Cognome, usalo per trovare tutti i clienti che soddisfano il criterio indicato e annota i loro nomi.

Si scopre che devi leggere l'intero indice per trovare tutti gli Anderson, i Robinson e i Thompson dal tavolo. È meglio che usare una scansione della tabella? Oltre a leggere l'intero indice, devi anche trovare, per ogni voce corrispondente, la riga corrispondente della tabella utilizzando il valore rowAddress , quindi annotare il FirstName da lì:

 For each row from IX_LastName If LastName like '%son' then Fetch Clients.* where RowAddress = IX_LastName.RowAddress Write down FirstName, LastName

Per noi è stato più semplice e veloce leggere la tabella in sequenza. Per il nostro RDBMS, dipenderebbe dalla percentuale di righe che soddisfano i criteri. Se ci sono solo una manciata di Anderson, Robinson e Thompson in una tabella di grandi dimensioni, un RDBMS leggerebbe meno blocchi di dati da voci di indice molto più strette anche se deve leggere alcuni blocchi dalla tabella quando viene trovata una corrispondenza. In caso contrario, la scansione della tabella richiede meno tempo.

Ordinare i dati nell'indice non fornisce alcun aiuto con tale query. La dimensione più piccola della riga dell'indice può essere utile, ma solo a volte.

Esercizio 3: LIKE con un carattere jolly alla fine

La prossima volta che arriva il nostro detective, dobbiamo trovare tutti i clienti i cui cognomi iniziano con "Rob-".

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE 'Rob%';

Prova a estrarre i dati corrispondenti alla query dallo stesso foglio di calcolo.

Se hai utilizzato l'approccio di scansione delle tabelle, hai perso l'opportunità di sfruttare appieno l'indice IX_LastName . È molto più veloce individuare la prima voce dell'indice che inizia con "Rob-" (Roberts), leggere le righe successive (sia Robertses che Robinsons) e fermarsi quando il LastName non corrisponde più al criterio:

 Get first row from IX_LastName where LastName <= 'Rob' While found and LastName < 'Roc' Fetch Clients.* where rowAddress = IX_LastName.rowAddress Write down FirstName, LastName Get next from IX_LastName

In questo caso, dopo la ricerca dell'albero B per la prima voce, leggiamo solo le voci che soddisfano il criterio. Smettiamo di leggere non appena leggiamo un nome che non corrisponde al criterio.

Affrontare i problemi di ridimensionamento dell'albero B

In genere, quando distribuiamo un nuovo database, sono presenti alcune tabelle di ricerca popolate e tabelle transazionali vuote. Il sistema funziona senza intoppi sin dall'inizio, soprattutto se abbiamo rispettato le buone pratiche di progettazione del database normalizzando le tabelle; creazione di chiavi primarie, esterne e univoche; e supporto di chiavi esterne con indici corrispondenti.

Dopo alcuni mesi o anni, quando il volume dei dati ha aumentato notevolmente la complessità del sistema e del database, iniziamo a notare un degrado delle prestazioni. Sorgono opinioni sul motivo per cui il sistema ha rallentato e cosa fare al riguardo.

L'opinione popolare è spesso che la dimensione del database sia il principale colpevole. La soluzione sembra essere quella di rimuovere i dati storici di cui non abbiamo bisogno ogni giorno e inserirli in un database separato per i rapporti e l'analisi.

Esploriamo prima l'ipotesi principale.

Query sull'intervallo SQL: il tempo di esecuzione dipende dalle dimensioni della tabella?

Considera una tipica query di intervallo da una singola tabella:

 SELECT Column1, …, ColumnN FROM Table WHERE Column BETWEEN X AND Y;

Supponendo che sia presente un indice su Column , il piano di esecuzione ottimale è:

 Get first row from IX_Column where Column between X and Y While found and Column <= Y Fetch Table.* where rowAddress = IX_Column.rowAddress Write down Column1, …, ColumnN Get next row from IX_Column

Contiamo i blocchi che un RDBMS dovrà leggere per restituire questi dati.

La parte Get first row è implementata dalla ricerca nell'albero B che abbiamo introdotto nella seconda lezione. Il numero di blocchi che deve leggere è uguale alla profondità del B-tree. Successivamente, leggiamo gli elementi successivi dal livello foglia dell'indice.

Con le query OLTP, in genere tutti i risultati verranno trovati all'interno di un blocco di indice (a volte due ma raramente di più). Inoltre, per ogni voce di indice, abbiamo accesso a un blocco nella tabella per trovare la riga corrispondente in base al suo indirizzo. Alcune righe di tabella potrebbero trovarsi all'interno dello stesso blocco di tabella che abbiamo già caricato, ma per semplificare la stima, supponiamo di caricare un nuovo blocco ogni volta.

Quindi la formula è:

B = D + 1 + R

B è il numero totale di blocchi letti, D è la profondità dell'albero B e R è il numero di righe restituite dalla query.

L'unico parametro che dipende dal numero di righe nella tabella è D, la profondità dell'albero B.

Per semplificare i calcoli e fare un punto, supponiamo che 1.000 voci di indice rientrino in un blocco. D = 1 purché nella tabella siano presenti meno di 1.000 righe. Per le tabelle che contengono transazioni commerciali, ciò potrebbe verificarsi il primo giorno lavorativo dopo la distribuzione del sistema. Abbastanza presto, la profondità dell'albero B aumenterà. Se nella tabella sono presenti meno di 1 milione di righe, l'indice sarà composto da due livelli.

Se siamo infastiditi dai tempi di risposta del database lenti e ne incoliamo il volume dei dati, tieni presente che le tabelle delle transazioni spesso hanno solo milioni di righe. Poiché solo 1 milione di righe si adattano a un indice B-tree a due livelli, la profondità deve essere almeno tre. La profondità non aumenterà a quattro a meno che non ci siano più di 1 miliardo di righe nella tabella. Ora abbiamo una stima più precisa:

B = 4 + R

Se R è piccolo, ridurre la profondità dell'albero B a due velocizzerebbe notevolmente la query. Quando eseguiamo la ricerca in base a un valore di chiave primaria o univoca, il sistema leggerà quattro blocchi anziché cinque, con un miglioramento del 20%. Se la query restituisce più righe, il miglioramento potrebbe non essere evidente. Il problema è che per molte applicazioni potremmo non essere in grado di supportare le operazioni aziendali richieste mantenendo meno di 1 milione di transazioni nel database.

Quindi la conclusione sembra essere che le dimensioni della tabella non contano; in altre parole, spostare i dati storici è una perdita di tempo e risorse.

Ma non così in fretta: impariamo di più sulla struttura di un indice B-tree e su come le modifiche ai dati lo influenzano.

Dettagli di implementazione dell'indice B-tree

Nella nostra copertura degli indici dell'albero B nella seconda lezione, abbiamo visto che tutti i livelli di un albero bilanciato sono (fisicamente) ordinati in base ai valori delle colonne chiave. Tuttavia, quando vogliamo inserire, aggiornare o eliminare un articolo, spesso dobbiamo spostare una grande quantità di dati per preservare l'ordine.

Supponiamo che stiamo inserendo nel mezzo di un blocco che sembra essere pieno. Dobbiamo dividere il blocco, riorganizzare i dati e talvolta persino aggiornare i dati su un altro livello di B-tree che punta a quello corrente.

Per rendere questi casi più efficienti, ogni elemento dell'indice contiene puntatori alle righe precedenti e successive, rendendolo doppio collegamento. Per l'inserimento in generale, questo significa che scriviamo i nuovi elementi il ​​più vicino possibile al precedente e correggiamo i puntatori.

Quando dobbiamo dividere anche un blocco, dobbiamo scrivere un nuovo elemento nel livello B-tree precedente. Si tratta solo di correggere alcuni suggerimenti in più, non è necessario riscrivere grandi porzioni dell'albero. Dopo una divisione, entrambi i blocchi di dati sono circa a metà. A seconda di dove c'è spazio libero sul disco, i blocchi "vicini" potrebbero essere fisicamente abbastanza distanti.

Dopo qualche tempo, la frammentazione dell'indice aumenta e il rallentamento dell'esecuzione della query diventa evidente. Con un RDBMS che esegue query nel modo in cui le abbiamo descritte, il presupposto dell'ordine e della vicinanza degli elementi diventa sempre meno corretto, portando a molte più letture. Nel peggiore dei casi, con tutti i blocchi di dati semivuoti, il sistema deve leggere il doppio dei blocchi.

Manutenzione dell'indice dell'albero B

La cura per questo è la deframmentazione dell'indice (o "reindicizzazione"). Ogni RDBMS fornisce una funzione per ricreare un intero indice; dopo la reindicizzazione, gli indici vengono nuovamente ordinati fisicamente.

La reindicizzazione è un'operazione piuttosto veloce, anche se legge e scrive un volume elevato di dati. I moderni RDBMS offrono in genere due modalità di reindicizzazione, con quella più veloce che richiede il blocco delle tabelle durante l'elaborazione. In ogni caso, è preferibile reindicizzare nelle ore non di punta. In caso contrario, l'elaborazione potrebbe rallentare le prestazioni del database.

Eliminazione dei dati storici

Quando abbiamo tabelle con miliardi o addirittura centinaia di milioni di righe, potrebbe non essere possibile completare un'operazione di reindicizzazione durante le ore non di punta.

Per evitare questa situazione, la soluzione potrebbe essere lo spostamento dei dati storici da un database OLTP. Tuttavia, se eliminiamo semplicemente le righe più vecchie di una soglia specifica, rendiamo gli indici ancora più frammentati e dobbiamo reindicizzarli ancora più frequentemente.

Partizionamento SQL in soccorso?

C'è un modo per evitare la frammentazione causata dalla rimozione dei dati storici, mantenendo solo le transazioni "attive" nel database di produzione. L'idea che tutti i principali RDBMS implementano è quella di dividere una tabella in blocchi più piccoli (chiamati partizioni ) e fornire la capacità di aggiungerli, rimuoverli e persino spostarli tra le tabelle (ad esempio, da una tabella attiva a una storica con lo stesso struttura).

Diamo un'occhiata alla tabella Reservations come partizionata in questo foglio di calcolo. La tabella è suddivisa per mese, con i nomi delle partizioni mappati su periodi di data e altri fogli di calcolo. Per vedere come viene eseguita una query su una tabella partizionata, faremo alcuni esercizi.

Esercizio 4: Query di partizione in SQL

Dal foglio di calcolo collegato sopra, prova ad estrarre i dati richiesti dalla seguente query, senza utilizzare alcun indice:

 SELECT HotelID, ReservationID, ClientID, DateFrom, DateTo FROM Reservations WHERE DateFrom BETWEEN TO_DATE('2021-03-01','YYYY-MM-DD') AND TO_DATE('2021-03-03');

Probabilmente hai capito che devi prima guardare il foglio di mappatura delle partizioni e trovare la partizione contenente le prenotazioni di marzo 2021. Successivamente, hai aperto la partizione corrispondente, letto i dati in sequenza e filtrato le righe che non soddisfacevano il condizione.

Sebbene sia semplice, probabilmente non ti è piaciuto mantenere così poche righe dopo averne lette così tante. Leggere la partizione di marzo era meglio che leggere l'intera tabella di prenotazione ma non era ancora l'ideale. E gli indici?

Indici globali

Gli RDBMS ci consentono di creare un indice globale per coprire tutte le partizioni di una tabella partizionata. Ma non c'è differenza tra il modo in cui funzionano gli indici globali e regolari sottostanti: gli indici globali non sono in grado di riconoscere le partizioni. Pertanto, le query CRUD che utilizzano un indice globale non coinvolgono la mappa delle partizioni per la relativa tabella.

Abbiamo solo bisogno di aggiornare la mappa delle partizioni quando eliminiamo un'intera partizione. Dobbiamo quindi rimuovere tutte le righe dall'indice che puntano alla partizione rimossa. Ciò significa che l'intero indice globale deve essere ricostruito.

Rimane necessaria una finestra di interruzione perché gli indici non possono essere utilizzati finché gli elementi obsoleti non vengono rimossi. Se riusciamo a eliminare regolarmente le partizioni, limitando il numero di quelle attive, l'operazione di reindicizzazione potrebbe rientrare nella finestra di interruzione. Pertanto, l'utilizzo delle partizioni aiuta a risolvere il problema originale riducendo il tempo necessario per le attività di manutenzione, inclusa la manutenzione degli indici globali.

Ma cosa succede se non possiamo ancora permetterci l'interruzione?

Indici partizionati a livello globale

Questa strategia risolve il problema: partizioniamo semplicemente l'indice nello stesso modo in cui partizioniamo la tabella. Nei fogli di calcolo a cui si collega il foglio di calcolo della partizione, ogni partizione contiene la propria parte della tabella Reservations e un foglio di indice chiamato IX_DateFrom, entrambi partizionati da DateFrom .

Per eseguire la query dell'Esercizio 4, un RDBMS dovrebbe prima esaminare una mappa delle partizioni dell'indice e identificare quali partizioni contengono date dall'intervallo. (Nel nostro caso, è solo una partizione di indice.) Successivamente, utilizzerà le ricerche dell'albero B, passerà al livello foglia e infine accederà alla tabella utilizzando l'indirizzo di riga corrispondente.

Quando eliminiamo una partizione da una tabella, è sufficiente eliminare la partizione corrispondente dall'indice. Non sono necessari tempi di inattività.

Indici locali

Lo svantaggio principale degli indici partizionati a livello globale è che dobbiamo occuparci di eliminare sia la tabella che la partizione dell'indice corrispondente. C'è solo un leggero costo aggiuntivo associato alla lettura e al mantenimento della mappa delle partizioni dell'indice stessa.

Gli indici locali implicano un approccio simile ma leggermente diverso. Invece di partizionare un singolo indice globale, creiamo un indice locale all'interno di ogni partizione di tabella. In tal modo, gli indici locali condividono il vantaggio principale degli indici partizionati a livello globale, ovvero nessun tempo di inattività, evitandone gli svantaggi.

Sembra una soluzione perfetta. Ma prima di festeggiare, esaminiamo il possibile piano di esecuzione di alcune query.

Esercizio 5: Indice partizionato localmente

Prova a eseguire di nuovo la query, questa volta utilizzando l'indice partizionato localmente su DateFrom .

Probabilmente hai utilizzato questo piano di esecuzione:

 For all partitions where [StartDateFrom, StartDateTo) intersects ['2021-03-01', '2021-03-03'] Get first row from IX_DateFrom where DateFrom between '2021-03-01' and '2021-03-03' While found and DateFrom < '2021-03-04' Fetch Reservations.* where RowAddress = IX_DateFrom.RowAddress Write down HotelID, ReservationID, ClientID, DateFrom, DateTo Get next row from IX_DateFrom

Siamo fortunati che tutte le date appartengano a una singola partizione, quindi abbiamo dovuto attraversare un solo indice locale. Se il periodo fosse lungo sei mesi, dovremmo leggere sei indici locali.

Esercizio 6: In contrasto

Il tuo compito è utilizzare nuovamente la mappa della partizione Prenotazioni, questa volta per creare un elenco di periodi in cui il Cliente 124 ha visitato l'Hotel 1:

 SELECT DateFrom, DateTo FROM Reservations WHERE ClientID = 124 AND HotelID = 1;

Qui possiamo vedere il principale svantaggio degli indici locali. Abbiamo dovuto leggere il foglio di indice locale IX_HotelID_CientID da ogni partizione della tabella Reservations :

 For all partitions Get first row from IX_HotelID_ClientID where ClientID = 124 and HotelID = 1 While found and ClientID = 124 and HotelID = 1 Fetch Reservations.* where RowAddress = IX_HotelID_ClientID.RowAddress Write down DateFrom, DateTo Get next row from IX_HotelID_ClientID

Questa esecuzione leggerebbe chiaramente più blocchi e richiederebbe più tempo che se la tabella non fosse partizionata.

Quindi, mentre abbiamo trovato un modo per mantenere la salute dei nostri indici durante il periodo di punta, la strategia ha anche rallentato alcune delle nostre query.

Se il nostro modello di business ci consente di mantenere un numero limitato di partizioni o almeno le query più frequenti contengono criteri che consentono all'RDBMS di leggere solo una o due partizioni, questa soluzione potrebbe essere ciò di cui abbiamo bisogno. In caso contrario, è meglio evitare il partizionamento e lavorare per migliorare il modello di dati, gli indici e le query e migliorare il server di database.

Indici in SQL: cosa imparare dopo

Questa è la fine del nostro viaggio. In SQL Indexes Explained, mi sono concentrato sull'implementazione dell'indice comune a tutti i moderni RDBMS. Mi sono anche concentrato su argomenti che interessano gli sviluppatori di applicazioni, a scapito di argomenti che in genere riguardano gli amministratori di database. Quest'ultimo farebbe bene a ricercare l'impatto del fattore di riempimento sulla frammentazione dell'indice, ma le persone in entrambi i ruoli probabilmente troveranno utile leggere ulteriori informazioni su:

• Memorizzazione nella cache di dati e indici
• Strutture di indici non B-tree, come hash, GiST, bitmap e indici columnstore
• Indici cluster (noti come tabelle organizzate per indici in Oracle)
• Indici funzionali
• Indici parziali

L'approccio al partizionamento di cui abbiamo discusso è il partizionamento dell'intervallo . È il tipo di partizionamento più comunemente usato, ma ce ne sono altri, come il partizionamento hash e il partizionamento di elenchi. Inoltre, alcuni RDBMS offrono l'opzione di più livelli di partizionamento.

Infine, gli sviluppatori SQL farebbero bene a esplorare altri argomenti importanti sull'esecuzione di query RDBMS: in primo luogo, l'analisi delle query, quindi la compilazione, la memorizzazione nella cache e il riutilizzo del piano di esecuzione basato sui costi.

Per i quattro RDMBS con cui ho esperienza, consiglio queste risorse come passaggi successivi:

Oracolo

• Panoramica dell'ottimizzatore
• Indici e tabelle organizzate per indici
• Gestione degli indici
• Panoramica delle partizioni
• Guida al partizionamento
• Chiedi a Tom

PostgreSQL

• Elaborazione delle query
• Indici in PostgreSQL
• Indici in PostgreSQL (documentazione ufficiale)
• Gestione del buffer
• Partizionamento della tabella
• Guida al partizionamento

Microsoft SQL Server

• Architettura di elaborazione delle query
• Indici
• Tabelle e indici partizionati

MySQL/MariaDB

• Comprensione del piano di esecuzione delle query
• Ottimizzazione e indici
• Partizionamento - Nozioni di base
• Partizionamento - Documentazione
• Documentazione MariaDB: ottimizzazione delle query e indici