Examen bd avancées jointure stratégies distribution

Examen bd avancées jointure stratégies distribution bases de

Télécharger PDF

Optimisation des Opérations de Jointure dans les Bases de Données Distribuées

Dans une requête SQL, qu'elle soit distribuée ou non, l’opération de jointure est l’opération la plus coûteuse en termes de ressources. Comprendre et optimiser cette opération est crucial pour la performance des systèmes de gestion de bases de données.

Stratégies d'Implémentation Physique de l'Opérateur de Jointure

Il existe quatre stratégies principales pour implémenter la jointure entre deux tables, par exemple T et S :

• Boucles imbriquées (Nested Loops Join)
• Tri-fusion (Sort-Merge Join)
• Hachage (Hash Join)
• Jointure par index (Index Join)

Jointure par Boucles Imbriquées

Cette stratégie consiste à charger tous les tuples de la première table T. Ensuite, pour chaque tuple de T, tous les tuples de la table S sont chargés et comparés pour trouver les correspondances. C'est la méthode la plus simple mais souvent la moins efficace pour de grandes tables.

Jointure par Tri-fusion

Proposée pour réduire le coût des boucles imbriquées, cette stratégie implique de trier les deux tables sur la colonne de jointure. Le parcours de la deuxième table est alors optimisé, car l'algorithme peut s'arrêter dès qu'une valeur supérieure à celle recherchée est rencontrée. L’efficacité de cette approche dépend fortement de la qualité de l’algorithme de tri utilisé.

Jointure par Hachage

Cette méthode applique une fonction de hachage sur l'attribut de jointure des deux tables. La jointure entre T et S est ainsi partitionnée en plusieurs jointures de plus petites tailles (entre des blocs ou des seaux de hachage). Cette stratégie requiert une fonction de hachage adéquate pour générer des partitions qui peuvent être jointes deux à deux en mémoire.

Jointure par Index

La jointure par index utilise soit un index de jointure pré-calculé, soit un index défini sur l'attribut de jointure de la deuxième table. Cet index permet un accès direct aux tuples de S liés à chaque tuple de T, réduisant ainsi le nombre de lectures.

Optimisation de la Jointure par la Distribution des Données et du Traitement

Les bases de données distribuées offrent des mécanismes d'optimisation de la jointure via deux aspects clés : la distribution des données et la distribution du traitement.

Distribution des Données

La distribution des données permet de fragmenter une jointure entre des tables volumineuses, qui nécessiteraient un nombre énorme d'opérations d'E/S (Entrées/Sorties), en plusieurs sous-jointures de tailles nettement inférieures. Ces sous-jointures peuvent souvent être exécutées en mémoire centrale, ce qui réduit considérablement leur coût d'exécution.

Distribution du Traitement

La distribution du traitement tire parti des possibilités de parallélisation des traitements. Ces traitements peuvent concerner des requêtes locales ou globales.

• Parallélisme des requêtes locales : Vise à calculer le résultat intermédiaire de jointures indépendantes d'une requête en parallèle, puis à réunir les résultats obtenus pour former la réponse finale. Par exemple, si une requête R contient les jointures "R JOIN S JOIN T JOIN W", alors "R JOIN S" et "T JOIN W" peuvent s'exécuter en parallèle.

• Parallélisme des requêtes globales : Peut être effectué après la décomposition de la requête en plusieurs sous-requêtes, où chacune s'exécute sur un nœud différent. Les sous-requêtes sont exécutées en parallèle sur chaque nœud, et les résultats locaux sont ensuite renvoyés au site où la requête globale a été lancée.

Détection des Verrous Mortels (Deadlocks) dans les Systèmes Distribués

La détection des verrous mortels (VM) dans un système distribué est essentielle pour garantir l'intégrité et la disponibilité des données. Trois stratégies principales sont employées à cet effet : la stratégie centralisée, la stratégie distribuée et la stratégie hiérarchisée.

