Indici (InterBase e Firebird)

Alexey Kovyazin, ultimo aggiornamento 07-Set-2005

Il concetto alla base degli indici è semplice e intuitivo ed è uno dei fondamenti più importanti della progettazione di database. Su base degli indici si fondano molti oggetti di base del database e, inoltre, l’uso corretto degli indici è la chiave per migliorare le prestazioni delle applicazioni di database. Tuttavia, cos’è un indice? Un indice è un puntatore ordinato dei record nella tabella. Puntatore significa che l’indice contiene i valori di uno o più campi della tabella e gli indirizzi delle pagine dati dove questi valori sono allocati (per i dettagli sulle pagine dati, vedere il capitolo “Struttura del database InterBase”) (parte 4). In altre parole, un indice è costituito da coppie di valori “valore del campo” - “posizione fisica di questo campo”.

Quindi, tramite il valore del campo (o dei campi) incluso nell’indice, usando l’indice possiamo trovare rapidamente il punto nella tabella dove è allocato il record contenente questo valore. Ordinato significa che i valori dei campi memorizzati nell’indice sono ordinati. Molto spesso l’indice viene paragonato a un catalogo di biblioteca, in cui tutti i libri sono registrati su schede e ordinati in qualche modo: per alfabeto o per argomento, e ogni scheda contiene le informazioni su dove esattamente il libro è allocato nel magazzino.

Perché abbiamo bisogno degli indici?

L’unica cosa che gli indici promuovono è l’accelerazione del recupero dei record tramite il suo campo indicizzato (indicizzato - significa incluso nell’indice). La funzione principale degli indici è fornire un recupero rapido dei record nella tabella. Qualsiasi uso dell’indice si riduce a questo.

Come viene realizzata questa funzione di recupero? All’input di questa funzione abbiamo il valore del campo indicizzato (o di più campi). Come risultato del recupero dovremmo ricevere l’intero record, in cui il campo indicizzato ha un valore preimpostato. Prima nell’indice (più precisamente, nell’array ordinato di valori del campo indicizzato) viene cercato il valore richiesto, poi viene preso l’indirizzo della pagina dati dove si trova il record richiesto, il server va a questa pagina e legge il record trovato. Sembra piuttosto scomodo, tuttavia la ricerca, usando l’indice, è molte volte più veloce dell’enumerazione sequenziale di tutti i valori della tabella.

Se continuiamo l’analogia tra indice e catalogo di biblioteca, vedremo che il recupero dei record, usando l’indice, è molto simile alla ricerca di un libro tramite scheda. Quando troviamo un libro in un catalogo piuttosto piccolo (in confronto all’intero magazzino della biblioteca), riceviamo immediatamente le informazioni su dove esattamente il libro è conservato e possiamo andare direttamente lì. La ricerca senza usare l’indice può essere paragonata all’enumerazione sequenziale di tutti i libri della biblioteca!

L’enumerazione di tutti i record nella tabella è chiamata diretta o naturale. Dobbiamo dire che nonostante la potenza dei computer moderni, l’enumerazione naturale può essere molto lunga se la tabella contiene un gran numero di record.

Come sono organizzati?

L’indice non è una parte della tabella, è un oggetto separato collegato alla tabella e ad altri oggetti del database. Questo è un punto molto importante dell’implementazione del DBMS che consente di separare l’archiviazione delle informazioni dalla loro rappresentazione.

InterBase, come qualsiasi altro database relazionale, memorizza i record nelle tabelle in modo non ordinato, cioè non si preoccupa affatto di come i record sono allocati fisicamente nella tabella. L’archiviazione non ordinata significa che due record aggiunti alla tabella uno dopo l’altro potrebbero non essere uno accanto all’altro. Inoltre, i dati estratti dalla tabella non hanno alcun ordine a parte quello che dovrebbe essere esplicitamente specificato dall’utente che effettua una query di recupero.

Tuttavia, non possiamo fare a meno di ordinare i dati memorizzati: gli utenti finali delle applicazioni vogliono vedere i dati in un ordine definito - ad esempio, i cognomi delle persone in ordine alfabetico. Gli indici risolvono il problema della rappresentazione dei dati in modo ordinato. I valori dei campi inclusi nell’indice sono ordinati e rappresentati in una vista speciale, ottimizzata per la ricerca dei valori richiesti (cioè, questo è essenziale per creare sequenze ordinate).

