Optimisation des requêtes SQL

2.1. Familles de SGBD

spof def

### 11.2. Algèbre et Semi-jointure (Semijoin)

Lorsqu'une relation est fragmentée, les filtres sont distribués :

$$\sigma_{pays=fra}(f_A \cup f_B) = \sigma_{pays=fra}(f_A) \cup \sigma_{pays=fra}(f_B)$$

La stratégie du Semijoin réduit le transfert réseau lors des jointures entre deux sites S1 et S2 :

1. Calcul des clés communes : $Temp_1 = \Pi_{R_1 \cap R_2}(r_1)$ sur S1.

2. Envoi de $Temp_1$ vers S2.

3. Filtrage local : $Temp_2 = r_2 \bowtie Temp_1$ sur S2.

4. Rapatriement exclusif des tuples utiles vers S1.

5. Jointure finale sur S1.

12. Transactions Distribuées

12.1. Concepts

Les transactions assurent les propriétés ACID( Atomique execution un bloc, Consistance passe d'un etat coherant un un autre etat coherant, Isolation pas de maj tant que pas commit, Durabilité des modifications sur la BD) . Une transaction globale manipule des données réparties et doit être validée (commit) ou annulée (abort) de manière unanime.

• Transaction Manager (TM) : Gère la concurrence et les logs au niveau local.

• Transaction Coordinator (TC) : demate une txn Orchestre le découpage et la validation globale des txn.

2 type de transaction :

• local : acces donne sur le site de txn

• Globa acces donne situee sur site different

12.2. Validation à Deux Phases (2PC)

Le protocole 2PC garantit l'atomicité et la cohérence des transactions distribuées en séparant l'exécution en deux étapes strictes entre un Coordinateur et plusieurs Participants.

Phase 1 : Préparation (Le vote)

1. Demande : Le coordinateur envoie un message <prepare T> à l'ensemble des participants.

2. Évaluation : Chaque participant exécute la transaction localement (sans la valider) pour s'assurer qu'il n'y a pas de conflit.

3. Réponse : Les participants écrivent leur intention dans leur journal local (log) et répondent au coordinateur par <yes T> ou <no T>.

Décision globale : Le coordinateur ne valide la transaction (Commit) que si 100 % des participants ont répondu "yes". Un seul "no" entraîne l'annulation globale (Abort).

Phase 2 : Application (La décision finale)

1. Ordre : Le coordinateur diffuse la décision finale (<commit T> ou <abort T>) à tous les participants.

2. Exécution : Les participants valident ou annulent les changements, puis libèrent les verrous sur les données.

3. Confirmation : Ils renvoient un accusé de réception (<acknowledge T>) au coordinateur pour clore la transaction.

12.3. Pannes et Blocages

1. Panne d'un Participant (Site)

• Avant le vote : Vu comme un <no> par le Coordinateur (Ci) ➔ Annulation.

• Après le vote : Ci ignore la panne et continue.

• Au redémarrage (analyse du log local) :

  • Log vide ➔ Annule (tombé avant de voter).

  • <commit> ou <abort> ➔ Applique la décision.

  • Uniquement <yes> (Incertitude) ➔ Interroge Ci ou les autres. Si injoignables ➔ Attente.

2. Panne du Coordinateur (Ci) Les sites tentent de déduire la décision finale :

• Si 1 site a <commit> ➔ Tous valident.

• Si 1 site a <abort> ➔ Tous annulent.

• Si 1 site n'a pas de <yes> ➔ Tous annulent.

• Le Blocage (Défaut majeur) : Si tous ont <yes> mais sans décision finale ➔ Système bloqué. Les verrous sont maintenus jusqu'au redémarrage de Ci.

3. Partitionnement Réseau

• Côté Ci : Le protocole continue normalement avec les sites joignables.

• Côté sites isolés : Traité comme une panne de Ci (tentative de décision ou blocage).

4. Alternative : Le 3PC

• Avantage : Élimine le problème de blocage.

• Défauts : Complexe, ajoute une phase, fait chuter les performances (pénalité réseau).

13. Contrôle de la Concurrence Distribuée

13.1. Gestion par Verrous

* Centralisée : Un site gère tout. Simple, mais crée un SPOF.

* Distribuée : Chaque site gère ses verrous. Complexe pour détecter les deadlocks inter-sites.

* Majorité : Nécessite l'accord de la moitié des répliques.

13.2. Horodatage (Timestamping)

Génération de timestamps distribuée en concaténant l'ID du nœud et l'horloge locale, ce qui pose le défi de la synchronisation (NTP).

13.3. Contrôle Optimiste (OCC)

Postule que les conflits sont rares.

1. Lecture : Travail sur copie locale.

2. Validation : Vérification des conflits avant commit.

3. Écriture : Validation ou Rollback/Retry automatique.

13.4. Multiversion (MVCC)

Maintien de plusieurs versions horodatées d'un tuple.

• Les lecteurs voient un instantané cohérent (snapshot).

• Lecteurs et écrivains ne se bloquent jamais mutuellement.

• Nécessite un nettoyage régulier (Garbage Collection).

Pdf tp1

Architecture distribuée (Réplication)

• Replica Set : Un groupe (cluster) de plusieurs serveurs MongoDB qui contiennent tous exactement la même copie de la base de données.

• Architecture Master/Slave : Un mode de fonctionnement où un serveur "chef" (Master) dirige, et des serveurs "esclaves" (Slaves) le copient.

• Nœud Primaire (Primary) : C'est le serveur "Master". C'est le seul autorisé à modifier la base de données (écritures).

• Nœud Secondaire (Secondary) : Ce sont les serveurs "Slaves". Ils copient en permanence le Primaire. On ne peut faire que des lectures dessus.

• Haute disponibilité : Le fait que la base de données reste toujours accessible pour les utilisateurs, même si un des serveurs physiques prend feu ou plante.

• Tolérance aux pannes (Failover) : La capacité du système à détecter la panne du Primaire et à réagir tout seul pour que le système continue de fonctionner.

• Mécanisme d'élection : Le vote automatique fait par les nœuds Secondaires entre eux pour désigner le nouveau Primaire quand l'ancien tombe en panne.

• Synchronisation : La mise à jour continue et ultra-rapide des nœuds Secondaires pour qu'ils aient les mêmes données que le nœud Primaire.

• Préférence de lecture (Read Preference) : Le réglage qui permet d'autoriser un client à aller lire les données sur un nœud Secondaire (pour éviter de surcharger le Primaire).

pdf tp2

Gestion et Topologie du Replica Set

• Ajout à la volée : Intégration de nouveaux nœuds sans arrêter le cluster.

• Réplication en chaîne (Chained Replication / chainingAllowed) : Capacité d'un Secondaire à se synchroniser depuis un autre Secondaire (et non depuis le Primaire) pour économiser la bande passante (syncSourceHost).

Types de Membres Spécifiques

• Membre Caché (Hidden Member) : Invisible pour les applications clientes, ne peut jamais devenir Primaire, mais possède le droit de vote. (Sauvegarde des données , Reporting / Statistique, backup)

• Membre Retardé (Delayed Member) : Un membre caché configuré avec un retard de synchronisation volontaire (utile en cas de suppression accidentelle de données).

• Arbitre (Arbiter) : Un nœud léger qui ne stocke aucune donnée utilisateur. Son unique rôle est de voter lors des élections pour départager les autres nœuds.

Élections et Tolérance aux Pannes

• Règle de la Majorité (N/2 + 1) : Nombre de votes requis pour qu'un nœud soit élu Primaire.

• Intérêt du nombre impair : Permet d'avoir toujours une majorité claire lors d'un vote.

• Split-Brain (Cerveau divisé) : Scénario catastrophique de partition réseau où deux parties isolées du cluster tenteraient d'élire chacune leur propre Primaire (bloqué par la règle de la majorité).

• Limites de vote : Un Replica Set peut contenir jusqu'à 50 nœuds, mais MongoDB limite à 7 le nombre maximum de nœuds votants (pour éviter la lenteur des élections).

Mécanismes Internes de Réplication

• Oplog (Operations Log) : Journal interne qui enregistre toutes les opérations modifiant les données. C'est le moteur de la réplication.

• Capped Collection : Type de collection utilisé par l'Oplog ayant une taille fixe (les anciennes données sont écrasées par les nouvelles quand il est plein).

• Write Concern : Niveau de garantie exigé lors d'une écriture (ex: attendre que l'écriture soit validée par la majorité avant de répondre au client).

