Sobre el problema de la implementación de funciones de base de datos "Fan out" - parte II
En la parte 1 de este artículo, introduje el problema de la base de datos en fan out, y pensamos que cada función de este tipo es en realidad una multifunción con 2 ^n versiones, dadas n entradas. En esta parte, nos centraremos en las soluciones actuales al problema en dos bases de datos de código abierto: MonetDB &ClickHouse. Además, intentaremos encontrar soluciones simples, pero ineficaces/ incompletas aun.
Resumen de solución estándar simple
La últimavez vimos brevemente una solución estándar para el problema de concat usando 4 funciones diferentes, una que llamamos escalar y 3 más que usaban al menos una entrada vectorial. Se veía así:
En pocas palabras, esta solución reutilizó la versión escalar (primera función en el fragmento de arriba) en las otras 3 versiones vectoriales (a continuación en el fragmento). La versión escalar sirve para una "ejecución de fila" (row execution): cada versión realmente establece los datos fila por fila (haciendo un bucle en el vector / vectores de entrada), y ejecuta la versión escalar para cada fila. Fácil y muy efectivo (suponiendo que la versión escalar es efectiva). Sin embargo, como ya indiqué, esta solución conlleva muchas desventajas: horrible duplicación de código (4 versiones), complicado de modificar (imagina que hay que cambiar la estructura de datos de vector a otra cosa) y no es fácilmente comprobable. Se trata de un código repetitivo, al igual que su código de prueba. No es la solución ideal, especialmente si tenemos que implementar más de 100 de estas funciones múltiples en una base de datos.
Acontinuación, intentaré ofrecer una visión general de las soluciones al problema en MonetDB y ClickHouse. El código de ambos proyectos es extremadamente complejo, así que intentaré concentrarme en el panorama general sin entrar en demasiados detalles. Creo que, aunque diferentes, no son tan diferentes de la solución anterior conceptualmente.
Solución MonetDB*
Echemos un vistazo a cómo se resuelve este problema en MonetDB*. Esta base de datos está implementada en lenguaje C y no es fácil de leer para la mayoría de los usuarios. Una sola versión de la implementación de subString se ve así:
No te preocupes, no estamos interesados en los detalles de implementación de esa función. Lo que nos interesa es la cantidad de versiones diferentes que tiene esta función en la base de datos. Un lugar fácil para examinar esto es en el registro de la subcadena en el archivo de catálogo de la base de datos:
En la terminología de MonetDB, arg es un escalar (por tanto arg("start",int) es un parámetro escalar con el nombre "inicio" y tipoint) y batarg es un vector con la misma declaración (nombre,tipo). En el código anterior, observa los últimos 3 argumentos en cada línea de registro y podrás ver que registranlas 7 versiones diferentes no escalar es de subString (la versión escalar está registrada en un archivo diferente). Por ejemplo, en la primera línea, los últimos 3 argumentos son: batarg ("s",str), batarg("start",int), batarg("index",int)lo que significa que registra la versión de subString con 3 vectores de entrada ("111" en nuestra tabla de verdad del artículo anterior).
Conclusión: ignorando todo este código específico de detalles de la base de datos (que es muy largo, como has visto arriba. Ahora imagina copiar y pegar ese código 7-8 veces repartido en cientos de filas), tenemos 7 funciones vectoriales diferentes e independientes + 1 función escalar adicional. En esta base de datos en específico, no encontrará ninguna prueba unitaria para ninguna de las versiones, y la reutilización del código en las 7 funciones (muy similares) no existe – solo han duplicado todo el código con pequeños cambios para todas las versiones. En pocas palabras: no es mejor que el ingenuo enfoque que hemos mostrado anteriormente con el ejemplo de concat.
Solución ClickHouse **
Esta base de datos está implementada en C ++ moderno (y muy bien escrito). Realmente es mi base de datos analítica favorita, un gran producto utilizado por muchas empresas en la nube (cloud-scale companies) y con un gran rendimiento. Puedo decir que lo he visto desde dentro, y los chicos de Yandex realmente han demostrado una gran innovación, diseño y han producido software de primera clase con excelentes técnicas avanzadas. Dicho esto, el problema que discutimos no se resuelve de una manera mucho mejor, solo con un código mucho más avanzado (con C++ moderno en lugar de C simple). Por cierto, creo que es mucho más complejo que el de MonetDB anterior. Echemos un vistazo.
Cada una de estas funciones múltiples en ClickHouse se implementa como una clase. Por ejemplo: class FunctionSubstring o classConcatImpl, ambos implementan la misma interfaz de clase. Vamos a echar un vistazo a la función subString's executeImpl:
La versión ClickHouse de esta función es mucho más compleja que la primera versión presentada anteriormente, así que tratemos de enfocarnos en lo que nos interesa:
1. La signatura o firma de la función es: subString(source, start, length) (subString(fuente, inicio, longitud)), siendo length opcional.
- Desde el principio, el código examina los 3 argumentos para concluir si cada uno es una constante o no (líneas 125-136). Termina con 2 versiones posibles para los argumentos inicio y longitud (start y length), y extrae los valores constantes si realmente son escalares (líneas 141-144). El código mantiene la ambigüedad de escalar / vector para cada parámetro al mantener una variable para cada versión. (e.g.: column_start & column_start_const para el parámetro start y start_value en caso de que sea una constante!).
- Ignorando las líneas 146-159 (esta es una variante de la clase que no nos interesa), puedes ver que las líneas 161-172 llaman a execute For Source con todos los argumentos posibles y con una conversión diferente de la última fuente del argumento. No quiero entrar en la diferencia entre los diferentes castings en las líneas 163, 166, 169 y 172, es demasiado complejo. Eventualmente, todas estas líneas llaman a la función executeForSource, presentada a continuación.:
- Nuevamente, sin entrar en muchos detalles, observa las rutas condicionales de los códigos que dependen de si cada parámetro es una constante o no. (líneas 91 y 105, y línea 89 que intenta averiguar si el parámetro de longitud (length) está en uso o no).
- Eventualmente, hay más llamadas a funciones en las líneas 94, 96, 101, 108, 110 y 115 - ¡todas son funciones diferentes!
- 6. De acuerdo - resuelven aquí más problemas que el original (por ejemplo: manejar el valor de inicio (start) negativo por alguna razón). ¡Pero echa un vistazo a la complejidad del código! Ya tenemos muchos caminos condicionales en las únicas 2 funciones que hemos examinado. Si profundizas en cualquiera de estas 6 llamadas de función, encontrarás más tipos que se utilizan para determinar cómo ejecutar la función subString subyacente. No sé cómo esto es sostenible, pero seguro que parece muy complejo.
Puede que me equivoque, pero creo que la raíz de esa complejidad es la forma en que tratan con todas estas versiones multifunción. En cualquier caso, no veo porqué implementar una función tan simple debería requerir tantas líneas de código. Tal vez me esté perdiendo algo y alguien más pueda aconsejarme. En pocas palabras: en esta implementación no hemos visto ninguna solución elegante y ordenada para el problema del fan out multifunción (muchas de las condiciones y funciones múltiples tampoco se eliminaron en esta solución).
Solución menos ingenua, pero sin usar TMP
Finalmente, me gustaría mostrar una solución mejorada a la primera que se muestra arriba. Me pregunto: ¿cuál es la "causa raíz" de nuestro problema? Creo que este es el hecho de que no podemos saber de antemano si un parámetro dado es una constante o un vector. Si pudiéramos abstraer eso de manera efectiva con un código ordenado, sin duplicaciones y repetición, estaremos en camino hacia la solución. Entonces, un enfoque (muy) ingenuo sería convertir cada parámetro escalar en un parámetro vectorial: simplemente inicia un vector del mismo tamaño con todas las celdas iguales a esa única constante. E.g.: si source es un vector con 10 M filas y start es la constante 0, crea un vectorde 10 M de longitud con todas las celdas iguales a 0. Eso ahora nos permitiría usar una única versión de la multifunción, ¡la que tiene todoslos vectores! ('111' en nuestra tabla de verdad).
Por supuesto, esta solución sería muy ineficiente en cuanto a la memoria,pero podemos modificarla un poco. En lugar de asignar un vector con 10 millones de filas de valor constante, podemos mantener ese valor una vez y usar algún tipo de abstracción que nos de ese único valor constante cuando solicitemos el valor en el índice i (como si fueraun vector). Veamos cómo se podría implementar esto. Echemos un vistazo a la siguiente clase Parameter:
Esta clase es una clase de plantilla en la que T es el tipo de parámetro. Sirve como la abstracción que buscamos en nuestro parámetro de tipo T- sea un simple T val o un vector<T>. Este tipo nos permite iniciarlo con T o con el vector <T> (ten en cuenta las 2 construcciones diferentes en el fragmento de código anterior). Por último, al usar getValue con el parámetro index, este tipo nos permite una abstracción de constante vs vector, permitiéndonos obtener el valor constante en el índice i aunque realmente no tengamos un vector detrás. Por supuesto, cuando de verdad hay un vector detrás, simplemente nos daría su i-ésimo elemento, como en cualquier vector.
Ahora podemos usar subString con la siguiente firma: subString (Parameter<String>,Parameter<int>, Parameter<Int> como nuestra única versión de subString (todavía necesitaríamos escribir código que "encajone" cada valor posible (constante o vector) en un objeto Parameter <T>). Ahora bien, ¿por qué no es una solución suficientemente buena? Recuerda que el rendimiento aquí es clave. Entonces, en lugar de usar acceso vectorial a travésde un bucle regular (regularloop) o una lectura de valor constante (constant value read), como en la primera versión anterior, lo reemplazamos con llamadas frecuentes a la función getValue (una porfila). Esta función utiliza una condición para cada cálculo de una sola fila. ¡Eso acaba con nuestro rendimiento! (Funciona dos veces más lento que la primera solución, si no más lento). Intentaré proporcionar una tabla de evaluaciones comparativas organizada al final de la parte 4 de este artículo). ¿Por qué? En resumen: esta condición no permitirá que el compilador use ninguna optimización de bajo nivel como SIMD, pre-cargar elementos vectoriales por lotes en la memoria / caché u otro (como tratar el valor escalar como una única constante que nunca cambia durante todo el cálculo).En cambio, creo que lo obliga a manejar la predicción de rama (branch prediction) en cada llamada, lo cual es irrelevante para este escenario. Hemos creado ese problema con nuestra solución, no estaba ahí en la primera solución). Reemplazar un problema por otro no era la idea.¡Además, una solución 2-3 veces más lenta no puede ser una solución al problema en una base de datos analítica a gran escala!
Antes deconcluir esta parte, quiero recalcar a los lectores modernos con conocimientos deC ++ que es posible implementar la clase Paramater <T> anterior de una manera mucho más elegante usando C++ 17's std::variant:
No entraré en detalles sobre esta implementación. Realmente es bastante sencillo una vezque estás familiarizado con std::variant (que por sí solo no es un concepto nuevo en otros idiomas). Lo sorprendente es que esta versión es incluso más lenta que la anterior sin usar std::variant! (Nuevamente,sería parte de la tabla de puntos de referencia al final de la parte 4 de esteartículo). Entonces, una vez más, esta no es la solución que buscamos.
Estos diferentes experimentos con resolución de tipo en tiempo de ejecución podrían empezar a convencerte de que buscamos una respuesta en el lugar equivocado; deberíamos intentar resolver esto en tiempo de compilación: ¡TMPal rescate!
Con eso concluye esta parte del artículo. Deja un comentario si tienes algo quepreguntar / comentar / arreglar o dale al botón Me gusta si quieres animarme:)
En la siguiente parte de este artículo, part III, Presentaré algunas técnicas y clases avanzadas de metaprogramación de plantillas de C ++(TMP) que se utilizarán como bloques de construcción para mi solución sugerida en la parte final que concluirá este conjunto de artículos. ¡Manténte al tanto!
_____________________________________________________________
* MonetDB- un sistema deadministración de base de datos de código abierto orientado a columnasdesarrollado en Centrum Wiskunde & Informatica en los Países Bajos. Fuediseñado para proporcionar un alto rendimiento en consultas complejas engrandes bases de datos, como la combinación de tablas con cientos de columnas ymillones de filas (de Wikipedia).
**ClickHouse – un sistema de administración de base de datos decódigo abierto para el procesamiento analítico en línea. ClickHouse fuedesarrollado por la empresa rusa de TI Yandex para el servicio de análisis webYandex.Metrica. ClickHouse permite el análisis de datos que se actualizan entiempo real. El sistema se comercializa para un alto rendimiento. (de Wikipedia).
Traducido por : Mirei Alba Kesti Izquierdo
