Parser, planifier et optimiser des requêtes SLQ.

Lorsqu’un client se connecte à un cluster PostgreSQL, un processus (backend process) lui est assigné dont la tache principale est d’exécuter des requêtes permettant au client d’interagir avec une base de données.

Rappel: Outre ces processus, le cluster nécessite un processus serveur, ainsi que de multiples processus afin de gérer l’écriture et la lecture des données de manières concurrente sur disque, mais aussi la réplication.

Chacun de ces processus peut avoir une mémoire qui lui est propre ainsi que des paramètres de configurations dédiés en fonction du comportement qu’on souhaite donner au cluster.

Organisation de l’utilisation de la mémoire

L’ensemble des processus ont une mémoire partagée où sont stockées les pages chargées depuis le disque, des informations l’état des fichiers de logs.

Les processus des clients ont la dure tâche de devoir répondre au requêtes. Pour ce faire, ils ont besoin de mémoires propres et si celle ci est insuffisante, à des fichiers temporaires.

Les étapes d’optimisation de requêtes dépendent cruellement de la quantité de mémoire dont dispose ces processus. Cette quantité de mémoire est paramétrable par processus client et doit être dimensionnée correctement en fonction d’une prévision du nombre de connexions.

En pratique On utilisera la variable work_mem du fichier de configuration pour cela. Par défaut, la valeur est de 4Mb, ce qui est bien en deçà de ce qu’on souhaite avoir quand on utilise une base de données de manière analytique (par exemple).

L’accès en lecture et en écriture aux données sur disque est réalisée via la mémoire partagée par un mécanisme complexe de chargement et déchargement des pages qui seront vues ultérieurement.

Notons que l’écriture sur disque des pages qui ont été modifié n’est pas répercuté immédiatement (voir TD).

Les processus clients (backend process)

L’objectif d’un processus client est de répondre à une requête SQL faite sur une base de données. Les grandes étapes sont les suivantes:

1. Parse On analyse syntaxiquement la requête et on construit l’arbre syntaxique de la requête
2. Rewrite On réécrit l’arbre de requête en fonction des règles implantés dans la bases de données
3. Plan On transforme l’arbre de la requête en un plan d’exécution en utilisant le modèle de coûts du cluster
4. Execute On exécute le plan de requête.

En pratique Il est possible d’avoir un résultat (en texte) des 4 premières étapes en activant les options debug_print_parse, debug_print_rewritten, debug_print_plan.

Un exemple simpliste

On se donne une table simple:

postgres=# SELECT * FROM t;
 id |     v
----|------------
  0 | postgres
  1 | cest super
(2 rows)

Phase d’analyse

L’analyse syntaxique utilise les classiques Bison et Flex dont les règles peuvent être extraits des codes sources disponibles ici pour bison et ici pour flex.

Le résutltat d’une simple requête comme SELECT * FROM t; donne le résultat suivant (la réécriture ne fait rien ici):

{QUERY
       :commandType 1
       :querySource 0
       ....
       :rtable (
          {RTE
          :eref
             {ALIAS
             :aliasname t
             :colnames ("id" "v")
             }
           ....
          }
       )
       :jointree
          {FROMEXPR
          :fromlist (
             {RANGETBLREF
             :rtindex 1
             }
          )
          :quals <>
          }
       :targetList (
          {TARGETENTRY
          :expr
             {VAR
             :varno 1
             :varattno 1
             :vartype 23
             ....
             }
          ....
          }
          {TARGETENTRY
          :expr
             {VAR
             :varno 1
             :varattno 2
             :vartype 25
             ....
             }
          ....
          }
       )
}

Plan de requêtes

L’optimiseur de requêtes a évaluer plusieurs plan de requêtes possible selon la situation et la configuration du cluster et à produit un arbre disposant d’algortihme a utiliser pour répondre à la requête:

