database - name - r repository

¿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 en primer lugar? ¿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 utilizamos un índice B-tree sobre Gender aquí, obtendremos muchos resultados si, por ejemplo, buscamos Gender = Male , que debe filtrarse más (por lo que no es muy útil). ¿Cómo mejora un mapa de bits la situación?

Answer 1

Como se indica en el artículo de Wikipedia, utilizan operaciones a nivel de 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 a 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 esto está destinado a ser charranes laicos y no techie

Entonces, la siguiente pregunta es ¿qué se necesita para evaluar a verdadero? Incluso la comparación de valores numéricos significa que la computadora tiene que ...

1. Asigne memoria para el valor que desea evaluar
2. Asignar memoria para el valor de control
3. Asigne el valor a cada uno (cuente 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).

repite si estás usando una cláusula de partes múltiples donde como "this = this AND that = that"

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

Pero al usar la lógica bit a bit, solo estás viendo valores 0 (falso) y 1 (verdadero). Se elimina el 90% de la sobrecarga para el trabajo de comparación.

Answer 2

El beneficio viene cuando se filtra en múltiples columnas, luego los índices correspondientes se pueden fusionar con operaciones bit a bit antes de seleccionar realmente los datos. Si tienes género, color_de_edad, color_de_cabello, entonces la consulta

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

primero haría un bitwise o entre el índice eye_colour [''blue''] y el índice hair_colour [''blonde''] y finalmente bitwise y entre el 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 usan generalmente en "combinaciones de estrellas" en aplicaciones de depósito de datos.

Answer 3

Una mejor representación de un índice de mapa de bits, si se le 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) así:

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

Los índices de mapa de bits 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 lo haría como una matriz de identidad grande). )

Entonces 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, encuentra todos los rowids donde el bit se estableció en 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 1 bit para Male, los 1 bit para Unspecified, haz un bitwise-O luego ve a 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 reorganiza en consecuencia ...), y puede crear una gran cantidad de contención ya que una 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 / se retrotraiga.