¿Cómo son útiles los índices de mapas de bits?

Question

Wikipedia da este ejemplo

Identifier Gender   Bitmaps 
           F M 
1   Female   1 0 
2   Male    0 1 
3   Male    0 1 
4   Unspecified  0 0 
5   Female   1 0 

Pero no entiendo esto.

• ¿Cómo es este un índice primero de todos? ¿No se supone que un índice apunta a filas (usando rowid) dada la clave?
• ¿Cuáles serían las consultas típicas en las que dichos índices serían útiles? ¿Cómo son mejores que los índices B-tree? Sé que si usamos un índice B-tree en Gender aquí, obtendremos muchos resultados si, por ejemplo, buscamos Gender = Male, que deben filtrarse más (por lo que no es muy útil). ¿Cómo mejora un mapa de bits la situación?

Answer 1

una mejor representación de un índice de mapa de bits, es si se les da el ejemplo anterior:

Identifier Gender   RowID 
1    Female   R1 
2    Male   R2 
3    Male   R3 
4    Unspecified  R4 
5    Female   R5 

el índice de mapa de bits en la columna de género sería (conceptualmente) tener este aspecto:

Gender  R1 R2 R3 R4 R5 
Female  1  0 0 0 1 
Male   0  1 1 0 0 
Unspecified 0  0 0 1 0 

Bitmap los índices se usan cuando el número de valores distintos en una columna es relativamente bajo (considere lo contrario donde todos los valores son únicos: el índice de mapa de bits sería tan ancho como cada fila, y). trix.)

Así, con este índice en su lugar una consulta como

SELECT * FROM table1 WHERE gender = 'Male' 

la base de datos busca una coincidencia en los valores de género en el índice, busca todos los ROWIDs donde el bit se pone a 1, y luego va y obtiene los resultados de la tabla.

una consulta como:

SELECT * FROM table1 WHERE gender IN ('Male', 'Unspecified') 

obtendría los bits 1 para el varón, los bits 1 para especificar, hacen un bit a bit-OR luego ir obtener las filas donde los bits resultantes son 1.

Entonces, las ventajas de usar un índice de mapa de bits sobre un índice de árbol ab * son el almacenamiento (con baja cardinalidad, los índices de mapa de bits son bastante compactos) y la capacidad de realizar operaciones bit a bit antes de resolver los rowids reales, que pueden ser bastante rápidos.

Tenga en cuenta que los índices de mapa de bits pueden tener implicaciones de rendimiento con inserciones/eliminaciones (conceptualmente, agrega/elimina una columna del mapa de bits y lo ajusta en consecuencia ...) y puede crear mucha contención como actualización en una fila puede bloquear la entrada de mapa de bits correspondiente y no puede actualizar una fila diferente (con el mismo valor de mapa de bits) hasta que la primera actualización se confirme o se retrotraiga.

Answer 2

Como se indica en el artículo de Wikipedia, utilizan operaciones bit a bit, que pueden funcionar mejor que la comparación de tipos de datos como enteros, por lo que la respuesta corta es una mayor velocidad de consultas.

Teóricamente, debería tomar menos cálculos y menos tiempo para seleccionar todos los hombres o todas las mujeres de su ejemplo.

Solo pensar en cómo funciona esto debería hacer que esto sea más obvio. Un bit es lógicamente verdadero o falso. Si desea realizar una consulta utilizando una cláusula WHERE, con el tiempo esto se evaluará como verdadero o falso para los registros con el fin de determinar si incluirlos en sus resultados.

Prefacio - el resto de este está destinado a ser charranes del laico y no aficionado a la tecnología

Así que la siguiente pregunta es ¿qué se necesita para evaluar la verdadera? Incluso comparando los valores numéricos significa que el equipo tiene que ...

1. Asignar memoria para el valor que desea evaluar
2. asignar memoria para el valor de control
3. Asignar el valor de cada uno (contar esto como dos pasos)
4. Compara los dos: para un valor numérico esto debería ser rápido, pero para las cadenas, hay más bytes para comparar.
5. Asigne los resultados a un valor 0 (falso) o 1 (verdadero).

repita si está utilizando una parte múltiple donde cláusula como Donde "este = esto y lo = que"

6. realizar operaciones bit a bit de los resultados generados en paso 5
7. Vamos con el valor final
8. desasignar la memoria asignada en los pasos 1-3

pero usando la lógica bit a bit, sólo estás a 0 (falso) y los valores 1 (verdadero) . Se elimina el 90% de la sobrecarga para el trabajo de comparación.

Answer 3

El beneficio se obtiene al filtrar en varias columnas, luego los índices correspondientes se pueden fusionar con operaciones bit a bit antes de seleccionar realmente los datos. si usted tiene género, eye_colour, hair_colour entonces la consulta

select * from persons where 
         gender = 'male' and 
         (eye_colour = 'blue' or hair_colour = 'blonde') 

que primero hacer un bit a bit o entre el eye_colour [ 'azul'] índice y el hair_colour [ 'rubia'] índice y por último bit a bit y entre la resultado y el índice de género ['masculino']. Esta operación se realiza muy rápido tanto de forma computacional como de E/S.
El flujo de bits resultante se usaría para seleccionar las filas reales.

Los índices de mapa de bits se utilizan generalmente en "combinaciones de estrellas" en aplicaciones de almacenamiento de datos.