{PLANNEDSTMT
       :commandType 1
       ...
       :planTree
          {SEQSCAN
          :startup_cost 0.00
          :total_cost 22.70
          :plan_rows 1270
          :plan_width 36
          ...
          :targetlist (
             {TARGETENTRY
             :expr
                {VAR
                ....
                }
             ...
             }
             {TARGETENTRY
             :expr
                {VAR
                ...
                }
             ...
             }
          )
          ....
          }
       :rtable (
          {RTE
          :eref
             {ALIAS
             :aliasname t
             :colnames ("id" "v")
             }
           ...
          }
       )
  }

Ici, le plus important concerne les indications en début de planTree indiquant l’algorithme utilisé et une évaluation du coût de la requête.

Coût initial vs coût total

Le coût total est généralement le coût utilisé par le planificateur pour choisir la requête la plus adéquate. Le coût initial est le coût de pré-calcul avant de pouvoir accéder au premier résultat.

Ce coût est pertinent notamment en présence d’un modificateur comme LIMIT ou de l’utilisation de EXISTS qui limite le nombre de tuple à retourner par la requête.

L’optimisation de requêtes avec une seule table

Quand une requête ne dispose pas de jointure, par exemple une requête de la forme SELECT * FROM table WHERE conditions, l’optimiseur doit quand même estimé comment la requête doit être effectuée si des indexes sont présents.

Les requêtes sans indexes

Le seul algorithme possible avec une seule table et sans autres information consiste à faire une boucle qui passe au travers toutes la table, chaque page les une après les autres.

La complexité d’une telle opération est simple a évaluer algorithmiquement si \(n\) est le nombre de tuple, on a besoin \(\mathcal{O}(n)\) opérations. Ce coût est trop grossier pour que PostgreSQL puisse s’en servir pour évaluer le coût réel.

En pratique l’algorithme se décompose comme suit:

1. On charge chaque page en mémoire
2. Pour chaque page en mémoire on lit chaque tuple.
3. Pour chaque tuple, on lui applique les opérations nécessaires.

La troisième étape va dépendre de la requête. Il est possible par exemple de faire des opérations arithmétiques, ou des opérations de conversion dans la partie à gauche du FROM.

Pour chacun de ces points, le modèle de coût configuré dans postgreSQL.conf permet d’avoir une estimation:

Calcul du coût de la requête:

1. seq_page_cost évalue le coût d’aller lire séquentiellement les pages. C’est un coéficient multiplicateur par page: nombre_de_pages * seq_page_cost

2. cpu_tuple_cost évalue le coût de traité un tuple dans une page. C’est un coéfficient mutliplicateur par tuples : nombre_de_tuples * cpu_tuple_cost

3. cpu_operator_cost évalue le coût de faire une opération supplémentaire sur les tuples. C’est un coéfficient multiplicateur par tuple: cpu_operator_cost * cpu_tuple_cost

Ainsi, pour la requête:

postgres=# EXPLAIN SELECT * FROM t WHERE id <1;
                     QUERY PLAN
-----------------------------------------------------
 Seq Scan on t  (cost=0.00..25.88 rows=423 width=36)
   Filter: (id < 1)
(2 rows)

Les requêtes avec indexes

Il est très simple de créer des indexes sur un (ou des) champs d’une table en faisant simplement CREATE INDEX ON table (field). Ces indexes peuvent changer drastiquement l’efficacité des algorithmes mais nécessite des informations statistiques afin de pouvoir évaluer cette efficacité.

Quelques rappels sur les indexes

Un index est une structure de données permettant de faire un accès à des valeurs particulières d’une table. En fonction du type d’indexe, des opérations de recherche plus ou moins flexibles peuvent être disponibles.

PostgreSQL permet l’utilisation de plusieurs type d’indexes, mais l’utilisation des B*-tree est conseillé et le choix par défault. L’implementation de PostgreSQL est proche de celles décrites dans les papiers:

1. P. Lehman and S. Yao, Efficient Locking for Concurrent Operations on B-Trees, ACM Transactions on Database Systems, Vol 6, No. 4, December 1981, pp 650-670.

