Mewakili Data Jarang di PostgreSQL

Saya berasumsi Anda sedang memikirkan matriks jarang dari konteks matematika:http://en.wikipedia. org/wiki/Sparse_matrix (Teknik penyimpanan yang dijelaskan ada untuk penyimpanan memori (operasi aritmatika cepat), bukan penyimpanan persisten (penggunaan disk rendah).)

Karena seseorang biasanya beroperasi pada matriks ini di sisi klien daripada di sisi server, SQL-ARRAY[] adalah pilihan terbaik!

Pertanyaannya adalah bagaimana memanfaatkan sparitas matriks? Berikut hasil dari beberapa investigasi.

Penyiapan:

• Postgres 8.4
• Matriks dengan 400*400 elemen dalam presisi ganda (8 Bytes) --> ukuran mentah 1,28MiB per matriks
• 33% elemen bukan nol --> 427kiB ukuran efektif per matriks
• rata-rata menggunakan ~1000 matriks populasi acak yang berbeda

Metode kompetisi:

• Andalkan otomatis kompresi sisi server kolom dengan SET STORAGE MAIN atau EXTENDED.
• Hanya simpan elemen bukan nol plus bitmap (bit varying(xx) ) yang menjelaskan lokasi elemen bukan nol dalam matriks. (Satu presisi ganda 64 kali lebih besar dari satu bit. Secara teori (mengabaikan overhead) metode ini harus ditingkatkan jika <=98% bukan nol;-).) Kompresi sisi server diaktifkan.
• Ganti nol dalam matriks dengan NULL . (RDBMS sangat efektif dalam menyimpan NULL.) Kompresi sisi server diaktifkan.

(Pengindeksan elemen bukan nol menggunakan 2nd index-ARRAY[] tidak terlalu menjanjikan dan karenanya tidak diuji.)

Hasil:

• Kompresi otomatis
  • tidak ada upaya implementasi tambahan
  • lalu lintas jaringan tidak berkurang
  • overhead kompresi minimal
  • penyimpanan tetap =39% dari ukuran mentah
• Bitmap
  • upaya penerapan yang dapat diterima
  • lalu lintas jaringan sedikit menurun; bergantung pada sparitas
  • penyimpanan tetap =33,9% dari ukuran mentah
• Ganti nol dengan NULL
  • beberapa upaya implementasi (API perlu mengetahui di mana dan bagaimana menyetel NULL di ARRAY[] saat membuat kueri INSERT)
  • tidak ada perubahan dalam lalu lintas jaringan
  • penyimpanan tetap =35% dari ukuran mentah

Kesimpulan:Mulailah dengan parameter penyimpanan EXTENDED/MAIN. Jika Anda memiliki waktu luang, selidiki data Anda dan gunakan pengaturan pengujian saya dengan tingkat ketersedian Anda. Tetapi efeknya mungkin lebih rendah dari yang Anda harapkan.

Saya menyarankan untuk selalu menggunakan serialisasi matriks (mis. Urutan baris-utama) ditambah dua kolom bilangan bulat untuk dimensi matriks NxM. Karena sebagian besar API menggunakan SQL tekstual, Anda menghemat banyak lalu lintas jaringan dan memori klien untuk "ARRAY[ARRAY[..], ARRAY[..], ARRAY[..], ARRAY[..], ..]" bersarang. !!!

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

Masukkan matriks yang sama ke semua tabel. Data konkret tergantung pada tabel tertentu. Jangan mengubah data di sisi server karena halaman yang tidak digunakan tetapi dialokasikan. Atau lakukan VAKUM.

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;