10 ans d’améliorations de l’optimiseur PostgreSQL

• De PostgreSQL 8 à 16, une comparaison du 90e centile de latence des requêtes avec le Join Order Benchmark confirme empiriquement une amélioration durable des performances en queue de distribution
• Par rapport à PostgreSQL 8, PostgreSQL 16 a presque divisé par deux la latence en queue, tandis que la période 13 à 16 reste globalement à un niveau stable
• Selon l’analyse de régression, chaque nouvelle version majeure apporte en moyenne 15 % d’amélioration des performances, même si un modèle linéaire ne décrit pas forcément bien l’évolution réelle
• L’expérience fixe les conditions avec GCC 13.2, Docker sur Arch Linux, shared_buffers à 8GB et work_mem à 8MB afin de se concentrer sur la qualité de l’optimiseur de requêtes
• Pour interpréter l’ampleur des gains, il faut prendre en compte non seulement l’optimiseur, mais aussi les évolutions du moteur d’exécution comme les workers parallèles et la compilation JIT

---

Configuration du benchmark PostgreSQL 8 à 16

• L’analyse porte sur les versions majeures 8 à 16 de PostgreSQL, un optimiseur de requêtes open source
• Le benchmark utilisé est le Join Order Benchmark, un ensemble de requêtes avec de nombreuses jointures complexes
  • Ce benchmark a été introduit dans l’article « How Good are Query Optimizers, Really? »
• Chaque version de PostgreSQL a été compilée avec GCC 13.2 dans un conteneur Docker Arch Linux
• L’environnement de mesure a été configuré pour évaluer la qualité de l’optimiseur de requêtes plutôt que les index ou les performances d’I/O
  • shared_buffers a été réglé sur 8GB, suffisamment pour contenir toute la base de données
  • work_mem a été fixé à 8MB pour toutes les versions
• Chaque requête est exécutée une première fois pour chauffer le cache, puis la latence médiane de 5 exécutions supplémentaires est enregistrée
• Pour chaque version majeure, la dernière version mineure disponible a été utilisée
  • Par exemple, pour PostgreSQL 8, la version testée est 8.4.22
  • Ces versions mineures sont généralement sorties après la nouvelle version majeure, mais n’incluent en principe que des corrections de bugs, sans nouvelles fonctionnalités ni améliorations de performances

Résultats des mesures et interprétation

• Les performances en queue de PostgreSQL se sont globalement nettement améliorées
  • En comparant PostgreSQL 8 et 16, la latence en queue a presque été divisée par deux
  • De PostgreSQL 13 à 16, le niveau reste globalement stable
• L’analyse de régression sert à vérifier si la tendance à la baisse entre le numéro de version majeure et la latence des requêtes est significative, et à quantifier les gains selon les versions
  • D’après une régression linéaire, chaque nouvelle version majeure apporte en moyenne 15 % d’amélioration des performances sur le Join Order Benchmark
  • Toutefois, un modèle linéaire peut être inadapté pour mesurer l’évolution réelle
• Il est difficile d’expliquer tous les gains uniquement par l’optimiseur de requêtes
  • Les améliorations du moteur d’exécution, comme les workers parallèles et la compilation JIT, influencent aussi les performances
  • L’évolution, année après année, des plans d’exécution de chaque requête du JOB reste un sujet d’analyse distinct
• Passer de PostgreSQL 8 à 16 peut réduire fortement la latence en queue d’une charge de travail
• Dans les comparaisons de recherche, il est important de noter que PostgreSQL lui-même devient continuellement un point de référence plus solide
  • Neo et Bao étaient comparés à PostgreSQL 11, tandis que des travaux plus récents se comparent à PostgreSQL 14, 15 et 16
  • Même si une ancienne méthode améliore PostgreSQL de 30 % et une méthode récente de 25 %, cette dernière a pu être comparée à une version de PostgreSQL déjà plus performante
• Les mesures brutes d’origine sont disponibles dans les données brutes

[GN⁺]

Avis sur Hacker News

