Indice bitmap - Bitmap index

Un indice bitmap è un tipo speciale di indice di database che utilizza bitmap .

Gli indici bitmap sono stati tradizionalmente considerati funzionare bene per le colonne a bassa cardinalità , che hanno un numero modesto di valori distinti, assoluto o relativo al numero di record che contengono i dati. Il caso estremo di cardinalità bassa sono i dati booleani (ad esempio, un residente in una città ha accesso a Internet?), Che ha due valori, Vero e Falso. Gli indici bitmap utilizzano matrici di bit (comunemente chiamate bitmap) e rispondono alle query eseguendo operazioni logiche bit a bit su queste bitmap. Gli indici bitmap hanno uno spazio significativo e un vantaggio prestazionale rispetto ad altre strutture per l'interrogazione di tali dati. Il loro svantaggio è che sono meno efficienti dei tradizionali indici B-tree per colonne i cui dati vengono aggiornati frequentemente: di conseguenza, sono più spesso impiegati in sistemi di sola lettura specializzati per query veloci, ad es. Data warehouse e generalmente inadatti per applicazioni per l' elaborazione delle transazioni online .

Alcuni ricercatori sostengono che gli indici bitmap sono utili anche per dati con cardinalità moderata o addirittura elevata (ad es. Dati con valore univoco) a cui si accede in sola lettura e le query accedono a più colonne indicizzate bitmap utilizzando AND , OR o XOR operatori ampiamente.

Gli indici bitmap sono utili anche nelle applicazioni di data warehousing per unire una tabella dei fatti di grandi dimensioni a tabelle di dimensioni più piccole come quelle disposte in uno schema a stella .

Esempio

Continuando l'esempio di accesso a Internet, un indice bitmap può essere logicamente visualizzato come segue:

Identificatore HasInternet Bitmap
Y N
1 sì 1 0
2 No 0 1
3 No 0 1
4 Non specificato 0 0
5 sì 1 0

A sinistra, Identifier si riferisce al numero univoco assegnato a ciascun residente, HasInternet è il dato da indicizzare, il contenuto dell'indice bitmap è mostrato come due colonne sotto l'intestazione bitmap . Ogni colonna nell'illustrazione a sinistra è una bitmap nell'indice bitmap. In questo caso, ci sono due bitmap, una per "ha internet" Sì e uno per "ha internet" No . È facile vedere che ogni bit nella bitmap Y mostra se una determinata riga si riferisce a una persona che ha accesso a Internet. Questa è la forma più semplice di indice bitmap. La maggior parte delle colonne avrà valori più distinti. Ad esempio, è probabile che l'importo delle vendite abbia un numero molto maggiore di valori distinti. Anche le variazioni sull'indice bitmap possono indicizzare efficacemente questi dati. Rivediamo brevemente tre di queste variazioni.

Nota: molti dei riferimenti qui citati sono esaminati in ( John Wu (2007) ). Per coloro che potrebbero essere interessati a sperimentare alcune delle idee qui menzionate, molte di esse sono implementate in software open source come FastBit, la libreria Lemur Bitmap Index C ++, la libreria Java Roaring Bitmap e il sistema Apache Hive Data Warehouse.

Compressione

Per ragioni storiche, la compressione bitmap e la compressione elenco invertito sono state sviluppate come linee di ricerca separate e solo successivamente sono state riconosciute come soluzioni essenzialmente dello stesso problema.

Il software può comprimere ogni bitmap in un indice bitmap per risparmiare spazio. C'è stata una notevole quantità di lavoro su questo argomento. Sebbene ci siano eccezioni come le bitmap ruggenti, gli algoritmi di compressione bitmap utilizzano in genere la codifica della lunghezza di esecuzione , come il codice bitmap allineato a byte, il codice ibrido allineato a parole, la compressione ibrida allineata con parole partizionate (PWAH), la parola elenco posizioni Aligned Hybrid, Compressed Adaptive Index (COMPAX), Enhanced Word-Aligned Hybrid (EWAH) e COmpressed 'N' Composable Integer SEt. Questi metodi di compressione richiedono uno sforzo minimo per comprimere e decomprimere. Ancora più importante, le bitmap compresse con BBC, WAH, COMPAX, PLWAH, EWAH e CONCISE possono partecipare direttamente alle operazioni bit per bit senza decompressione. Ciò conferisce loro notevoli vantaggi rispetto alle tecniche di compressione generiche come LZ77 . La compressione BBC e le sue derivate vengono utilizzate in un sistema di gestione di database commerciale . BBC è efficace sia nel ridurre le dimensioni degli indici che nel mantenere le prestazioni delle query . BBC codifica le bitmap in byte , mentre WAH codifica in parole, adattandosi meglio alle CPU attuali . "Sia sui dati sintetici che sui dati delle applicazioni reali, i nuovi schemi di parole allineate utilizzano solo il 50% in più di spazio, ma eseguono operazioni logiche sui dati compressi 12 volte più velocemente della BBC". È stato segnalato che le bitmap PLWAH occupano il 50% dello spazio di archiviazione consumato dalle bitmap WAH e offrono prestazioni fino al 20% più veloci sulle operazioni logiche . Considerazioni simili possono essere fatte per CONCISE e Enhanced Word-Aligned Hybrid.

Le prestazioni di schemi come BBC, WAH, PLWAH, EWAH, COMPAX e CONCISE dipendono dall'ordine delle righe. Un semplice ordinamento lessicografico può dividere la dimensione dell'indice per 9 e rendere gli indici molte volte più veloci. Più grande è la tabella, più importante è ordinare le righe. Sono state proposte anche tecniche di rimescolamento per ottenere gli stessi risultati dell'ordinamento durante l'indicizzazione dei dati in streaming.

Codifica

