Différences

Ci-dessous, les différences entre deux révisions de la page.

--- cnam:nfp107:seance10 [2023/04/22 15:38] – créée jcheron
+++ cnam:nfp107:seance10 [2023/04/22 21:06] (Version actuelle) – [Index] jcheron
@@ Ligne 1: / Ligne 1: @@
 ====== Séance 10 : Interrogation de données - Optimisation ======
-Plan d'exécution
+====== Plan d'exécution ======
 Une requête SQL est déclarative (Elle détermine le Quoi ?).
 Elle n'indique pas comment calculer le résultat ⇒ programme
@@ Ligne 7: / Ligne 8: @@
 Dans un SGBD le programme qui exécute une requête est appelé plan d’exécution.
 Ce plan d'exécution est un arbre, constitué d’opérateurs, agissant sur des jeux de données.
+//TODO image//
 Source : sys.bdpedia.fr
-Choix du plan d'exécution
+===== Choix du plan d'exécution =====
-Plan logique
-Notations
+==== Plan logique ====
-Selection :
+=== Notations ===
+__Selection :__
 La selection travaille sur R et definit une relation qui ne contient que les tuples de R qui satisfont à la condition (ou prédicat) specifiée.
-σ predicat (R)
+<sxh ;gutter:false>σ predicat (R)</sxh>
-... FROM R WHERE predicat
+<sxh sql;gutter:false>... FROM R WHERE predicat</sxh>
-Projection :
+__Projection :__
 La projection travaille sur R et definit une relation restreinte à un sous-ensemble des attributs de R, en extrayant les valeurs des attributs specifiés et en supprimant les doublons.
-Projection : π a1,...,ak (R)
+<sxh ;gutter:false>Projection : π a1,...,ak (R)</sxh>
-SELECT a1,...,ak FROM R
+<sxh sql;gutter:false>SELECT a1,...,ak FROM R</sxh>
-Jointure theta :
+__Jointure theta :__
 La theta-jointure définit une relation qui contient les tuples qui satisfont le predicat P du produit cartesien de R et S. Le predicat P est de la forme R.aiθS.bj où θ est l’un des operateurs de comparaison ( <,≤,>,≥,=,!= )
-θ-join : R ⋈ predicat S
+<sxh ;gutter:false>θ-join : R ⋈ predicat S</sxh>
-FROM R INNER JOIN S on predicat
+<sxh sql;gutter:false>FROM R INNER JOIN S on predicat</sxh>
-Exemple
-Requête :
+=== Exemple ===
+__Requête :__
+<sxh sql;gutter:false>
 SELECT titre FROM Film f INNER JOIN Role r on r.idFilm=f.id WHERE f.annee=1995 AND r.nom_role='John McClane'
-Représentation algébrique
+</sxh>
+__Représentation algébrique__
+//TODO image//
 Le SGDB et l'optimiseur de requêtes trouve les expressions équivalentes, évalue leur coût et choisit la meilleure.
-Il est impossible/contre-performant d'énumérer tous les plans possibles (trop long) : on applique des heuristiques.
+<wrap important>Il est impossible/contre-performant d'énumérer tous les plans possibles (trop long) : on applique des heuristiques.</wrap>
 Heuristique classique : réduire au plus tôt la taille des données
-en filtrant les nuplets par des sélections
+  * en filtrant les nuplets par des sélections
-en les simplifiant par des projections
+  * en les simplifiant par des projections
-Illustration de la recherche du plan logique optimal
+=== Illustration de la recherche du plan logique optimal ===
 Séparation des sélections :
+//TODO image//
 Application des sélections aux tables concernées :
+//TODO image//
 Principes essentiels :
-L’algèbre permet d’obtenir une version opératoire de la requête.
+  - L’algèbre permet d’obtenir une version opératoire de la requête.
-Les équivalences algébriques permettent d’explorer un ensemble de plans.
+  - Les équivalences algébriques permettent d’explorer un ensemble de plans.
-L’optimiseur évalue le coût de chaque plan.
+  - L’optimiseur évalue le coût de chaque plan.
 De manière
-Heuristique : l'optimiseur ne peut pas tout explorer
+  * Heuristique : l'optimiseur ne peut pas tout explorer
-Incomplète : Reste à l'optimiseur à choisir le bon algorithme pour chaque opération.
+  * Incomplète : Reste à l'optimiseur à choisir le bon algorithme pour chaque opération.
-Plan physique
+==== Plan physique ====
 Le plan physique consiste pour l'optimiseur à choisir les opérateurs.
 Notion d'itérateur (open(), next(), close() methods)