• J’utilise Postgres depuis 15 ans et j’ai passé l’essentiel de ma carrière à modéliser et résoudre des problèmes d’optimisation mathématique ; sur ce sujet, je pense que l’essentiel tient en trois points
  Tout problème d’optimisation a besoin de données de coût, et plus ces données sont nombreuses et bonnes, mieux c’est. Postgres a connu des améliorations, comme les statistiques inter-colonnes, mais il reste encore de gros angles morts, par exemple la latence des appels système. La latence de lecture d’une page depuis le disque varie fortement d’un système à l’autre, pourtant Postgres ne la mesure pas directement et s’appuie sur des paramètres de configuration. Les statistiques de clés étrangères manquent aussi : les jointures qui suivent des clés étrangères ne devraient pas produire de mauvais plans, mais cela arrive encore parfois
  Pour les requêtes particulièrement grosses et coûteuses, il faudrait une planification différée ou des plans alternatifs. Aujourd’hui, le plan est figé avant l’exécution, mais le nombre de lignes ou les estimations de cardinalité obtenus au début de l’exécution pourraient fortement améliorer les plans des étapes suivantes
  Le machine learning est aussi un domaine où il y a de la marge, mais les tentatives que j’ai vues jusqu’ici ne m’ont pas impressionné. Il ne faut pas utiliser le machine learning pour le plan lui-même, mais pour la découverte et l’estimation des coûts. Il faut construire de meilleurs modèles de coût et permettre au moteur d’optimisation d’exploiter ces données

  • J’aimerais en savoir plus. Par exemple, je suis surpris de voir la latence des appels système figurer si haut dans la liste. Selon moi, le point de vue courant dans la communauté des bases de données est que les modèles de coût sont globalement corrects, et que ce sont les estimations de cardinalité qui sont vraiment mauvaises
    Pour la planification différée/alternative, je me demande si l’exécution adaptative des requêtes est une approche raisonnable. On peut faire en sorte que les informations obtenues au début de l’exécution influencent la suite du plan, mais je crains que si les premières jointures sont mal choisies, ce qui est fréquent, il soit difficile de s’en remettre sans quelque chose comme Yannakakis/SIPs
    À propos du « machine learning pour l’optimisation de requêtes », j’ai clairement un biais. Cela dit, toutes les approches de « machine learning pour la planification » que j’ai vues utilisent au fond le machine learning pour la découverte/l’estimation des coûts. Ces approches essaient d’équilibrer les données qu’elles collectent, c’est-à-dire l’exploration, et la qualité des plans qu’elles produisent, c’est-à-dire l’exploitation. Fait intéressant, utiliser le machine learning d’une manière totalement séparée de la planification rend les estimations plus précises, mais dégrade les plans de requête réels : https://people.csail.mit.edu/tatbul/publications/flowloss_vl...
    J’ai des intérêts dans ce domaine, donc il faut prendre mon avis avec recul
  • Les plans alternatifs ont vraiment l’air intéressants. Il n’y a pas longtemps, j’ai vu un plan de requête qui estimait qu’une sous-requête produirait environ 1 000 lignes et lui appliquait donc une boucle imbriquée avec un scan d’index, alors qu’en réalité il y en avait environ 1 milliard
    Je ne sais pas encore pourquoi l’estimation était aussi erronée, mais si l’on pouvait basculer d’une boucle imbriquée vers une jointure par hachage quand le nombre de lignes dépasse un certain seuil, cela aiderait beaucoup à éviter les plans catastrophiques
  • Je me demande ce que signifie exactement l’absence de statistiques de clés étrangères. Postgres, comme beaucoup de bases de données relationnelles, ne crée pas automatiquement d’index sur les clés étrangères, mais j’imagine que tu le sais déjà
    Tu parles d’un problème d’ordre des jointures ?
  • Je me demande si MSSQL est meilleur sur ce point

