Algorithmes et Bases de Données, année 2019

Parser, planifier et optimiser des requêtes SLQ (suite)

Nous avons vu la semaine dernière comment PostgreSQL optimise des requêtes n’utilisant qu’une seule table. L’objectif aujourd’hui est d’étudier les optimisations quand une clause utilise plusieurs tables et réalise une jointure.

On décompose le problème en deux parties:

• Optimiser les requêtes avec deux tables
• Générraliser à des requêtes avec un nombre arbitraire de table.

Structure générale de l’algorithme

L’algorithme va faire un certain nombre de simplifciation de la requête:

• Il va “applatir” les sous requêtes en une jointure:

SELECT * FROM a, (SELECT b.x as p, c.z as q FROM b,c WHERE b.x = c.y) WHERE a.t = p;

Peut être réécrit:

SELECT * FROM a, b, c WHERE b.x = c.y AND a.t = b.x;

Le plannificateur peut ainsi se raméner à l’optimisation de requêtes de la forment:

\(\text{SELECT}\ldots\text{FROM} T_1,\ldots, T_k \text{WHERE} \ldots\)

Quand le nombre de jointures n’est pas trop grand, il va explorer toutes les manières de les réaliser et choisir la plus optimale. Si le nombre de jointures est trop gros il va basculer sur une heuristique basée sur un algorithme génétiques (Genetic Query Optimization ou GEQO). Par défault, PostgreSQL utilise l’algorithme standard pour un nombre de jointures inférieures à 12. Ce paramètre est réglable via la variable geqo_threshold.

Le cas d’une seule jointure

On va dans un premier temps revoir les différents algorithmes possibles pour réaliser une jointure entre deux tables et analyser le coût dans le modèle de coût proposé par PostgreSQL. Puisque les algorithmes sont assymétriques, nous allons évaluer l’algorithme de jointure en appelant la table de gauche la table extérieure et celle de droite la table intérieure. Dans la suite: * \(N_e\) désigne la taille de la table extérieur et \(P_e\) son nombre de pages * \(N_i\) désigne la taille de la table intérieur et \(P_i\) son nombre de pages

Boucles imbriquées (Nested Loops)

Une simple double boucle. Ici le coût s’évalue simplement:

\(\textsc{cout_total} = \textsc{tuple_cpu_cost} N_e N_i + \textsc{seq_page_cost}(N_e P_i + P_e)\)

On voit que ce type de plan sera surtout coûteux quand la table extérieur est grosse car le terme (N_e P_i) risque de dominer. Ce plan n’arrive jamais en pratique même s’il est évalué.

Boucles imbriquée avec Materialisation en mémoire (Materialized)

Une première amélioration consiste, si c’est possible, à charger en mémoire la table extérieur. PostgreSQL utilise alors une structure de données plus compacte que les pages (un tuple stores) qui consiste essentiellement en une liste chaînée. Si cette dernière ne tient pas dans work_mem il est possible d’utiliser des fichiers temporaires, ce qui reste bien plus intéressants que de charger des pages en mémoire via le BufferPool.

En pratique, cela nécessite un parcours séquentiel de chaque table ainsi que des accès à la mémoire. Pour l’évaluation du coût, il faudrait prendre en compte les cas où on utilise des fichiers temporaires, mais pour plus de simplifciation on considère que ça tient en mémoire et on obtient:

\(\textsc{cout_total} = 2\textsc{tuple_cpu_cost} N_e N_i + \textsc{seq_page_cost}(P_i + P_e)\)

Boucles imbriquées avec utilisation d’indexes

Lorsqu’un index est présent sur la table intérieur il est possible de l’utiliser pour accélerer la recherche en réalisant une lecture séquentielle de la table extérieure et en utilisant l’index pour accéder directemnt aux valeurs de la table intérieur.

Ce type de plan est particulièrement efficace lorsqu’on réalise une jointure entre une petite table exterieur sur une grosse table intérieur (qui doit donc être indexée).

Remarque. Il devrait être possible par ailleurs de parcourir la table extérieur après un tri de celle ci afin d’éviter plusieurs descente d’arbre. Ce n’est apparement pas utilisé par PostgreSQL (le gain est surement néglieable…).

La gestion des indexes et l’évaluation d’un plan de requêtes quand ils sont présents est un problème difficile qui a nécessité l’introduction de structure de données dediées (parametrized path). D’après les échanges des developpeurs, l’évaluation de ces plans de requêtes est un problème difficile et mal traité (sans que ça n’est de grosses conscéquences d’après eux sur l’efficacité de l’optimiseur).

Merge Join

L’algorithme (déjà vu en cours) va trier les deux tables et réaliser une lecture séquentiel synchronisé de des deux tables. Cela est possible que pour des equi-join c’est-à-dire des jointures avec uniquement une condition d’égalité.

Le coût d’un merge join est essentiellement celui d’une lecture séquentiel des tables et d’un tris de chaque de tables. Il est possible également de matérializer un ou deux tables en mémoires.

Exercice Évaluer le coût d’un merge join quand la table intérieur est matérialisable en mémoire.

Optimisation à plusieurs jointures

L’algorithme d’optimisation va procéder par récurence pour produire un arbre de jointure (binaire) dont les noeuds sont étiquetés par les informations suivantes:

• L’ensemble des tables jointes
• La listes de potentiels algorithmes pour réaliser la jointures
• Des structures dédiées pour maintenir des informations sur les clauses (classes d’équivalences entre les variables …)
• La taille estimée de la table.

Pour chaque algorithmes potentiels, on va stoquer& des informations supplémentaires:

• Est-ce que la sortie de l’algorithme est une liste de tuple triées et si oui par quelles valeures.

La récurrence s’effectue sur la taille du nombre de relations de base qui ont été jointes. On commence donc par les ensembles de deux tables, puis trois, ect … Il s’agit essentiellement d’un algorithmes dynamiques, on ne recalcul rien et on mémorise les résultats antérieurs pour ne pas les recalculer.

Chaque sous-ensembel des tables à joindre sera ainsi évalué ce qui est donc un algorithme exponentiel (au plus 4096 neouds dans l’arbre néanmoins puisque le nombre de tables est inférieur à 12).

Pour chaque noeuds de l’arbre, il est possible de choisir:

• Ses sous tables intérieures et extérieures
• L’algorithme choisie pour faire la jointure
• Le coût initial et total résultants
• Les ordres et parametrisations que l’on peut obtenir.

Pour un ensemble de tables données, on va garder toutes les possibilités qui ne sont pas dominée par un autre choix et supprimer les autres.

Quelques remarques complémentaires

Nous n’avons pas parler des cas où les jointures sont des FULL JOIN (LEFT/RIGHT JOIN). Cela contraint l’arbre de jointure fortemment, car ce sont des opérations non commutatives. Les semijoins (EXISTS) nécessitent également un traitement particulier car pour eux le coût initial est prépondérant.

Par ailleurs, avec les dernières versions de PostgreSQL, le traitement des requêtes parallèles est apparut nécessitant d’introduire des algorithmes pouvant découper le problèmes en sous problèmes partiels.

Compiled the: dim. 07 janv. 2024 23:19:22 CET