GoSuda

Animated Bitmap

By snowmerak
views ...

¿Qué es un Bitmap?

Aquí, un Bitmap es un tipo de índice. Si vino pensando en gráficos, puede retroceder.

Conceptos Fundamentales

Un Bitmap es una forma de tecnología de indexación de bases de datos. Representa el valor de una columna específica como un elemento o forma de un arreglo o vector de bits, donde cada bit indica la presencia o ausencia de un valor particular en esa columna. Por lo tanto, la forma más básica es asignar un índice de bits a cada fila y representar la existencia con 0 y 1.

Por ejemplo, supongamos que tenemos una tabla con una columna de género. Digamos que esta tabla tiene 5 filas y los valores de la columna de género son los siguientes:

  1. Masculino
  2. Femenino
  3. Masculino
  4. Femenino
  5. Otro

En este caso, el índice Bitmap para la columna de género se puede expresar de la siguiente manera:

  • Masculino: 10100
  • Femenino: 01010
  • Otro: 00001

Entonces, ¿dónde se utiliza realmente?

Por lo tanto, todos pensarán que no se trata simplemente de representar eso. Para utilizar correctamente los índices Bitmap, consideremos el siguiente caso.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Supongamos que esta tabla tiene 1,000,000 de filas. Y supongamos que ejecutamos la siguiente consulta.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Esta consulta busca filas donde las columnas active y sex son ambas TRUE. Entonces, para encontrar las filas que cumplen la condición de que ambas columnas son TRUE de la manera más rápida, podríamos utilizar la operación bit and.

  • Supongamos que un índice Bitmap para la columna active 1100110011... (un arreglo de 1,000,000 de bits) ya está indexado, y
  • Supongamos que un índice Bitmap para la columna sex 1010101010... (un arreglo de 1,000,000 de bits) ya está indexado.

Entonces, podemos realizar una operación bit and en los dos índices Bitmap para encontrar rápidamente las filas donde ambas columnas son TRUE. Dado que es una operación de bits simple, se pueden obtener resultados mucho más rápido que con otros escaneos de índices.

Compromisos

Los índices Bitmap pueden ser muy eficientes, pero tienen algunos compromisos. Aunque hay muchas otras desventajas, por ahora solo abordaremos una.

Los índices Bitmap son más adecuados para una cardinalidad baja (es decir, cuando el número de valores posibles en una columna es pequeño). Si se utiliza un índice Bitmap en una columna de cardinalidad alta, el Bitmap puede volverse muy grande.

Si se utiliza un índice Bitmap en una columna de cardinalidad alta, se debe generar un Bitmap separado para cada valor único, lo que puede requerir una gran cantidad de espacio de almacenamiento. Por ejemplo, si una columna tiene 1,000,000 de valores únicos, se deben generar 1,000,000 de Bitmaps, lo que puede ser muy ineficiente.

Por lo tanto, nosotros

Podemos utilizar Roaring Bitmap para reemplazar los Bitmaps que provienen de alta cardinalidad. Roaring Bitmap tiene varias características, pero la filosofía y característica fundamental más importante es seleccionar dinámicamente el método de almacenamiento más adecuado según la densidad de los datos para maximizar tanto la tasa de compresión como la velocidad de operación.

Conceptos Fundamentales de Roaring Bitmap

Indexación en 2 Fases

Roaring Bitmap pasa por las siguientes 2 fases para almacenar un entero. Aunque se llama indexación en 2 fases, simplemente se puede considerar como un arreglo bidimensional.

  • Extracción de los 16 bits superiores: Se extraen los 16 bits superiores del entero y se utilizan como índice. Este se convierte en el índice del arreglo exterior de un arreglo bidimensional con una longitud total de 65536. Este arreglo almacena las direcciones de los contenedores que se describirán más adelante.
  • Extracción de los 16 bits inferiores: Se extraen los 16 bits inferiores del entero y se utilizan como la posición dentro del contenedor.

Contenedores

Este contenedor corresponde al arreglo interior de un arreglo bidimensional, como se comparó anteriormente. Sin embargo, a diferencia de los 16 bits superiores, la estructura interna de este contenedor varía según la cantidad de datos internos. Roaring Bitmap admite los siguientes 3 tipos de contenedores:

  • Contenedor de arreglo (Array Container): Este contenedor se utiliza cuando hay pocos datos almacenados internamente. Específicamente, se utiliza para almacenar menos de 4096 elementos. Este contenedor se implementa simplemente como un arreglo de enteros ordenados. Se pueden encontrar elementos mediante búsqueda binaria.
  • Contenedor de Bitmap (Bitmap Container): Este contenedor se utiliza cuando hay muchos datos almacenados internamente. Específicamente, se utiliza para almacenar más de 4096 elementos. Este contenedor se implementa como un Bitmap de 65536 bits (8192 bytes). Cada bit indica si el entero en esa posición existe o no.
  • Contenedor de ejecución (Run Container): Este contenedor se utiliza para almacenar rangos de enteros consecutivos. Por ejemplo, es eficiente para almacenar enteros consecutivos como 1, 2, 3, 4, 5. Este contenedor se implementa como una lista de pares (valor inicial, longitud). Si hay muchos, simplemente significa que están todos desde el principio hasta el final, por lo que solo se almacena (0, 65536).

