Representación de datos dispersos en PostgreSQL

Question

¿Cuál es la mejor manera de representar una matriz de datos dispersa en PostgreSQL? Los dos métodos obvios que veo son:

1. Almacenar datos en una sola mesa con una columna separada para todas las funciones imaginables (potencialmente millones), pero con un valor predeterminado es NULL para las características no utilizadas. Esto es conceptualmente muy simple, pero sé que con la mayoría de las implementaciones de RDMS, esto suele ser muy ineficiente, ya que los valores NULL usualmente toman espacio. Sin embargo, leí un artículo (no puedo encontrar su enlace desafortunadamente) que afirmaba que PG no toma datos para los valores NULL, por lo que es más adecuado para almacenar datos dispersos.

2. Cree tablas separadas "fila" y "columna", así como una tabla intermedia para vincularlas y almacenar el valor de la columna en esa fila. Creo que esta es la solución RDMS más tradicional, pero hay más complejidad y gastos generales asociados.

También encontré PostgreDynamic, que pretende apoyar mejor a la escasez de datos, pero no quieren cambiar toda mi servidor de base de datos a un tenedor PG sólo para esta función.

¿Hay alguna otra solución? ¿Cuál debería usar?

Answer 1

algunas soluciones vienen a la mente,

1) separar sus características en grupos que generalmente se fijan juntos, crear una tabla para cada grupo con un uno-a-uno relación de clave externa a los datos principales, sólo se únete a las tablas que necesites al consultar

2) Usa el anti-patrón EAV, crea una tabla 'característica' con un campo de clave externa de tu tabla principal así como un nombre de campo y una columna de valor, y almacena las características como filas en esa tabla en lugar de como atributos en su tabla principal

3) De forma similar a cómo PostgreDynamic lo hace , cree una tabla para cada 'columna' en su tabla principal (usan un espacio de nombres separado para esas tablas) y cree funciones para simplificar (así como indexar de manera eficiente) el acceso y la actualización de las tablas

4) crea una columna en tus datos primarios usando XML, o VARCHAR, y almacena algún formato de texto estructurado que represente tus datos, crea índices sobre los datos con índices funcionales, escribe funciones para actualizar los datos (o usa las funciones XML si estás utilizando ese formato)

5) usar el módulo contrib/hstore para crear una columna de hstore tipo que puede contener pares de valores clave, y puede ser indexado y actualiza

6) liv e con una gran cantidad de campos vacíos

Answer 2

Un valor NULO no ocupará espacio cuando sea NULO. Tomará un bit en un mapa de bits en el encabezado de la tupla, pero eso estará allí independientemente.

Sin embargo, el sistema no puede ocuparse de millones de columnas, punto. Hay un máximo teórico de un poco más de mil, IIRC, pero realmente no quieres llegar tan lejos.

Si realmente necesita tantos, en una sola tabla, necesita ir al método EAV, que es básicamente lo que dice en (2).

Si cada entrada tiene solo unas pocas claves, le sugiero que consulte los módulos de contribución "hstore" que le permiten almacenar este tipo de datos de manera muy eficiente, como una tercera opción. Se ha mejorado aún más en la próxima versión 9.0, por lo que si está un poco lejos de la implementación de producción, es posible que desee mirar directamente a esa. Sin embargo, también vale la pena en 8.4. Y admite algunas búsquedas bastante eficientes basadas en índices. Definitivamente vale la pena investigar.

Answer 3

Asumo que está pensando en matrices dispersas de contexto matemático: técnicas http://en.wikipedia.org/wiki/Sparse_matrix (el almacenamiento describió existen para el almacenamiento de memoria (operación rápida aritmética), no en el almacenamiento persistente (bajo uso de disco).)

Dado que uno normalmente opera en 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 dispersión de la matriz? Aquí los resultados de algunas investigaciones.

Configuración:

• Postgres 8.4
• Matrices w/400 * 400 elementos de doble precisión (8 bytes) -> 1.28MiB tamaño en bruto por matriz
elementos
• 33% no cero - -> 427kiB tamaño efectivo por matriz
• promedió usando ~ 1000 diferentes matrices pobladas aleatorios

métodos compiten:

• confiar en el lado del servidor automáticacompresión de columnas con el conjunto de almacenamiento principal o extendida.
• Solo almacene los elementos distintos de cero más un mapa de bits (bit varying(xx)) describiendo dónde ubicar los elementos distintos de cero en la matriz. (Una precisión doble es 64 veces mayor que un bit. En teoría (ignorando los gastos generales) este método debería ser una mejora si < = 98% no son 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 valores NULL). La compresión del lado del servidor está activada.

(indexación de elementos distintos de cero utilizando un segundo índice de ARRAY [] no es muy prometedor y por lo tanto no evaluados.)

Resultados:

• compresión automática
  • sin esfuerzos de implementación adicionales
  • sin tráfico de red reducido
  • mínima compresión overhead
  • almacenamiento persistente = 39% del tamaño prima
• Bitmap
  • esfuerzo de implementación aceptable
  • tráfico de red disminuyó ligeramente; depende de escasez
  • almacenamiento persistente = 33,9% del tamaño prima
• Sustituir ceros con nulos
  • un poco de esfuerzo de aplicación (API necesita saber dónde y cómo establecer los valores NULL en el ARRAY [] al construir la consulta INSERT)
  • sin cambios en el tráfico de la red
  • persistent storage = 35% of th e tamaño prima

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

Sugiero siempre usar la serialización de matrices (por ejemplo, orden de Fila mayor) más dos columnas enteras para las dimensiones de matriz NxM. Como la mayoría de las API usan SQL textual, está guardando mucho tráfico de red y memoria de cliente para "ARRAY [ARRAY [..], ARRAY [..], ARRAY [..], ARRAY [..], ..] anidados". !!!

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

Insertar las mismas matrices en todas las mesas. Los datos concretos dependen de la tabla determinada. No cambie los datos en el lado del servidor debido a las páginas asignadas pero no utilizadas. 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; 

Answer 4

Sé que este es un hilo viejo, pero MadLib proporciona un tipo de vector escasa para Postgres, junto con el aprendizaje automático y varios métodos estadísticos.