• L’optimiseur de requêtes de Postgres essaie de réduire le nombre de pages lues depuis le disque et le nombre de pages écrites sur le disque pour les résultats intermédiaires. Il me semble donc erroné de configurer des shared buffers assez grands pour contenir toutes les données puis de benchmarker l’optimiseur de requêtes
  Dans ce cas, on mesure la vitesse de l’optimiseur de requêtes et de l’exécuteur de jointures, pas la qualité des plans de requête générés. Il ne serait même pas étonnant qu’en réalité les plans générés par chaque version soient tous identiques et que seule la vitesse d’exécution ait été mesurée

  • Non. Ce qui est optimisé, ce n’est pas seulement les pages lues depuis le disque, mais un coût qui inclut aussi des éléments comme l’utilisation CPU
    Le coût est une unité arbitraire conçue pour être corrélée au temps écoulé, pas au nombre de lectures disque ; comparer des plans avec tout en RAM est donc parfaitement valable. Par convention, la lecture d’une page depuis le disque est mise à l’échelle à 1,0, mais ce n’est pas la même chose que dire que « l’optimiseur minimise le nombre de lectures de pages disque ». Sur une machine donnée, on aurait tout aussi bien pu fixer 1 ms à 1,0
  • Il est tout à fait possible que les plans soient similaires et que l’on ait mesuré des améliorations du moteur d’exécution. Le Join Order Benchmark est conçu pour tester la qualité de l’optimiseur
    L’optimiseur de PG essaie de réduire non seulement le nombre de pages lues depuis le disque, mais aussi le nombre de tuples examinés par le CPU, le nombre d’évaluations de prédicats, etc., et tous ces chiffres sont agrégés en un « coût », la fonction que l’optimiseur cherche à minimiser
    Les mesures de performances en cache froid et en cache chaud peuvent donner des résultats différents, et cette expérience correspond clairement à un scénario de cache chaud. Mais le cache froid a aussi le problème évoqué. Avec la taille des données du Join Order Benchmark, les améliorations des B-tree de PG qui économisent quelques opérations d’I/O peuvent dominer les améliorations basées sur le CPU
    À titre de référence, le plan de la requête à latence P90 est passé, entre PG 8.4 et PG 16, d’un plan utilisant une jointure en boucle et une jointure par fusion à un plan utilisant une jointure par hachage, et cette requête n’est plus la requête P90. On peut y voir au moins une partie de preuve d’améliorations de l’optimiseur

• L’article mentionne le compilateur JIT de PostgreSQL, mais jusqu’ici je ne l’ai vu que dégrader les performances des requêtes. Je l’ai mis dans ma checklist d’installation comme option à désactiver

  • Un client a rencontré ses pires problèmes de performance après être passé à Postgres. Étrangement, cela ne se produisait que dans Docker et dans la configuration du serveur de test, pas sur les machines des développeurs. Les développeurs exécutaient Postgres via Homebrew
    Il s’est avéré que Homebrew installait Postgres sans support JIT, et qu’une requête qui se terminait en 200 ms sur les machines des développeurs prenait 4 à 5 secondes dans les environnements avec JIT activé. Comme nous n’utilisons pas Postgres de façon très poussée, il nous a fallu un certain temps pour trouver la cause ; depuis, nous désactivons toujours le JIT et nous ne nous retournons pas
  • Le compilateur JIT est excellent pour les requêtes analytiques
    Dans PostgreSQL, on peut aussi configurer les seuils d’activation du JIT, donc il est possible de relever le seuil à partir duquel le JIT se déclenche
  • Le JIT de pg montre assez bien que LLVM n’est pas très adapté au JIT, et l’absence dans Postgres d’un cache persistant de requêtes partagées aggrave encore les choses
    S’il pouvait compiler de façon asynchrone en vue de requêtes futures, ce serait probablement moins nuisible. En fait, les JIT classiques, en particulier les backends d’optimisation, fonctionnent plutôt comme ça
  • Postgres ne peut-il pas compiler une requête en JIT une fois, puis exécuter plusieurs fois la requête compilée ?

