Implementación de Leapfrog Triejoin sobre estructuras de datos compactas

Abstract

Las operaciones de join en bases de datos resultan costosas, ya sea en el tiempo que toma o en el espacio utilizado por los índices que resuelven dichas consultas.

En el último tiempo se han introducido los algoritmos Worst Case Optimal para joins. Estos algoritmos permiten resolver una consulta en tiempo lineal respecto al máximo tamaño posible de la respuesta de dicha consulta en alguna base de datos. El problema de estos algoritmos es que para poder responder de manera tan eficiente deben almacenar las tablas en todas las permutaciones posibles de los atributos, y dependiendo de cómo se están indexando estos datos, el espacio ocupado puede llegar a ser muy grande.

La solución desarrollada propone dos índices para almacenar los datos, LTJ IV y LTJ WM, que se basan en estructuras compactas. Además provee una implementación del algoritmo Leapfrog Trie Join (el algoritmo Worst Case Optimal más popular) que está abstraída de los índices que utiliza, lo que permite que futuros usuarios puedan implementar otra versión de un índice que siga la interfaz provista.

El índice LTJ IV tuvo buenos resultados, siendo más rápido que los índices clásicos con los que se lo comparó y ocupando sólo unas 3 veces el tamaño original de los datos que se indexaron, asimismo utilizó menos de un tercio del tamaño del menor índice no compacto Worst Case Optimal, y aproximadamente la mitad de los clásicos no Worst Case Optimal. Por otro lado el índice LTJ WM no tuvo tan buenos resultados, siendo más rápido que algunos de los índices comparados, pero en general teniendo tiempos de respuesta de consultas bastante altos. Junto con esto utiliza más espacio que LTJ IV, por lo que no resultó ser una buena solución en comparación.

Se concluye que la representación compacta de las estructuras del algoritmo Leapfrog Triejoin permite reducir su espacio a un tercio del original e incluso reducir sus tiempos de consulta en un 30\%. Los nuevos índices no resultaron competitivos, en cambio, contra Ring, un índice comprimido ya existente que es más sofisticado, pero sólo funciona para tablas de tres atributos.