Gli indici bitmap di base utilizzano una bitmap per ogni valore distinto. È possibile ridurre il numero di bitmap utilizzate utilizzando un metodo di codifica diverso . Ad esempio, è possibile codificare valori distinti C utilizzando bitmap log (C) con codifica binaria .

Ciò riduce il numero di bitmap, risparmiando ulteriore spazio, ma per rispondere a qualsiasi domanda, è necessario accedere alla maggior parte delle bitmap. Ciò lo rende potenzialmente non efficace quanto la scansione di una proiezione verticale dei dati di base, nota anche come vista materializzata o indice di proiezione. Trovare il metodo di codifica ottimale che bilanci le prestazioni (arbitrarie) delle query, le dimensioni dell'indice e la manutenzione dell'indice rimane una sfida.

Senza considerare la compressione, Chan e Ioannidis hanno analizzato una classe di metodi di codifica multicomponente e sono giunti alla conclusione che la codifica a due componenti si trova al vertice della curva delle prestazioni rispetto alla dimensione dell'indice e quindi rappresenta il miglior compromesso tra dimensione dell'indice e prestazioni delle query.

Binning

Per le colonne ad alta cardinalità, è utile raggruppare i valori, dove ogni bin copre più valori e costruire le bitmap per rappresentare i valori in ogni bin. Questo approccio riduce il numero di bitmap utilizzate indipendentemente dal metodo di codifica. Tuttavia, gli indici raggruppati possono rispondere solo ad alcune query senza esaminare i dati di base. Ad esempio, se un bin copre l'intervallo da 0,1 a 0,2, quando l'utente richiede tutti i valori inferiori a 0,15, tutte le righe che rientrano nel bin sono possibili hit e devono essere controllate per verificare se sono effettivamente inferiori a 0,15 . Il processo di controllo dei dati di base è noto come controllo del candidato. Nella maggior parte dei casi, il tempo utilizzato dal controllo del candidato è notevolmente più lungo del tempo necessario per lavorare con l'indice bitmap. Pertanto, gli indici raggruppati mostrano prestazioni irregolari. Possono essere molto veloci per alcune query, ma molto più lenti se la query non corrisponde esattamente a un bin.

Storia

Il concetto di indice bitmap è stato introdotto per la prima volta dal professor Israel Spiegler e Rafi Maayan nella loro ricerca "Storage and Retrieval Considerations of Binary Data Bases", pubblicata nel 1985. Il primo prodotto di database commerciale a implementare un indice bitmap è stato Computer Corporation of America's Model 204 . Patrick O'Neil ha pubblicato un documento su questa implementazione nel 1987. Questa implementazione è un ibrido tra l'indice bitmap di base (senza compressione) e l'elenco degli identificatori di riga (elenco RID). Nel complesso, l'indice è organizzato come un albero B + . Quando la cardinalità della colonna è bassa, ogni nodo foglia dell'albero B conterrà un lungo elenco di RID. In questo caso, richiede meno spazio per rappresentare gli elenchi RID come bitmap. Poiché ogni bitmap rappresenta un valore distinto, questo è l'indice bitmap di base. Con l'aumentare della cardinalità della colonna, ogni bitmap diventa scarsa e potrebbe richiedere più spazio su disco per memorizzare le bitmap piuttosto che per memorizzare lo stesso contenuto degli elenchi RID. In questo caso, passa a utilizzare gli elenchi RID, il che lo rende un indice albero B + .

Bitmap in memoria

Uno dei motivi principali per l'utilizzo degli indici bitmap è che i risultati intermedi prodotti da essi sono anch'essi bitmap e possono essere riutilizzati in modo efficiente in ulteriori operazioni per rispondere a query più complesse. Molti linguaggi di programmazione lo supportano come una struttura dati ad array di bit. Ad esempio, Java ha la BitSet classe.

Alcuni sistemi di database che non offrono indici bitmap persistenti utilizzano bitmap internamente per accelerare l'elaborazione delle query. Ad esempio, PostgreSQL versione 8.1 e successive implementano un'ottimizzazione della "scansione dell'indice bitmap" per accelerare operazioni logiche arbitrariamente complesse tra gli indici disponibili su una singola tabella.

Per le tabelle con molte colonne, il numero totale di indici distinti per soddisfare tutte le query possibili (con condizioni di filtro di uguaglianza su uno dei campi) cresce molto velocemente, essendo definito da questa formula:

.

Una scansione dell'indice bitmap combina espressioni su indici diversi, richiedendo quindi un solo indice per colonna per supportare tutte le query possibili su una tabella.

L'applicazione di questa strategia di accesso agli indici B-tree può anche combinare query di intervallo su più colonne. In questo approccio, viene creata una bitmap in memoria temporanea con un bit per ogni riga della tabella (1  MB può quindi memorizzare oltre 8 milioni di voci). Successivamente, i risultati di ogni indice vengono combinati nella bitmap utilizzando operazioni bit per bit . Dopo che tutte le condizioni sono state valutate, la bitmap contiene un "1" per le righe che corrispondono all'espressione. Infine, la bitmap viene attraversata e vengono recuperate le righe corrispondenti. Oltre a combinare in modo efficiente gli indici, questo migliora anche la località di riferimento degli accessi alle tabelle, poiché tutte le righe vengono recuperate in sequenza dalla tabella principale. La bitmap interna viene eliminata dopo la query. Se sono presenti troppe righe nella tabella per utilizzare 1 bit per riga, viene invece creata una bitmap "con perdita", con un singolo bit per pagina del disco. In questo caso, la bitmap viene utilizzata solo per determinare quali pagine recuperare; i criteri di filtro vengono quindi applicati a tutte le righe nelle pagine corrispondenti.

Riferimenti

Appunti
Bibliografia