• C’est intéressant, mais le schéma de numérotation des versions de Postgres a changé avec la v10. 9.6, 9.5, 9.4, 9.3, 9.2, 9.1, 9.0, 8.4, 8.3, 8.2, 8.1, 8.0 sont en réalité toutes des versions majeures distinctes
  Il serait aussi intéressant de voir comment les performances ont évolué dans ces versions

  • Cela dit, de la v9.0 à la 9.6, j’ai apprécié le fait qu’ils aient maintenu une compatibilité du système de fichiers entre versions majeures, permettant des mises à niveau sur place plus rapides en ne remplaçant que les binaires
    Cela les a peut-être freinés, mais les mises à jour annuelles qui nécessitent plus de downtime ou une réindexation ne sont pas très agréables, et c’est peut-être pour cela que beaucoup de sites repoussent les mises à niveau jusqu’à la fin du support des anciennes versions. C’est probablement particulièrement vrai pour les utilisateurs d’AWS RDS
    Les mises à niveau par réplication logique depuis la v10 ont des avantages en matière de disponibilité, mais si le schéma n’est pas relativement simple, c’est un gros projet avec des coûts inévitables et des risques importants
  • Tout à fait d’accord. J’ai interprété les numéros de version à la manière de semver et choisi la dernière version de chaque version majeure, mais ce n’est pas ainsi que PostgreSQL a traditionnellement traité les numéros de version majeurs
    Par exemple, PG 8.2 et 8.1 sont des versions majeures différentes, mais je les ai interprétées comme des versions mineures. La principale raison de ce choix était de réduire le nombre de versions à tester, et je suis d’accord qu’une analyse plus complète devrait tester chaque véritable version majeure

• Il est dit que « bien sûr, toutes ces améliorations ne sont pas dues à l’optimiseur de requêtes », mais il serait intéressant de voir s’il y a eu des changements de plans d’exécution selon les versions

• Cela me rappelle la loi de Proebsting : https://proebsting.cs.arizona.edu/law.html

  • L’avantage de l’optimisation des compilateurs, c’est qu’elle permet d’améliorer les performances sans toucher physiquement aux CPU existants. Année après année, quelqu’un extrait davantage de performances d’une machine conçue par d’autres, et l’effet cumulé devient important
    Imaginez l’impact environnemental d’une optimisation de 1 % des performances de Python. Combien de CO2 en moins dans l’atmosphère ? Ce serait probablement plus que l’empreinte environnementale combinée de vous-même, de votre famille et de vos amis. Peut-être même comparable à celle de toute la ville où vous vivez. Tout cela simplement parce que quelqu’un a pris le temps d’implémenter quelques astuces d’opérations sur les bits
  • Je ne vois pas bien pourquoi. Cette loi semble plutôt dire que les améliorations de performance logicielles n’ont pas beaucoup d’importance, alors que cet article dit que les améliorations de Postgres ont été substantielles
    Est-ce parce que 15 % semble être un chiffre faible ? Dans ce contexte, il ne l’est pas du tout. C’est moins que les 60 % de la loi citée, et encore moins si l’on divise façon 15/10, mais il ne faut pas comparer les performances de Postgres aux progrès du matériel. Pour égaler une amélioration de performance de 1 % sur ce qui est mesuré ici, il faudrait une amélioration matérielle énorme
    Je ne pense pas que cette loi soit aussi ridicule que certains le disent, mais elle porte sur le temps de compilation des langages de programmation. Je ne comparerais pas quelque chose d’aussi relativement peu important au stockage et à la consommation de données, qui comptent parmi les sujets les plus importants de l’informatique
  • Dans ce cas, le chercheur a compilé toutes les versions de PostgreSQL avec le même GCC 13.2 et les a testées sur le même système d’exploitation
  • Cela ressemble à une « loi » assez faible. Était-ce une blague ? Les bases semblent être des chiffres sortis de nulle part, du niveau de « supposons que », et la conclusion est aussi largement à côté. Elle semble suggérer qu’une optimisation qui améliore chaque année de 4 % les performances de nombreux logiciels dans le monde serait une perte de temps
    Comme point de comparaison, seule la loi de Murphy est proposée. Je serais curieux de connaître l’écart entre le coût de développement d’un matériel plus rapide et celui de l’amélioration continue des compilateurs. Selon la comparaison du retour sur investissement, par exemple en dollars par point de pourcentage de gain de performance, cette « loi » pourrait avoir un certain poids
    En revanche, cet article sur Postgres semble montrer des rendements décroissants de l’optimisation, ce qui contredit l’hypothèse de cette « loi » selon laquelle les gains seraient constants d’une année sur l’autre. En même temps, cela pourrait aussi confirmer l’idée implicite de Proebsting selon laquelle, à long terme, l’optimisation est un mauvais investissement

