Le modèle relationnel permet une vision logique très simple des relations : des tables, manipulé par un langage facile à utiliser, qui ne spécifient aucune information physique. Une vision naïve de l'implantation physique des relations est possible : chaque relation est un fichier simplement séquentiel de données sur disque. Un tel mode de stockage conduit, à l'évidence, à des performances catastrophiques : l'organisation physique des relations sur disque ne peut se contenter d'une simple organisation séquentielle des informations. Les bases de données, utilisent naturellement des organisations physiques plus sophistiquées. Ces méthodes d'accès, efficaces, ont pour but de déterminer, à partir d'une clé de recherche, l'ensemble minimum des pages de disque à lire.
Les méthodes d'accès sont encore aujourd'hui l'un des éléments les plus mal connus et les plus difficilement maîtrisées par les utilisateurs des systèmes de gestion de bases de données (SGBD). Les raisons sont sans doute liées à la difficulté du problème, mais aussi, à notre avis, à la multiplicité des méthodes et des propositions particulières. L'utilisateur a beaucoup de mal à s'y retrouver et utilise de façon incomplète les possibilités proposées par les systèmes.
Dans un SGBD, le mode d'enregistrement des relations influe sur les performances. En effet, comme dans un livre, les informations sont écrites sur des pages (ici des pages de disque) regroupées selon un certain nombre de règles (les tuples sont, par exemple, triés sur les valeurs d'un attribut particulier ou bien sont regroupés dans une même page après application d'une fonction de hachage�). La connaissance par le SGBD, des règles adoptées de rangement des informations, permet de gagner un temps précieux en n'allant examiner que les pages utiles. Ce mode de rangement est appelé le placement ou clustering.
L'accès performant aux données est un problème traditionnel du développement des Systèmes d'Information. L'impératif de rapidité face à de gros volumes de données a entraîné, dès les années 60, la mise au point de méthodes évoluées. Elles n'ont fait que se perfectionner et se sophistiquer depuis. L'aboutissement de cette période est marquée par le livre monumental de D.E. Knuth [Knuth 73], qui dresse un panorama complet des méthodes désormais classiques de recherche et d'accès des données. Les organisations classiques de fichiers sont fondées sur les valeurs d'un champ particulier choisi généralement comme identifiant et appelé clé.
Les fichiers d'enregistrements sont des structures adressables : chaque enregistrement est identifié par une clé. Ils supportent deux techniques traditionnelles d'accès : le hachage et les arbres.
Dans le cas de fichiers statiques, un regroupement par hachage (une fonction de hachage, bien choisie, est appliquée à la clé et détermine la page où est placé l'article) permet de retrouver un enregistrement en un seul accès disque en théorie. L'arbre en requiert toujours plusieurs. Par contre, lorsque le fichier, comme c'est le cas dans des applications de plus en plus nombreuses, est dynamique, i.e. qu'il évolue dans le temps, alors l'arbre se comporte encore relativement bien, tandis que les performances du hachage peuvent devenir très mauvaises. Il peut même être nécessaire de re-hacher tous les enregistrements dans un nouveau fichier. De plus les arbres ont la propriété importante de conserver les articles triés, ce qui n'est pas le cas, en général, du hachage. Nous présenterons dans ce chapitre ces deux techniques de base, puis indiquerons le mode de fonctionnement et d'utilisation de structures d'accès indirect ou index secondaires.
L'index peut être dense (nombre
de clés égal au nombre d'articles dans le fichier) ou non dense
(nombre de clés inférieur). Conserver l'ordre des clés
permet de former des index non denses. Dans une clé k un index non dense
renvoit à l'adresse de l'ensemble des articles présentant les
valeurs de clés comprise entre la clé k et la clé suivante
de l'index. Par exemple, pour une relation EMPLOYE (N°, NOM,
SERVICE, AGE) :
Les possibilités pratiques
peuvent être visualisées sur le tableau suivant où sont
indiquées quelques méthodes connues (ISAM, VSAM, UFAS, IS3):
L'index souvent stocké (au moins en partie) dans une mémoire secondaire,.est lui-même un fichier. Ce dernier peut être organisé en plusieurs niveaux et constituer un index hiérarchique.
Exemple d'un index à 3
niveaux :
Pour mieux caractériser la notion d'index hiérarchisé, et la rendre indépendante des particularités d'implantation, une structure d'arbre comportant un nombre variable de niveaux est introduite. Cette structure est appelée arbre équilibré ou arbres-B (B-Tree) [Bayer 72]. La définition formelle d'un arbre-B est la suivante : B=Balance
Un arbre balancé est un arbre tel que :
1) chaque chemin depuis la racine vers une feuille est de même longueur h (hauteur de l�arbre);
2) chaque n�ud contient k clés, triées de gauche à droite, et k+1 pointeurs ;
3) un n�ud est soit terminal, soit possède (k+1) fils tels que les clés du ième fils (1£ i, i£ k+1) ont des valeurs comprises entre les valeurs des (i-1)ème et ième clés du père ;
4) on appelle ordre m d�un B-Tree le nombre de pointeurs utilisés dans un n�ud à moitié plein : m = [ k+1 / 2] (on le nomme parfois éventail - " fan-out " � de l�arbre).
Le principe de ces structures repose sur la comparaison de la valeur des clés. Les n�uds de l'arbre contiennent des clés triées et des pointeurs vers des n�uds fils. Lors de la recherche d'une clé k, cette dernière est d'abord comparée à chaque clé du n�ud racine ; ce qui permet de choisir une branche vers un n�ud de niveau inférieur où l'opération est renouvelée ; et cela jusqu'à trouver l'enregistrement de clé k ou atteindre les feuilles.
Les valeurs contenues dans un n�ud
partagent les valeurs de clé possibles en un nombre d'intervalles égal
au nombre de branches.
L'arbre équilibré peut contenir uniquement les index ou l'ensemble index- articles. Dans le premier cas, les articles sont stockés dans un fichier séparé (méthode IS3 de IBM). Les articles ne sont pas triés. L'index est alors dense. Dans le second, les articles sont également stockés dans l'arbre ; les clés sont placées aux niveaux supérieurs et les articles dans les feuilles : on parle de B+ Tree ; c'est l'organisation séquentielle indexée régulière (VSAM de IBM, UFAS de CII) ; les articles sont triés et l'index n'a pas à être dense.
L'insertion et la suppression d'une clé dans l'arbre sont des opérations relativement complexes et coûteuses. Il est souvent nécessaire de réorganiser l'arbre pour qu'il reste équilibré. Cependant une fois cette réorganisation (ré-équilibrage) effectuée, les performances restent inchangées.
Conserver l'ordre des articles permet sans utiliser l'index un accès séquentiel très rapide aux données. Cette possibilité est importante pour un grand nombre d'applications.
Les deux avantages des arbres B sont donc leur bon comportement pour des fichiers dynamiques et le stockage ordonné des articles qui permet deux types d'accès, sélectif et séquentiel. Par contre, l'utilisation d'une structure de données volumineuse qui nécessite plusieurs accès disque (typiquement 3 à 5 E/S pour l'accès à un article) rend les B-Trees peu attrayants lorsqu'accéder à des performances élevées sont recherchées.
Cette méthode, comparée aux méthodes précédentes, est supérieure, à la fois du point de vue de l'espace mémoire (pas de structure de données supplémentaire) et de la vue vitesse (calcul arithmétique plus rapide qu'une succession de comparaisons). Malheureusement, trouver des fonctions qui déterminent des emplacements différents pour des clés différentes, en évitant de laisser trop d'adresses inutilisées n'est pas facile.
Les fonctions qui évitent de déterminer des valeurs en double sont étonnamment rares. KNUTH rapporte dans son livre "The Art of Computer Programming" le "birthday paradox" qui affirme que si 23 personnes ou plus se trouvent réunis dans une pièce, il y a une chance sur deux pour que deux d'entre elles aient le même jour et le même mois de naissance ! En d'autres termes, si nous voulons qu'une fonction aléatoire transforme et place 23 clés dans une table de 365 emplacements, la probabilité qu'il n'y ait pas deux clés au même emplacement est inférieure à 1/2 (0.49 exactement). Le "birthday paradox" nous indique qu'il y aura probablement des clés distinctes (ki ? kj) dont le hachage donnera la même valeur h(ki) = h(kj). Un tel événement est appelé une collision. Plusieurs possibilités existent pour résoudre le problème des collisions.
Le hachage consiste donc à choisir la meilleure fonction h possible (c'est-à-dire qui minimise les collisions) et à sélectionner une méthode pour résoudre, le plus économiquement possible, les collisions.
Résoudre une collision consiste à déterminer une adresse à partir d'une information fournie. Cette information est un champ particulier de l'enregistrement : la clé. L'adresse obtenue est appelé le hash-code. La fonction utilisée peut être quelconque. Une bonne fonction est choisie en fonction de la distribution des clés. Elle doit satisfaire deux critères parfois contradictoires :
2) elle doit minimiser les collisions.
1) traiter la valeur de la clé comme une séquence de bits, formée par concaténation des bits de chaque champ de la clé
2) découper la séquence en tranches d'un certain nombre de bits
3) additionner les groupes de bits considérés comme des entiers
4) diviser la somme par le nombre premier M et utiliser le reste.
D'autres fonctions pseudo-aléatoires plus ou moins complexes peuvent être utilisées (pour plus de détails voir [Knuth 73]).
Cette résolution par "chaînage" est souvent une idée simple et excellente. Les insertions et les recherches infructueuses sont rapides.
Un chaînage plus sophistiqué, dit chaînage imbriqué, est également réalisable. Il permet de mieux occuper l'espace (de nombreuses têtes de liste restent vides si augmenté est pour diminuer la taille moyenne des listes). Dans cette approche, chaque emplacement de la table a un champ pointeur qui indique l'emplacement de la table où se trouve l'article suivant de la liste. Lors d'une insertion, si la place est occupée, on insère à la première place libre (par ordre croissant ou décroissant des adresses), puis les pointeurs sont mis à jour.
Dans le même esprit, la méthode d'adressage ouvert permet de ne plus utiliser de pointeur du tout. La politique d'insertion est simplement d'occuper la première place libre. Le gain de place est important, l'insertion très simple. La recherche, en revanche, se complique très sérieusement : si l'article de clé K n'est pas trouvé en h(K), on ne peut conclure à son absence dans le fichier avant d'avoir parcouru tous les paquets qui par débordement peuvent lee contenir. L'organisation étant cyclique (le dernier paquet débordant en priorité dans le premier paquet), cette organisation conduit dans le cas des recherches infructueuses à parcourir tout le fichier. En revanche, la méthode est assez bonne pour des recherches où la présence de la clé recherchée dans le fichier est sûre.
Pour conclure, nous indiquerons que le hachage a longtemps été considéré essentiellement comme une méthode de recherche en mémoire centrale (recherche dans des tables). En effet, dans ce cas, la répartition statique des valeurs de clé est généralement connue et permet de choisir la bonne dimension de la table et une bonne fonction de hachage. En revanche, si le nombre d'enregistrements croît et la répartition des clés est mal connue, les mauvaises performances dues aux collisions limitent la méthode. C'est le cas du hachage statique pour les fichiers. Récemment des méthodes dite de hachage dynamique lèvent ces inconvénients.
Plus précisément, le fichier est divisé en p cellules de taille fixe. Une fonction pseudo-aléatoire h, appelée fonction de hachage, attribue à la clé une cellule mémoire identifiée par h(c). La cellule est appelée paquet et peut contenir un certain nombre d'enregistrements. Un fichier aléatoire définit la distribution des articles dans des paquets dont l'adresse est calculée à l'aide d'une fonction de hachage appliquée à la clé. La taille des paquets correspond à un nombre entier de pages (un accès disque).
Un article de clé c est inséré dans le paquet h(c), appelé paquet primaire pour c, tant que le paquet n'est pas plein. La recherche de c démarre toujours par un accès au paquet h(c). Si le paquet h(c) est plein lorsque l'enregistrement de clé c doit être inséré, une collision se produit. Un algorithme de résolution de collision détermine alors une adresse de paquet de débordement m (m?h(c)), où sera rangé l'enregistrement en débordement.
Une méthode de résolution de collision simple place l'enregistrement en débordement dans un paquet non primaire (? h(c), " c) qui sera chaîné au paquet primaire. Mais, dès que les paquets primaires débordent, les recherches nécessitent au minimum deux accès et les performances se dégradent rapidement. D'autres techniques de résolution, citées lors du hachage en mémoire centrale, peuvent alors être utilisées.
La difficulté reste le choix d'une "bonne" fonction de hachage. Elle doit distribuer uniformément les enregistrements dans les paquets, et minimise, ainsi les débordements, tout en conservant un bon taux d'occupation de la mémoire secondaire. Le choix d'une telle fonction, déterminant une distribution uniforme d'adresses à partir d'une distribution non uniforme de clés, n'est pas évident. Il nécessite, de surcroît, une bonne connaissance à priori de la répartition des valeurs de clés. C'est rarement le cas pour les fichiers.
La rapidité est l'avantage principale de la méthode d'accès aléatoire. Par contre, le taux d'occupation de la mémoire secondaire réellement utilisée peut rester assez éloigné de 1. Enfin, la taille d'un fichier doit être fixée à priori (choix du nombre de paquets primaires).
L'administrateur choisit précisément les privilégiés. Cependant, ce choix s'effectue, à un instant donné, en fonction des besoins instantanés de l'application. Du point de vue de la conception physique, ces besoins sont représentés par un ensemble de questions fréquentes. Or, rien ne garantit que cet ensemble n'évoluera pas dans le temps.
Il n'est pas toujours possible de changer l'organisation physique. En effet, l'interruption de service imposée par le déchargement/rechargement peut être inacceptable pour certaines applications. De surcroît, l'évolution des questions peut être trop rapide ou trop provisoire pour qu'une solution par réorganisation physique soit envisageable.
Une technique complémentaire au placement les index est donc nécessaire.
Les index constituent des chemins d'accès secondaires (c'est-à-dire permettant un accès direct sur les valeurs d'attributs non plaçants). Ces index sont des structures de données et sont utilisés comme des accélérateurs d'accès.
La définition de chemins d'accès secondaires complète le placement. La possibilité de construire ou de supprimer ces chemins "à la demande" assure une adaptation instantanée aux besoins des applications. Index et placement sont complémentaires. Le placement reste en effet optimal (seuls les blocs utiles sont accédés) et indépendent de la sélectivité des attributs (on appelle ici sélectivité le rapport du nombre de valeurs distinctes d'un attribut au nombre de tuples de la relation). En revanche, les index, très sensibles à la sélectivité des attributs, deviennent rapidement inefficaces quand celle-ci est trop élevée. Pour une application donnée, une répartition judicieuse des attributs entre placement et index rend un maximum d'accès très efficace.
Un index est une structure destinée à localiser rapidement les tuples dont un attribut a une certaine valeur. Il associe la valeur de l'attribut et l'adresse des pages où se trouvent les tuples possédant cette valeur d'attribut. A partir d'une entrée sur la valeur d'un attribut spécifié dans la qualification d'une question, l'index fournit la liste des pages contenant les tuples qui peuvent vérifier le prédicat de recherche.
L'index peut ainsi être défini comme un ensemble de couples (valeur d'attribut de recherche, adresse). Une seconde possibilité constitue des couples (valeur d'attribut de recherche, valeur d'attribut plaçant). L'attribut plaçant est généralement la clé dans les organisations traditionnelles. La première solution a pour avantage un format plus court et un accès plus rapide aux pages de la relation qui sont alors recherchées par une adresse directe. Cependant, la manipulation des adresses de blocs nécessite la mise à jour de l'index à chaque migration de tuple d'une page vers une autre (ce qui se produit fréquemment lors des insertions). Cette mise à jour est nécessaire à chaque insertion ou suppression de tuple, mais également à chaque éclatement ou regroupement des pages de données. La seconde solution ne présente pas cet inconvénient. Elle utilise une sorte d'indirection : l'index permet de retrouver les clés plaçantes des tuples présentant la valeur cherchée. La clé plaçante est ensuite utilisée pour atteindre le tuple par la méthode d'accès employée pour le placement de la relation (hachage ou B-Tree par exemple).
Dans un SGBD, une solution très naturelle constitue une relation INDEX, de schéma (valeur d'attribut, adresse de page) pour stocker les informations de l'index. Cette méthode est largement utilisée par les produits du commerce, mais complique le processus d'insertion à cause des mises à jour de l'index.
System R implante des chemins d'accès secondaires des index, est formés de couples dont le premier terme est la valeur de l'attribut indexé (c'est-à-dire sur les valeurs duquel on construit un index) et le second terme l'identifiant. Un index est un ensemble des couples (clé d'accès, TID). Il est stocké sous forme d'un B+ Tree dont les pages sont les pages d'index, triées sur la clé d'accès. Il permet d'accéder aux tuples recherchés dans un ordre donné, c'est-à-dire sur les valeurs croissantes ou décroissantes de l'attribut indexé. L'obtention des TID des tuples recherchés n'exige pas d'accès aux pages de données.
System R permet d'organiser le placement
d'une relation en fonction d'un index. L'efficacité d'un index dépend
en effet du placement physique de la relation. Si la relation est placée
en accord avec l'index, l'index est dit plaçant (clustering index). Dans
le cas contraire il est dit non plaçant (unclustering index).
Les chemins d'accès dont dispose le système sont donc le parcours séquentiel, l'index plaçant et l'index non plaçant. Leur utilisation est pour chaque relation référencée dans un traitement décidée par l'optimiseur.
Définir des index multi-attributs plaçants (on a alors un placement multi-attributs) est possible. Les champs concernés sont enregistrés sous la forme d'un code qui conserve l'ordre numérique ou lexicographique. Une question du type "At1=valeur1 et valeur2<At2<valeur3" peut ainsi être accélérée par un index unique. D'autres méthodes implantent des index séparés (un par attribut) et un opérateur d'intersection des listes d'adresses que fournissent les différents index (utilisés dans le cas de questions qui spécifient les valeurs de plusieurs attributs indexés). System R évite cette intersection et les structures de données multiples. Cependant, l'utilisation de l'index est impossible si le premier champ n'est pas spécifié dans la question car l'ordre n'est plus utilisable.
Les index sont de surcroît largement utilisés par les algorithmes de jointure implantés.
Ainsi, System R privilégie les accès sur valeur de clé (égalité ou inégalité) destinés à sélectionner un ensemble important de tuples triés sur le critère de recherche. Les accès sur valeurs de clé sont également efficaces si un index est construit sur la clé. Par contre, les chemins d'accès implantés ne sont guère efficaces pour des critères peu sélectifs de type 'exact match' (égalité d'un attribut et d'une valeur) sélectionnant un ensemble de tuples.
POSTGRES tente, pour des non spécialistes, de simplifier la définition de ces nouvelles méthodes grâce à des interfaces conviviales. Les nouvelles méthodes d'accès sont enregistrées dans une structure de données particulière appelée "gabarit". Cette structure documente les conditions d'efficacité de la méthode en fonction des opérateurs, des types de données et stocke des informations d'évaluation de coût. L'ensemble des méthodes est vu uniformément comme une collection d'abstractions génériques telles que "ouvrir", "fermer", "chercher(critère)" (premier, suivant, unique), "insérer", "supprimer".
Son concepteur a toutefois beaucoup de mal à interfacer correctement la nouvelle méthode, notamment en ce qui concerne la gestion de transactions. Même si l'on partage l'avis des concepteurs de INGRES/POSTGRES selon lequel il n'existe pas de méthode universelle et qu'il faut en proposer plusieurs, définies par l'utilisateur, des outils qui facilitent le travail de ce dernier restent à définir.
Des index secondaires, organisés en B-Trees sont également possibles. Enfin, POSTGRES permet à l'utilisateur de définir une collection d'index sur des types de données abstraits .
2/ les B-Trees sont les méthodes qui supportent le mieux toutes les distributions (parce qu'ils se réorganisent en conséquence), mais au prix d'un coût moyen assez élevé.
Ce chapitre et les précédents
permettent d'avoir maintenant une idée plus complète des étapes
de l'évaluation d'une requête SQL que résume le schéma
ci-dessous :
La première étape analyse syntaxiquement et sémantiquement la requête
L'analyse sémantique en revanche fait appel à des informations de la métabase qui constituent la source des vérifications qui doivent être effectuées : chaque objet évoqué dans la requête - relation, attribut, vue - doit être présent dans la métabase. Cette vérification se traduit par des contrôles sur le schéma de la base, contrôles qui ne sont en fait que des sélections sur les relations de la métabase stockant ce type d'informations. La non existence d'objets évoqués dans la question conduit bien sûr à l'arrêt du traitement de la question et un message sera renvoyé à l'utilisateur.
Les droits relatifs aux relations de la base effectivement invoquées peuvent ensuite être vérifiées. Le mécanisme vérificateur des contraintes d'intégrité (a priori et/ou a posteriori, par requête ou par transaction) prend ensuite le contrôle.
Deux problèmes principaux se présentent : (1) comment réduire l'espace des solutions et ne calculer les coûts que d'un nombre "raisonnable" de plans (ne pas passer trop de temps dans un composant du SGBD qui est sensé précisément gagner du temps est important) ; (2) disposer de modèles de coûts à la fois simples et réalistes.
[Knuth 73] D.E. KNUTH : "The Art of Computer Programming", Vol 3, "Sorting and Searching", Addisson Wesley 1973.
[Litwin 80] W. LITWIN : "Linear Hashing : A New Tool For Files and Tables Addressing" , Proc. of the 6th Int. Conf. on Very Large Data Bases, Montréal, Sept. 1980.
[Stonebraker 86] M. STONEBRAKER, L. ROWE : "The Design of POSTGRES", ACM SIGMOD, Int. Conf. on Management of Data, 1986.
[VALD84a] VALDURIEZ P.,GARDARIN G.: "Join and Semijoin Algorithms for Multiprocessor Database Systems", ACM Transactions on Databases Systems, V9, N° 1, march 1984.
[DEWI85] DEWITT DJ, GERBER R. :"Multiprocessor Hash-Based Join Algorithms", Proc. of the 11th Int. Conf on VLDB , Stockholm, 1985.