Rushmore est plus qu’une technologie, c’est un mythe.

http://en.wikipedia.org/wiki/Mount_Rushmore

Cela ne devrait cependant pas nous empécher de vouloir découvir ce qu’il y a derrière ce mythe. Il est primordial de séparer les faits de la fiction. Dans la décade précédente la règle était de créer un index sur DELETED() le contraire est vrai aujourd’hui. Pourtant, aucune de ces deux propositions n’est totalement valide en réalité. L’origine de la performance de Visual FoxPro a deux fondements. L’une de ces fondations est Rushmore, l’autre est l’utilisation intensive du cache. La différence de performance avec d’autres systèmes de base de données ayant, comme Rushmore, des algorithmes de recherche centrés sur une image des données, est surtout due à Rushmore, plutôt qu’à la stratégie de l’utilisation du cache et de l’accès optimisé au réseau.

Rushmore est un algorithme centré sur une image des données (Bitmap). Visual FoxPro crée une liste de chaque condition pouvant être optimisé avec Rushmore. Cette liste détermine si un enregistrement respecte ou non les critères de recherche. Visual FoxPro n’utilise qu’un seul bit pour chaque enregistrement, car il n’y a que deux états possible. Huit enregistrements sont contenus dan un octet, Pour une table de 8 millions d’enregistrements, chaque condition de recherche requiert 1 MB de mémoire. Chaque bit est d’abord à 0 – non déterminé – et l’enregistrement correspondant est de ce fait dans le jeu résultant. Lorsque les images sont déterminées elles sont combinées bit à bit. Si la condition suivante est utilisée dans une requête :
NAME = "Smith" AND InvoiceDate < DATE()-60

Cette requête implique la création de deux images indépendantes, chacune contenant tous les enregistrements pour "Smith" et tous les enregistrements ayant une facture depuis moins de 60 jours. Peu importe, dans chaque diagramme que l’autre condition ne soit pas remplie. Après que les deux images aient été combinées bit à bit avec AND il en résulte une image ne comportant que les seuls enregistrements remplissant les deux conditions.
Il n’est pas difficile d’imaginer que le besoin en mémoire pour batir ces images peut rapidement grossir et ralentir une requête. Si une seule condition doit être vérifiée, le vieux style de code xBase peut être utilisé :

SET ORDER TO MonIndex
SEEK Value
SCAN WHILE Champ=Values
_Exécute_quelque_chose
ENDSCAN

Dans bien des cas, c’est même plus rapide qu’une requête Rushmore optimisée car Visual FoxPro n’a pas à créer de bitmap. D’un autre coté, cette technique n’utilise pas le cache de la même manière que Rushmore qui accélère des requêtes répétées sur les mêmes données. Rushmore travaille beaucoup comme la boucle SCAN ci-dessus pour la mise à jour du bit à l’intérieur de cette boucle.

Comment cette boucle est elle effectivement créée? Le facteur principal est que les index dans Visual FoxPro sont stockés comme un B-tree, soit un arbre équilibré qui est composé d'un nombre identique de niveaux dans chaque branche. Chaque nœud est un bloc de 512 octets qui peut contenir jusqu’à 100 pointeurs de nœuds inférieurs. Le nœud le plus proche de la racine de réfère à la clé, seules des nœuds des feuilles correspondent aux enregistrements. Chaque noeud ne se référant pas uniquement à deux autres blocs, comme on pourrait le penser, la hierarchie dans le fichier index peut généralement se retrouver très aplatie. En outre, tous les nœuds sont reliés horizontalement.

Lorsque Visual FoxPro recherche une valeur, il traverse l’arbre verticalement jusqu’à trouver l’enregistrement, puis continue sa lecture horizontalement jusqu’à ce que la valeur de la recherche corresponde à celle de l’index. Cette stratégie d’analyse réduit le nombre de nœuds d’index à lire, mais accroit le nombre de noeuds à modifier lors de la mise à jour de l’index. Lors de la lecture horizontale, met à jour le bit correspondant à chaque enregistrement trouvé, ceci est possible car les entrées d’index contiennent tant les numéros d’enregistrements que les valeurs de clés. Les données étant toutefois stockées compressées. L’opérateur égal fonctionne de cette manière.

