Representerar Sparse Data i PostgreSQL

Jag antar att du tänker på glesa matriser från matematisk kontext:http://en.wikipedia. org/wiki/Sparse_matrix (De lagringstekniker som beskrivs där är för minneslagring (snabb aritmetisk operation), inte persistent lagring (låg diskanvändning).)

Eftersom man vanligtvis använder denna matris på klientsidan snarare än på serversidan är en SQL-ARRAY[] det bästa valet!

Frågan är hur man drar fördel av glesheten i matrisen? Här resultaten från några undersökningar.

Inställningar:

Postgres 8.4
Matriser med 400*400 element i dubbel precision (8 byte) --> 1,28 MB råstorlek per matris
33 % icke-noll element --> 427 kB effektiv storlek per matris
genomsnittligt med ~1000 olika slumpmässigt befolkade matriser

Konkurrerande metoder:

Förlita dig på automatiken komprimering på serversidan kolumner med SET STORAGE MAIN eller EXTENDED.
Lagra bara element som inte är noll plus en bitmapp (bit varying(xx) ) som beskriver var man ska lokalisera elementen som inte är noll i matrisen. (En dubbel precision är 64 gånger större än en bit. I teorin (om man ignorerar omkostnader) borde denna metod vara en förbättring om <=98 % är icke-noll;-).) Serversidans komprimering är aktiverad.
Ersätt nollorna i matrisen med NULL . (RDBMS:erna är mycket effektiva för att lagra NULLs.) Komprimering på serversidan är aktiverad.

(Indexering av element som inte är noll med hjälp av en 2nd index-ARRAY[] är inte särskilt lovande och därför inte testad.)

Resultat:

Automatisk komprimering
- inga extra implementeringsinsatser
- ingen minskad nätverkstrafik
- minimal kompressionskostnad
- beständig lagring =39 % av råstorleken
Bitmapp
- acceptabel implementeringsansträngning
- nätverkstrafiken minskade något; beroende av gleshet
- beständig lagring =33,9 % av råstorleken
Ersätt nollor med NULL
- viss implementeringsansträngning (API behöver veta var och hur man ställer in NULL i ARRAY[] medan INSERT-frågan konstrueras)
- ingen förändring av nätverkstrafiken
- beständig lagring =35 % av råstorleken

Slutsats:Börja med parametern EXTENDED/MAIN lagring. Om du har lite ledig tid undersök dina data och använd min testuppsättning med din sparsamhetsnivå. Men effekten kan bli lägre än du förväntar dig.

Jag föreslår att du alltid använder matrisen serialisering (t.ex. rad-storordning) plus två heltalskolumner för matrisdimensionerna NxM. Eftersom de flesta API:er använder textbaserad SQL sparar du mycket nätverkstrafik och klientminne för kapslade "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)
);

Infoga samma matriser i alla tabeller. De konkreta uppgifterna beror på den specifika tabellen. Ändra inte data på serversidan på grund av oanvända men tilldelade sidor. Eller gör en 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;