Rappresentare Sparse dati in PostgreSQL

Question

Qual è il modo migliore per rappresentare una matrice di dati sparsi in PostgreSQL? I due metodi evidenti che vedo sono:

1. Memorizzare i dati in una tabella di un singolo con una colonna separata per ogni caratteristica immaginabile (potenzialmente milioni), ma con un valore predefinito è NULL per le funzioni non utilizzate. Questo è concettualmente molto semplice, ma so che con la maggior parte delle implementazioni RDM, che questo è in genere molto inefficiente, dal momento che i valori NULL prende ususually up alcuni spazio. Tuttavia, ho letto un articolo (non riesce a trovare il suo legame purtroppo) che ha sostenuto PG non occupa i dati per i valori NULL, che lo rende più adatto per la memorizzazione di dati sparsi.

2. Crea "riga" separata e tabelle "colonna", così come una tabella intermedia per collegarli e memorizzare il valore per la colonna a quella riga. Credo che questa sia la soluzione RDMS più tradizionale, ma c'è una maggiore complessità e le spese generali ad esso associati.

Ho trovato anche PostgreDynamic , che pretende di migliore supporto dati sparsi, ma non voglio passare tutta la mia server di database ad un bivio PG solo per questa funzione.

Ci sono altre soluzioni? Quale dovrei usare?

Answer 1

alcune soluzioni in mente,

1) Separare le vostre caratteristiche in gruppi che di solito sono impostati insieme, creare una tabella per ogni gruppo con un uno-a-uno chiave esterna per i dati principali, unire solo su tavoli che serve quando l'esecuzione di query

2) Utilizzare l'EAV anti-modello, creare una tabella 'funzione' con un campo chiave esterna dalla tabella primaria, così come un nome di campo e una colonna valore e memorizzare le caratteristiche come righe di quel tavolo, invece di come attributi nella tabella primaria

3) Analogamente a quanto PostgreDynamic fa, creare una tabella per ogni 'colonna' nella tabella primaria (che utilizzano uno spazio dei nomi separato per quelle tabelle), e creare funzioni per semplificare (così come in modo efficiente indice) l'accesso e l'aggiornamento i dati di tali tabelle

4) creare una colonna nei dati primari utilizzando XML, o VARCHAR, e memorizzare alcune formato di testo strutturato all'interno di esso che rappresenta i dati, creare indici sui dati con gli indici funzionali, funzioni di scrittura per aggiornare i dati (o utilizzare il codice XML funzioni, se si utilizza tale formato)

5) utilizzare il contrib / hstore modulo per creare una colonna di tipo hstore che può contenere coppie di valori-chiave, e può essere indicizzato e aggiornato

6) vivono con un sacco di campi vuoti

Answer 2

sto supponendo che stai pensando di matrici sparse dal contesto matematico: http://en.wikipedia.org/wiki/Sparse_matrix (Le tecniche di memorizzazione descritte sono per memoria (operazione aritmetica veloce), non memorizzazione persistente (scarso utilizzo del disco).)

Dal momento che uno di solito non funzionano su questo matrici sul lato client piuttosto che su un lato server SQL-ARRAY [] è la scelta migliore!

La domanda è: come approfittare della scarsità della matrice? Ecco i risultati di alcune indagini.

Configurazione:

• Postgres 8.4
• Matrici w / 400 * 400 elementi a doppia precisione (8 byte) -> 1.28MiB dimensioni greggio a matrice
• 33% non zero elementi -> 427kiB dimensione effettiva a matrice
• media utilizzando ~ 1000 diverse matrici popolate casuali

Competere metodi:

• Contare sulla lato server automatico compressione di colonne con SET memoria principale o esteso.
• Solo memorizzare i non-zero elementi più un bitmap (bit varying(xx)) descrivono dove localizzare i non-zero elementi nella matrice. (Una doppia precisione è 64 volte più grande di un bit. In teoria (ignorando spese generali) questo metodo dovrebbe essere un miglioramento se <= 98% sono non-zero ;-).) Compressione lato server viene attivato.
• sostituisci gli zeri nella matrice con NULL . (I RDBMS sono molto efficaci nel NULL memorizzazione.) Compressione lato server viene attivato.

