Ha senso & # 8220; fake & # 8221; indici bitmap?

Question

Sto pianificando un software che sia al cuore un'applicazione OLAP (aiuta ad analizzare i dati di misurazione) e avrà un qualche tipo di schema a stella per il suo database, perché i valori memorizzati verranno esaminati da diverse angolazioni (tempo, origine, tipo ecc.) e le richieste richiederanno dati aggregati lungo queste dimensioni. Le query tendono a fornire molte righe (fino a circa 100.000).

Le mie ricerche su questo argomento (vedi anche my domanda qui ) sembra indicare che gli indici bitmap sono un buon modo per cercare i dati come sto pianificando. Tuttavia, voglio supportare più motori db, alcuni dei quali non offrono indici bitmap sulle loro tabelle (in particolare, MySQL).

Ora, posso certamente costruire e mantenere il mio indice bitmap e usarlo per cercare gli ID di riga che puntano alla tabella dei fatti. Tuttavia, sospetto che questo annullerà l'intero scopo dell'indice, perché il database cercherà ancora gli ID di riga in un B-Tree. Qualcuno con un background teorico più profondo o più esperienza può dirmi se guadagno ancora qualcosa, come non dover fare JOIN lenti nelle tabelle delle dimensioni?

Gradirei anche suggerimenti su cosa devo valutare se la risposta non è semplice.

Answer 1

Alcuni motori DB che non supportano direttamente gli indici bitmap hanno ancora ottimizzazioni a stella che possono eseguire questo tipo di query senza colpire la tabella dei fatti. SQL Server, ad esempio, ha una funzionalità chiamata Index Intersection che fa qualcosa di simile costruendo bitmap al volo per fare la risoluzione. Microsoft afferma che le prestazioni di questo sono paragonabili agli indici bitmap. Vedi Questo post per un po 'di fan-out su questo argomento.

Non sono sicuro se MySQL lo fa, ma Postgresql lo fa sicuramente. IIRC alcune delle varianti (Greenplum, penso) supportano anche direttamente gli indici bitmap e si parlava di incorporarlo nel motore DB principale. Non ricordo se questo è stato ancora fatto.

Penso che scoprirai che la maggior parte delle piattaforme DBMS moderne offrono ottimizzazioni di query a stella di un tipo o di un altro, quindi probabilmente non dovrai reinventare la ruota. Potresti trovarne uno o due che non riescono a farlo, ma hai sempre la possibilità di non supportarli.

Answer 2

Ho avuto fortuna con gli indici bitmap durante la manipolazione di molti dati in memoria utilizzando strutture di dati personalizzate, ma sono un po 'scomodi da implementare su un database di terze parti che non ha un buon (postgresql-like ) API per l'estensione delle strutture dell'indice.

In generale, dato che cercherai comunque attraverso un indice B-Tree non otterrai nulla se la mia esperienza è una guida.

Quindi no.

Se la tua applicazione è intrinsecamente OLAP in natura e hai un piccolo numero di dimensioni che si raggruppano naturalmente in intervalli ordinati e hai davvero bisogno di cambiare gli asintotici del tuo problema, potresti prendere in considerazione la costruzione di una 'tabella sommatoria' come puoi interrogarlo per qualsiasi risposta gerarchica con 2 ^ d operazioni e puoi ammortizzarlo se stai facendo una serie di query correlate.

Un esempio in 2d con coordinate xey, in cui sei interessato alla somma in un intervallo da (x1, y1) a (x2, y2).

Memorizzati separatamente dovresti sommare un numero di voci proporzionale all'area.

Usando un sommabile, per ogni posizione (x, y) non memorizzare il valore di quella posizione, ma invece memorizzare la somma della regione da (0,0) a (x, y).

Quindi puoi rispondere a qualsiasi query sull'intervallo chiedendo:

somma (x2, y2) - somma (x1, y2) - somma (x2, y1) + somma (x1, y1)

una quantità costante di overhead (beh, logaritmico nella dimensione del set di dati, supponendo che tu abbia un indice su xey che lo stia memorizzando in SQL)

Questo ovviamente si interrompe se si hanno attributi complicati che non si dividono in intervalli, ma in grado di gestire semplici indici lessicografici, date, ecc.