Separare l’archiviazione dei dati dalla loro rappresentazione dà ulteriori vantaggi rispetto all’ordinamento diretto - forse avrete bisogno di ordinare la tabella iniziale in modi diversi. Allora gli indici vi aiuteranno - ci possono essere fino a 64 indici per ogni tabella!

Se parliamo dell’implementazione degli indici a livello fisico, essi rappresentano un albero binario i cui nodi rappresentano coppie “valore del campo nell’indice” - “allocazione dei dati nella tabella”. Il recupero del record richiesto nell’indice viene eseguito usando il meccanismo di hash-search - uno degli algoritmi di ricerca più veloci.

Applicazione degli indici

Ora che è chiaro cosa possiamo pretendere dagli indici, è il momento di conoscere la loro funzione in un database. Gli indici sono usati in tre casi principali:

Accelerazione dell’esecuzione delle query. Gli indici vengono creati per i campi usati nelle condizioni di ricerca delle query SQL.
Supporto dell’unicità dei valori nei campi; un vincolo di chiave primaria (di cui si è parlato nel capitolo “Tabelle. Chiavi primarie”) richiede che nella tabella non ci siano due valori identici dei campi inclusi in una chiave primaria. Per soddisfare questa condizione, quando si inserisce un nuovo record si dovrebbe cercare lo stesso valore che verrà inserito. Per il recupero dei record viene usata una varietà speciale di indice - un indice univoco (vedi sotto).
Supporto dell’integrità referenziale. I vincoli di chiave esterna (che sono considerati nel capitolo “Vincoli del database”) vengono usati per verificare che i valori inseriti nella tabella esistano necessariamente in un’altra tabella. Quando si crea una chiave esterna, viene creato automaticamente un indice. Questo indice viene applicato per accelerare le query che usano il join delle tabelle, così come per verificare le condizioni della chiave esterna. Abbiamo brevemente coperto tutte le possibili applicazioni degli indici. Ora considereremo le peculiarità di ogni caso in maggior dettaglio e risponderemo alle domande più frequenti riguardanti l’applicazione degli indici.

Accelerazione dell’esecuzione delle query usando gli indici

È stato descritto sopra che l’applicazione degli indici può accelerare notevolmente l’esecuzione delle query. È davvero così nella maggior parte dei casi, ma ci sono alcune precisazioni. Prima, risponderemo alla domanda che sorge frequentemente tra coloro che hanno familiarizzato con gli indici. Se gli indici accelerano il recupero da un database, perché non indicizzare tutti i campi nella tabella? Ci sono due momenti che bloccano l’indicizzazione generale: lo spazio su disco e i costi quando si modificano i dati nella tabella. Ogni indice creato ha una dimensione pari alla dimensione dei dati nel campo indicizzato, più la dimensione dei dati dell’allocazione dei record. Se creiamo indici per ogni campo nella tabella, la loro dimensione totale sarà maggiore della dimensione dei dati nella tabella! Pertanto, la creazione di un gran numero di indici porta a una grande spesa di spazio su disco.

Il secondo momento è più importante. Questi sono gli oneri quando si modificano i dati nella tabella. In un DBMS relazionale, come sapete, i record nelle tabelle non sono ordinati e di conseguenza l’aggiunta/eliminazione dei record avviene senza oneri significativi delle risorse del server. Anche se un record viene eliminato dal mezzo di un database, non c’è spostamento di dati per riempire questo vuoto - non è richiesto: il server semplicemente marcherà il posto vuoto e scriverà qualcosa lì quando necessario. Per quanto riguarda l’aggiunta, nella maggior parte dei casi viene eseguita alla fine della tabella. Tuttavia, sebbene il server non sposti i dati principali nella tabella quando li modifica, i dati memorizzati negli indici vengono riordinati ogni volta che si aggiungono/eliminano i record! In altre parole, il server deve ricostruire l’indice quando si aggiunge un record al centro della tabella. Certamente, l’implementazione dell’indice è in qualche modo destinata a frequenti riorganizzazioni, ma queste operazioni richiedono comunque tempo e risorse del processore e quando c’è un gran numero di indici nella tabella, la modifica dei dati al suo interno può essere molto più lenta che nella stessa tabella senza indici!

