Algorithmes et bases de données, année 2019

Introduction à PostgreSQL

Dans ce cours on utilisera principalement la dernière version (12.2) de PostgreSQL téléchargeable ici. Le logiciel est égalent installable depuis le paquet (pour Debian/Ubuntu par exemple) ou recompiler directement depuis git.

Les codes sources contiennent des informations intéressantes sur le fonctionnement interne de PostgreSQL et on privilégiera donc une installation à partir des source.

Des ressources pour aller plus loin:

L’architecture générale

PostgreSQL met à disposition à la fois des algorithmes efficaces de manipulation de données sur disque, une architecture pour les interrogées efficacement, une gestion de l’accès concurrent aux données et des outils avancés de fouilles et d’indexation de données.

Les différents composants de PostgresSQL, outre la gestion de la mémoire en RAM et sur disque se décompose comme suit:

  1. Optimisation des requêtes
  2. Gestion des accès concurrents
  3. Gestion de la bufferisation
  4. Robustesse à la Panne et réplication.

Une architecture de client/serveur

PostgreSQL a une architecture générale de client/serveur avec un processus “master” qui écoute et qui est dupliqué (fork) à chaque connexion d’un client. Il faut donc que le daemon tourne en permanence. Certaine opération de maintenances sont également déclenchée à intervalle régulier. L’objectif est de permettre l’administration d’un cluster (regroupement) de bases de données disposant de son propre système droit et privilèges.

Des accès concurrents

Une base de données doit permettre de gérer des connections multiples (parfois très nombreuses) en lecture et en écriture sans compromettre les données. La base de donnée doit apparaître inchangé au début et à la fin de l’exécution d’une requête. Ces accès concurrent entraîne une complexité technique substantiel qui ne sera que partiellement abordée plus tard.

La structure sur disque d’une table

Une table est stocké en un fichier qui est lui même subdivisé en page de taille fixe. Chaque page contient des informations supplémentaires (header) suivit d’une liste de pointeurs encodé sur un nombre fixe d’octets pointant vers l’adresse des tuples dans la page (stocké en partant de la fin).

Cette structure permet de ne pas avoir à ce soucier du nombre de tuples stockés dans chaque page ni d’avoir a allouer un espace pour l’adresse des tuples (qui sont de tailles variables).

Cela permet d’avoir une adresse physique pour tuple de la table. On verra comment les modifications et suppressions sont gérés lors du cours sur la concurrence. À chaque page on associe un entier (son numéro dans la liste des pages) et à chaque tuple un index. Accéder à une page donnée se fait donc avec un simple fseek et fread.

La taille des pages à un impact sur les performances globale qui est non trivial (dépend de l’architecture, du type de disque, de la quantité de RAM, de l’utilisation).

Optimisation de requêtes et modèle de coûts

Au coeur d’une base de données, il y a les heuristiques pour optimiser les requêtes de l’utilisateur. Ces heuristiques utilises beaucoup d’informations:

En toute généralité, trouver l’algorithme optimale pour une requêtes est très coûteux: c’est NP-complet, ce qui explique le recours à des heuristiques parfois complexe.

PostgreSQL utilise un optimiseur particulier basé sur un algorithme génétique.

Afin de piloter ces algorithmes, on lui fournit des statistiques sur les tables afin que le coût de chaque opération soit évaluable. Le coût d’une opération dépend très fortement du context et du matériel. Il est possible des les modifiés dans les fichiers de configurations.

Bufferisation des données

L’accès au données passe par un outil dédiés qui s’intercalle entre la mémoire partagée entre les processus actifs et les données présentes sur disque.

L’objectif de cet outil est de charger des pages en mémoire, et de les garder aussi longtemps que nécessaire, de les modifier en mémoire et de répercuter éventuellemnet ces modifications sur disque.

Le buffer communique avec deux processus en backend pour cela:

  1. checkpointer
  2. backgroundwriter