Compresión de datos

por | Jun 28, 2017 | Bases de Datos | 0 Comentarios

Los almacenes de datos por columnas se caracterizan por el aumento de la localidad de los datos, esto es así porque los valores de una misma columna están próximos en el dispositivo de almacenamiento externo, gracias a ello se puede resolver de forma eficiente, dado que las operaciones de E/S de lectura de páginas que se desencadenan recuperan únicamente datos potencialmente útiles.

La localidad facilita la compresión de los datos ya se basa fundamentalmente en buscar repeticiones en una serie de datos (el conjunto de valores de cada una de las columnas de una tabla puede ser visto como una serie), que se representan de forma resumida.

Los valores representados son:

  1. Número de valores diferentes que toma la columna.
  2. Número de valores repetidos que existen para cada valor.
  3. Frecuencia de aparición de la columna en predicados de selección
  4. Tipo de datos asociado.

Tipos de algoritmos de compresión:

Tipos de algoritmos de compresion

Fuente: Universidad Oberta de Cataluña

 

Reducen el número de valores (celdas)

Run-length encoding

  • Reduce el número de celdas de una columna.
  • Elimina valores repetidos.
  • Reemplaza valores iguales que aparecen en celdas consecutivas por una tripleta de:
    • Valor.
    • Posición de inicio.
    • Número de repeticiones.

Uso: Columnas ordenadas.

Algoritmo compresión - Run-length encoding

Cluster encoding

  • Reduce el número de celdas de una columna.
  • Elimina valores repetidos.
  • Trabaja a nivel de bloque:
    • Se distribuyen los valores de la columna en N bloques (clusters) de tamaño fijo.
    • Si todos los valores del bloque son iguales se sustituye el valor sino se mantiene intacto.

Uso: Columnas ordenadas por clave secundaria

Algoritmo compresión - cluster encoding

Reducen el tamaño de valores (celdas)

Diccionary encoding

  • Crea un diccionario con todos los valores de la columna
  • Sustituye los valores de la columna por referencias a su valor.

Uso: Columna de tipo string o tamaño considerable y puede combinarse con otros algoritmos.

Algoritmo compresión - Diccionary encoding

Bit-vector encoding

  • Permite representar múltiples valores para cada fila.
  • Crea M vectores de bits de N posiciones.
    • M valores que toman los datos.
    • N longitud del vector a comprimir.

Uso: Columna con pocos valores posibles: sexo, categoría, … y puede combinarse con otros algoritmos.

Algoritmo compresión - Bit-Vector encoding

Frame of reference encoding

  • Coger un valor de referencia para todas las celdas
  • Reescribir la columna restando el valor de la referencia.
  • Los que se salen mucho de la media se tratan como valores atípicos, indicando infinito y marcando el valor sin comprimir.

Uso: Columna con poca variabilidad con respecto al valor medio.

Algoritmo compresión - Frame of Reference encoding

Diferential encoding

  • Necesita que la columna este ordenada
  • Parecido a Frame of reference pero restableciendo el valor al salir de rango

Uso: Columna con poca variabilidad con respecto al valor medio y ordenados. Ejemplo fechas.

Algoritmo compresión - Diferencial encoding

Elección del tipo de compresión:

eleccion del tipo de compresion

Fuente: Universidad Oberta de cataluña

Adicionalmente, productos como Vertica/C-Store, Actian Vector/VectorWise o Amazon Redshift acostumbran a incorporar utilidades que ayudan a elegir los algoritmos de compresión,

0 comentarios

Enviar un comentario

Tu dirección de correo electrónico no será publicada.