Queste sono le due ragioni principali che interferiscono con l’indicizzazione generale. Oltre a queste, ci sono alcune altre osservazioni che limitano l’applicazione degli indici. La prima è la regola del 20%. Dice che se la query di recupero restituisce più del 20% dei record dalla tabella, l’uso dell’indice può rallentare il recupero dei dati! Certamente, la situazione dipende da una query concreta e dalle condizioni impostate per il recupero, ma dovremmo ricordare che il 20% dei record è una soglia quando l’efficienza dell’uso degli indici diventa dubbia. La seconda osservazione non è formulata in modo così chiaro. È collegata al lavoro dell’ottimizzatore di InterBase.

L’ottimizzatore è una raccolta di meccanismi che sviluppano il piano di esecuzione della query. Quando l’utente fornisce qualsiasi query SQL a InterBase, specifica cosa il server dovrebbe restituire dopo l’esecuzione della query, ma non definisce COME il server dovrebbe eseguire la query. L’ottimizzatore sulla base della query data crea il piano della sua esecuzione, cioè da dove e in quale ordine i dati per l’esecuzione della query verranno presi, quali indici verranno usati in quel momento. Quando il server analizza le condizioni di recupero (queste sono principalmente parti dell’espressione WHERE, ORDER BY, ecc.) per ogni campo incluso nella condizione, il server cerca di usare l’indice. Sfortunatamente, l’algoritmo di creazione del piano è incompleto e l’ottimizzatore usa frequentemente indici che non sono troppo efficaci per la query concreta, a causa di ciò il tempo di esecuzione può essere rallentato essenzialmente. Pertanto, la creazione di indici non necessari può portare alla creazione di piani non ottimali.

Va notato che nel clone Yaffil questo problema è risolto grazie all’uso di algoritmi moderni di creazione dei piani. Il terzo caso in cui l’indice non è necessario sono i campi con un insieme limitato di valori - ad esempio, il campo che memorizza le informazioni sul sesso della persona e contiene solo due valori possibili - “F” e “M”; non ha senso indicizzare questo campo. Quindi, abbiamo considerato i principali vincoli per la creazione degli indici. Ora dovremmo coprire il problema di quando è necessario usare gli indici per ottenere un miglioramento delle prestazioni. Ci sono 3 casi principali in cui un campo deve essere indicizzato:

Quando questo campo è usato nelle condizioni di recupero nelle query
Quando i join delle tabelle usano questo campo
Quando questo campo è usato nell’istruzione di ordinamento ORDER BY Se il campo è applicato nel modo sopra menzionato, la creazione dell’indice per esso può portare a un miglioramento delle prestazioni della query.

Consideriamo una sintassi per la creazione degli indici. Ecco il formato completo del comando DDL che consente di creare indici:

CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);

L’espressione minima per creare l’indice è la seguente:

CREATE INDEX my_index ON Table_example(ID)

In questo esempio, l’indice con nome my_index viene creato per la tabella Table_example, e il campo ID è il campo indicizzato. L’indice è ascendente, cioè i valori in esso sono ordinati in modo crescente, così come non univoco, e significa che il campo ID può avere diversi valori identici. È certamente l’esempio più semplice di indice - il più comune. Come possiamo vedere dalla descrizione della sintassi, l’indice può contenere non uno, ma diversi campi. Tale indice viene usato quando le query vengono eseguite frequentemente e contengono una combinazione di campi indicizzati nelle condizioni di ricerca o ordinamento. Ad esempio, se abbiamo una tabella contenente i campi Cognome, Nome, Patronimico, tale indice verrà applicato quando si effettua la query che usa l’ordinamento per Cognome, Nome e Patronimico. In generale, non è necessario specificare le condizioni per tutti e 3 i campi applicati nell’indice per usare i suoi vantaggi. Se vogliamo ordinare il risultato della query, l’indice verrà usato nel caso in cui il primo campo nella condizione di ordinamento coincida con il primo campo nell’indice. Ad esempio, il nostro indice verrà applicato nel caso di ordinamento per Cognome e Nome.

Secondo la documentazione, per l’ottimizzazione dell’esecuzione di query contenenti nell’istruzione WHERE un join di campi con condizione OR, dovremmo usare non l’indice aggregato, ma diversi indici singoli per tutti i campi inclusi nella condizione OR.

