algorithm - software - ¿Alguien sabe algo sobre OLAP Internals?

software olap

Question

Sé un poco sobre las funciones internas de la base de datos. De hecho, he implementado un motor de base de datos relacional pequeño y simple, utilizando estructuras ISAM en el disco y los índices BTree y todo ese tipo de cosas. Fue divertido y muy educativo. Sé que soy mucho más consciente sobre el diseño cuidadoso de esquemas de bases de datos y la escritura de consultas ahora que sé un poco más sobre cómo funcionan los RDBMS bajo el capó.

Pero no sé nada sobre modelos de datos OLAP multidimensionales, y me ha costado encontrar información útil en Internet.

¿Cómo se almacena la información en el disco? ¿Qué estructuras de datos componen el cubo? Si un modelo MOLAP no usa tablas, con columnas y registros, entonces ... ¿qué? Especialmente en datos altamente dimensionales, ¿qué tipos de estructuras de datos hacen que el modelo MOLAP sea tan eficiente? ¿Las implementaciones de MOLAP utilizan algo análogo a los índices de RDBMS?

¿Por qué los servidores OLAP son mucho mejores en el procesamiento de consultas ad hoc? Los mismos tipos de agregaciones que pueden tardar horas en procesarse en una base de datos relacional ordinaria se pueden procesar en milisegundos en un cubo OLTP. ¿Cuáles son los mecanismos subyacentes del modelo que lo hacen posible?

Answer 1

El libro Microsoft SQL Server 2008 Analysis Services Unleashed detalla algunas de las particularidades de SSAS 2008 con detalles decentes. No es exactamente un "así es exactamente como SSAS funciona bajo el capó", pero es bastante sugerente, especialmente en el lado de la estructura de datos. (No es tan detallado / específico sobre los algoritmos exactos.) Algunas de las cosas que yo, como aficionado en esta área, reuní de este libro. Esto es todo acerca de SSAS MOLAP:

• A pesar de todo lo que se dice acerca de los cubos multidimensionales, los datos de la tabla de hechos (también conocido como grupo de medida) aún se almacenan en una primera aproximación básicamente en tablas 2D, una fila por hecho. Varias operaciones OLAP parecen consistir en iterar sobre filas en tablas 2D.
• Sin embargo, los datos son potencialmente mucho más pequeños dentro de MOLAP que dentro de una tabla SQL correspondiente. Un truco es que cada cadena única se almacena solo una vez, en un "almacén de cadenas". Las estructuras de datos pueden referirse a cadenas en una forma más compacta (por ID de cadena, básicamente). SSAS también comprime las filas dentro de la tienda MOLAP de alguna forma. Esta reducción, supongo, permite que más datos permanezcan en RAM simultáneamente, lo cual es bueno.
• Del mismo modo, SSAS a menudo puede iterar sobre un subconjunto de los datos en lugar del conjunto de datos completo. Algunos mecanismos están en juego:
  • Por defecto, SSAS crea un índice hash para cada valor de dimensión / atributo; por lo tanto, sabe "de inmediato" qué páginas del disco contienen los datos relevantes para, por ejemplo, Año = 1997.
  • Hay una arquitectura de almacenamiento en caché donde los subconjuntos relevantes de los datos se almacenan en la memoria RAM separada de todo el conjunto de datos. Por ejemplo, es posible que haya almacenado en caché un subcubo que tenga solo algunos de sus campos, y que solo pertenezca a los datos de 1997. Si una consulta solo hace referencia a 1997, se repetirá solo sobre ese subcubo, acelerando así las cosas . (Pero tenga en cuenta que un "subcubo" es, en una primera aproximación, solo una tabla 2D).
  • Si se trata de agregados predefinidos, estos subconjuntos más pequeños también se pueden calcular previamente en el tiempo de procesamiento del cubo, en lugar de simplemente calcularlos / almacenarlos en caché a pedido.
• Las filas de la tabla de hechos de SSAS son de tamaño fijo, lo que presumiblemente ayuda de alguna forma. (En SQL, en contraste, puede tener columnas de cadenas de ancho variable).
• La arquitectura de almacenamiento en caché también significa que, una vez que se ha calculado una agregación, no es necesario volver a analizarla desde el disco y volver a calcularla una y otra vez.

Estos son algunos de los factores en juego en SSAS de todos modos. No puedo afirmar que no haya otras cosas vitales también.

Answer 2

Implementé un par de sistemas que imitaban lo que hacen los cubos OLAP, y aquí hay un par de cosas que hicimos para que funcionen.

1) Los datos del núcleo se mantuvieron en una matriz dimensional, todos en la memoria, y todas las claves se implementaron a través de jerarquías de punteros a la matriz subyacente. De esta manera, podríamos tener múltiples conjuntos diferentes de claves para los mismos datos. Los datos en la matriz eran el equivalente de la tabla de hechos, a menudo solo tenía un par de datos, en una instancia, este era el precio y el número vendido.

2) La matriz subyacente a menudo era escasa, por lo que una vez que se creó, utilizamos para eliminar todas las celdas en blanco para ahorrar memoria, una gran cantidad de aritmética de puntero duro, pero funcionó.

3) Como teníamos jerarquías de teclas, pudimos escribir rutinas con bastante facilidad para desglosar / subir una jerarquía fácilmente. Por ejemplo, accederíamos al año de datos, pasando por las claves de meses, que a su vez se asignaron a días y / o semanas. En cada nivel, agregamos datos como parte de la construcción de los cálculos hechos en cubo mucho más rápido.

4) No implementamos ningún tipo de lenguaje de consulta, pero apoyamos el desglose en todos los ejes (hasta 7 en nuestros cubos más grandes), y eso estaba directamente relacionado con la interfaz de usuario que gustaba a los usuarios.

5) Implementamos el núcleo en C ++, pero en estos días creo que C # podría ser lo suficientemente rápido, pero me preocuparía cómo implementar arrays dispersos.

Espero que ayude, parezca interesante.