pdf tp3

1. Le Sharding (Partitionnement des données)

Le sharding est la solution de MongoDB pour gérer des bases de données géantes. Au lieu de tout stocker sur un seul serveur surpuissant (ce qui a des limites), on "découpe" (fragmente horizontalement) la collection de données pour la répartir sur plusieurs serveurs.

L'architecture d'un cluster shardé repose sur 3 composants indissociables :

1. Les Shards (Serveurs de données) : Ce sont les serveurs physiques qui stockent les morceaux de la base de données. Chaque Shard ne possède qu'une partie des données totales.

2. Les Config Servers (Serveurs de configuration) : C'est le cerveau du cluster. Ils stockent le "plan" (les métadonnées) indiquant exactement sur quel Shard se trouve chaque morceau de donnée.

3. Le Mongos (Routeur) : C'est le point de contact pour l'utilisateur. Il reçoit la requête, demande au Config Server où se trouvent les données, transmet la requête aux bons Shards, fusionne les réponses, et renvoie le résultat à l'utilisateur. Le Mongos ne stocke aucune donnée.

2. Le Mécanisme de Distribution (Comment on découpe ?)

• La Clé de Sharding (Shard Key) : Pour découper les données, MongoDB a besoin d'un critère. L'administrateur choisit un champ spécifique (ex: l'âge, le code postal, ou un identifiant). La valeur de ce champ déterminera sur quel Shard le document sera envoyé.

• Les Chunks (Morceaux) : MongoDB ne répartit pas les documents un par un. Il crée des "blocs" de données contigus appelés chunks (ex: un chunk pour les codes postaux de 75000 à 75020). Par défaut, un chunk fait 64 Mo.

• L'Équilibreur de charge (Load Balancer) : Un processus automatique surveille les Shards. Si un serveur commence à stocker beaucoup plus de chunks que les autres, l'équilibreur va déplacer silencieusement des chunks vers les serveurs moins remplis pour répartir l'effort équitablement.

7. Évaluation et Optimisation des Requêtes

L'évaluation et l'optimisation des requêtes sont cruciales pour les performances des SGBD, surtout dans un contexte distribué.

7.1. Rappels sur le Stockage des Données

• Enregistrement (tuple): Un ensemble de champs formant une ligne dans une table.

• Bloc: Unité de chargement des données en mémoire principale, contenant une entête et plusieurs enregistrements.

• Fichier de données (table): Collection de blocs, organisée de manière séquentielle ou en tas (heap).

7.2. Rappels sur les Index

Les index accélèrent l'accès aux tuples ayant une valeur particulière d'un ou plusieurs attributs (clé de recherche).

Un index est un ensemble de <clé, pointeur>.

7.2.1. Types d'Index

• Dense/Non-dense: Un index dense a une entrée pour chaque enregistrement dans le fichier de données.

• Primaire/Secondaire: Un index primaire est sur la clé primaire de la table.

7.2.2. Structures de Données pour les Index

• Arbres:

  • B+-tree: Stocke les données uniquement dans les feuilles, les nœuds internes contiennent des clés de recherche et des pointeurs vers les nœuds enfants. Très utilisé pour les SGBD relationnels.

    

  • B-tree: Les données peuvent être stockées dans les nœuds internes et les feuilles.

• Tables de hachage (Hash): Distribuent les enregistrements dans des "buckets" via une fonction de hachage. Efficace pour les recherches d'égalité.

  

7.2.3. Avantages et Inconvénients des Index

• Avantage: Évaluation efficace des requêtes sur la clé indexée.

• Inconvénient: Coût de mise à jour de l'index en cas de modifications fréquentes de la table.

7.3. Algèbre Relationnelle et Plans d'Exécution

• SQL / Calcul Relationnel: Langage déclaratif, décrit le résultat souhaité.

• Algèbre Relationnelle: Langage procédural, décrit comment calculer le résultat (combinaison d'opérations sur des ensembles). Elle est à la base de l'optimisation des requêtes SQL.

Une requête SQL peut avoir plusieurs réécritures équivalentes en algèbre relationnelle, chacune pouvant donner lieu à un plan d'exécution différent avec des coûts variés. Par exemple, pour la requête SELECT DISTINCT nom, intitule FROM enseignant NATURAL JOIN enseigne NATURAL JOIN cours WHERE dpt = 'Info';, différentes réécritures sont possibles:

7.4. Analyse des Plans d'Exécution (Query Plan)

Les SGBD utilisent un optimiseur de requêtes pour choisir le plan d'exécution le plus efficace parmi les différentes alternatives. L'analyse d'un query plan (via EXPLAIN dans PostgreSQL) permet de comprendre comment une requête est exécutée et d'identifier les goulots d'étranglement.

1. Les méthodes de lecture (Scans)

C'est comment le moteur va physiquement chercher les lignes.

• Seq Scan (Sequential Scan) : Le balayage "stupide". Il lit toute la table de haut en bas, ligne par ligne.

• Index Scan : Il lit l'index pour trouver l'adresse de la ligne, puis va chercher la ligne complète dans la table.

• Bitmap Index Scan : Il lit l'index, mais au lieu d'aller chercher les lignes tout de suite, il crée une "carte" en mémoire (le bitmap) de tous les blocs physiques de la table qui contiennent des résultats.

• Bitmap Heap Scan : Il prend la "carte" générée par le Bitmap Index Scan et va chercher les vraies lignes sur le disque en optimisant les accès (il lit les blocs dans l'ordre physique pour ne pas faire d'allers-retours inutiles).

• Index Only Scan : Le Saint Graal de la performance. Le moteur ne lit que l'index et ne va même pas vérifier la table. Cela arrive si l'index contient toutes les colonnes demandées dans ton SELECT.

• CTE Scan (Common Table Expression Scan) : C'est l'action de lire les résultats temporaires générés par une clause WITH (une sous-requête nommée).

• Function Scan : Les lignes renvoyées ne viennent pas d'une table, mais d'une fonction PostgreSQL (par exemple generate_series(1, 100)).

• Foreign Scan : Le moteur va chercher des données qui ne sont pas physiquement sur ce serveur, mais sur une base de données distante (via un Foreign Data Wrapper).

2. Les Jointures (Joins)

Comment le moteur relie deux tables entre elles.

• Nested Loop (Boucle imbriquée) : Pour chaque ligne trouvée dans la Table A, il boucle sur la Table B pour chercher une correspondance. Très rapide si la Table A a peu de résultats et que la Table B est indexée.

• Hash Join : Il prend la plus petite des deux tables, la charge entièrement en mémoire vive (RAM) sous forme de dictionnaire (Table de hachage), puis il lit la grosse table et vérifie pour chaque ligne si elle correspond à une entrée du dictionnaire. Très efficace pour les grosses requêtes.

• Hash : C'est l'action préparatoire du Hash Join. C'est le moment où il construit la fameuse table de hachage en mémoire.

• Hash Semi Join : Utilisé pour les clauses EXISTS ou IN. Dès qu'il trouve une correspondance dans la deuxième table, il arrête de chercher pour cette ligne et passe à la suivante.

• Merge Join : Une méthode de jointure très efficace, mais qui exige que les deux tables soient déjà triées sur la colonne de jointure. Le moteur lit les deux listes en parallèle et les assemble un peu comme on ferme une fermeture éclair.

3. Les Conditions et Filtres

• Index Cond (Index Condition) : La condition de ta clause WHERE qui est utilisée pour naviguer à l'intérieur de l'index.

• Recheck Cond : Associé au Bitmap Heap Scan. Si la carte bitmap a manqué de mémoire, elle devient moins précise (elle cible des "zones" au lieu de lignes exactes). Postgres doit donc "re-vérifier" la condition sur les lignes une fois qu'il les a trouvées.

• Hash Cond : La condition exacte de ta jointure (le ON a.id = b.id) utilisée pendant un Hash Join.

• One-Time Filter : Une condition évaluée une seule fois au tout début (ex: WHERE 1 = 0). Si c'est faux, Postgres annule tout le plan et ne fait rien.

4. Sous-requêtes et Opérations d'ensemble

• Append : C'est la colle. Il prend le résultat de plusieurs requêtes et les met bout à bout (utilisé pour les UNION ou si tu lis une table partitionnée).

• SubPlan 1 : L'exécution d'une sous-requête (souvent exécutée pour chaque ligne de la requête principale, ce qui peut être très lent).

• Subquery Scan : Le moteur lit le résultat d'une sous-requête comme si c'était une vraie table.

• HashSetOp Intersect : Implémente l'opérateur INTERSECT en utilisant le système de hachage pour trouver les lignes communes entre deux requêtes.

5. Gestion de la mémoire et des résultats

• Materialize : Il stocke temporairement le résultat d'une opération en mémoire (ou sur disque) pour pouvoir le relire plusieurs fois sans avoir à recalculer. Très utilisé avec les Nested Loops.

• Heap Blocks : Pas une action, mais une métrique. Ça indique combien de blocs de données physiques de la table (Heap) ont été lus sur le disque ou trouvés dans le cache.

• Buckets / Batches : Ce sont les statistiques du Hash Join.

  • Buckets = les "cases" du dictionnaire en mémoire.

  • Batches = si la table était trop grosse pour la RAM, Postgres l'a coupée en "lots" (batches) qu'il a dû écrire sur le disque dur. S'il y a plus de 1 batch, ta requête est ralentie par le disque.

6. Les Tris, Limites et Agrégations

C'est ici que le moteur calcule tes ORDER BY, GROUP BY ou DISTINCT.

• Sort : L'action de trier les données. S'il y a assez de RAM, c'est fait en mémoire (quicksort). Sinon, Postgres crée des fichiers temporaires sur le disque (external merge), ce qui ralentit considérablement la requête.

• Limit : Le moteur arrête simplement de lire et de traiter des lignes dès qu'il a atteint le nombre demandé par ta clause LIMIT.

• Aggregate (HashAggregate / GroupAggregate) : C'est l'action qui calcule les fonctions mathématiques (comme SUM(), COUNT(), AVG()) ou qui regroupe les lignes pour un GROUP BY.

• WindowAgg (Window Aggregate) : Utilisé spécifiquement quand tu fais des calculs analytiques avec la clause OVER() (les fonctions de fenêtrage).

• Unique : Élimine les doublons adjacents pour satisfaire un SELECT DISTINCT. (Nécessite souvent que les données aient été triées juste avant).

7. Divers

• Result : Utilisé quand le moteur n'a même pas besoin de lire une table. Par exemple pour un simple SELECT 2 + 2; ou si un One-Time Filter a déterminé que la requête ne renverra rien de toute façon.

• ModifyTable (Insert / Update / Delete) : C'est le nœud de plus haut niveau quand tu fais une requête d'écriture. Il prend les lignes trouvées par les étapes précédentes et modifie physiquement la table.