Per quanto riguarda la questione dell’ordine di ordinamento degli indici, questo può essere ascendente o discendente. Perché abbiamo bisogno di diversi ordini di ordinamento? Ovviamente, per diversi tipi di ordinamento! Se desideriamo ordinare le persone per cognome in ordine ascendente, creiamo un indice ascendente (ASC), e se in ordine discendente (da Z a A) - allora discendente! Se vogliamo entrambi, dobbiamo creare entrambi gli indici.

Supporto dell’integrità referenziale tramite indici

C’è un’altra opzione nella definizione dell’indice: UNIQUE. Se la specifichiamo, l’indice consentirà di inserire nella tabella solo valori univoci. In realtà, questa è la base per l’implementazione delle chiavi univoche. Le chiavi univoche sono ampiamente utilizzate nei database. Cioè, la PK è una chiave-indice univoca, ma non ogni chiave univoca è una PK. Sopra abbiamo parlato solo della PK. Una chiave primaria è il tipo più comune di chiave univoca. Quando si crea una chiave primaria per la tabella, viene automaticamente creato un indice univoco. Gli viene assegnato un nome composto da RDB$PRIMARYNNN, dove NNN è un numero univoco sequenziale all’interno del database. Pertanto, due principali vincoli di integrità referenziale - una chiave univoca e una chiave primaria - sono realizzati grazie all’uso di un indice univoco. È ovvio che la nozione di unicità è incompatibile con la nozione di valore indefinito. In altre parole, non dovrebbero esserci valori di tipo NULL nei campi contenuti negli indici univoci. Prima di creare un indice univoco per un campo, è necessario impostare il vincolo NOT NULL. Se l’indice viene creato per dati già esistenti, al momento della creazione, il campo indicizzato verrà controllato per la presenza di eventuali valori ripetuti. Se ne contiene, ti sarà vietato creare l’indice.

Oltre ai vincoli di chiave univoca e primaria, il meccanismo degli indici è alla base dell’implementazione di un altro vincolo di integrità referenziale: una chiave esterna. Il vincolo di chiave esterna è impostato per uno o più campi di qualsiasi tabella e impedisce l’inserimento in questi campi di valori che non sono inclusi nella chiave primaria dell’altra tabella, quella padre. Per implementare la chiave esterna, cioè per eseguire il controllo se un valore esiste nella tabella padre, viene automaticamente creato un indice speciale. Il suo nome è RDB$FOREIGNNN, dove NNN è un numero univoco sequenziale all’interno del database.

Perché il meccanismo degli indici viene utilizzato per implementare i vincoli di integrità referenziale? Il fatto è che gli indici in InterBase sono in una posizione speciale e privilegiata - si dice che vengono eseguiti al di fuori del contesto delle transazioni. Questa è una proprietà molto importante. Parleremo delle transazioni più avanti, nel capitolo a loro dedicato. Ora menzioneremo solo che quando gli indici sono al di fuori delle transazioni, significa che tutti gli utenti che lavorano simultaneamente con i dati nella stessa tabella devono rispettare i vincoli di integrità referenziale.

Ottimizzazione della produttività degli indici

Nel titolo di questa parte possiamo trovare un paradosso: gli indici, come detto sopra, servono ad accelerare l’esecuzione delle query, e si scopre che devono anche essere ottimizzati! Ma cosa fare (tale è la vita) - qualcuno deve prendersi cura degli indici. Cosa succede agli indici? Perché “perdono forma”? Dovremo dire ancora una volta che gli indici sono implementati come un albero binario. E quando un nuovo record viene aggiunto (aggiornato, eliminato - come preferisci) alla tabella, viene aggiunto un nuovo ramo all’albero. Questi rami non vengono aggiunti al centro dell’albero, ma alle cime di altri rami. Gradualmente l’albero diventa sempre più ramificato (o sbilanciato) e la ricerca - meno efficace. La ricostruzione dell’albero o (in alcuni casi) il ricalcolo delle statistiche può migliorare la situazione.

Periodicamente è necessario ricreare l’indice per ripristinarne la produttività. La ricreazione dell’indice avviene nei seguenti casi:

Quando si ricostruisce l’indice usando il comando ALTER INDEX.
Quando si elimina e si ricrea l’indice usando i comandi DROP INDEX e CREATE INDEX.
Quando si esegue il backup e il ripristino da una copia di backup usando lo strumento gbak.

