Representación de datos dispersos en PostgreSQL

Supongo que está pensando en matrices dispersas del contexto matemático:http://en.wikipedia. org/wiki/Sparse_matrix (Las técnicas de almacenamiento descritas allí son para almacenamiento en memoria (operación aritmética rápida), no para almacenamiento persistente (bajo uso de disco).)

Dado que normalmente se opera con estas matrices en el lado del cliente en lugar de en el lado del servidor, ¡SQL-ARRAY[] es la mejor opción!

La pregunta es ¿cómo aprovechar la escasez de la matriz? Aquí los resultados de algunas investigaciones.

Configuración:

• Postgres 8.4
• Matrices con 400*400 elementos en doble precisión (8 bytes) --> 1,28 MiB de tamaño bruto por matriz
• 33 % de elementos distintos de cero --> 427 kiB de tamaño efectivo por matriz
• promedio usando ~1000 matrices pobladas aleatoriamente diferentes

Métodos de competencia:

• Confíe en el automático compresión del lado del servidor de columnas con ESTABLECER ALMACENAMIENTO PRINCIPAL o EXTENDIDO.
• Almacenar solo los elementos distintos de cero más un mapa de bits (bit varying(xx) ) que describe dónde ubicar los elementos distintos de cero en la matriz. (Una doble precisión es 64 veces más grande que un bit. En teoría (ignorando los gastos generales), este método debería ser una mejora si <=98% son distintos de cero;-).) La compresión del lado del servidor está activada.
• Reemplazar los ceros en la matriz con NULL . (Los RDBMS son muy efectivos para almacenar NULL). La compresión del lado del servidor está activada.

(La indexación de elementos distintos de cero utilizando un segundo índice-ARRAY[] no es muy prometedora y, por lo tanto, no se ha probado).

Resultados:

• Compresión automática
  • sin esfuerzos adicionales de implementación
  • sin tráfico de red reducido
  • sobrecarga mínima de compresión
  • almacenamiento persistente =39 % del tamaño sin procesar
• mapa de bits
  • esfuerzo de implementación aceptable
  • el tráfico de red disminuyó ligeramente; depende de la escasez
  • almacenamiento persistente =33,9 % del tamaño sin procesar
• Reemplazar ceros con NULL
  • algún esfuerzo de implementación (la API necesita saber dónde y cómo configurar los valores NULL en ARRAY[] mientras se construye la consulta INSERT)
  • sin cambios en el tráfico de red
  • almacenamiento persistente =35 % del tamaño sin procesar

Conclusión:Comience con el parámetro de almacenamiento EXTENDIDO/PRINCIPAL. Si tiene algo de tiempo libre, investigue sus datos y use mi configuración de prueba con su nivel de escasez. Pero el efecto puede ser menor de lo esperado.

Sugiero usar siempre la serialización de matriz (por ejemplo, orden de fila principal) más dos columnas enteras para las dimensiones de matriz NxM. Dado que la mayoría de las API utilizan SQL textual, está ahorrando una gran cantidad de tráfico de red y memoria de cliente para "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)
);

Inserte las mismas matrices en todas las tablas. Los datos concretos dependen de la tabla determinada. No cambie los datos en el lado del servidor debido a páginas no utilizadas pero asignadas. O haz un VACÍO.

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;