Chapitre 6 bda Bases de données avancées Télécharger pdf

Télécharger PDF

Requêtes distribuées

Année Master S – USTHB 1ère. Dernière révision : Avril 2024.

Traitement des requêtes centralisées

Décomposition : La requête SQL est transformée en arbre algébrique.

Ordonnancement et Optimisation : Cette étape vise à optimiser les opérations relationnelles et les algorithmes d'accès aux données en utilisant :

Les propriétés des opérateurs (Associativité, Commutativité).
Des heuristiques (en évaluant les opérations les moins coûteuses possible de la requête).

Exécution : L'exécution élabore le résultat de la requête.

Le processus pour une requête centralisée se déroule comme suit : Requête centralisée → Décomposition → Optimisation → Plan d’exécution → Exécution → Résultats.

Évaluation d’une requête centralisée

Rappels : Un arbre algébrique est l'arbre généré suite à une expression relationnelle, dont :

Le nœud racine est le résultat de la requête.
Les nœuds intermédiaires sont les opérateurs.
Les arcs représentent les flux de données.
Les nœuds terminaux (ou feuilles) sont les relations.

Dans un système distribué, cet arbre est impacté par la répartition des données. Ceci implique :

Une prise en compte de la localisation des données, ce qui impacte l'optimisation.
Une complexité liée à l'optimisation globale et l'optimisation locale.

Traitement des requêtes distribuées

Le processus général est : Requête → Schéma global → Décomposition → Arbre algébrique → Informations sur la localisation et la fragmentation → Localisation → Requête répartie avec localisation et fragmentation → Modèles de coûts et statistiques → Optimisation → Plan d’exécution répartie → Exécution sur le site de contrôle → Exécution sur les sites locaux → Résultats.

Le site de contrôle est en général le site où la requête a été lancée.

Optimisation des requêtes distribuées

Le processus d'optimisation des requêtes distribuées comporte plusieurs couches :

Décomposition de requête : Cette couche prend la requête en termes de relations globales et effectue une première décomposition partielle à l'aide d'heuristiques sur l'ordonnancement des opérations.
Localisation de données : Cette couche prend en compte la localisation des données sur le système. On remplace les feuilles de l'arbre relationnel par leurs algorithmes de reconstruction.
Optimisation globale : Cette couche prend en compte les statistiques pour trouver un plan d'exécution proche de l'optimal sur les fragments.
Optimisation locale : Cette couche s'exécute sur chacun des systèmes de gestion de bases de données (SGBD) impliqués dans la requête. Elle effectue des optimisations classiques à l'aide d'heuristiques.

Décomposition

La requête globale (Req), par exemple "Quels sont les produits stockés à Alger ?", est décomposée en sous-requêtes locales. Par exemple, si nous cherchons les produits d'Alger : Π_{Prod, Libellé} (σ_{Ville='Alger'} (Produit)).

Relations :

Produit (Prod, Libellé, Pu, ...)
Stock (Prod, Ville, Qté)

Exemple de projection : Π_{Prod, Libellé} (Produit).

Localisation

La localisation d'une requête distribuée procède en plusieurs étapes :

Génération de l'arbre canonique.
Simplification (ou réduction).

L'arbre canonique est obtenu en remplaçant chaque relation globale par sa décomposition en fragments correspondante. Par exemple :

Union des fragments pour la fragmentation horizontale.
Jointure des fragments pour la fragmentation verticale.

Exemple d'arbre de requête et de reconstitution :

Si la table Stock est fragmentée horizontalement par la ville :

Stock₁ = σ_{Ville='Alger'} (Stock)
Stock₂ = σ_{Ville <> 'Alger'} (Stock)
Alors : Stock = Stock₁ U Stock₂

Si la table Produit est fragmentée verticalement :

Produit₁ = Π_{Prod, Libellé} (Produit)
Produit₂ = Π_{Prod, Pu,...} (Produit)

Simplification

Cette étape consiste à déterminer les opérations inutiles dans une requête, c'est-à-dire celles qui produisent un résultat vide ou identique à l'opérande.

Exemple 1 : Une opération de restriction sur un fragment horizontal qui est en contradiction avec le prédicat de fragmentation produit un résultat vide. Par exemple, appliquer σ_{Ville='Alger'} au fragment Stock₂ défini par Ville <> 'Alger'.
Exemple 2 : Éliminer les sélections de conditions inutiles. Par exemple, σ_{Ville='Alger'} sur le fragment Stock₁ défini par Ville='Alger', si la condition est identique à celle de la fragmentation.
Exemple 3 : Une opération de projection sur un fragment vertical qui ne projette pas l'attribut commun de reconstruction, ni les attributs projetés, donne un résultat vide. Par exemple : Π_{Prod, Libellé} (Produit₂).