È inoltre possibile utilizzare il ricalcolo delle statistiche. Ma bisogna capire che questa operazione non cambia lo stato dell’indice, informa semplicemente l’ottimizzatore su informazioni precise riguardo al suo stato, consentendo di utilizzare correttamente questo indice. In altre parole, il ricalcolo delle statistiche non è una “cura” per l’indice, ma solo una diagnosi accurata del suo stato. Consideriamo tutti questi modi di ottimizzazione degli indici in maggiore dettaglio. L’uso del comando ALTER INDEX ha il seguente formato:

ALTER INDEX nome {ACTIVE | INACTIVE};

Qui nome è il nome dell’indice, e ACTIVE e INACTIVE - due stati dell’indice in cui può essere convertito usando il comando ALTER INDEX. Il parametro ACTIVE significa che l’indice è attivo e può essere applicato in tutte le query e procedure. Se imposti l’indice su INACTIVE, ciò comporterà la disconnessione del suo utilizzo. Per riorganizzare l’albero, devono essere eseguiti sequenzialmente due comandi:

ALTER INDEX nome INACTIVE; ALTER INDEX nome ACTIVE;

Pertanto, l’indice verrà ricostruito. L’uso di ALTER INDEX ha una serie di vincoli: non è possibile ricostruire gli indici utilizzati nelle chiavi primarie, univoche ed esterne; non è possibile ricostruire l’indice se è attualmente utilizzato da qualsiasi query; e inoltre, per modificare l’indice è necessario avere i diritti di amministratore (SYSDBA) o essere il creatore dell’indice dato.

La ricreazione dell’indice usando i comandi DROP INDEX e CREATE INDEX porta alla completa eliminazione dell’indice dal database e poi alla sua creazione da zero. La sintassi del comando DROP INDEX è ovvia:

DROP INDEX nome_indice;

Dopo l’eliminazione, è necessario creare l’indice con lo stesso nome e parametri usando il comando CREATE INDEX, la cui sintassi abbiamo già considerato. Il modo di ricostruire l’indice tramite la sua completa ricreazione ha vincoli simili a quelli per l’uso di ALTER INDEX.

Il terzo modo di ricostruire l’indice si basa sulla proprietà delle copie di backup dei database InterBase create dall’utilità gbak. Il fatto è che, durante il backup, i dati inclusi nell’indice non vengono salvati in una copia di backup, viene memorizzata solo la definizione dell’indice. Quando si ripristina da una copia di backup, l’indice viene ricreato. Se vuoi saperne di più sul backup, consulta il capitolo “Backup e ripristino da una copia di backup” (parte 4).

Il quarto modo per migliorare la produttività degli indici è raccogliere statistiche sugli indici usando il comando SET STATISTICS. La statistica della tabella è un valore nell’intervallo da 0 a 1, il cui valore dipende dal numero di record diversi nella tabella. L’ottimizzatore InterBase usa le statistiche per definire l’efficienza dell’applicazione di questo o quell’indice in una query. Quando il numero di record nella tabella può cambiare notevolmente (ad esempio, a causa di un gran numero di inserimenti o rimozioni), il ricalcolo delle statistiche può migliorare considerevolmente la produttività. Il comando di ricalcolo delle statistiche è il seguente:

SET STATISTICS INDEX nome;

Qui nome è il nome dell’indice per cui vengono ricalcolate le statistiche. Il ricalcolo delle statistiche non ricostruisce l’indice e pertanto è esente dalla maggior parte dei vincoli impostati per i modi sopra descritti di miglioramento della produttività, tranne che solo il creatore dell’indice o l’amministratore di sistema (l’utente con nome SYSDBA) può ricalcolare le statistiche. Statistiche corrette consentono all’ottimizzatore di prendere una decisione corretta sull’uso o meno di un determinato indice.

Abbiamo considerato alcuni modi per migliorare la produttività degli indici. Usando i comandi ALTER INDEX e DROP/CREATE INDEX, possiamo ricostruire qualsiasi indice tranne gli indici di sistema creati automaticamente, destinati a garantire l’integrità referenziale. Se desideri ricostruire questi indici, dovresti usare i comandi di modifica e creazione delle tabelle - ALTER TABLE e CREATE TABLE, poiché questi indici sono parte integrante delle chiavi delle tabelle.