GoSuda

Mapa de bits vibrante

By snowmerak views ...

¿Qué es un mapa de bits?

Aquí, el mapa de bits (bitmap) es un tipo de índice. Si llegó pensando en gráficos, puede volver atrás.

Concepto básico

El mapa de bits es una forma de la técnica de indexación de las bases de datos. Representa los valores de una columna determinada como un elemento o una forma de un arreglo o vector de bits, de modo que cada bit indica si existe o no un valor específico de esa columna. Por ello, la forma más básica consiste en asignar un índice de bit a cada row y expresar su existencia mediante 0 y 1.

Por ejemplo, supongamos que existe una tabla con una columna de sexo. Digamos que esta tabla tiene 5 rows y que los valores de la columna de sexo son los siguientes:

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

En este caso, el índice de mapa de bits para la columna de sexo puede expresarse de la siguiente manera:

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

Entonces, ¿dónde se utiliza realmente?

Seguramente todos piensan que no se trata simplemente de representar eso. Para comprender el uso adecuado del índice de mapa de bits, 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 rows. Y supongamos que se ejecuta la siguiente consulta.

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

Esta consulta busca los rows en los que las columnas active y sex son ambas TRUE. Entonces, la forma más rápida de encontrar los rows que cumplen la condición de que ambas columnas sean TRUE sería utilizar la operación bit and.

  • Supongamos que el índice de mapa de bits de la columna active ya está indexado previamente como 1100110011... (arreglo de 1,000,000 de bits).
  • Supongamos que el índice de mapa de bits de la columna sex ya está indexado previamente como 1010101010... (arreglo de 1,000,000 de bits).

Entonces, al realizar la operación bit and sobre ambos índices de mapa de bits, se pueden encontrar rápidamente los rows en los que ambas columnas son TRUE. Como se trata de una simple operación de bits, se puede obtener el resultado mucho más rápido que con otros escaneos de índice.

Compromisos

Aunque el índice de mapa de bits puede ser muy eficiente, presenta algunos compromisos. Tiene muchas otras desventajas, pero por ahora solo abordaremos una.

Se trata de que el índice de mapa de bits es más adecuado para una cardinalidad baja (es decir, cuando la columna tiene pocos valores posibles). Si se utiliza un índice de mapa de bits en una columna de alta cardinalidad, el mapa de bits puede volverse muy grande.

Al utilizar un índice de mapa de bits en una columna de alta cardinalidad, es necesario generar un mapa de bits separado para cada valor único, por lo que puede requerir mucho espacio de almacenamiento. Por ejemplo, si una columna tiene 1,000,000 de valores únicos, habría que generar 1,000,000 de mapas de bits, lo que puede resultar muy ineficiente.

Entonces, nosotros

Para reemplazar los mapas de bits que surgen con la alta cardinalidad, se puede utilizar una estructura llamada Roaring Bitmap. Roaring Bitmap tiene varias características, pero su principio fundamental y su rasgo más importante es seleccionar dinámicamente la forma de almacenamiento más adecuada según la densidad de los datos, maximizando tanto la tasa de compresión como la velocidad de las operaciones.

Concepto básico de Roaring Bitmap

Indexación de dos niveles

Para almacenar un entero, Roaring Bitmap pasa primero por los siguientes dos niveles. Aunque se llame indexación de dos niveles, basta con pensar que es simplemente un arreglo bidimensional.

  • Extracción de los 16 bits superiores: se extraen los 16 bits superiores del entero y se usan como índice. Es el índice del arreglo externo de un arreglo bidimensional con una longitud total de 65536. Este arreglo almacena la dirección del contenedor que se describe más adelante.
  • Extracción de los 16 bits inferiores: se extraen los 16 bits inferiores del entero y se usan como posición dentro del contenedor.

Contenedor

Este contenedor corresponde al arreglo interno del arreglo bidimensional que acabamos de comparar. Sin embargo, a diferencia del correspondiente a los 16 bits superiores, la estructura interna de este contenedor varía según la cantidad de datos que contenga. Roaring Bitmap admite los siguientes 3 tipos de contenedores.

  • Array Container: este contenedor se utiliza cuando la cantidad de datos almacenados internamente es pequeña. Concretamente, se usa cuando almacena 4096 elementos o menos. Está implementado como un arreglo de enteros ordenado. Se puede encontrar un elemento mediante búsqueda binaria.
  • Bitmap Container: este contenedor se utiliza cuando la cantidad de datos almacenados internamente es grande. Concretamente, se usa cuando almacena más de 4096 elementos. Está implementado como un mapa de bits de 65536 bits (8192 bytes). Cada bit indica si el entero de esa posición existe o no.
  • 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. Está implementado como una lista de pares (valor inicial, longitud). Si están todos presentes, es decir, si existen desde el principio hasta el final, basta con almacenar un único (0, 65536).

