Laboratoire d'Informatique de Grenoble

Le but de ma thèse est d’étudier l’optimisation et la distribution de requêtes, principalement de requêtes récursives, qui manipulent de larges volumes de données. 

Je propose des extensions d’approches formelles suivant deux axes de travaux de recherche: (1) les algèbres basées sur le modèle de données relationnel et pour lesquelles je propose Dist-µ-RA, ainsi que (2) les algèbres basées sur les collections de types arbitraires, et pour lesquelles je propose µ-monoids. Dist-µ-RA est un système qui étend l’algèbre  µ-RA au contexte distribué. Concernant l’aspect algébrique, il s’intègre bien avec l’algèbre relationnelle et hérite de ses avantages tels que sa capacité à optimiser les requêtes quelles que soient leur forme initiale et leur traduction vers l’algèbre. Concernant l’aspect de distribution, différentes stratégies d’évaluation de termes algébriques récursifs dans un contexte distribué ont été étudiées. Ces stratégies sont implémentées sous forme de plans physiques avec des techniques qui automatisent la distribution des données afin de réduire les coûts de communication. Les résultats expérimentaux sur des graphes réels et synthétiques montrent l’efficacité de l’approche proposée par rapport aux systèmes existants. µ-monoids est une extension de l’algèbre de monoïdes avec un opérateur de point fixe qui modélise la récursion. L’algèbre µ-monoids est capable de modéliser des calculs récursifs sur des collections distribuées similaires à ceux effectués sur les plateformes Big Data. L’intérêt principal de l’opérateur de point fixe “µ” est que, sous réserve de conditions souvent remplies en pratique, il peut-être considéré comme un homomorphisme de monoïdes et peut donc être évalué avec des boucles parallèles avec une fusion finale plutôt qu’avec une boucle globale nécessitant des transferts réseau supplémentaires à chaque itération. Des règles de réécriture pour optimiser les termes récursifs, telles que le poussage de filtres, ont été proposées. Je propose en particulier une condition suffisante sur le terme évalué en boucle quelle que soit sa forme, ainsi qu’une méthode qui utilise les types polymorphes et un système de types comme celui de Scala pour vérifier si cette condition est remplie. Je propose également une règle qui préfiltre les points fixes avant les jointures. La troisième règle permet de pousser des fonctions d’agrégation dans les points fixes. Les expériences menées sur la plateforme Spark montrent les gains en performances apportés par ces optimisations systématiques.