Une méthode d’optimisation hybride pour une
évaluation robuste de requêtes

Approche d’optimisation basée sur des estimations en points singuliers

Les méthodes proposées dans cette approche font usage de valeurs singulières d’estimations. Pendant la phase initiale d’optimisation, l’optimiseur considère que les estimations sont précises. Cette approche peut être décrite comme suit (Cf. Figure 2.2, Page 35) : un optimiseur traditionnel est d’abord utilisé pour produire un plan optimal par rapport à un modèle de coûts. A l’exécution, des statistiques actualisées sont recueillies et comparées à celles utilisées par l’optimiseur. Si la différence est significative, alors l’exécution en cours est interrompue. Les statistiques actualisées sont utilisées pour ré-optimiser le reste du plan. A chaque invocation, l’optimiseur associe des valeurs spécifiques aux paramètres nécessaires aux calculs de coûts. Les plans d’exécution choisis sont alors optimaux pour des conditions d’exécution particulières. 34 Chapitre 2: État de l’art Figure 2.2 – Approche d’optimisation basée sur des estimations en points singuliers Cette approche d’optimisation permet de détecter les erreurs d’estimations et corriger les sous-optimalités qui en résultent en modifiant le reste d’un plan durant l’exécution. Les phases d’optimisation et d’exécution peuvent être entrelacées, éventuellement, plusieurs fois lors de l’exécution d’une requête. Les méthodes dans cette approche divergent sur la fréquence à laquelle elles peuvent modifier un plan d’exécution. Cette modification peut se produire soit entre les opérateurs soit lors de l’exécution d’un opérateur. Dans le reste de cette section, nous proposons de classifier les méthodes dans cette approche selon ce critère, i.e., granularité de modifications de plans d’exécution. Nous distinguons deux classes de méthodes : (1) des méthodes basées sur une correction de plans au niveau inter-opérateurs, et (2) des méthodes basées sur une correction de plans au niveau intra-opérateurs. Le reste de cette section est consacré à la description de ces deux classes de méthodes. 2.2.1 Méthodes basées sur une correction au niveau inter-opérateurs Dans cette classe de méthodes, un optimiseur découpe un plan d’exécution d’une requête en plusieurs étapes, dites sous-plans. Un sous-plan peut contenir un ou plusieurs opérateurs. Les résultats intermédiaires produits par un sous-plan sont matérialisés puis utilisés comme entrée pour le sous-plan suivant. La collecte de statistiques peut être déclenchée après l’évaluation de certains sous-plans ou après un évènement particulier 35 Chapitre 2: État de l’art comme l’arrivée de résultats partiels à partir des SGBDs locaux dans un environnement multi-bases (e.g., MIND [EDNO97]). Pour décrire ce principe d’une manière plus précise, nous prenons comme exemple une requête de jointure entre trois relations R, S, et T. Supposons que le plan P0 (Cf. Figure 2.3) est initialement sélectionné pour exécuter cette requête. Supposons qu’à l’exécution du premier sous-plan O1, une erreur d’estimation est détectée. Comme illustré dans la figure 2.3, la réaction à cette erreur se produit après terminaison du sous-plan en cours O1. Le plan est ré-optimisé et l’exécution de la requête reprend avec un nouveau plan. Figure 2.3 – Correction d’un plan d’exécution au niveau inter-opérateurs La littérature fournit plusieurs méthodes s’inscrivant dans cette classe de méthodes. Chacune des méthodes proposées a été conçue dans l’objectif de corriger des sous-optimalités causées par un ou des événements spécifiques, et chacune propose une ou des corrections possibles. Par exemple, Ozcan et al. [EDNO97] se sont concentrés sur l’indisponibilité de statistiques nécessaires pour pouvoir produire un plan d’exécution optimal. Ils ont introduit, dans le cadre du système multi-bases MIND, des stratégies de ré-ordonnancement 36 Chapitre 2: État de l’art dynamique d’opérateurs inter-sites (e.g., jointure). Ces stratégies exploitent les résultats partiels disponibles pour détecter les erreurs d’estimations et corriger un plan d’exécution. Cette correction consiste à ré-ordonnancer les opérateurs d’un plan pendant l’exécution. Dans une première étape, MIND décompose une requête en sous-requêtes. Celles-ci sont ensuite envoyées aux différents sites pour être exécutées en parallèle. A l’exécution, des statistiques sur les résultats intermédiaires retournés par les SGBDs locaux sont utilisées pour définir l’ordre d’exécution des opérateurs dépendant de ces résultats. Dans le même esprit, Neumann et al. [NGl13] ont proposé une méthode (CIE) qui vise à résoudre le problème d’optimisation de requêtes du à l’imprécision des estimations des cardinalités. Pour cela, les auteurs se sont basés sur le principe d’exécution incrémentale. Tout d’abord, un plan d’exécution optimal est construit en utilisant un optimiseur traditionnel. Puis, ce plan est découpé en sous-plans : les fragments sensibles du plan sont identifiés, ce sont les fragments où des erreurs d’estimations des cardinalités pourraient conduire à des sous-optimalités du reste du plan. CIE évalue la propagation d’erreurs éventuelles à ces fragments dans le reste du plan. Lorsque cette propagation dépasse un certain seuil, elle est considérée fatale pour le reste du plan. Ensuite, ces fragments sont exécutés, les résultats sont matérialisés. La cardinalité requise est obtenue. Un nouveau plan optimal peut ainsi être trouvé pour le reste de la requête en déclenchant une ré-optimisation. Matérialiser les résultats d’un sous-plan et les utiliser comme entrée pour le sous-plan suivant a également été proposé dans [KD98]. Dans ce travail, Kabra et DeWitt [KD98] ont introduit une méthode appelée « Mid-Query Re-optimization ». Cette méthode permet de détecter et de corriger la sous-optimalité d’un plan pendant l’exécution. Les auteurs ont adressé le problème de sous-optimalités de plans provenant d’un mauvais ordonnancement d’opérateurs, d’un choix inapproprié des algorithmes de jointure ou d’une mauvaise allocation de la mémoire. Ces anomalies seraient causées par des estimations de coûts erronées ou obsolètes, ou par un manque d’informations nécessaires relatives aux conditions d’exécution au moment de l’optimisation. Dans cette méthode [KD98], un optimiseur tra37 Chapitre 2: État de l’art ditionnel est d’abord utilisé pour générer un plan optimal. Ce plan est ensuite annoté par les statistiques utilisées par l’optimiseur. Pendant l’exécution, des statistiques actualisées sont collectées. Celles-ci sont comparées à celles utilisées pour choisir le plan. Si elles y sont différentes d’une manière significative (i.e., la différence dépasse un certain seuil), l’optimiseur est invoqué pour ré-optimiser le reste du plan. Les statistiques sont collectées par des opérateurs de collecte de statistiques, insérés dans le plan à des points dits points de contrôle. Un opérateur de collecte de statistiques est un opérateur unaire qui sert à contrôler les tuples qui le traversent. La méthode d’insertion de ces opérateurs associe un niveau d’incertitude (faible, moyen, élevé) aux différentes estimations. Seules les estimations affectant la qualité d’un plan sont vérifiées à l’exécution. 