Este método permite que Roaring Bitmap utilice la memoria de manera muy eficiente y ofrezca un rendimiento óptimo para diversas densidades de datos.

Funciones de Roaring Bitmap

Funciones básicas

Roaring Bitmap proporciona las siguientes funciones básicas.

  • Inserción: agrega un nuevo entero al mapa de bits. En este proceso, se puede seleccionar el contenedor adecuado o convertir el contenedor cuando sea necesario.
  • Eliminación: elimina un entero existente del mapa de bits. En este proceso también se realiza un tratamiento adecuado según el estado del contenedor.
  • Búsqueda: verifica si un entero específico existe en el mapa de bits. Este proceso se ejecuta con gran rapidez.

Operaciones de conjuntos

Roaring Bitmap también admite las siguientes operaciones de conjuntos.

  • Unión (Union): crea un nuevo mapa de bits que contiene todos los elementos de ambos mapas de bits.
  • Intersección (Intersection): crea un nuevo mapa de bits que contiene únicamente los elementos presentes en ambos mapas de bits.
  • Diferencia simétrica (Symmetric Difference): crea un nuevo mapa de bits que contiene los elementos que están presentes en solo uno de los dos mapas de bits.

Estas operaciones se optimizan según el tipo de contenedor del mapa de bits, por lo que se ejecutan con gran rapidez.

En el lenguaje Go

En el lenguaje Go, se puede utilizar fácilmente Roaring Bitmap mediante el paquete github.com/RoaringBitmap/roaring. Este paquete proporciona todas las funciones de Roaring Bitmap y está optimizado según 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)     // inicializar con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // inicializar con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // agregar 5
14	b2.Add(10) // agregar 10
15
16	b2.Remove(12) // eliminar 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// como las operaciones de bitmap modifican el original, se crea una copia para usar
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]

Entre las funciones principales que no aparecen en el ejemplo anterior se encuentran:

  • Contains(x uint32) bool: verifica si un valor específico existe en el mapa de bits
  • GetCardinality() uint64: devuelve la cantidad de elementos incluidos en el mapa de bits
  • Rank(x uint32) uint64: devuelve la cantidad de elementos menores o iguales a un valor específico
  • ToBytes() ([]byte, error): serializa el mapa de bits en un slice de bytes
  • FromBytes(data []byte) error: restaura el mapa de bits a partir de un slice de bytes
  • Clone() *Bitmap: crea una copia del mapa de bits
  • Clear(): inicializa el mapa de bits
  • NextValue(x uint32) int64: devuelve el siguiente elemento mayor o igual que x
  • PreviousValue(x uint32) int64: devuelve el elemento anterior menor o igual que x
  • Maximum() uint32: devuelve el elemento más grande del mapa de bits
  • Minimum() uint32: devuelve el elemento más pequeño del mapa de bits

Estas son las funciones disponibles. Para más detalles, consulte la documentación oficial.

Como referencia, el paquete roaring incluye internamente un paquete que admite uint64 además de uint32. Ofrece una interfaz casi idéntica, por lo que puede reemplazarse directamente para su uso.

 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)     // inicializar con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // inicializar con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // agregar 5
14	b2.Add(10) // agregar 10
15
16	b2.Remove(12) // eliminar 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// como las operaciones de bitmap modifican el original, se crea una copia para usar
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 poderosa que permite almacenar y manipular de forma eficiente conjuntos de enteros de alta cardinalidad. Si se utiliza el paquete github.com/RoaringBitmap/roaring en Go, se pueden aprovechar fácilmente todas las funciones de Roaring Bitmap. Este paquete maximiza el uso de memoria y el rendimiento mediante diversos tipos de contenedores y operaciones optimizadas. Roaring Bitmap puede aplicarse de manera útil en diversos campos, como la indexación de bases de datos, el análisis de registros y el cálculo estadístico, para implementar un procesamiento de datos eficiente.

Roaring Bitmap destaca especialmente en conjuntos de datos a gran escala y puede utilizarse de forma útil en diversas aplicaciones. Combinado con la sintaxis concisa y eficiente del lenguaje Go, Roaring Bitmap ofrece a los desarrolladores una herramienta poderosa. Se espera que, junto con el desarrollo de Roaring Bitmap, se logren más funciones y optimizaciones.

¿Y por qué hice esto? Lo hice para la indexación por cada etiqueta (tag) en una base de datos de series temporales y para realizar operaciones de unión rápidas.