(indicizzazione dei non-zero elementi usando un secondo indice ARRAY [] Non è molto promettente e per questo non testato).

Risultati:

• Automatic compressione
  • Non ci sono sforzi di attuazione aggiuntivo
  • no ridotto il traffico di rete
  • sovraccarico compressione minima
  • memoria persistente = 39% della dimensione grezza
• Bitmap
  • sforzo implementazione accettabile
  • il traffico di rete leggermente diminuita; dipende sparsity
  • storage persistente = 33,9% della dimensione grezza
• Sostituire gli zeri con i NULL
  • un certo sforzo di implementazione (esigenze API per sapere dove e come impostare le NULL nella matrice [] durante la costruzione della query INSERT)
  • nessun cambiamento nel traffico di rete
  • memoria persistente = 35% della dimensione grezza

Conclusione: Inizia con il parametro di memorizzazione EXTENDED / MAIN. Se avete un po 'di tempo libero indagare i dati e usare la mia configurazione di prova con il vostro livello di scarsità. Ma l'effetto può essere inferiore a quella prevista.

Suggerisco sempre di utilizzare la serializzazione matrice (ordine esempio Row-maggiore) più due colonne interi per le dimensioni della matrice NxM. Dal momento che la maggior parte delle API utilizzano SQL testuale si sta salvando un sacco di traffico di rete e della memoria client per "ARRAY [ARRAY [..], ARRAY [..], ARRAY [..], ARRAY [..], ..]" annidata !!!

Tebas

---

CREATE TABLE _testschema.matrix_dense
(
  matdata double precision[]
);
ALTER TABLE _testschema.matrix_dense ALTER COLUMN matdata SET STORAGE EXTERN;


CREATE TABLE _testschema.matrix_sparse_autocompressed
(
  matdata double precision[]
);

CREATE TABLE _testschema.matrix_sparse_bitmap
(
  matdata double precision[]
  bitmap bit varying(8000000)
);

Inserisci le stesse matrici in tutte le tabelle. I dati concreti dipende dalla certa tavolo. Non modificare i dati sul lato server a causa di pagine inutilizzate, ma allocate. O fare il vuoto.

SELECT 
pg_total_relation_size('_testschema.matrix_dense') AS dense, 
pg_total_relation_size('_testschema.matrix_sparse_autocompressed') AS autocompressed, 
pg_total_relation_size('_testschema.matrix_sparse_bitmap') AS bitmap;

Answer 3

Un valore NULL occuperà spazio quando è NULL. Ci vorrà up un bit in una bitmap nell'intestazione tupla, ma che ci sarà a prescindere.

Tuttavia, il sistema non può che fare con milioni di colonne, periodo. C'è un massimo teorico di un po 'più di mille, IIRC, ma davvero non si vuole arrivare a tanto.

Se davvero bisogno che molti, in una singola tabella, è necessario andare al metodo EAV, che è fondamentalmente quello che stai dicendo in (2).

Se ogni voce ha solo relativamente pochi tasti, vi consiglio di guardare ai moduli contrib "hstore", che consente di archiviare questo tipo di dati in modo molto efficiente, come una terza opzione. E 'stato migliorato ulteriormente nella prossima versione 9.0, quindi se siete un po' lontano dalla distribuzione di produzione, si potrebbe desiderare di guardare direttamente quello. Tuttavia, vale la pena in 8.4 pure. E lo fa sostenere alcune ricerche basate su indici abbastanza efficienti. Sicuramente vale la pena di essere esaminata.

Answer 4

So che questo è un vecchio thread, ma Madlib fornisce un tipo di vettore sparse per Postgres, insieme a molti apprendimento automatico e metodi statistici.