-Bloquants => Matérialisation
+=== Bloquants => Matérialisation ===
-Non bloquants => Pipelinage
+//TODO image//
-Opérateurs bloquants
+=== Non bloquants => Pipelinage ===
+//TODO image//
+=== Opérateurs bloquants ===
 Parfois il n’est pas possible d’éviter le calcul complet de l’une des opérations avant de continuer. On est alors en présence d’un opérateur dit bloquant dont le résultat doit être entièrement produit (et matérialisé en cache ou écrit sur disque) avant de démarrer l’opération suivante. Par exemple:
-le tri (order by);
+  * le tri (order by);
-la recherche d’un maximum ou d’un minimum (max, min);
+  * la recherche d’un maximum ou d’un minimum (max, min);
-l’élimination des doublons (distinct);
+  * l’élimination des doublons (distinct);
-le calcul d’une moyenne ou d’une somme (sum, avg);
+  * le calcul d’une moyenne ou d’une somme (sum, avg);
-un partitionnement (group by);
+  * un partitionnement (group by);
 On distingue donc :
-le temps de réponse: c’est le temps mis pour obtenir un premier nuplet; il est quasi-instantané pour une exécution sans opérateur bloquant;
+  * le temps de réponse: c’est le temps mis pour obtenir un premier nuplet; il est quasi-instantané pour une exécution sans opérateur bloquant;
-le temps d’exécution: c’est le temps mis pour obtenir l’ensemble du résultat.
+  * le temps d’exécution: c’est le temps mis pour obtenir l’ensemble du résultat.
-Index
+==== Index ====
 Un index est une structure de données permettant d'accélérer les recherches dans une table en associant à une clé d'index (la liste des attributs indexés) l'emplacement physique de l'enregistrement sur le disque.
 Les accès effectués sur un index se font sur des structures optimisées pour la recherche (liste triée, B-tree…) au lieu de se faire par parcours séquentiel et intégral des enregistrements.
-B-Tree
+=== B-Tree ===
-Intérêt :
+<WRAP tip>
+__Intérêt :__
 R = Nombre de valeurs possibles/Nombre d'enregistrements ⇒ 1
+</WRAP>
 Les index B-TREE sont les plus couramment utilisés.
@@ Ligne 89: / Ligne 125: @@
 Les index doivent être utilisés sur les attributs :
-souvent mobilisés dans une restriction (donc une jointure)
+  * souvent mobilisés dans une restriction (donc une jointure)
-très discriminés (c'est à dire pour lesquels peu d'enregistrements ont les mêmes valeurs)
+  * très discriminés (c'est à dire pour lesquels peu d'enregistrements ont les mêmes valeurs)
-rarement modifiés
+  * rarement modifiés
+<WRAP important>
 Inconvénients :
