Struttura dati per archiviare tabelle di database arbitrarie

Question

Mi piacerebbe progettare una struttura dati JVM (Java/Scala) che può essere utilizzata per rappresentare e archiviare il contenuto di tabelle di database relazionali arbitrarie. La struttura dei dati dovrebbe essere veloce (non troppo intensiva per il gc, cache-friendly) e efficiente in termini di memoria, quindi le tabelle più grandi possono essere contenute nella RAM.

Una soluzione efficiente in termini di memoria è quella di memorizzare ogni colonna separatamente in una matrice primitiva, ma sono preoccupato per la compatibilità della cache perché gli elementi nella stessa riga non vengono memorizzati insieme. Una riga con N colonne incorrerà in N cache miss, non importa quanto siano strette le colonne.

Un'altra soluzione consiste nel memorizzare ogni riga in un array di oggetti in cui ogni elemento rappresenta un campo e viene convertito nel tipo corretto al momento del recupero, ma ciò richiede la memorizzazione di tipi numerici nella loro forma scatolata, quindi non è molto efficiente in termini di memoria. E probabilmente non è nemmeno efficiente.

Un'altra soluzione consiste nel layout dei dati di ogni riga in un array di byte nello stesso modo in cui i database reali serializzano le loro righe, utilizzando solo il numero di byte necessario. Questo è efficiente per la cache e la memoria efficiente, ma sono preoccupato per il costo di serializzazione/de-serializzazione su ogni accesso.

Qual è il modo migliore?

Answer 1

Qual è lo scopo di questo? Probabilmente è meglio memorizzare semplicemente i dati che si recuperano dal database (come gli oggetti a cui lo si indirizza) in una sorta di livello di memorizzazione nella cache come EhCache, OSCache, memcache, ecc., Piuttosto che reinventare la ruota.

Answer 2

Perché non utilizzare hsqldb o h2?

Entrambi supportano la modalità in memoria e sono Java puri. Ti costringono ad usare SQL per accedere ma dall'altra parte, non devi implementare il tuo join.

Entrambi sono open source, quindi è anche possibile utilizzarlo come riferimento per le prestazioni e vedere se farlo da solo per colonna/per riga la struttura dei dati sarebbe più veloce e vale la pena.

Answer 3

Una quarta soluzione consiste nel memorizzare i dati di ogni riga come stringhe anziché come array di byte. Ciò potrebbe evitare i costi di serializzazione in nella maggior parte dei casi, a condizione che la maggior parte dei dati siano stringhe.

Questo sarà anche più facile da eseguire il debug e sarà indipendente dalla piattaforma. Ovviamente ha alcune limitazioni: ad es. un float non può essere rappresentato così com'è, ma può essere memorizzato in qualcosa di simile a un formato SQL DECIMAL.

Qualsiasi soluzione sarà un compromesso.

EDIT Tuttavia, preferirei la soluzione di array di byte per il tuo caso: un array di byte per riga. Questo dovrebbe essere più adatto alla cache per le file a dimensione fissa. Ma allora dovresti anche fornire una soluzione per le file di dimensioni variabili. Un linguaggio di basso livello sembra adattarsi meglio a tale compito, in C si potrebbero definire due formati: righe di dimensioni fisse in cui i metadati della tabella contengono colonne-offset (es. Colonna 1: byte 0..31, colonna 2: byte 32..127 ecc.) e un secondo formato di riga di dimensioni variabili, dove le righe contengono le dimensioni delle colonne (ad esempio i byte 1..3 contengono le dimensioni, il seguente numero di byte contiene i dati, quindi altri 4 byte contengono le dimensioni, i seguenti dati e così via).