Stratégie Centralisée

Dans cette approche, un nœud unique, appelé coordinateur, est responsable de la gestion de la détection des verrous mortels. Tous les graphes d'attente locaux sont envoyés à ce nœud. Le coordinateur construit le graphe global d'attente et exécute un algorithme de détection de cycle. Si un ou plusieurs cycles sont détectés, un verrou mortel est identifié. Le coordinateur résout ce verrou en annulant un minimum de transactions pour briser tous les cycles, puis informe les sites concernés de l'annulation.

Algorithme exécuté sur chaque site local (Stratégie Centralisée)

Chaque site construit son graphe d'attente local. Si un cycle est détecté localement, des transactions victimes sont choisies et annulées, et le graphe d'attente est mis à jour. Ensuite, le graphe local est envoyé au site coordinateur.

Algorithme exécuté sur le site coordinateur (Stratégie Centralisée)

Le coordinateur initialise son graphe d'attente avec son propre graphe local. Il fusionne ensuite les graphes d'attente reçus de tous les autres sites pour former un graphe global. Si la fonction "RechercherCycle" détecte un cycle dans le graphe global, le coordinateur choisit des transactions victimes, les annule, informe tous les sites où ces transactions sont en exécution, et met à jour le graphe global.

Remarque : La fonction "RechercherCycle(GA)" est une fonction booléenne qui retourne vrai (1) si le graphe d'attente (GA) contient au moins un cycle, et faux (0) sinon.

Stratégie Distribuée

Avec cette stratégie, chaque nœud du système est autonome et responsable de la gestion des verrous mortels. Chaque nœud construit son graphe local, résout les verrous mortels qu'il trouve localement et envoie son graphe à tous les autres nœuds. Il reçoit également les graphes des autres nœuds pour construire une version locale du graphe global d'attente. Chaque site exécute ensuite un algorithme de détection de cycle sur son graphe global, choisit des transactions victimes si un verrou mortel est trouvé, les annule et informe les sites concernés.

Algorithme exécuté sur chaque site (Stratégie Distribuée)

Chaque site construit son graphe d'attente local et l'envoie à tous les autres nœuds. Il construit également le graphe global par union des graphes reçus. Si un cycle est détecté dans ce graphe global, des transactions victimes sont choisies, annulées, et les sites où elles s'exécutent sont informés. Le graphe d'attente est ensuite mis à jour.

Stratégie Hiérarchisée

Cette stratégie établit une hiérarchie de responsabilité préétablie entre les nœuds. Chaque nœud envoie son graphe d'attente local à son nœud père dans la hiérarchie. Chaque nœud père construit un graphe partiel en combinant les graphes de ses enfants et son propre graphe. Si un nœud père détecte des verrous mortels dans son graphe partiel, il les résout et transmet le graphe partiel mis à jour à son propre nœud père, et ce processus se poursuit jusqu'à la racine de la hiérarchie.

Algorithme exécuté sur chaque site (Stratégie Hiérarchisée)

Chaque site construit son graphe d'attente local. Il construit ensuite un graphe partiel (GAP) en fusionnant les graphes de ses nœuds enfants. Si un cycle est détecté dans le GAP, des transactions victimes sont choisies, annulées, et les sites concernés sont informés. Le GAP est ensuite mis à jour et envoyé au nœud père.

Stratégies de Fragmentation pour les Bases de Données d'Entreprise

Considérons une base de données pour la gestion des appels des employés d'une entreprise, avec les tables : Employé(NSS, NomE, Adresse, Salaire) et Appel(NSS, Date, DuréeGlobale). L'objectif est de répartir les employés en partitions basées sur leur salaire, avec des intervalles de 10 000 DA, sachant que les salaires sont compris entre 10 000 et 31 000 DA.

Meilleure Fragmentation de la Table Employé

La meilleure fragmentation pour la table Employé est d'utiliser une fragmentation horizontale basée sur l'attribut Salaire, en créant des partitions pour des intervalles de valeurs :