Este enfoque permite que Roaring Bitmap use la memoria de manera muy eficiente y proporcione un rendimiento óptimo para diversas densidades de datos.

Funcionalidades de Roaring Bitmap

Funcionalidades Básicas

Roaring Bitmap proporciona las siguientes funcionalidades básicas:

  • Inserción: Agrega un nuevo entero al Bitmap. Durante este proceso, se puede seleccionar un contenedor apropiado o transformar un contenedor si es necesario.
  • Eliminación: Elimina un entero existente del Bitmap. Durante este proceso, se realiza un procesamiento apropiado según el estado del contenedor.
  • Búsqueda: Verifica si un entero específico existe en el Bitmap. Este proceso se realiza muy rápidamente.

Operaciones de Conjunto

Roaring Bitmap también admite las siguientes operaciones de conjunto:

  • Unión: Crea un nuevo Bitmap que contiene todos los elementos de dos Bitmaps.
  • Intersección: Crea un nuevo Bitmap que contiene solo los elementos presentes en ambos Bitmaps.
  • Diferencia Simétrica: Crea un nuevo Bitmap que contiene elementos presentes en solo uno de los dos Bitmaps.

Estas operaciones están optimizadas según el tipo de contenedor del Bitmap y se realizan muy rápidamente.

En lenguaje Go

En el lenguaje Go, se puede utilizar fácilmente Roaring Bitmap usando el paquete github.com/RoaringBitmap/roaring. Este paquete proporciona todas las funcionalidades de Roaring Bitmap y está optimizado para las características del lenguaje Go.

Instalación

1go get github.com/RoaringBitmap/roaring/v2

Ejemplo de uso

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Inicializado con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializado con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Agrega 5
14	b2.Add(10) // Agrega 10
15
16	b2.Remove(12) // Elimina 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Las operaciones de bitmap modifican el original, así que se usa una copia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

Otras funcionalidades principales no mostradas en el código de ejemplo anterior son:

  • Contains(x uint32) bool: Verifica si un valor específico existe en el Bitmap.
  • GetCardinality() uint64: Devuelve el número de elementos contenidos en el Bitmap.
  • Rank(x uint32) uint64: Devuelve el número de elementos menores o iguales a un valor específico.
  • ToBytes() ([]byte, error): Serializa el Bitmap a un slice de bytes.
  • FromBytes(data []byte) error: Restaura el Bitmap desde un slice de bytes.
  • Clone() *Bitmap: Crea una copia del Bitmap.
  • Clear(): Inicializa el Bitmap.
  • NextValue(x uint32) int64: Devuelve el siguiente elemento mayor o igual a x.
  • PreviousValue(x uint32) int64: Devuelve el siguiente elemento menor o igual a x.
  • Maximum() uint32: Devuelve el elemento más grande del Bitmap.
  • Minimum() uint32: Devuelve el elemento más pequeño del Bitmap.

Estas son algunas de las funcionalidades. Para obtener más detalles, consulte la documentación oficial.

Cabe señalar que el paquete roaring incluye un paquete que admite uint64 además de uint32. Proporciona una interfaz casi idéntica, por lo que se puede reemplazar directamente.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Inicializado con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializado con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Agrega 5
14	b2.Add(10) // Agrega 10
15
16	b2.Remove(12) // Elimina 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Las operaciones de bitmap modifican el original, así que se usa una copia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Conclusión

Roaring Bitmap es una herramienta potente para almacenar y manipular eficientemente conjuntos de enteros de alta cardinalidad. En el lenguaje Go, el paquete github.com/RoaringBitmap/roaring permite utilizar todas las funcionalidades de Roaring Bitmap con facilidad. Este paquete maximiza el uso de la memoria y el rendimiento a través de varios tipos de contenedores y operaciones optimizadas. Roaring Bitmap se puede utilizar en diversas áreas como la indexación de bases de datos, el análisis de registros y los cálculos estadísticos para implementar un procesamiento de datos eficiente.

Roaring Bitmap destaca especialmente por su alto rendimiento en conjuntos de datos a gran escala y puede ser útil en diversas aplicaciones. Combinado con la sintaxis concisa y eficiente del lenguaje Go, Roaring Bitmap proporciona una herramienta potente a los desarrolladores. Se espera que Roaring Bitmap siga evolucionando y que se realicen más mejoras y optimizaciones en el futuro.

¿Por qué hice esto? Para la indexación de cada etiqueta y las rápidas operaciones de unión en bases de datos de series temporales.