D’autres opérations agissent de manière similaire. Par exemple, si des enregistrements qui ne soient pas égaux doivent être trouvés, Visual FoxPro génère d’abord une image de tous les enregistrements, puis en élimine les enregistrements correspondant à l’égalité. De manière comparable pour une recherche sur une inégalité.
Avec Rushmore, Visual FoxPro peut déterminer quels enregistrements n’appartiennent pas au résultat, pas ceux qui en font partie. C’est pourquoi la phase « Rushmore » est suivie par une phase de post-scan. Chaque enrgistrment relevé par Rushmore est lu complétement depuis le disque. Sans une expression optimisée ce serait tous les enregistrements de toutes les tables concernées. Chacun de ces enregistrements est ensuite vérifié pour les conditions non optimisables. En outre, toutes les expressions optimisées sont évaluées à nouveau, un changement pouvant être intervenu depuis la création du bitmap. Un résultat pourrait ainsi ne pas contenir tous les enregistrements correspondant à la requète, mais jamais un enregistrement qui n’y correspondrait pas.

Il y a cependant une exception à cette règle. Pour compter des enregistrements, Visual FoxPro tente d’éviter la phase de post-scan. Lorsque le bitmap est construit et qu’il ne subsiste aucune condition non optimisée, Visual FoxPro commence à compter le résultat. De ce fait COUNT FOR et SELECT CNT(*) FROM sont extrémement rapides si la requète est totalement optimisée. Une optimisation partielle n’est pas suffisante. Il n’est pas non plus profitable d’utiliser d’autres méthodes telles SELECT SUM(1) FROM…
Lorsque de la création du bitmap Visual FoxPro doit lire tous les blocs d’index qui corespondent aux critères de recherche. Lors d’accès répétés Visual FoxPro récupère ces blocs du cache. Toutefois, le cache est ignoré si une station modifie un champ d’index où ajoute un nouvel enregistrement. Visual FoxPro peut seulement déterminer qu’une autre station a changé l’index, mais pas ce qui a exactement changé. Le cache entier est alors ignoré. Vous pouvez exploiter cela pour mesurer la performance. En utilisant une deuxième instance de FoxPro qui remplace un champ d’index dans le premier enregistrement dans une boucle.

Il y a quelque temps il fut constaté qu’un index sur DELETED() n’est pas toujours la solution optimale. Une sorte d’école apparu, condamnant complétement cet index, ce qui n’est pas non plus une bonne idée. Déterminer si Rushmore est la bonne voie est aisé : si plus d’octets sont lus dans le fichier index que d’enregistrements retirés pendant le post-scan, la performance de Rushmore décroit. Une comparaison des octets transférés doit être faite.

Il faut cependant garder en mémoire que le cache a un impact avec Rushmore et que les index CDX sont stockés compressés. Le commencement identique de mots n’est stocké qu’une fois. Le réél montant de données peut être déterminé avec le système de Monitoring de Windows, et de manière plus précise encore avec un moniteur réseau tel NETMON.EXE qui apparu avec Windows 2000 server, ou par Ethereal, disponible gratuitement chez http://www.ethereal.com. Un tel moniteur réseau révèle quelle partie d’un fichier est effectivement lue. Combinée avec la structure des fichiers, un grand nombre de détail peut en être déduit. Si de nombreuses données sont modifiées par une application, le cache est fréquement invalidé. Une telle application bénéficiera moins de Rushmore que, par exemple un catalogue sur CD qui aura placé en cache toutes les données après une courte utilisation.

Une application ayant de nombreux enregistrements annulés tirera aussi bénéfice de Rushmore. Si l’application visite un enregistrement plusieurs fois, l’algorithme requierant par exemple de naviguer vers l’enregistrement précédent ou suivant, Rushmore, par la réutilisation du bitmap, est supérieur aux anciens styles de code xBase qui doivent lire et relire les données.

Pour éviter de longues attentes aux utilisateurs lors des requètes, celles-ci doivent être pleinement optimisables, cela donne un réél avantage, car la création d’un bitmap est significativement plus rapide que l’entière lecture de la table, et le bitmap peut être réutilisé.
Un autre facteur important est la distribution des valeurs dans le fichier index. Il y a une différence considérable entre la recherche d’une valeur unique comme la recherche d’une clé primaire, où dans une donnée ne contenant qu’une dizaine de valeurs, comme un statut. Un exemple extrème en est l’index sur DELETED() pour lequel tous les champs ont généralement la même valeur. De tels index doivent généralement être évités sauf si leur besoin s’impose (pour des comptages par exemple).

Quelques liens remarqués sur Rushmore :

http://www.foxprohistory.org/rushmore.htm

http://support.microsoft.com/?scid=kb%3Ben-us%3B114781&x=10&y=9

http://my.advisor.com/articles.nsf/aid/18772!OpenDocument&Click=

http://bcook.cs.georgiasouthern.edu/cs575/rushmore.htm

http://fox.wikis.com/wc.dll?Wiki~VFP9RushmoreAndCodepage~VFP

http://f1technologies.blogspot.com/2006/01/vfp-gridoptimize-gotcha.html

http://wwwmsdner.com/dev-archive/38/17-60-382155.shtm