Vertegenwoordigen van schaarse gegevens in PostgreSQL

Ik neem aan dat je denkt aan dunne matrices vanuit een wiskundige context:http://en.wikipedia. org/wiki/Sparse_matrix (De daar beschreven opslagtechnieken zijn voor geheugenopslag (snel rekenkundige bewerking), niet voor permanente opslag (laag schijfgebruik).

Aangezien men meestal op deze matrices aan de clientzijde werkt in plaats van aan de serverzijde, is een SQL-ARRAY[] de beste keuze!

De vraag is hoe te profiteren van de schaarste van de matrix? Hier de resultaten van enkele onderzoeken.

Opstelling:

• Postgres 8.4
• Matrices met 400*400 elementen met dubbele precisie (8 bytes) --> 1,28 MiB onbewerkte grootte per matrix
• 33% niet-nul elementen --> 427kiB effectieve grootte per matrix
• gemiddeld met behulp van ~1000 verschillende willekeurig bevolkte matrices

Concurrerende methoden:

• Vertrouw op de automatische serverzijde compressie kolommen met SET STORAGE MAIN of EXTENDED.
• Sla alleen de niet-nul elementen op plus een bitmap (bit varying(xx) ) waarin wordt beschreven waar de niet-nul-elementen in de matrix moeten worden gevonden. (Eén dubbele precisie is 64 keer groter dan één bit. In theorie (overheadkosten buiten beschouwing gelaten) zou deze methode een verbetering moeten zijn als <=98% niet nul is;-).) Compressie aan de serverzijde is geactiveerd.
• Vervangen de nullen in de matrix met NULL . (De RDBMS'en zijn zeer effectief in het opslaan van NULL's.) Compressie aan de serverzijde is geactiveerd.

(Het indexeren van niet-nul-elementen met een 2e index-ARRAY[] is niet erg veelbelovend en daarom niet getest.)

Resultaten:

• Automatische compressie
  • geen extra implementatie-inspanningen
  • geen verminderd netwerkverkeer
  • minimale compressie-overhead
  • permanente opslag =39% van de onbewerkte grootte
• Bitmap
  • aanvaardbare implementatie-inspanning
  • netwerkverkeer licht afgenomen; afhankelijk van schaarste
  • permanente opslag =33,9% van de onbewerkte grootte
• Vervang nullen door NULL's
  • enige implementatie-inspanning (API moet weten waar en hoe de NULL's in de ARRAY[] moeten worden ingesteld tijdens het maken van de INSERT-query)
  • geen verandering in netwerkverkeer
  • permanente opslag =35% van de onbewerkte grootte

Conclusie:Begin met de parameter EXTENDED/MAIN storage. Als je wat vrije tijd hebt, onderzoek je gegevens en gebruik mijn testopstelling met je spaarzaamheidsniveau. Maar het effect kan lager zijn dan u verwacht.

Ik stel voor om altijd de matrix-serialisatie (bijv. Rij-hoofdvolgorde) plus twee integer-kolommen te gebruiken voor de matrixdimensies NxM. Aangezien de meeste API's tekstuele SQL gebruiken, bespaart u veel netwerkverkeer en clientgeheugen voor geneste "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)
);

Voeg dezelfde matrices in alle tabellen in. De concrete gegevens zijn afhankelijk van de bepaalde tabel. Wijzig de gegevens aan de serverzijde niet vanwege ongebruikte maar toegewezen pagina's. Of doe een VACUM.

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;