stringtranslate.com

Índice de mapa de bits

Un índice de mapa de bits es un tipo especial de índice de base de datos que utiliza mapas de bits .

Los índices de mapa de bits se han considerado tradicionalmente como buenos para columnas de baja cardinalidad , que tienen un número modesto de valores distintos, ya sea de forma absoluta o relativa al número de registros que contienen los datos. El caso extremo de baja cardinalidad son los datos booleanos (por ejemplo, ¿tiene acceso a Internet un residente de una ciudad?), que tienen dos valores, Verdadero y Falso. Los índices de mapa de bits utilizan matrices de bits (comúnmente llamadas mapas de bits) y responden a las consultas realizando operaciones lógicas bit a bit en estos mapas de bits. Los índices de mapa de bits tienen una ventaja significativa en cuanto a espacio y rendimiento sobre otras estructuras para la consulta de dichos datos. Su desventaja es que son menos eficientes que los índices de árbol B tradicionales para columnas cuyos datos se actualizan con frecuencia: en consecuencia, se emplean con más frecuencia en sistemas de solo lectura que están especializados en consultas rápidas, por ejemplo, almacenes de datos, y generalmente no son adecuados para aplicaciones de procesamiento de transacciones en línea .

Algunos investigadores sostienen que los índices de mapa de bits también son útiles para datos de cardinalidad moderada o incluso alta (por ejemplo, datos de valor único) a los que se accede de manera de solo lectura, y las consultas acceden a múltiples columnas indexadas en mapa de bits utilizando ampliamente los operadores AND , OR o XOR . [1]

Los índices de mapa de bits también son útiles en aplicaciones de almacenamiento de datos para unir una tabla de hechos grande a tablas de dimensiones más pequeñas , como aquellas dispuestas en un esquema de estrella .

Ejemplo

Continuando con el ejemplo del acceso a Internet, un índice de mapa de bits puede verse lógicamente de la siguiente manera:

A la izquierda, Identificador se refiere al número único asignado a cada residente, TieneInternet son los datos que se van a indexar, el contenido del índice de mapa de bits se muestra como dos columnas bajo el encabezado bitmaps . Cada columna en la ilustración de la izquierda bajo el encabezado Bitmaps es un mapa de bits en el índice de mapa de bits. En este caso, hay dos mapas de bits de este tipo, uno para "tiene internet" Sí y otro para "tiene internet" No . Es fácil ver que cada bit en el mapa de bits Y muestra si una fila en particular se refiere a una persona que tiene acceso a Internet. Esta es la forma más simple de índice de mapa de bits. La mayoría de las columnas tendrán más valores distintos. Por ejemplo, es probable que el monto de ventas tenga una cantidad mucho mayor de valores distintos. Las variaciones en el índice de mapa de bits también pueden indexar estos datos de manera efectiva. Revisamos brevemente tres de estas variaciones.

Nota: Muchas de las referencias citadas aquí se revisan en (John Wu (2007)). [2] Para aquellos que puedan estar interesados ​​en experimentar con algunas de las ideas mencionadas aquí, muchas de ellas están implementadas en software de código abierto como FastBit, [3] la biblioteca C++ Lemur Bitmap Index, [4] la biblioteca Java Roaring Bitmap [5] y el sistema Apache Hive Data Warehouse.

Compresión

Por razones históricas, la compresión de mapas de bits y la compresión de listas invertidas se desarrollaron como líneas de investigación separadas, y solo más tarde se reconoció que resolvían esencialmente el mismo problema. [6]

