PostgreSQLLa base de données la plus sophistiquée au monde.
Documentation PostgreSQL 14.11 » Internes » Index B-Tree » Fonctions de support B-Tree

64.3. Fonctions de support B-Tree

Comme montré dans Tableau 38.9, btree définit une fonction de support obligatoire et quatre facultatives. Les cinq méthodes définies par l'utilisateur sont :

order

Pour chaque combinaison de types de données pour laquelle une famille d'opérateur btree fournit des opérateurs de comparaison, elle doit fournir une fonction de support de comparaison inscrite dans pg_amproc avec la fonction de support 1 et amproclefttype/amprocrighttype égaux aux types de données gauche et droit pour la comparaison (c'est-à-dire les même types de données que l'opérateur correspondant a inscrit dans pg_amop). La fonction de comparaison doit prendre en entrée deux valeurs non nulles A et B et retourner une valeur int32 qui est < 0, 0, ou > 0 quand, respectivement A < B, A = B, ou A > B. Une valeur de retour NULL est également interdite : toutes les valeurs du type de données doivent être comparables. Voir src/backend/access/nbtree/nbtcompare.c pour plus d'exemples.

Si les valeurs comparées sont d'un type avec collation, l'identifiant de collation approprié sera passé à la fonction de support de comparaison, en utilisant le mécanisme standard PG_GET_COLLATION().

sortsupport

De manière facultative, une famille d'opérateur btree peut fournir une ou plusieurs fonctions sort support, inscrites comme fonctions de support numéro 2. Ces fonctions permettent d'implémenter des comparaisons dans l'optique de tri de manière plus efficace qu'appeler naivement la fonction de support de comparaison. Les API impliquées pour cela sont définies dans src/include/utils/sortsupport.h.

in_range

De manière facultative, une famille d'opérateur btree peut fournir une ou plusieurs fonctions de support in_range inscrites comme fonction de support numéro 3. Celles-ci ne sont pas utilisées durant les opérations d'index btree ; mais plutôt, elles étendent les sémantiques de la famille d'opérateur de telle manière qu'elles puissent supporter les clauses de fenêtrage contenant les types de limite de cadre RANGE décalage PRECEDING et RANGE décalage FOLLOWING (voir Section 4.2.8). Fondamentalement, les informations supplémentaires fournies sont comment additionner et soustraire une valeur d'un décalage d'une manière qui est compatible avec le tri de données de la famille.

Une fonction in_range doit avoir la signature

in_range(val type1, base type1, offset type2, sub bool, less bool)
returns bool
      

val et base doivent être du même type, qui est un des types supportés par la famille d'opérateur (c'est-à-dire un type pour lequel elle fournit un tri). Cependant, offset peut être d'un type de données différent, qui peut par ailleurs ne pas être supporté par la famille. Un exemple est que la famille time_ops incluse par défaut fournit une fonction in_range qui a un offset de type interval. Une famille peut fournir des fonctions in_range pour n'importe lesquels des types de données qu'elle supporte, et un ou plusieurs types offset. Chaque fonction in_range devrait être inscrite dans pg_amproc avec amproclefttype égal à type1 et amprocrighttype égal à type2.

Les sémantiques essentielles pour une fonction in_range dépendent des deux paramètres de drapeau booléens. Elle devrait ajouter ou soustraire base et offset, puis comparer val au résultat, comme ceci :

  • si !sub et !less, renvoyer val >= (base + offset)

  • si !sub et less, renvoyer val <= (base + offset)

  • si sub et !less, renvoyer val >= (base - offset)

  • si sub et less, renvoyer val <= (base - offset)

Avant de procéder, la fonction devrait vérifier le signe d' offset : s'il est inférieur à zéro, lever l'erreur ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE (22013) avec un message d'erreur tel que « taille précédente ou suivante invalide dans la fonction de fenêtrage ». (Cela est requis par le standard SQL, bien que des familles d'opérateur non standards pourraient peut être choisir d'ignorer cette restriction, puisqu'il n'y a pas vraiment de nécessité de sémantique dans ce cas.) Cette exigence est déléguée à la fonction in_range si bien que le code du moteur n'a pas besoin de comprendre ce que « inférieur à zéro » signifie pour un type de données particulier.

Une autre attente est que les fonctions in_range devraient, si applicable, éviter de générer une erreur si base + offset ou base - offset devait causer un débordement. Le résultat de comparaison correct peut être déterminé même si cette valeur devait être en dehors de l'intervalle des valeurs du type de données. Notez que si le type de données inclut des concepts tels que « infinity » ou « NaN », des précautions supplémentaires pourraient être nécessaires pour s'assurer que les résultats de in_range soient en accord avec l'ordre de tri normal de la famille d'opérateur.

Les résultats de la fonction in_range doivent être cohérents avec l'ordre de tri imposé par la famille d'opérateur. Pour être précis, pour n'importe quelles valeurs fixées de offset et sub, alors :

  • Si in_range avec less = true est vrai pour certains val1 et base, il doit être vrai pour chaque val2 <= val1 avec le même base.

  • Si in_range avec less = true est faux pour certains val1 et base, il doit être faux pour chaque val2 >= val1 avec le même base.

  • Si in_range avec less = true est vrai pour certains val et base1, il doit être vrai pour chaque base2 >= base1 avec le même val.

  • Si in_range avec less = true est faux pour certains val et base1, il doit être faux pour chaque base2 <= base1 avec le même val.