• Employé 1 : Sélection des employés avec Salaire < 10000
• Employé 2 : Sélection des employés avec 10000 ≤ Salaire < 20000
• Employé 3 : Sélection des employés avec 20000 ≤ Salaire < 30000
• Employé 4 : Sélection des employés avec Salaire ≥ 30000

Meilleure Fragmentation de la Table Appel

Pour la table Appel, la meilleure approche est une fragmentation horizontale dérivée, basée sur la clé étrangère NSS en relation avec les fragments de la table Employé :

• Appel 1 : Jointure de Appel avec Employé 1
• Appel 2 : Jointure de Appel avec Employé 2
• Appel 3 : Jointure de Appel avec Employé 3
• Appel 4 : Jointure de Appel avec Employé 4

Modes de Fragmentation Adéquats sous Oracle

Sous Oracle, le mode de fragmentation le plus adapté pour la table Employé est le mode Range Partitioning (partitionnement par plages), et pour la table Appel, le mode Reference Partitioning (partitionnement par référence).

Commandes SQL de Fragmentation

Voici les commandes SQL correspondantes pour implémenter cette fragmentation :

Pour la table Employé

CREATE TABLE Employé (NSS NUMBER PRIMARY KEY, NomE VARCHAR2(100), Adresse VARCHAR2(200), Salaire NUMBER)

PARTITION BY RANGE(Salaire) (

PARTITION Moins10000 VALUES LESS THAN 10000,

PARTITION Entre10et20000 VALUES LESS THAN 20000,

PARTITION Entre20et30000 VALUES LESS THAN 30000,

PARTITION Plus30000 VALUES LESS THAN MAXVALUE

);

Pour la table Appel

CREATE TABLE Appel (ID_Appel NUMBER PRIMARY KEY, NSS NUMBER, Date_Appel DATE, DuréeGlobale NUMBER,

CONSTRAINT fk_emp FOREIGN KEY (NSS) REFERENCES Employé(NSS)

)

PARTITION BY REFERENCE(fk_emp);

Garantir la Transparence de la Fragmentation pour l'Utilisateur

Pour garantir la transparence de la fragmentation pour l'utilisateur, il est nécessaire de masquer la complexité sous-jacente. Une approche consiste à remplir les tables partitionnées avec les données des tables d'origine, puis à supprimer ces dernières et enfin à renommer les tables partitionnées pour leur donner les mêmes noms que les tables d'origine. Ceci permet aux applications existantes de continuer à fonctionner sans modification, accédant aux données de manière transparente, ignorant la structure fragmentée.

Foire Aux Questions (FAQ)

Qu'est-ce qu'une opération de jointure coûteuse en SQL distribué ?

Une opération de jointure est considérée comme coûteuse en SQL distribué principalement à cause du volume de données à transférer entre les différents nœuds du système, ainsi qu'en raison des opérations d'E/S nécessaires pour lire et comparer les données des tables impliquées. La complexité de coordination entre les sites ajoute également à ce coût.

Quelles sont les méthodes principales pour optimiser les jointures dans un environnement distribué ?

Les méthodes principales pour optimiser les jointures dans un environnement distribué incluent l'utilisation de stratégies d'implémentation physique efficaces (boucles imbriquées, tri-fusion, hachage, jointure par index) et, surtout, la distribution des données (fragmentation) et la distribution du traitement (parallélisme des requêtes locales et globales).

Comment la fragmentation des données aide-t-elle à améliorer les performances des bases de données ?

La fragmentation des données améliore les performances en divisant de grandes tables en fragments plus petits et plus gérables. Cela réduit la quantité de données à traiter pour chaque requête, permet d'exécuter des opérations en parallèle sur différents fragments et optimise l'utilisation de la mémoire, car de plus petites sous-jointures peuvent être traitées en mémoire centrale, minimisant ainsi les coûteuses opérations d'E/S sur disque.