El software puede comprimir cada mapa de bits en un índice de mapa de bits para ahorrar espacio. Se ha trabajado mucho en este tema. [7] [8] Aunque hay excepciones como los mapas de bits Roaring, [9] los algoritmos de compresión de mapa de bits suelen emplear codificación de longitud de ejecución , como el código de mapa de bits alineado por bytes, [10] el código híbrido alineado por palabras, [11] la compresión híbrida alineada por palabras particionadas (PWAH), [12] la compresión híbrida alineada por palabras de lista de posiciones, [13] el índice adaptativo comprimido (COMPAX), [14] el híbrido alineado por palabras mejorado (EWAH) [15] y el conjunto de enteros componibles 'N' comprimidos (CONCISE). [16] [17] Estos métodos de compresión requieren muy poco esfuerzo para comprimir y descomprimir. Más importante aún, los mapas de bits comprimidos con BBC, WAH, COMPAX, PLWAH, EWAH y CONCISE pueden participar directamente en operaciones bit a bit sin descompresión. Esto les da ventajas considerables sobre las técnicas de compresión genéricas como LZ77 . La compresión BBC y sus derivados se utilizan en un sistema de gestión de bases de datos comercial . BBC es eficaz tanto para reducir los tamaños de índice como para mantener el rendimiento de las consultas . BBC codifica los mapas de bits en bytes , mientras que WAH codifica en palabras, lo que se adapta mejor a las CPU actuales . "Tanto en datos sintéticos como en datos de aplicaciones reales, los nuevos esquemas de alineación de palabras utilizan solo un 50% más de espacio, pero realizan operaciones lógicas en datos comprimidos 12 veces más rápido que BBC". [18] Se informó que los mapas de bits PLWAH ocupan el 50% del espacio de almacenamiento consumido por los mapas de bits WAH y ofrecen un rendimiento hasta un 20% más rápido en operaciones lógicas . [13] Se pueden hacer consideraciones similares para CONCISE [17] y Enhanced Word-Aligned Hybrid. [15]

El rendimiento de esquemas como BBC, WAH, PLWAH, EWAH, COMPAX y CONCISE depende del orden de las filas. Una simple ordenación lexicográfica puede dividir el tamaño del índice por 9 y hacer que los índices sean varias veces más rápidos. [19] Cuanto más grande sea la tabla, más importante es ordenar las filas. También se han propuesto técnicas de reorganización para lograr los mismos resultados de ordenación al indexar datos en tiempo real. [14]

Codificación

Los índices de mapa de bits básicos utilizan un mapa de bits para cada valor distinto. Es posible reducir la cantidad de mapas de bits utilizados utilizando un método de codificación diferente . [20] [21] Por ejemplo, es posible codificar valores distintos de C utilizando mapas de bits log(C) con codificación binaria . [22]

Esto reduce la cantidad de mapas de bits, lo que permite ahorrar aún más espacio, pero para responder a cualquier consulta, es necesario acceder a la mayoría de los mapas de bits. Esto hace que no sea tan eficaz como escanear una proyección vertical de los datos base, también conocida como vista materializada o índice de proyección. Encontrar el método de codificación óptimo que equilibre el rendimiento de la consulta (arbitraria), el tamaño del índice y el mantenimiento del índice sigue siendo un desafío.

Sin considerar la compresión, Chan y Ioannidis analizaron una clase de métodos de codificación de múltiples componentes y llegaron a la conclusión de que la codificación de dos componentes se encuentra en el punto intermedio entre el rendimiento y el tamaño del índice y, por lo tanto, representa el mejor equilibrio entre el tamaño del índice y el rendimiento de la consulta. [20]

Apilar

Para las columnas de alta cardinalidad, es útil agrupar los valores, donde cada grupo cubre múltiples valores y construir los mapas de bits para representar los valores en cada grupo. Este enfoque reduce la cantidad de mapas de bits utilizados independientemente del método de codificación. [23] Sin embargo, los índices agrupados solo pueden responder algunas consultas sin examinar los datos base. Por ejemplo, si un grupo cubre el rango de 0,1 a 0,2, entonces cuando el usuario solicita todos los valores menores a 0,15, todas las filas que caen en el grupo son posibles coincidencias y deben verificarse para verificar si realmente son menores a 0,15. El proceso de verificación de los datos base se conoce como verificación de candidatos. En la mayoría de los casos, el tiempo utilizado por la verificación de candidatos es significativamente más largo que el tiempo necesario para trabajar con el índice de mapa de bits. Por lo tanto, los índices agrupados exhiben un rendimiento irregular. Pueden ser muy rápidos para algunas consultas, pero mucho más lentos si la consulta no coincide exactamente con un grupo.