-diminuent les performances en mise à jour (puisqu'il faut mettre à jour les index en même temps que les données).
+  * diminuent les performances en mise à jour (puisqu'il faut mettre à jour les index en même temps que les données).
-ajoutent du volume à la base de données et leur volume peut devenir non négligeable.
+  * ajoutent du volume à la base de données et leur volume peut devenir non négligeable.
-Ne permettent pas toujours de gagner en efficacité (voir plus bas).
+  * Ne permettent pas toujours de gagner en efficacité (voir plus bas).
-Source : use-the-index-luke.com
+</WRAP>
-Bitmap
+//TODO image//
-Intérêt :
+Source : [[https://use-the-index-luke.com/fr/sql/anatomie-dun-index/le-b-tree|use-the-index-luke.com]]
+=== Bitmap ===
+<WRAP tip>
+__Intérêt :__
 R = Nombre de valeurs possibles/Nombre d'enregistrements ⇒ 0
+</WRAP>
 Les index Bitmap sont destinés à l'indexation de colonnes qui comportent donc peu de valeurs distinctes et beaucoup d'enregistrements pour chacune de ces valeurs.
@@ Ligne 110: / Ligne 154: @@
 De tels index optimisent la recherche relative à une question du type : “l'enregistrement appartient-il à un sous ensemble du domaine sur l'index ?”.
-Inconvénients :
+<WRAP important>
+__Inconvénients :__
 diminuent de manière importante les performances en mise à jour (puisqu'il faut mettre à jour les index en même temps que les données).
-utilisables uniquement pour peu de valeurs distinctes = le meilleur ratio de valeurs distinctes au nombre total occurrences est d'environ 1 pour 1000,
+utilisables uniquement pour peu de valeurs distinctes = le meilleur ratio de valeurs distinctes au nombre total occurrences est d'environ 1 pour 1000.
-FullText
+</WRAP>
-Les index FullText permettent de faire des recherches sur les champs de type string (CHAR, VARCHAR et TEXT).
-Création :
+=== FullText ===
+Les index FullText permettent de faire des recherches sur les champs de type string (CHAR, VARCHAR et TEXT).
+== Création : ==
+<sxh sql>
 CREATE FULLTEXT INDEX ind_full_titre
 ON Livre (titre);
-Utilisation :
+</sxh>
+== Utilisation : ==
+<sxh sql>
 SELECT *
 FROM Livre
 WHERE MATCH(titre)
 AGAINST ('story');
-Modes possibles :
+</sxh>
-IN NATURAL LANGUAGE MODE
+== Modes possibles : ==
-IN BOOLEAN MODE
+  * IN NATURAL LANGUAGE MODE
-WITH QUERY EXPANSION
+  * IN BOOLEAN MODE
-Index partiels
+  * WITH QUERY EXPANSION
-Permettent de poser un index de manière conditionnelle ⇒ limite la taille de l'index et accélère les recherches :
+==== Index partiels ====
+Permettent de poser un index de manière conditionnelle ⇒ limite la taille de l'index et accélère les recherches :
+<sxh sql>
 CREATE INDEX nr_mail
           ON mails (subject)
        WHERE status = 'NR'
-Efficacité des index
+</sxh>
+==== Efficacité des index ====
 L'utilisation d'un index ne suffit pas à la performance, même si la recherche dans l'index est plus rapide qu'un parcours séquentiel :
 Une recherche nécessite les 3 opérations suivantes
-le parcours de l'arbre
+  * le parcours de l'arbre
-la suite de la chaîne de nœuds feuilles
+  * la suite de la chaîne de nœuds feuilles
-la récupération des données de la table
+  * la récupération des données de la table
 L'index n'optimise que le parcours de l'arbre/séquentiel.
-Points importants :
+=== Points importants : ===
+  * Nombre de valeurs (unique ou multiple/nombre de valeurs distinctes)
+  * Index composites et importance de l'ordre des champs dans l'index (voir [[https://use-the-index-luke.com/fr/sql/la-clause-where/index-concatenes|Index composites]])
+  * Index lents ⇒ un TABLE ACCESS FULL (lecture de plusieurs enreg par bloc) peut être plus rapide qu'un **INDEX RANGE SCAN** (lecture 1 à 1 de plusieurs enregs) (voir [[https://use-the-index-luke.com/fr/sql/la-clause-where/index-lents-partie-2|Index lents]])
+  * Index et usage de fonctions ⇒ index avec fonctions possibles pour fonctions pures (voir [[https://use-the-index-luke.com/fr/sql/la-clause-where/fonctions|Usage de fonctions]])
+  * [[https://use-the-index-luke.com/fr/sql/la-clause-where/variables-liees|Index et requêtes préparées]]
+==== Analyse de requêtes ====
-Nombre de valeurs (unique ou multiple/nombre de valeurs distinctes)
-Index composites et importance de l'ordre des champs dans l'index (voir Index composites)
-Index lents ⇒ un TABLE ACCESS FULL (lecture de plusieurs enreg par bloc) peut être plus rapide qu'un INDEX RANGE SCAN (lecture 1 à 1 de plusieurs enregs) (voir Index lents)
-Index et usage de fonctions ⇒ index avec fonctions possibles pour fonctions pures (voir Usage de fonctions)
-Index et requêtes préparées
-Analyse de requêtes
 La plupart des SGDB possédent un analyseur de requêtes permettant de visualiser le plan d'exécution d'une requête.
-PostgreSQL explain :
+__PostgreSQL explain :__
-explain ⇒ Donne le plan d'exécution estimé
+//TODO image//
-explain analyze ⇒ Donne le plan d'exécution réel (attention, exécute la requête)
-Ressources
+  * explain ⇒ Donne le plan d'exécution estimé
-Explain beautifier
+  * explain analyze ⇒ Donne le plan d'exécution réel (attention, exécute la requête)
-Explain documentation
-Application
+=== Ressources ===
+  * [[https://explain.dalibo.com/|Explain beautifier]]
+  * [[https://www.postgresql.org/docs/9.1/sql-explain.html|Explain documentation]]
+==== Application ====
+<WRAP todo>
 Benchmark avec et sans Index BTree + Analyse des plans de requête (PostGreSQL) sur :
-Select monotable sur champ
+  * Select monotable sur champ
-Join sur champ
+  * Join sur champ
-Select avec fonction (LCASE(name) par exemple)
+  * Select avec fonction (LCASE(name) par exemple)
-Utilisation de fonction de regroupement
+  * Utilisation de fonction de regroupement
-Order By
+  * Order By
-Références
+</WRAP>
-Cours de Philippe RIGAUX (CNAM)
+==== Références ====
-Use the index Luke
-MySQL performance optimization
+  * [[http://sys.bdpedia.fr/|Cours de Philippe RIGAUX (CNAM)]]
-PostgreSQL performance tuning
+  * [[https://use-the-index-luke.com/|Use the index Luke]]
+  * [[https://www.oreilly.com/library/view/high-performance-mysql/9780596101718/ch04.html|MySQL performance optimization]]
+  * [[https://www.geekytidbits.com/performance-tuning-postgres/|PostgreSQL performance tuning]]