2. V. Lanin and D. Shasha, A Symmetric Concurrent B-Tree Algorithm, Proceedings of 1986 Fall Joint Computer Conference, pp 380-389

Des versions de ces papiers peuvent vous être communiqué par mail sur demande si les accès sont difficiles. Sinon n’hésitez pas à utiliser un site internet à la légalité douteuse: scihub.

Ce sujet est difficile, mais vous pouvez également en lire plus sur l’implémentation de PostgreSQL dans le README et sur le blog ici

La sélectivité d’une WHERE-clause.

L’efficacité d’un index lors de l’execution d’une requête dépend de la taille de l’index, des performances en lecture aléatoire de la selectivtié des conditions dans la clause à droite du WHERE.

La sélectivité de ces clauses peut être définit comme la proportion des tuples validant la condition.

Exemple: Si une table contient 1000 personne avec les informations de date de naissances et de genre. Le premier champ date de naissance à de bonne chance d’être sélectif car peu de personne auront la même date de naissance alors que le genre sera très faiblement sélectif.

La sélectivité est un paramètre important pour évaluer s’il vaut mieux faire un table scan ou des lectures aléatoires dans la table. Les paramètres par défauts de PostgreSQL suggère qu’un accès aléatoire est 4 fois plus lent qu’un accès séquentiel. Pour qu’un index soit intéressant par rapport à un scan complet de la table, il faut donc que ce dernier sélectionne une petite fraction de la table.

L’évaluation de la sélectivité utilise une simple interpolation linéaire à partir de statistiques collectées par PostgreSQL.

Remarque. Les statistiques des tables d’une requêtes sont accessible directement dans une table nommée pg_stat.

Le coût d’une requête avec index

(A améliorer/raffiner)

Lorsqu’on utilise simplement un index, avec une condition suffisamment sélective pour le plannificateur, alors la requête va utiliser l’index. Il s’agit de l’algorithme index scan: on va rechercher l’adresse des tuples satisfaisant la condition en parcourant l’arbre de recherche et en réalisant un accès non séquentiel aux données.

Assez naturellement, le coût d’une telle requête est la somme pour chaque valeur qu’on est allé chercher dans un index de la descente (grosso modo \(\mathcal O(\log(n))\) où \(n\) est la taille de l’index ainsi que le nombre d’accès à des tuple de manière non séquentiel dans la table grâce à une lecture d’un tuple d’index et une lecture de page et une lecture d’un tuple.

On peut naturellement factoriser les lectures pages si les tuples ayant une même valeur sont souvent dans une même page. Pour évaluer cela on utilise un paramètre de la corrélation.

Améliorer le facteur de corrélation peut améliorer l’efficacité du Index Scan sensiblement. Pour cette raison, il peut être intéressant de changer la répartition des tuples physiquement dans le fichier à l’aide de la commande CLUSTER.

Les requêtes avec masque sur les pages

(À améliorer/raffiner)

Il peut arriver que la condition de la clause derrière WHERE ne soit pas très sélective mais qu’une lecture séquentiel de la table complète ne soit pas la meilleur solution pour autant. Une solution intermédiaire consiste à construire (en mémoire?) un masque binaire des pages contenant un ou des tuples que l’on souhaite garder.

Ce masque peut être construit en une lecture de l’index et utiliser pour éviter de charger inutilement des pages dans la mémoire partagée en “sautant” par dessus.

Cet algorithme est nommé *Bitmap Index Scan**.

Les requête en adressage directe

À améliorer

Chaque ligne a une adresse physique (numéro de page, numéro de tuple dans le page). Quand la table n’est pas soumise à des modifications, il est possible de lire directement à cette adresse.

Attention, ce n’est pas une adresse permanente !

Pour faire des lecture à des adresses physiques directement, il est possible d’utiliser la colomne cachées: ctid. Le coût d’une lecture sera alors exactement le coût d’une lecture non séquentiel.

PostgreSQL utilise le terme de TID scan.

L’optimisation de requêtes avec jointures

Compiled the: mer. 04 sept. 2024 12:49:39 CEST