L'uso di indici ed eseguire scansioni di tabelle sono due approcci fondamentali per l'accesso ai dati in un database, ciascuno con distinti compromessi a seconda della situazione.
Un indice in un database è una struttura di dati che consente una ricerca più rapida consentendo al sistema di individuare rapidamente le righe senza scansionare tutte le righe nella tabella. La maggior parte dei database relazionali utilizza le strutture di albero B+ per gli indici, che organizzano chiavi e puntatori in forma di albero. Ciò consente ricerche, inserzioni e eliminazioni nella complessità del tempo logaritmico $$ O (\ log n) $$, che in genere è molto più veloce della scansione dell'intera tabella con una complessità di $$ o (n) $$. Gli indici possono essere raggruppati o non cluster, con indici raggruppati che memorizzano i dati in ordine fisicamente ordinato, migliorando le prestazioni della scansione dell'intervallo al costo delle spese generali extra sulle modifiche dei dati. Gli indici possono anche essere compositi, parziali, filtrati o basati su hash, sintonizzati per modelli di query specifici.
Al contrario, una scansione della tabella (o una tabella completa) legge ogni riga nella tabella in sequenza, indipendentemente dalla selettività della query. Ciò comporta la scansione di tutti i blocchi di dati della tabella ed è spesso considerato il metodo di accesso più costoso perché elabora più dati del necessario. Tuttavia, le scansioni delle tabelle possono funzionare bene in alcuni casi. Ad esempio, quando le domande recuperano una grande percentuale di righe, il sovraccarico dell'uso di un indice (che spesso richiede ricerche aggiuntive per le righe effettive) può superare il costo della scansione dell'intera tabella una volta. Le scansioni delle tabelle possono utilizzare letture multi-blocco, che consentono di leggere grandi blocchi di dati con meno operazioni I/O, riducendo così la latenza rispetto alla lettura di molti singoli blocchi richiesti casualmente dalle scansioni indici.
Un importante compromesso prevede la selettività e le dimensioni del set di dati restituiti dalla query. Se la query filtra fino a un numero limitato di righe (alta selettività), gli indici generalmente superano le scansioni della tabella perché devono solo accedere ai dati rilevanti. Ma con l'aumentare della percentuale di righe, il costo delle scansioni dell'indice aumenta poiché potrebbero essere necessarie più ricerche chiave e il motore del database deve eseguire ulteriori operazioni di I/O casuali. Ad una certa soglia, spesso circa il 10-20% delle righe della tabella ma dipende dalla larghezza dei dati e dall'hardware, una scansione della tabella completa diventa più efficiente. Questo perché i costi di scansione rimangono costanti indipendentemente dalla selettività, semplicemente leggendo la tabella in sequenza una volta.
Le scansioni indici in genere leggono meno pagine rispetto a una tabella quando le colonne coperte sono meno o più compatte rispetto alle righe della tabella completa. Ad esempio, un indice potrebbe includere solo le colonne indicizzate senza i dati della riga della tabella completa, rendendolo più sottile e consentendo a più righe di adattarsi a ciascuna pagina del database. Ciò riduce gli sovraccarichi I/O durante la scansione dell'indice rispetto alla scansione degli interi dati della tabella. Inoltre, alcuni indici possono essere filtrati (indici parziali) per escludere le righe irrilevanti, riducendo ulteriormente l'impronta di scansione.
D'altra parte, le scansioni della tabella completa scrivono meno onere sul lato di manutenzione del database. Gli indici introducono le spese generali durante le operazioni di modifica dei dati come inserto, aggiornamento ed eliminazione. Ogni modifica alla tabella richiede l'aggiornamento degli indici, a volte portando ad un aumento della latenza di scrittura e spese generali di archiviazione, in particolare se esistono molti indici sulla tabella. Questo sovraccarico può anche influenzare la concorrenza e portare alla contesa in ambienti di scrittura pesante. Pertanto, le scansioni della tabella, che leggono semplicemente i dati nel suo ordine naturale senza ulteriore manutenzione della struttura, evitano questo costo.
Un'altra considerazione importante è l'effetto della memorizzazione nella cache e delle caratteristiche hardware. Le scansioni della tabella beneficiano dell'I/O sequenziale e del prefetching, consentendo al sistema di leggere più blocchi contigui in modo efficiente, spesso dalla memoria se memorizzata nella cache. Al contrario, le scansioni dell'indice incorporano I/O casuali per recuperare blocchi di dati disparati, soprattutto se la scansione dell'indice deve cercare puntatori di riga nella memoria di heap. Ciò può rendere le scansioni degli indici più lenti sui sistemi con prestazioni I/O casuali più lente, sebbene SSD e pool di memoria di grandi dimensioni rischiano questo divario. La situazione può anche dipendere da specifiche come il parallelismo e le capacità multi-threading del motore di database, in cui le scansioni delle tabelle parallele possono aumentare significativamente la throughput.
Inoltre, la frammentazione interna e il layout di stoccaggio fisico influenzano i compromessi delle prestazioni. Le scansioni delle tabelle su tabelle organizzate con heap potrebbero soffrire di record inoltrati, in cui le righe sono passate a diverse pagine a causa di aggiornamenti, peggioramento dell'efficienza di scansione. Gli indici cluster, che archiviano i dati ordinati per chiave, possono evitare questo problema e talvolta effettuano una "scansione della tabella" equivalente a una scansione indice cluster. Tuttavia, i benefici derivano dal costo di costosi riordini delle righe durante la riduzione dei dati pesanti.
Dal punto di vista dell'ottimizzatore di query, la decisione tra una scansione indice e una scansione della tabella viene in genere presa mediante modelli di stima basati sui costi, tenendo conto delle statistiche sulla distribuzione dei dati, sui conteggi delle righe e sui costi hardware. L'ottimizzatore bilancia CPU, I/O e costi di memoria per scegliere il percorso di accesso più efficiente. Queste decisioni possono essere influenzate da fattori come la memoria disponibile, lo stato di memorizzazione nella cache e i modelli di query. Non esiste una soglia fissa tra quando usare l'uno o l'altro; Il punto crossover varia per sistema e carico di lavoro.
In sintesi, i compromessi tra l'uso di indici e scansioni di tabelle includono:
- Performance vs. Volume dei dati: indici superano quando si filtrano in poche righe; Le scansioni della tabella possono essere migliori per il recupero dei dati di grandi dimensioni.
- Modelli I/O: le scansioni dell'indice causano letture casuali di I/O; Le scansioni della tabella beneficiano di I/O sequenziali e letture multi-blocco.
- Overhead di manutenzione: gli indici aumentano i costi di operazione di scrittura dovuti agli aggiornamenti sulle strutture dell'indice; Le scansioni delle tabelle non lo sostengono.
- Efficienza di archiviazione: gli indici possono essere compatti coprendo meno colonne; Le scansioni della tabella elaborano righe complete e potenzialmente più dati.
- Effetti di memorizzazione nella cache: le scansioni della tabella possono utilizzare la memorizzazione in modo efficace della memorizzazione nella cache dei dati, in particolare con letture sequenziali di grandi dimensioni; Le scansioni dell'indice potrebbero non beneficiare di tanto a causa dell'accesso casuale.
- Decisione ottimizzatore: ottimizzatori di query basati sui costi scelgono dinamicamente tra queste opzioni in base alle statistiche sulle query e alle specifiche del carico di lavoro.
- Impatto del layout dei dati: le tabelle di heap possono sostenere sanzioni come i record inoltrati durante le scansioni; Gli indici cluster organizzano fisicamente i dati ma aumentano i costi di aggiornamento.