On Cost Estimation for the Recursive Relational Algebra

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.Recursion is becoming a key construct in analytic systems, thanks to the increasing popularity of data structures such as graphs and growth in data over the internet. This resurgence has seen different optimization techniques proposed for recursive queries. Recursive queries are particularly useful for retrieving nodes reachable along deep paths in a graph. Their evaluation involves an iterative application of a function or operation until some condition is satisfied. Cost models remain an essential component of a query optimizer, most important for estimating the cost of query plans and quality plans selection by the optimizer. For recursive queries, however, cost estimation is far from trivial and has received less attention.One of the challenges encountered in costing a recursive query operator or plan includes determining the convergence rate of the recursive. Many systems ignore convergence rate in the data statistics, implementation algorithm, and other factors that determine a good cost estimation for recursive query execution. The lack of cost estimation framework support for recursive queries and a validation framework in general for cost model are the main motivation for this work.In this thesis, we propose a cost estimation technique for recursive terms of the extended relational algebra. This technique uses data statistics and information about the maximum iterative steps needed for recursive evaluation to converge, to estimate the cost of query plans and select an estimated cheapest query plan, in terms of computing resources usage e.g. memory footprint, CPU and I/O, and evaluation time. We also present a cost validation framework where we define a set of metrics and standard specifications for cost model and the conditions for query plan optimality. These set of metrics and specifications are then used for assessing the efficacy and consistency of the plan-selection function of a cost model and they can also serve as a guide for developing advanced cost models.We evaluate the effectiveness of our cost estimation technique on a set of recursive graph queries on both generated and real datasets of significant size. Experiments show that our cost estimation technique improves the performance of recursive query evaluation on popular relational database engines