Méthodes basées sur une correction au niveau intra-opérateurs

Les méthodes dans cette classe affinent la granularité de la modification de plans d’exécution. Elles permettent de corriger un plan pendant l’exécution d’un opérateur. Les statistiques sont collectées après qu’un bloc de tuples soit traité. Un bloc peut être constitué d’un ou plusieurs tuples. Dans cette perspective, les méthodes suivantes ont été proposées : le routage de tuples [AH00], et le partitionnement dynamique de données [IHW04]. Le routage de tuples a été le principe du travail présenté par Avnur et al. [AH00]. Dans [AH00], les auteurs ont proposé un mécanisme d’évaluation de requêtes nommé «Eddy». Eddy réordonne en continu les opérateurs d’une requête afin de s’adapter dynamiquement aux variations des caractéristiques de données (coût d’un opérateur, sélectivités d’opérateurs, taux d’arrivé des tuples). Eddy peut être considéré comme un routeur de tuples positionné entre des relations et des opérateurs. Chaque opérateur doit avoir une ou deux files d’attentes d’entrée pour recevoir les tuples envoyés par Eddy et une file d’attente de sortie pour retourner les tuples résultats à Eddy. Les tuples reçus par Eddy sont acheminés vers les opérateurs dans des ordres différents. Eddy sélectionne automatiquement un ordre pour acheminer chaque tuple. Pour illustrer ceci, considérons la requête Q = σ(R) on σ(S) on σ(T). Un opérateur Eddy, deux opérateurs de jointure et trois opérateurs de sélection sont nécessaires pour exécuter cette requête. Eddy exécute Q en routant les tuples reçus à partir des relations R, S et T, vers les opérateurs de sélection et de jointure. Lorsqu’un opérateur reçoit un tuple de Eddy, il y applique le prédicat correspondant et retourne les résultats à Eddy. Ce dernier transmet les résultats aux opérateurs restant pour la suite de l’exécution. Les performances dans le mécanisme Eddy sont fortement dépendantes de la stratégie de 41 Chapitre 2: État de l’art routage. Celle-ci se réfère à l’ensemble de règles utilisées pour choisir -pour un tuple- la destination valide. La stratégie de routage doit être efficace et intelligente afin de minimiser le temps de réponse. Par exemple, Eddy ne doit pas acheminer les tuples de R à l’opérateur de sélection σ(S). La principale limite dans Eddy, c’est que les algorithmes de routage sont des algorithmes gloutons. Ces algorithmes opèrent d’une manière itérative. A chaque itération, ils minimisent une fonction partielle des coûts en choisissant un optimal local. Ceci ne permet toujours pas d’obtenir une optimalité globale [BB05]. De plus, Eddy doit explorer plusieurs routes pour trouver le plan adéquat. Ceci peut induire un sur-coût important [BB05]. Dans la même perspective qu’Eddy [AH00], à savoir obtenir un résultat global à partir de résultats partiels, Ives et al. [IHW04] ont proposé une méthode d’optimisation basée sur le partitionnement dynamique de données. Cette méthode vise à corriger les sousoptimalités de plans causées par des erreurs d’estimations dues au manque d’informations sur les sources de données lors de l’optimisation. Comme dans Eddy [AH00], la correction d’un plan se fait pendant l’exécution d’un opérateur. Cependant, le principe de fonctionnement est différent. Dans [IHW04], un ensemble de plans d’exécution est associé à chaque requête. Ces plans seront exécutés en parallèle ou en séquence sur des partitions de données distinctes. Les décisions sur la façon de répartir les données dépendent de nombreux facteurs, par exemple, la sémantique de chaque opérateur, les statistiques disponibles sur les données. L’exécution d’un plan associé à une requête est contrôlée. Ce plan peut être remplacé par un nouveau plan s’il s’avère sous-optimal. Les tuples traités par chaque plan représentent un partitionnement de données. Quand un plan d’exécution est remplacé, un nouveau partitionnement de données est produit. L’union des tuples produits par les différents plans ne fournit qu’une partie du résultat global. Ainsi, pour calculer le résultat global d’une requête, il faut calculer les résultats des combinaisons des divers partitionnements de données. Pour illustrer ceci, nous fournissons un exemple d’une requête Q de jointure entre trois relations R, S et T. Supposons qu’en se basant sur des statistiques disponibles, un plan P0 est d’abord généré pour Q = (R on S) on T. Lors de l’exécution, 42 Chapitre 2: État de l’art des statistiques actualisées sont recueillies. Supposons que l’optimiseur se rend compte que P0 est sous-optimal et qu’il serait préférable de remplacer P0 par un plan P1 pour Q = R on (S on T). Plutôt que de redémarrer la requête en utilisant P1, l’optimiseur suspend le plan partiellement exécuté, à savoir P0 qui a déjà retourné des résultats. P0 représente la phase 0 de l’exécution. Les tuples traités dans cette phase sont dénotés R0 , S 0 et T 0 . P1 représente la 1ère phase. Les tuples traités dans cette phase sont dénotés R1 , S 1 et T 1 .   Dans cette méthode, comme dans toutes les méthodes précédemment décrites dans l’approche d’optimisation basée sur des estimations en points singuliers, l’objectif est d’assurer des performances optimales dans des circonstances d’exécution spécifiques. Ces circonstances sont modélisées par des estimations singulières des paramètres nécessaires aux calculs des coûts. Pour atteindre leur objectif, les méthodes dans cette approche s’appuient sur un comportement réactif. Quand une sous-optimalité d’un plan d’exécution est détectée, l’optimiseur de requêtes est invoqué pour corriger cette sous-optimalité. Une correction décidée par l’optimiseur peut être fondée sur des estimations à nouveau erronées. Par conséquent, l’optimiseur peut être ré-invoqué plusieurs fois durant l’exécution d’une requête. Ceci peut induire un sur-coût important et une dégradation des performances. Une approche alternative a été proposée pour éviter ce problème. Celle-ci vise la prévention plutôt que la correction de sous-optimalités de plans d’exécution. La possibilité d’erreurs dans les estimations utilisées par l’optimiseur est tenue en compte dès la phase initiale d’optimisation. Pour modéliser ces erreurs potentielles, cette approche alternative fait usage de plusieurs points plutôt qu’un point singulier pour estimer chaque paramètre présumé incertain. Cette approche est appelée optimisation basée sur des estimations en 43 Chapitre 2: État de l’art un ensemble points. Elle est détaillée dans la section suivante.