• Cette analyse est un peu confuse. Je ne vois pas comment une tendance à la baisse absente du graphique a été confirmée dans les données
  La médiane semble baisser un peu sur les premières versions, puis remonter sur les versions récentes. Comme le R² est très faible, la corrélation ne paraît pas convaincante. En gros, on dirait que la latence de queue s’est améliorée, et que le reste dépend de l’environnement

  • Je suis l’auteur du billet
    L’interprétation selon laquelle « la latence de queue s’est améliorée et le reste dépend de l’environnement » est valable, mais je la vois comme une lecture prudente. Bien sûr, dans de nombreuses applications, peut-être même la plupart, la latence de queue est très importante. En outre, la latence de queue correspond aussi à ce que les ingénieurs travaillant sur l’optimiseur ciblent principalement : réduire le temps d’exécution des requêtes les plus longues

• À quoi ressemble l’optimisation de requêtes ? Je me demande s’il s’agit d’optimiser au niveau SQL ou au niveau des algorithmes.

  • Dans les bases de données que j’ai utilisées, en dehors de PostgreSQL, la plupart des optimisations se font au niveau des algorithmes. Autrement dit, il s’agit de choisir le meilleur algorithme et l’ordre d’exécution optimal pour une requête donnée.
    Plusieurs requêtes SQL différentes peuvent être traduites en une même « commande » ou un même plan d’exécution, et il semble que la sémantique de SQL elle-même laisse peu de marge à l’optimisation au niveau du langage.
    Comme indiqué dans un autre commentaire, l’une des décisions importantes consiste à déterminer si un scan complet de table peut être remplacé par une recherche dans un index ou un scan d’index.
    Par exemple, si un scan complet de table est nécessaire et que, pour chaque ligne, il faut effectuer un calcul important afin de décider si elle doit faire partie de l’ensemble de résultats, l’optimiseur peut transformer ce scan complet en scan de table parallèle et fusionner les résultats de chaque tâche parallèle.
    Quand on écrit du code haute performance pour un compilateur, il faut savoir comment l’optimiseur du compilateur transforme le code source en code machine. Cela permet de privilégier le code que l’optimiseur traite bien et d’éviter les motifs qui produisent du code machine plus lent. Au final, l’optimiseur est programmé pour détecter certains motifs et les transformer.
    C’est la même chose avec les optimiseurs de requêtes et les plans d’exécution. Il faut apprendre quels motifs l’optimiseur de requêtes de la base de données utilisée sait traiter pour produire un plan d’exécution efficace.
  • On décrit toutes les façons possibles d’exécuter le SQL, puis on choisit le plan le plus rapide. Par exemple, si l’on cherche la ligne d’un utilisateur dont le user_id vaut xx, il s’agit de choisir entre lire toute la table et filtrer, ou utiliser une structure de données dédiée.
    Avec un index, on peut trouver la ligne en temps logarithmique par rapport au nombre de lignes. Il y a aussi beaucoup d’autres possibilités : choisir l’ordre des jointures, choisir la stratégie de jointure, pousser les conditions de filtrage vers la source, etc. C’est le vaste domaine de l’optimisation SQL.
  • À très haut niveau, l’objectif du planificateur de requêtes est de minimiser le coût de lecture des données depuis le disque. Il collecte des statistiques de colonnes pré-calculées, comme le nombre de lignes et le nombre de valeurs distinctes, afin d’estimer combien de lignes correspondront à la requête.
    Il utilise ces informations pour déterminer l’ordre des jointures, choisir les index, etc. Les jointures peuvent être exécutées au moyen de plusieurs algorithmes, comme le hachage, les boucles ou la fusion. L’option la moins coûteuse dépend de facteurs tels que le fait qu’un côté tienne en mémoire de travail, que les deux côtés soient déjà triés, par exemple grâce à un scan d’index, etc.
  • L’optimisation de requêtes consiste à choisir les algorithmes qui fourniront le résultat demandé par le SQL.

• Le site semble être hors ligne, donc on peut consulter ceci à la place : https://web.archive.org/web/20240417050840/https://rmarcus.i...