Exemple : Arbre final simplifié.

Optimisation

Rôle de l'optimisation : Déterminer une stratégie d'exécution distribuée à moindre coût.

Le temps total d'exécution :

Pour les requêtes centralisées : Temps d'E/S + Temps de traitement BD.
Pour les requêtes distribuées : Temps d'E/S + Temps de traitement BD + Temps de communication (transferts de données, des résultats).

Il faut prendre en considération les gains en cas de parallélisme.

Objectifs et facteurs de l'optimisation : Minimiser la fonction de coût d'exécution.

Tenir compte de :

Du parallélisme.
Des coûts de transferts.
Des profils des fragments (taille, nombre de n-uplets, taille du domaine des attributs...).
De la taille des résultats intermédiaires.
De la topologie du réseau.

Exécution : processus d’exécution des requêtes distribuées

Le processus d'exécution des requêtes distribuées consistera en plusieurs étapes, c'est-à-dire l'exécution de requêtes locales et d'un processus d'exécution global. Le plan d'exécution est l'ensemble des traitements, y compris les opérations de communications des données nécessaires pour les exécutions locales et la synchronisation.

Exécution : Stratégies d’exécution

Les décisions à prendre dans le plan d'exécution sont les suivantes :

Ordre des jointures.
Stratégie de jointure.
Sélection des copies (site le moins engorgé).
Choix des sites d'exécution (en fonction du coût de communication).
Choix des algorithmes d'accès répartis.
Choix du mode de transfert (tuple/paquets).

Gestion du catalogue

Dans un système distribué, le catalogue ne contient pas seulement les données d'un catalogue classique (vues, index, ...), mais également toutes les informations nécessaires au système pour assurer la fragmentation et la localisation.

Quelques possibilités :

Centralisé : L'ensemble du catalogue est mémorisé sur un seul site central unique. Cette approche viole l'objectif « pas de contrôle centralisé ».
Duplication totale : L'ensemble du catalogue est entièrement mémorisé sur chaque site. Cela entraîne une perte importante d'autonomie.
Partitionné : Chaque site gère son propre catalogue concernant les objets de son site. L'ensemble du catalogue est l'union de tous les catalogues locaux et disjoints. Les opérations qui ne sont pas locales sont très coûteuses (accéder à un objet distant nécessite d'accéder en moyenne à plusieurs sites).
Combinaison de 1 et 3 : Chaque site gère son propre catalogue local, et de plus, un site gère une copie unifiée de tous les catalogues locaux. Plus efficace que la stratégie 3 mais viole l'objectif « pas de contrôle centralisé ».

Exercice

Soit le schéma relationnel traitant les visites de propriétés et les clients :

PROPRIETE (NUMP, VILLEP) : 10000 enregistrements stockés à Alger.
CLIENT (NUMC, PRIXMAX) : 100000 enregistrements stockés à Blida.
VISITES (NUMP, NUMC) : 1 000 000 d'enregistrements stockés à Alger.

On veut lister les propriétés qui dépendent de l'agence d'Alger et sont visitées par des clients dont la limite maximale de prix est supérieure à 30000.

Pour simplifier, on suppose que :

Il y a un maximum de 10 clients dont le PrixMax est supérieur à 30000.
Il y a 100000 visites de propriétés d'Alger.
Le temps de traitement est négligeable par rapport au temps de communication.

Nous supposons que le système de communication offre un taux de transmission de 10000 octets par seconde et qu'il faut une seconde de délai d'accès pour chaque message d'un site à un autre.

Question : Identifier toutes les stratégies possibles pour la requête et calculer le coût de chaque stratégie.

Schéma d'allocation

Débit de transmission : 10000 octets/seconde.
Délais d'accès (ou délais de synchronisation/d'attente) : 1 seconde.

Dictionnaire des relations

Relation	Attributs	Taille tuple	Cardinalité
Visite	2	100 octets	1 000 000
Propriété	2	100 octets	10 000
Client	2	100 octets	100 000

Requête SQL

Lister les propriétés d'Alger visitées par des clients dont le prix maximal est supérieur à 30 000 :

SELECT P.NUMP FROM PROPRIETE P, CLIENT C, VISITES V WHERE P.VILLE='ALGER' AND C.PRIXMAX > 30000 AND V.NUMC=C.NUMC AND V.NUMP=P.NUMP;

Ce processeur génère des requêtes distribuées.

Coûts associés à une requête distribuée

Le respect d'une certaine fonction de coût optimisée en exécution est primordial.

De façon générale, les coûts associés à une requête distribuée sont :