Historia

El concepto de índice de mapa de bits fue introducido por primera vez por el Profesor Israel Spiegler y Rafi Maayan en su investigación "Consideraciones de almacenamiento y recuperación de bases de datos binarias", publicada en 1985. [24] El primer producto de base de datos comercial que implementó un índice de mapa de bits fue el Modelo 204 de Computer Corporation of America . Patrick O'Neil publicó un artículo sobre esta implementación en 1987. [25] Esta implementación es un híbrido entre el índice de mapa de bits básico (sin compresión) y la lista de identificadores de fila (lista RID). En general, el índice está organizado como un árbol B+ . Cuando la cardinalidad de la columna es baja, cada nodo de hoja del árbol B contendría una larga lista de RID. En este caso, se requiere menos espacio para representar las listas RID como mapas de bits. Dado que cada mapa de bits representa un valor distinto, este es el índice de mapa de bits básico. A medida que aumenta la cardinalidad de la columna, cada mapa de bits se vuelve disperso y puede requerir más espacio en disco para almacenar los mapas de bits que para almacenar el mismo contenido como listas RID. En este caso, cambia para usar las listas RID, lo que lo convierte en un índice de árbol B+ . [26] [27]

Mapas de bits en memoria

Una de las razones más importantes para utilizar índices de mapa de bits es que los resultados intermedios que se generan a partir de ellos también son mapas de bits y se pueden reutilizar de manera eficiente en operaciones posteriores para responder consultas más complejas. Muchos lenguajes de programación admiten esto como una estructura de datos de matriz de bits. Por ejemplo, Java tiene la BitSetclase.

Algunos sistemas de bases de datos que no ofrecen índices de mapa de bits persistentes utilizan mapas de bits internamente para acelerar el procesamiento de consultas. Por ejemplo, las versiones 8.1 y posteriores de PostgreSQL implementan una optimización de "exploración de índice de mapa de bits" para acelerar operaciones lógicas arbitrariamente complejas entre índices disponibles en una sola tabla.

Para tablas con muchas columnas, el número total de índices distintos para satisfacer todas las consultas posibles (con condiciones de filtrado de igualdad en cualquiera de los campos) crece muy rápido y se define mediante esta fórmula:

. [28] [29]

Un escaneo de índice de mapa de bits combina expresiones en diferentes índices, por lo que requiere solo un índice por columna para admitir todas las consultas posibles en una tabla.

La aplicación de esta estrategia de acceso a los índices de árbol B también puede combinar consultas de rango en múltiples columnas. En este enfoque, se crea un mapa de bits temporal en memoria con un bit para cada fila de la tabla (1  MB puede almacenar más de 8 millones de entradas). A continuación, los resultados de cada índice se combinan en el mapa de bits mediante operaciones bit a bit . Después de evaluar todas las condiciones, el mapa de bits contiene un "1" para las filas que coinciden con la expresión. Finalmente, se recorre el mapa de bits y se recuperan las filas coincidentes. Además de combinar índices de manera eficiente, esto también mejora la localidad de referencia de los accesos a la tabla, porque todas las filas se obtienen secuencialmente de la tabla principal. [30] El mapa de bits interno se descarta después de la consulta. Si hay demasiadas filas en la tabla para usar 1 bit por fila, se crea en su lugar un mapa de bits "con pérdida", con un solo bit por página de disco. En este caso, el mapa de bits solo se usa para determinar qué páginas se deben obtener; luego, los criterios de filtro se aplican a todas las filas en las páginas coincidentes.

Referencias

