La era de los datos está aquí, y aunque tal vez haya empezado hace varias décadas, podemos decir que los datos están evolucionando y posiblemente muy rápido, y a su vez, la necesidad de entender estos datos es cada vez mayor. Existe mucha investigación sobre estas tendencias, nuevas maneras de almacenar tablas, nuevas maneras de extraerlas, y claro que con nuevas maneras de procesar datos también existen nuevas propuestas de indexación y estructuras de datos para que se puedan satisfacer los requerimientos del DBMS al que sirven (y a su vez, que satisfagan la naturaleza de los datos que guardan, ya sea OLAP u OLTP), teniendo como ejemplo in-memory databases. Este artículo explora algunas de las propuestas de índices localizadas a través de publicaciones en la base de datos de arXiv, que pertenece a la Universidad de Cornell, con el propósito de ilustrar los retos que tenemos que enfrentarnos para poder evolucionar al mismo ritmo que nuestros datos lo hacen.
Índices híbridos (Hybrid indexes)
Este tipo de índice fue diseñado para aplicaciones del tipo OLTP sobre manejadores del tipo main-memory parallel databases, y la publicación original puede ser encontrada aquí (http://www.cs.cmu.edu/~./dga/papers/hybrid-index-sigmod2016.pdf). Esta publicación trata sobre la implementación de este tipo de índice sobre el manejador H-Store, el cual es un DBMS experimental main-memory desarrollado por un equipo de varias universidades (el lector interesado puede probar este manejador en instalaciones con Ubuntu). Aunque este tipo de bases de datos (main-memory) puede considerarse como otra categoría de base de datos en comparación a ambientes bancarios trabajando con Db2 en z/OS y tal vez no sea adecuado para servir a millones de transacciones por segundo, es común la tendencia de favorecer y explotar el uso de memoria, lo cual hemos visto en el mundo de Mainframe en actualizaciones como el mover estructuras arriba de la barra, mover buffer pools a memoria, o la nueva capacidad de Db2 de fast index traversal.
Dentro de ambientes de alto nivel de transacciones, es evidente que los registros más recientes o modificados recientemente sean leídos con mayor frecuencia hasta llegar al punto donde se vuelven estáticos, en donde serán leídos a través de queries que buscan por rangos (ranged queries) u operaciones agregadas (por ejemplo, al usar las funciones AVG, SUM y similares), y en este último caso se confirma su naturaleza estática. Esta premisa generó lo que los autores llaman hybrid indexes, lo cual fue extendido a un índice de tres partes o etapas:
- Una estructura dinámica que almacenará los datos recientes (referenciado como hot data), es decir, los registros recientemente insertados o modificados.
- Una estructura compactada (en modo lectura solamente) para almacenar datos estáticos. En este momento los datos se pueden considerar como datos históricos.
- Un filtro binario (bloom filter) que dirige al query a la estructura correspondiente de manera que un query no debe realizar un scan en las dos etapas de los puntos anteriores.
El nuevo índice híbrido es flexible en su implementación ya que las estructuras de datos de su interior pueden variar desde un árbol B++, una lista ligada (linked list) o cualquier otra estructura. La publicación completa provee una breve discusión sobre cómo varios tipos de estructuras de datos pueden compactarse para ser utilizadas en la etapa estática y también ofrece varias alternativas de cómo se puede realizar un merge para migrar datos de la etapa dinámica hacia la etapa estática.
El diagrama general de este índice se observa a continuación:
El filtro binario (bloom filter) recibe el predicado del query y evalúa si existen registros que califican al igual que su ubicación para direccionar la lectura a solo una etapa y de ahí hacia el RDS. Si el query busca datos que no existen será la tarea del bloom filter el evitar su acceso innecesario a alguna otra estructura del índice. Como fue mencionado previamente, al mantener dos tipos de estructuras es necesario un algoritmo eficiente que realice un merge de manera periódica, por ejemplo, utilizando un indicador (ratio threshold).
En pruebas se detectó una mejora de tiempos de respuesta de entre el 4% al 20% dependiendo de las estructuras utilizadas (árbol B++ o algunas otras) y el tipo de datos que fueron almacenados (las pruebas incluyen números enteros y caracteres). También fue detectada una variación e incremento de respuesta entre estructuras de datos comprimidas vs compactadas.
La clave u objetivo de esta propuesta es presentar un índice que pueda ser manejado en memoria, lo cual es una habilidad explotada por H-Store y otros manejadores del tipo main-memory. Probablemente en el futuro cercano estaremos viendo este mismo enfoque en otros tipos de manejadores ya que está dirigido a cargas de trabajo transaccional.
Índices aprendidos (Learned indexes)
En esencia, un índice es una estructura tal que, al ser escaneada, regresa un apuntador o llave hacia una ubicación dentro de una tabla (o columna en el caso de un índice de columna), pero si es visto desde otro ángulo, un índice es un modelo donde su atributo objetivo (target feature) es una llave o apuntador al registro específico o a un rango de registros y este mismo atributo objetivo es una variable continua, en donde también tenemos que un bloom filter se puede considerar como un clasificador binario. Tomando en cuenta este enfoque, se puede realizar un descubrimiento interesante: Un índice es un modelo que puede ser aprendido (o en el término directo, machine learned). Un equipo de Google publicó recientemente una propuesta de un nuevo índice que combina el mundo de Machine Learning y manejadores de bases de datos, el cual llamaron learned indexes (la publicación original se encuentra aquí https://arxiv.org/abs/1712.01208). Su intención es promover la investigación sobre bases de datos en el campo de Machine Learning.
La publicación original también abre una nueva posibilidad en términos de hardware. Actualmente existe un amplio campo de investigación para obtener predicciones más ágiles y reducir los tiempos de entrenamiento de modelos, en donde frecuentemente se direcciona el trabajo de redes neuronales a procesadores GPU o al nuevo procesador de Google TPU (Tensor Processing Unit).
Anotación adicional: Qué es un TPU?
De manera de introducción, una red neuronal puede ser vista como una serie de multiplicaciones de matrices, teniendo la salida de una neurona con la siguiente forma:
z = f ( w1x1 + w2x2 + … + wnxn + b )
Donde w son los pesos de entrada, b es la entrada de bias, la función f es una función de activación de la neurona (sigmoide, Relu, tanh u otra) y z es la salida de la neurona (llamada logit).
El proceso de entrenamiento de una red requiere un gran número de multiplicaciones que pueden ser muy costosas dependiendo del número de capas de la red, y en algunos casos puede resultar en millones de operaciones. Para este problema, y sabiendo que muchas de las soluciones de Google están basadas en redes neuronales, ellos crearon un nuevo chip dirigido a este tipo de operaciones a través de un compilador que traduce llamadas del API de TensorFlow al set de instrucciones de este nuevo chip, y de ahí su nombre Tensor Processing Unit.
Ahora que estamos en términos de Machine Learning, un índice puede ser un problema del tipo de regresión y un bloom filter es un clasificador binario, pero esto conlleva a una aclaración importante en el campo de Bases de Datos:
- Un índice de base de datos no puede regresar un falso negativo, es decir, no debe regresar que un registro no existe cuando de hecho sí existe.
- El índice podría, de acuerdo a la consideración de la implementación, regresar algún falso negativo, en donde el peor escenario provocaría table scans que finalmente regresan un mensaje SQLCODE +100.
Para tratar esta situación, los autores consideran que se puede complementar agregando otro tipo de estructura más tradicional, en cuyo caso es ahora otro tipo de índice híbrido.
Continuando con la definición de términos ahora en una perspectiva de Machine Learning, un árbol B puede evolucionar a un regresor lineal o una red neuronal, en donde un escaneo puede regresar un apuntador min-max (y esto a su vez puede considerarse como la función de error del modelo) y la operación de reconstrucción del índice pasa a ser el entrenamiento del modelo. Por otro lado, si el Tablespace se encuentra ordenado (cluster ordered) se podría tomar ventaja de este hecho y el aprendizaje de la distribución de datos equivale a calcular su CDF (Cumulative Distribution Function), convirtiendo la situación en un problema de estadística.
Dentro de la implementación de este nuevo tipo de índice, los autores proponen una estrategia de índice recursivo donde cada capa toma la llave/apuntador como entrada y selecciona el modelo para la siguiente capa hasta que se regresa una predicción, y en cada capa se estará disminuyendo la función de error. Este diseño es flexible en que la primera capa puede ser una red neuronal y las últimas capas pueden ser regresores lineales o árboles B tradicionales con el objetivo de minimizar la cantidad de operaciones resultantes, y dentro de su desempeño el peor de los casos sería el de un árbol B en donde todas las capas son a su vez árboles B.
Como se esperaba de un problema de Machine Learning, la complejidad del modelo y el ajuste de parámetros pueden crear una diferencia, donde se puede tomar ventaja de grid search para la optimización de parámetros y por otro lado, la complejidad del modelo podría ser mejor solucionado a través de regresores lineales en lugar de redes neuronales (y a su vez, en algunos casos una red neuronal de una sola capa podría dar mejor desempeño sobre redes de varias capas). Con esta configuración, se realizaron experimentos sobre índices secundarios utilizando tres tipos de datos y el modelo de comparación siendo un índice de árbol B, teniendo como resultados lo siguiente:
Adicionalmente, esta propuesta de learned indexes puede ser extendida hacia índices del tipo hash y bloom filters en los que cada tipo presenta un reto único: En el caso de implementación del tipo hash el uso de CDF parece apropiado, mientras que en bloom filters, el problema puede plantearse de manera que hay que encontrar una función f que pueda regresar un radio de cero en falsos negativos (false negative rate FNR) y tal vez un radio de cero en falsos positivos (false positive rate FPR).
Sin embargo, para investigaciones futuras, el problema de overfitting es importante y evidente. De manera general en el paradigma de Machine Learning, overfitting indica que el modelo va a memorizar la distribución y patrones a tal nivel que su certeza será absoluta pero no podrá generalizar sobre nuevos datos. Para el caso de índices, esto indica que el índice que aprenda la distribución de datos perfectamente podrá ofrecer buenos resultados siempre y cuando sea índice en modo sólo lectura y no sería óptimo para procesar datos recientemente insertados o actualizados. En cualquier caso, la pregunta sería ¿qué tan frecuente debo entrenar los índices?
Aunque esta publicación recomienda learned indexes como un nuevo tipo de índices para Data Warehouses o índices de solo lectura que se reconstruyan una vez al día, este trabajo propone varias alternativas que pueden ser exploradas a más detalle para crear un índice que pueda ser actualizable y cómo es que este índice generaliza sobre datos en constante flujo.
Conclusiones
La nueva era de Base de Datos comenzó hace unos años y todos los días escuchamos sobre este tema mientras que al mismo tiempo escuchamos sobre nuevas tendencias en datos y esto a su vez impulsa la investigación en el campo de Bases de Datos para entregar soluciones adecuadas e innovadoras que pueden evolucionar y satisfacer los nuevos requerimientos. La aparición de publicaciones similares ha creado tecnologías que ahora conocemos como Hadoop, MapReduce, Spark, Dockers y muchas otras tecnologías que constantemente nos están retando a cambiar nuestra manera de ver y trabajar con datos, de forma que es importante estar al tanto de nuevas propuestas, nuevos descubrimientos, nuevas soluciones, y contribuir con nuevas ideas para que podamos experimentar una evolución más uniforme.
Referencias
- Kraska, A. Beutel, Ed. Chi., J. Dean, and N. Polyzotis (2017). The Case for Learned Index Structures. ArXiv.org Cornell University Library, 1-27. Consultado el 2 de Enero del 2018 desde https://arxiv.org/abs/1712.01208
- Zhang, D. G. Andersen, A. Pavlo, M. Kaminsky, L. Ma, and R. Shen. Reducing the storage overhead of main-memory OLTP databases with hybrid indexes. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016 K. S. (2017, May 12).
- An in-depth look at Google’s first Tensor Processing Unit (TPU). Consultado el 3 de Enero del 2018 desde https://cloud.google.com/blog/big-data/2017/05/an-in-depth-look-at-googles-first-tensor-processing-unit-tpu
- Buduma, N. (2017). Fundamentals of Deep Learning: Designing Next-generation Artificial Intelligence Algorithms / c Nikhil Buduma. Beijing, Boston, Farnham, Sebastopol, Tokyo: OReilly.
- Muller, A. C., & Guido, S. (2017). Introduction to machine learning with python: a guide for data scientists. Sebastopol, CA: OReilly.
#espanol