Laboratoire d'Informatique de Grenoble

Résumé:
La récursivité devient un élément clé des systèmes analytiques, grâce à la popularité croissante des structures de données telles que les graphes et à l'augmentation des données sur Internet. Cette résurgence a vu différentes techniques d'optimisation proposées pour cette classe de requêtes. Les requêtes récursives sont particulièrement utiles pour récupérer les nœuds accessibles le long de chemins profonds dans un graphe. Leur évaluation implique une application itérative d'une fonction ou d'une opération jusqu'à ce qu'une condition soit satisfaite. Le modèle de coût reste une composante essentielle d'un optimiseur de requêtes, surtout pour l'estimation du coût des plans de requête et la sélection des plans de qualité par l'optimiseur. Pour les termes récursifs, cependant, l'estimation des coûts est loin d'être triviale et a reçu moins d'attention.

L'une des difficultés rencontrées dans le calcul du coût d'un opérateur ou d'un plan d'interrogation récursif consiste à déterminer le taux de convergence du récursif. De nombreux systèmes ignorent le taux de convergence dans les statistiques de données, l'algorithme de mise en œuvre et d'autres facteurs qui déterminent une bonne estimation du coût de l'exécution d'une requête récursive. L'absence d'un cadre d'estimation des coûts pour les requêtes récursives et d'un cadre de validation en général pour le modèle de coût sont la principale motivation de ce travail.

Dans cette thèse, nous proposons une technique d'estimation des coûts pour les termes récursifs de l'algèbre relationnelle étendue. Cette technique utilise des statistiques de données et des informations sur les étapes itératives maximales nécessaires à la convergence de l'évaluation récursive, pour estimer le coût des plans de requête et sélectionner un plan de requête estimé le moins cher, en termes d'utilisation des ressources informatiques, par exemple l'empreinte mémoire, le CPU et les E/S, et le temps d'évaluation. Nous présentons également un cadre de validation des coûts dans lequel nous définissons un ensemble de mesures et de spécifications standard pour le modèle de coût, et la condition d'optimalité du plan de requête. Cet ensemble de mesures et de spécifications est ensuite utilisé pour évaluer l'efficacité et la cohérence de la fonction de sélection du plan d'un modèle de coût et peut également servir de guide pour l'élaboration de modèles de coût efficaces. Nous évaluons l'efficacité de notre technique d'estimation des coûts sur un ensemble de requêtes de graphes récursives sur des ensembles de données générées et réelles de taille significative, notamment. Les expériences montrent que notre technique d'estimation des coûts améliore la performance de l'évaluation des requêtes récursives sur les moteurs de bases de données relationnelles les plus populaires.