Notas
  1. ^ Índice de mapa de bits frente a índice de árbol B: ¿cuál y cuándo?, Vivek Sharma, Oracle Technical Network.
  2. ^ John Wu (2007). "Referencias comentadas sobre el índice de mapas de bits". Archivado desde el original el 30 de junio de 2012.
  3. ^ Bit rápido
  4. ^ Biblioteca C++ con índice de mapas de bits de Lemur
  5. ^ Mapas de bits rugientes
  6. ^ Jianguo Wang; Chunbin Lin; Yannis Papakonstantinou; Steven Swanson. "Un estudio experimental de la compresión de mapas de bits frente a la compresión de listas invertidas" Archivado el 7 de diciembre de 2019 en Wayback Machine . 2017. doi: 10.1145/3035918.3064007
  7. ^ T. Johnson (1999). "Medidas de rendimiento de índices de mapa de bits comprimidos" (PDF) . En Malcolm P. Atkinson; Maria E. Orlowska ; Patrick Valduriez; Stanley B. Zdonik; Michael L. Brodie (eds.). VLDB'99, Actas de la 25.ª Conferencia internacional sobre bases de datos muy grandes, 7-10 de septiembre de 1999, Edimburgo, Escocia, Reino Unido . Morgan Kaufmann. págs. 278-89. ISBN. 978-1-55860-615-9.
  8. ^ Wu K, Otoo E, Shoshani A (5 de marzo de 2004). "Sobre el rendimiento de los índices de mapa de bits para atributos de alta cardinalidad" (PDF) .
  9. ^ Chambi, S.; Lemire, D.; Kaser, O.; Godin, R. (2016). "Mejor rendimiento de mapas de bits con mapas de bits Roaring". Software: práctica y experiencia . 46 (5): 709–719. arXiv : 1402.6407 . doi :10.1002/spe.2325. S2CID  1139669.
  10. ^ Compresión de datos alineada con bytes
  11. ^ Método de compresión de mapas de bits alineados con palabras, estructura de datos y aparato
  12. ^ van Schaik, Sebastiaan; de Moor, Oege (2011). "Una estructura de datos de accesibilidad eficiente en memoria mediante compresión de vectores de bits". Actas de la conferencia internacional de 2011 sobre gestión de datos . SIGMOD '11. Atenas, Grecia: ACM. págs. 913–924. doi :10.1145/1989323.1989419. ISBN 978-1-4503-0661-4.
  13. ^ ab Deliège F, Pedersen TB (2010). "Lista de posiciones alineada con palabras híbridas: optimización del espacio y el rendimiento para mapas de bits comprimidos" (PDF) . En Ioana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Leger, Felix Naumann, Anastasia Ailamaki, Fatma Ozcan (eds.). EDBT '10, Actas de la 13.ª Conferencia internacional sobre la extensión de la tecnología de bases de datos . Nueva York, NY, EE. UU.: ACM. págs. 228–39. doi :10.1145/1739041.1739071. ISBN . 978-1-60558-945-9.S2CID12234453  .​
  14. ^ ab F. Fusco; M. Stoecklin; M. Vlachos (septiembre de 2010). "NET-FLi: compresión, archivo e indexación sobre la marcha del tráfico de red en streaming" (PDF) . Proc. VLDB Endow . 3 (1–2): 1382–93. doi :10.14778/1920841.1921011. S2CID  787443.
  15. ^ ab Lemire, D.; Kaser, O.; Aouiche, K. (2010). "La ordenación mejora los índices de mapas de bits alineados con palabras". Ingeniería de datos y conocimiento . 69 : 3–28. arXiv : 0901.3751 . doi :10.1016/j.datak.2009.08.006. S2CID  6297890.
  16. ^ Conciso: conjunto de números enteros comprimidos y componibles Archivado el 28 de mayo de 2011 en Wayback Machine .
  17. ^ ab Colantonio A, Di Pietro R (31 de julio de 2010). "Conciso: conjunto entero comprimido y componible" (PDF) . Information Processing Letters . 110 (16): 644–50. arXiv : 1004.0403 . doi :10.1016/j.ipl.2010.05.018. S2CID  8092695. Archivado desde el original (PDF) el 22 de julio de 2011 . Consultado el 2 de febrero de 2011 .
  18. ^ Wu K, Otoo EJ, Shoshani A (2001). "Una comparación del rendimiento de los índices de mapa de bits" (PDF) . En Henrique Paques, Ling Liu , David Grossman (eds.). CIKM '01 Actas de la décima conferencia internacional sobre gestión de la información y el conocimiento . Nueva York, NY, EE. UU.: ACM. págs. 559–61. doi :10.1145/502585.502689. ISBN . 978-1-58113-436-0.S2CID10974671  .​
  19. ^ D. Lemire; O. Kaser; K. Aouiche (enero de 2010). "La ordenación mejora los índices de mapas de bits alineados con palabras". Ingeniería de datos y conocimiento . 69 (1): 3–28. arXiv : 0901.3751 . doi :10.1016/j.datak.2009.08.006. S2CID  6297890.
  20. ^ ab C.-Y. Chan; YE Ioannidis (1998). "Diseño y evaluación de índices de mapa de bits" (PDF) . En Ashutosh Tiwary; Michael Franklin (eds.). Actas de la conferencia internacional ACM SIGMOD de 1998 sobre gestión de datos (SIGMOD '98) . Nueva York, NY, EE. UU.: ACM. pp. 355–6. doi :10.1145/276304.276336. ISBN 0897919955.
  21. ^ C.-Y. Chan; YE Ioannidis (1999). "Un esquema de codificación de mapa de bits eficiente para consultas de selección" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 1999 sobre gestión de datos (SIGMOD '99) . Nueva York, NY, EE. UU.: ACM. págs. 215–26. doi :10.1145/304182.304201. ISBN. 1581130848.
  22. ^ PE O'Neil; D. Quass (1997). "Mejora del rendimiento de las consultas con índices de variantes". En Joan M. Peckman; Sudha Ram; Michael Franklin (eds.). Actas de la conferencia internacional ACM SIGMOD de 1997 sobre gestión de datos (SIGMOD '97) . Nueva York, NY, EE. UU.: ACM. págs. 38–49. doi :10.1145/253260.253268. ISBN 0897919114.
  23. ^ N. Koudas (2000). "Indexación de mapas de bits con eficiencia espacial". Actas de la novena conferencia internacional sobre gestión de la información y el conocimiento (CIKM '00) . Nueva York, NY, EE. UU.: ACM. págs. 194-201. doi :10.1145/354756.354819. ISBN . 978-1581133202.S2CID 7504216  .
  24. ^ Spiegler I; Maayan R (1985). "Consideraciones sobre almacenamiento y recuperación de bases de datos binarias". Procesamiento y gestión de la información . 21 (3): 233–54. doi :10.1016/0306-4573(85)90108-6.
  25. ^ O'Neil, Patrick (1987). "Model 204 Architecture and Performance". En Dieter Gawlick; Mark N. Haynie; Andreas Reuter (eds.). Actas del 2º Taller Internacional sobre Sistemas de Transacción de Alto Rendimiento . Londres, Reino Unido: Springer-Verlag. págs. 40–59.
  26. ^ D. Rinfret; P. O'Neil; E. O'Neil (2001). "Aritmética de índices en porciones de bits". En Timos Sellis (ed.). Actas de la conferencia internacional ACM SIGMOD de 2001 sobre gestión de datos (SIGMOD '01) . Nueva York, NY, EE. UU.: ACM. págs. 47–57. doi :10.1145/375663.375669. ISBN 1581133324.
  27. ^ E. O'Neil; P. O'Neil; K. Wu (2007). "Opciones de diseño de índices de mapa de bits y sus implicaciones en el rendimiento" (PDF) . 11.º Simposio internacional sobre ingeniería y aplicaciones de bases de datos (IDEAS 2007) . págs. 72–84. doi :10.1109/IDEAS.2007.19. ISBN 978-0-7695-2947-9.
  28. ^ Alex Bolenok (9 de mayo de 2009). "Creación de índices".
  29. ^ Egor Timoshenko. "Sobre las colecciones mínimas de índices" (PDF) .
  30. ^ Tom Lane (26 de diciembre de 2005). "Re: Índices de mapa de bits, etc." Listas de correo de PostgreSQL . Consultado el 6 de abril de 2007 .
Bibliografía