Des déclarations similaires avec des conditions inversées continuent à s'appliquer quand less = false.

Si le type est trié (type1) par rapport à une collation, l'OID de collation approprié sera passé à la fonction in_range en utilisant le mécanisme standard PG_GET_COLLATION().

Les fonctions in_range n'ont pas besoin de gérer les valeurs en entrée NULL, et typiquement elles seront marquées comme strict.

equalimage

Une famille d'opérateurs btree facultative peut fournir les fonctions de support equalimage (« l'égalité implique une égalité d'image »), inscrites comme fonctions de support numéro 4. Ces fonctions permettent au code du moteur de déterminer quand il est sûr d'appliquer l'optimisation de dédoublonnage btree. Actuellement, les fonctions equalimage sont seulement appelées lors de la construction ou reconstruction d'un index.

Une fonction equalimage doit avoir comme signature

equalimage(opcintype oid) returns bool
      

La valeur retournée est une information statique relative à une classe d'opérateur et une collation. Retourner true indique que la fonction order pour la classe d'opérateur est garantie de retourner seulement 0 (« les arguments sont égaux ») quand ses arguments A et B sont aussi interchangeables sans aucune perte d'information sémantique. Ne pas inscrire une fonction equalimage ou retourner false indique que cette condition ne peut être tenue.

L'argument opcintype est le pg_type.oid du type de données que la classe d'opérateur indexe. Ceci est une commodité qui permet de réutiliser la même fonction equalimage sous-jacente entre plusieurs classes d'opérateurs. Si opcintype est un type de données collationné, l'identifiant de collation appropriée sera passé à la fonction equalimage, par le mécanisme standard PG_GET_COLLATION().

Tant que la classe d'opérateur est concernée, retourner true indique que le dédoublement est sûr (ou sûr pour la collation dont l'identifiant a été passé à sa fonction equalimage). Cependant, le code du moteur considérera le dédoublonnage sécurisé pour un index, si chaque colonne indexée utilise une classe d'opérateur ayant inscrit une fonction equalimage, et si chaque fonction retourne true par appel.

L'égalité d'image est presque la même condition qu'une simple égalité bit à bit. Il n'y a qu'une seule et subtile différence : en indexant un type de données « varlena », la représentation sur disque de deux images de données égales peuvent ne pas être identiques bit à bit, à cause des incohérences lors de l'application de la compression TOAST sur les données en entrée. Dans les règles, quand une fonction equalimage d'une classe d'opérateur retourne true, on peut présumer sans se tromper que la fonction C datum_image_eq() correspondra avec la fonction order de la classe d'opérateur (sous réserve que le même identifiant de collation soit passé aux fonctions equalimage et order).

Le code du moteur est fondamentalement incapable de déduire quoi que ce soit au sujet du statut « l'égalité implique l'égalité d'image » d'une classe d'opérateur incluse dans une famille de types de données multiples en se basant sur les détails d'autres classes d'opérateur de la même famille. Aussi, il n'est pas pertinent pour une famille d'opérateurs d'inscrire une fonction equalimage inter-type, et essayer déclenchera une error. En effet, le statut de « l'égalité implique l'égalité d'image » ne dépend pas juste de la sémantique de l'ordre/égalité, qui est plus ou moins définie au niveau de la famille d'opérateur. En général, les sémantiques d'un type particulier de données doivent être considérées séparément.

La convention suivie par les classes d'opérateur incluses avec la distribution principale PostgreSQL est d'inscrire une fonction générique equalimage. La plupart des classes d'opérateur inscrivent btequalimage(), qui indique que le dédoublonnage est sécurisé sans conditions. Les classes d'opérateur pour les types de données collationnés comme text inscrivent btvarstrequalimage(), qui indique que le dédoublonnage est sécurisé avec les collations déterministes. La bonne pratique pour une extension tierce est d'inscrire leur propre fonction personnalisée pour garder le contrôle.

options

En option, une famille d'opérateur B-tree peut fournir des fonctions de support des options (« options spécifiques à la classe d'opérateur »), enregistrées sous le numéro 5 des fonctions de support. Ces fonctions définissent un ensemble de paramètres visibles à l'utilisateur et contrôlant le comportement de la classe d'opérateur.

Une fonction de support options doit avoir cette signature 

options(relopts local_relopts *) returns void
      

La fonction se voit fournie un pointeur vers une structure local_relopts qui doit être remplie avec un ensemble d'options spécifiques à une classe d'opérateur. Les options sont accessibles à partir des autres fonctions de support en utilisant les macros PG_HAS_OPCLASS_OPTIONS() et PG_GET_OPCLASS_OPTIONS().

Actuellement, aucune classe d'opérateur B-Tree n'a de fonction de support options. B-tree n'autorise pas une représentation flexible des clés comme GiST, SP-GiST, GIN et BRIN le font. Donc, options n'a probablement pas beaucoup d'intérêt pour la méthode d'accès aux index B-tree actuellement. Néanmoins, cette fonction de support a été ajouté au B-tree par cohérence, et trouvera probablement son utilité lors des prochaines évolutions du B-tree dans PostgreSQL.