Le coût du temps d'accès (E/S) lors de l'accès aux données sur le disque.
Le coût du temps d'unité centrale (UC) induit lors du traitement sur les données en mémoire principale.
Le coût des communications associées au transfert des données via le réseau.

Le but de cet exercice est d'identifier les différentes stratégies d'exécution de la requête, et de calculer leurs coûts. Il est demandé de négliger le temps de traitement.

Le temps de communication est prééminent dans le cas de cet exercice. Par ailleurs, on ne s'est pas intéressé au temps de renvoi du résultat de la requête, car ce temps dépend du site où la requête s'exécute. Dans tous les cas, ce coût serait ajouté au temps d'exécution calculé.

Calculs préliminaires :

Temps de transfert des tables Propriété et Visite (total 1 010 000 tuples) du site Alger au site Blida :
[(1 000 000 + 10 000) * 100 octets / 10 000 octets/s] = 10100 secondes (environ 2,8 heures, l'original mentionnait 28 heures par erreur).
Temps de transfert de la table Client (100 000 tuples) du site Blida au site Alger :
[100 000 * 100 octets / 10 000 octets/s] = 1000 secondes (environ 16,7 minutes).

Stratégies possibles

Nous identifions 6 stratégies :

Stratégie 1 : Déplacer la relation CLIENT (de Blida) à Alger pour traiter la requête.
Coût = 1s (délai d'accès) + (100 000 * 100 octets / 10 000 octets/s) = 1 + 1000 = 1001 secondes (environ 16,7 minutes).
Stratégie 2 : Déplacer les relations PROPRIETE et VISITES (d'Alger) à Blida pour traiter la requête.
Coût = 1s (délai d'accès) + ((1 000 000 + 10 000) * 100 octets / 10 000 octets/s) = 1 + 10100 = 10101 secondes (environ 2,8 heures).
Stratégie 3 : Joindre les deux relations (client et propriété/visite) en transférant l'intégralité du client.
Coût = 100 000 * 100 / 10 000 = 1000 secondes (ce calcul est un fragment de coût sans délai d'accès explicite ici).
Un autre fragment de coût mentionné était : 100 000 * (1 + (1/8) / 10 000).
Stratégie 4 : Sélectionner les clients dont le prix maximal est supérieur à 30000 à Blida, puis transférer ces clients qualifiés et leurs vérifications vers Alger.
Coût = 10 * (1 + 100 / 10 000) + 10 * (1 + (1/8) / 10 000) ≈ 20.10 secondes.
Le terme 10 * 100 / 10 000 représente le temps de transmission des 10 tuples clients qualifiés.
Stratégie 5 : Joindre les résultats sur les numéros de propriété et de client à Blida pour les tuples ayant le prix maximal supérieur à 30000. L'hypothèse est que le résultat de la projection est de 100 caractères.
Coût = 1 + (100 000 * 100 / 10 000) = 1001 secondes (environ 16,7 minutes). (Ce coût est identique à la stratégie 1).
Ce calcul inclut 1s de délai d'accès (pour la vérification de chaque tuple) et 100 000 * 100 / 10 000 pour le temps de transmission du résultat.
Stratégie 6 : Sélectionner les clients dont le prix maximal est supérieur à 30000 à Blida et déplacer le résultat (les 10 clients qualifiés) à Alger pour y exécuter la requête.
Coût = 1s (délai d'accès) + (10 * 100 octets / 10 000 octets/s) = 1 + 0.1 = 1.1 secondes.

FAQ sur les Requêtes Distribuées

Qu'est-ce qu'une requête distribuée ?: Une requête distribuée est une requête qui accède à des données stockées sur plusieurs sites d'un système de gestion de bases de données distribuées. Son traitement implique des étapes de décomposition, de localisation des données et d'optimisation spécifiques à l'environnement distribué.
Quels sont les principaux facteurs à considérer pour l'optimisation des requêtes distribuées ?: Les facteurs clés incluent le parallélisme des opérations, les coûts de transfert de données entre les sites, le profil des fragments de données (taille, cardinalité, domaine des attributs), la taille des résultats intermédiaires et la topologie du réseau. L'objectif est de minimiser le coût total d'exécution, principalement dominé par le temps de communication.
Comment la gestion du catalogue affecte-t-elle les requêtes distribuées ?: Le catalogue dans un système distribué contient non seulement les métadonnées habituelles (vues, index) mais aussi des informations cruciales sur la fragmentation et la localisation des données. Selon le modèle de gestion (centralisé, dupliqué, partitionné ou combiné), le coût d'accès à ces informations peut varier significativement et influencer l'efficacité des opérations distantes.