Repræsentation af sparsomme data i PostgreSQL

Jeg går ud fra, at du tænker på sparsomme matricer fra matematisk kontekst:http://en.wikipedia. org/wiki/Sparse_matrix (De beskrevne lagringsteknikker er til hukommelseslagring (hurtig aritmetisk operation), ikke vedvarende lagring (lavt diskforbrug).

Da man normalt opererer på denne matricer på klientsiden i stedet for på serversiden er en SQL-ARRAY[] det bedste valg!

Spørgsmålet er, hvordan man kan udnytte sparsomheden i matrixen? Her er resultaterne fra nogle undersøgelser.

Opsætning:

Postgres 8.4
Matricer med 400*400 elementer i dobbelt præcision (8 bytes) --> 1,28 MiB rå størrelse pr. matrix
33 % ikke-nul elementer --> 427 kB effektiv størrelse pr. matrix
gennemsnit ved hjælp af ~1000 forskellige tilfældigt udfyldte matricer

Konkurrerende metoder:

Stol på automatikken komprimering på serversiden af kolonner med SET STORAGE MAIN eller EXTENDED.
Gem kun elementer, der ikke er nul, plus en bitmap (bit varying(xx) ) der beskriver, hvor de ikke-nul-elementer skal placeres i matrixen. (Én dobbelt præcision er 64 gange større end én bit. I teorien (ignorerer overheads) burde denne metode være en forbedring, hvis <=98 % er ikke-nul;-).) Serverside-komprimering er aktiveret.
Erstat nullerne i matrixen med NULL . (RDBMS'erne er meget effektive til at gemme NULL'er.) Serversidekomprimering er aktiveret.

(Indeksering af ikke-nul elementer ved hjælp af en 2nd index-ARRAY[] er ikke særlig lovende og derfor ikke testet.)

Resultater:

Automatisk komprimering
- ingen ekstra implementeringsindsats
- ingen reduceret netværkstrafik
- minimal kompressionsoverhead
- vedvarende lagring =39 % af den rå størrelse
Bitmap
- acceptabel implementeringsindsats
- netværkstrafikken faldt lidt; afhængig af sparsomhed
- vedvarende lagring =33,9 % af den rå størrelse
Erstat nuller med NULL
- en vis implementeringsindsats (API skal vide, hvor og hvordan NULL'erne skal indstilles i ARRAY[], mens INSERT-forespørgslen konstrueres)
- ingen ændring i netværkstrafikken
- vedvarende lagring =35 % af den rå størrelse

Konklusion:Start med parameteren UDVIDET/MAIN lagring. Hvis du har lidt fritid, så undersøg dine data og brug min testopsætning med dit sparsomhedsniveau. Men effekten kan være lavere, end du forventer.

Jeg foreslår altid at bruge matrix-serialiseringen (f.eks. række-major rækkefølge) plus to heltalskolonner til matrixdimensionerne NxM. Da de fleste API'er bruger tekstbaseret SQL, sparer du meget netværkstrafik og klienthukommelse for indlejrede "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)
);

Indsæt de samme matricer i alle tabeller. De konkrete data afhænger af den bestemte tabel. Ændr ikke dataene på serversiden på grund af ubrugte, men tildelte sider. Eller lav et 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;