Darstellung von Sparse-Daten in PostgreSQL

Ich nehme an, Sie denken an Sparse-Matrizen aus dem mathematischen Kontext:http://en.wikipedia. org/wiki/Sparse_matrix (Die dort beschriebenen Speichertechniken dienen der Speicherspeicherung (schnelle arithmetische Operationen), nicht der dauerhaften Speicherung (geringe Plattennutzung).

Da man auf diesen Matrizen in der Regel eher clientseitig als serverseitig operiert, ist ein SQL-ARRAY[] die beste Wahl!

Die Frage ist, wie man die Sparsity der Matrix ausnutzt. Hier die Ergebnisse einiger Untersuchungen.

Einrichtung:

• Postgres 8.4
• Matrizen mit 400 * 400 Elementen in doppelter Genauigkeit (8 Bytes) --> 1,28 MiB Rohgröße pro Matrix
• 33 % Nicht-Null-Elemente --> 427 KB effektive Größe pro Matrix
• gemittelt unter Verwendung von ~1000 verschiedenen zufällig bestückten Matrizen

Konkurrierende Methoden:

• Verlassen Sie sich auf die Automatik serverseitige Komprimierung von Spalten mit SET STORAGE MAIN oder EXTENDED.
• Speichern Sie nur die Nicht-Null-Elemente plus eine Bitmap (bit varying(xx) ) beschreibt, wo die Nicht-Null-Elemente in der Matrix zu finden sind. (Eine doppelte Genauigkeit ist 64-mal größer als ein Bit. Theoretisch (ohne Overheads) sollte diese Methode eine Verbesserung darstellen, wenn <=98% ungleich Null sind;-).) Serverseitige Komprimierung ist aktiviert.
• Ersetzen die Nullen in der Matrix mit NULL . (Die RDBMSs sind sehr effektiv beim Speichern von NULLen.) Die serverseitige Komprimierung ist aktiviert.

(Die Indizierung von Nicht-Null-Elementen mit einem 2. Index-ARRAY[] ist wenig erfolgsversprechend und daher nicht getestet.)

Ergebnisse:

• Automatische Komprimierung
  • kein zusätzlicher Implementierungsaufwand
  • kein reduzierter Netzwerkverkehr
  • minimaler Komprimierungsaufwand
  • Permanenter Speicher =39 % der Rohgröße
• Bitmap
  • akzeptabler Implementierungsaufwand
  • Netzwerkverkehr leicht zurückgegangen; auf Sparsamkeit angewiesen
  • Permanenter Speicher =33,9 % der Rohgröße
• Nullen durch NULLen ersetzen
  • etwas Implementierungsaufwand (die API muss wissen, wo und wie die NULLen im ARRAY[] gesetzt werden, während die INSERT-Abfrage erstellt wird)
  • keine Änderung des Netzwerkverkehrs
  • Permanenter Speicher =35 % der Rohgröße

Fazit:Beginnen Sie mit dem Speicherparameter EXTENDED/MAIN. Wenn Sie etwas Freizeit haben, untersuchen Sie Ihre Daten und verwenden Sie meinen Testaufbau mit Ihrem Sparsity-Level. Der Effekt ist jedoch möglicherweise geringer als erwartet.

Ich schlage vor, immer die Matrixserialisierung (z. B. Row-Major Order) plus zwei Integer-Spalten für die Matrixdimensionen NxM zu verwenden. Da die meisten APIs Text-SQL verwenden, sparen Sie viel Netzwerkverkehr und Clientspeicher für verschachtelte "ARRAY[ARRAY[..], ARRAY[..], ARRAY[..], ARRAY[..], ..]" !!!

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)
);

Fügen Sie dieselben Matrizen in alle Tabellen ein. Die konkreten Daten hängen von der jeweiligen Tabelle ab. Ändern Sie die Daten serverseitig nicht wegen ungenutzter, aber belegter Seiten. Oder machen Sie ein VAKUUM.

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;