33.13. Interfacer des extensions d'index

33.13.1. Méthodes d'indexage et classes d'opérateurs

La table pg_am contient une ligne pour chaque méthode d'indexage (connue en interne comme méthode d'accès). Le support pour l'accès normal aux tables est implémenté dans PostgreSQL mais toutes les méthodes d'index sont décrites dans pg_am. Il est possible d'ajouter une nouvelle méthode d'indexage en définissant les routines d'interface nécessaires et en créant ensuite une ligne dans la table pg_am --- mais ceci est bien au-delà du sujet de ce chapitre.

Les routines pour une méthode d'indexage n'ont pas à connaître directement les types de données sur lesquels opère la méthode d'indexage. Au lieu de cela, une classe d'opérateur identifie l'ensemble d'opérations que la méthode d'indexage doit utiliser pour fonctionner avec un type particulier de données. Les classes d'opérateurs sont ainsi dénommées parce qu'une de leur tâche est de spécifier l'ensemble des opérateurs de la clause WHERE utilisables avec un index (c'est-à-dire, qui peuvent être requalifiés en balayage d'index). Une classe d'opérateur peut également spécifier des procédures d'appui, nécessaires pour les opérations internes de la méthode d'indexage mais sans correspondance directe avec un quelconque opérateur de clause WHERE pouvant être utilisé avec l'index.

Il est possible de définir plusieurs classes d'opérateurs pour le même type de données et la même méthode d'indexage. Ainsi, de multiples ensembles de sémantiques d'indexation peuvent être définis pour un seul type de données. Par exemple, un index B-tree exige qu'un tri ordonné soit défini pour chaque type de données auquel il peut s'appliquer. Il peut être utile pour un type de donnée de nombre complexe de disposer d'une classe d'opérateur B-tree qui trie les données selon la valeur absolue complexe, une autre selon la partie réelle, etc. Typiquement, une des classes d'opérateur sera considérée comme plus utile et sera marquée comme l'opérateur par défaut pour ce type de données et cette méthode d'indexage.

Le même nom de classe d'opérateur peut être utilisé pour plusieurs méthodes d'indexage différentes (par exemple, les méthodes d'index B-tree et hash ont toutes les deux des classes d'opérateur nommées oid_ops) mais chacune de ces classes est une entité indépendante et doit être définie séparément.

33.13.2. Stratégies des méthode d'indexage

Les opérateurs associés à une classe d'opérateur sont identifiés par des << numéros de stratégie >>, servant à identifier la sémantique de chaque opérateur dans le contexte de sa classe d'opérateur. Par exemple, les B-trees imposent un classement strict selon les clés, du plus petit au plus grand. Ainsi, des opérateurs comme << plus petit que >> et << plus grand que >> sont intéressants pour un B-tree. Comme PostgreSQL permet à l'utilisateur de définir des opérateurs, PostgreSQL ne peut pas rechercher le nom d'un opérateur (par exemple, < ou >=) et rapporter de quelle comparaison il s'agit. Au lieu de cela, la méthode d'indexage définit un ensemble de << stratégies >>, qui peuvent être comprises comme des opérateurs généralisés. Chaque classe d'opérateur spécifie l'opérateur effectif correspondant à chaque stratégie pour un type de donnée particulier et pour une interprétation de la sémantique d'index.

La méthode d'indexage B-tree définit cinq stratégies, exposées dans le Tableau 33-2.

Les index de découpage expriment seulement une égalité bit à bit et utilisent ainsi une seule stratégie exposée dans le Tableau 33-3.

Les index R-tree expriment des relations d'appartenance à un rectangle. Ils utilisent huit stratégies, exposées dans le Tableau 33-4.

Les index GiST sont encore plus flexibles : ils n'ont pas du tout d'ensemble fixe de stratégies. En lieu et place, la routine d'appui de cohérence de chaque classe d'opérateur GiST particulière interprète les numéros de stratégie comme elle l'entend.

Notez que tous les opérateurs de stratégie renvoient des valeurs de type booléen. Dans la pratique, tous les opérateurs définis comme stratégies de méthode d'indexage doivent renvoyer un type boolean puisqu'ils doivent apparaître au plus haut niveau d'une clause WHERE pour être utilisés avec un index.

En fait, la colonne amorderstrategy dans pg_am indique si la méthode d'indexage supporte les balayages ordonnés. Zéro indique qu'elle ne les supporte pas ; si elle les supporte, amorderstrategy est le numéro de stratégie qui correspond à l'opérateur de classement. Par exemple, B-tree a amorderstrategy = 1, qui est son numéro de stratégie pour << plus petit que >>.

33.13.3. Routines d'appui des méthodes d'indexage

Généralement, les stratégies n'apportent pas assez d'informations au système pour indiquer comment utiliser un index. Dans la pratique, les méthodes d'indexage demandent des routines d'appui additionnelles pour fonctionner. Par exemple, les méthodes d'index B-tree doivent être capables de comparer deux clés et de déterminer laquelle est supérieure, égale ou inférieure à l'autre. De la même façon, la méthode d'indexage R-tree doit être capable de calculer les intersections, unions et dimensions des rectangles. Ces opérations ne correspondent pas à des opérateurs utilisés dans les commandes SQL ; ce sont des routines administratives utilisées en interne par des méthodes d'index.

Tout comme les stratégies, la classe d'opérateur reconnaît les fonctions spécifiques avec lesquelles elle doit jouer chacun de ces rôles pour un type de donnée et une interprétation sémantique. La méthode d'indexage définit l'ensemble des fonctions dont elle a besoin et la classe d'opérateur identifie les fonctions correctes à utiliser en les assignant aux << numéros de fonction d'appui >>.

Les B-trees demandent une seule fonction d'appui, exposée dans le Tableau 33-5.

De façon identique, les index de découpage requièrent une fonction d'appui exposée dans le Tableau 33-6.

Les index R-tree requièrent trois fonctions d'appui exposées dans le Tableau 33-7.

Les index GiST requièrent sept fonctions d'appui exposées dans le Tableau 33-8.

Contrairement aux opérateurs de stratégie, les fonctions d'appui renvoient le type de donnée, quelqu'il soit, que la méthode d'indexage particulière attend, par exemple, dans le cas de la fonction de comparaison des B-trees, un entier signé.

33.13.4. Exemple

Maintenant que nous avons vu les idées, voici l'exemple promis de création d'une nouvelle classe d'opérateur. Cette classe d'opérateur encapsule les opérateurs qui trient les nombres complexes selon l'ordre de la valeur absolue, aussi avons-nous choisi le nom de complex_abs_ops. En premier lieu, nous avons besoin d'un ensemble d'opérateurs. La procédure pour définir des opérateurs a été discutée dans la Section 33.11. Pour une classe d'opérateur sur les B-trees, nous avons besoin des opérateurs :

• valeur absolue less-than (stratégie 1) ;
• valeur absolue less-than-or-equal (stratégie 2) ;
• valeur absolue equal (stratégie 3) ;
• valeur absolue greater-than-or-equal (stratégie 4) ;
• valeur absolue greater-than (stratégie 5) ;

Le code C de l'opérateur d'égalité ressemble à ceci :

#define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)

bool
complex_abs_eq(Complex *a, Complex *b)
{
    double amag = Mag(a), bmag = Mag(b);
    return (amag == bmag);
}

Les quatre autres opérateurs sont très similaires. Vous pouvez trouver leur code dans src/tutorial/complex.c et src/tutorial/complex.sql dans la distribution des sources.

Maintenant, déclarons les fonctions et les opérateurs basés sur ces fonctions :

CREATE FUNCTION complex_abs_eq(complex, complex) RETURNS boolean
    AS 'nom_fichier', 'complex_abs_eq'
    LANGUAGE C;

CREATE OPERATOR = (
    leftarg = complex,
    rightarg = complex,
    procedure = complex_abs_eq,
    restrict = eqsel,
    join = eqjoinsel
);

Il est important de spécifier les fonctions de sélectivité de restriction et de jointure, sinon l'optimiseur sera incapable de faire un usage effectif de l'index. Notez que les cas 'less-than', 'equal' et 'greater-than' doivent utiliser des fonctions différentes de sélectivité.

Voici d'autres choses importantes à noter :

• Il ne peut y avoir qu'un seul opérateur nommé, disons, = et acceptant un type complex pour ses deux opérandes. Dans le cas présent, nous n'avons aucun autre opérateur = pour complex mais, si nous construisons un type de donnée fonctionnel, nous aurions certainement désiré que = soit l'opération ordinaire d'égalité pour les nombres complexes (et non pour l'égalité de leurs valeurs absolues). Dans ce cas, nous aurions eu besoin d'utiliser un autre nom d'opérateur pour notre fonction complex_abs_eq.

• Bien que PostgreSQL puisse se débrouiller avec des fonctions ayant le même nom, tant qu'elles ont en argument des types de données différents, C peut seulement faire face à une fonction globale ayant un nom donné. Aussi ne devons-nous pas donner un nom simple comme abs_eq. Habituellement, c'est une bonne habitude d'inclure le nom du type de données dans le nom de la fonction C, pour ne pas provoquer de conflit avec des fonctions pour d'autres types de donnée.

• Nous aurions pu faire de abs_eq le nom PostgreSQL de la fonction, en laissant à PostgreSQL le soin de la distinguer de toute autre fonction PostgreSQL de même nom par les types de données en argument. Pour la simplicité de l'exemple, nous donnerons à la fonction le même nom au niveau de C et au niveau de PostgreSQL.

La prochaine étape est l'enregistrement de la routine d'appui nécessaire pour les B-trees. Le code exemple C qui implémente ceci est dans le même fichier qui contient les fonctions d'opérateur. Voici comment déclarer la fonction :

CREATE FUNCTION complex_abs_cmp(complex, complex)
    RETURNS integer
    AS 'filename'
    LANGUAGE C;

Maintenant que nous avons les opérateurs requis et la routine d'appui, nous pouvons enfin créer la classe d'opérateur.

CREATE OPERATOR CLASS complex_abs_ops
    DEFAULT FOR TYPE complex USING btree AS
        OPERATOR        1       < ,
        OPERATOR        2       <= ,
        OPERATOR        3       = ,
        OPERATOR        4       >= ,
        OPERATOR        5       > ,
        FUNCTION        1       complex_abs_cmp(complex, complex);

Et c'est fait ! Il devrait être possible maintenant de créer et d'utiliser les index B-tree sur les colonnes complex.

Nous aurions pu écrire les entrées de l'opérateur de façon plus explicite comme dans

        OPERATOR        1       < (complex, complex) ,

mais il n'y a pas besoin de faire ainsi quand les opérateurs prennent le même type de donnée que celui pour lequel la classe d'opérateur a été définie.

Les exemples ci-dessus supposent que vous voulez que cette nouvelle classe d'opérateur soit la classe d'opérateur B-tree par défaut pour le type de donnée complex. Si vous ne voulez pas, supprimez simplement le mot DEFAULT.

33.13.5. Dépendance du système pour les classes d'opérateur

PostgreSQL utilise les classe d'opérateur pour inférer les propriétés des opérateurs de plusieurs autres façons que le seul usage avec les index. Donc, vous pouvez créer des classes d'opérateur même si vous n'avez pas l'intention d'indexer une quelconque colonne de votre type de donnée.

En particulier, il existe des caractéristiques de SQL telles que ORDER BY et DISTINCT qui requièrent la comparaison et le tri des valeurs. Pour implémenter ces caractéristiques sur un type de donnée défini par l'utilisateur, PostgreSQL recherche la classe d'opérateur B-tree par défaut pour le type de donnée. Le membre << equals >> de cette classe d'opérateur définit pour le système la notion d'égalité des valeurs pour GROUP BY et DISTINCT, et le tri ordonné imposé par la classe d'opérateur définit le ORDER BY par défaut.

La comparaison des tableaux de types définis par l'utilisateur repose sur les sémantiques définies par la classe d'opérateur B-tree par défaut.

S'il n'y a pas de classe d'opérateur B-tree par défaut pour le type de donnée, le système cherchera une classe d'opérateur de découpage. Mais puisque cette classe d'opérateur ne fournit que l'égalité, c'est en pratique seulement suffisant pour établir l'égalité de tableau.

Quand il n'y a pas de classe d'opérateur par défaut pour un type de donnée, vous obtenez des erreurs telles que << could not identify an ordering operator >> si vous essayez d'utiliser ces caractéristiques SQL avec le type de donnée.

33.13.6. Caractéristiques spéciales des classes d'opérateur

Il y a deux caractéristiques spéciales des classes d'opérateur dont nous n'avons pas encore parlées, essentiellement parce qu'elles ne sont pas utiles avec les méthodes d'index les plus communément utilisées.

Normalement, déclarer un opérateur comme membre d'une classe d'opérateur signifie que la méthode d'indexage peut retrouver exactement l'ensemble de lignes qui satisfait la condition WHERE utilisant cet opérateur. Par exemple,

SELECT * FROM table WHERE colonne_entier < 4;

peut être accompli exactement par un index B-tree sur la colonne entière. Mais il y a des cas où un index est utile comme un guide inexact vers la colonne correspondante. Par exemple, si un index R-tree enregistre seulement les rectangles limite des objets, alors il ne peut pas exactement satisfaire une condition WHERE qui teste le chevauchement entre des objets non rectangulaires comme des polygones. Cependant, nous pourrions utiliser l'index pour trouver des objets dont les rectangles limites chevauchent les limites de l'objet cible. Dans ce cas, l'index est dit être à perte pour l'opérateur, et nous ajoutons RECHECK à la clause OPERATOR dans la commande CREATE OPERATOR CLASS. RECHECK est valide si l'index garantie de retourner toutes les lignes requises, plus peut-être des lignes supplémentaires pouvant être éliminées par le recours à l'opérateur original.

Considérons à nouveau la situation où nous gardons seulement dans l'index le rectangle délimitant un objet complexe comme un polygone. Dans ce cas, il n'est pas très intéressant de conserver le polygone entier dans l'index - nous pouvons aussi bien conserver seulement un objet simple du type box. Cette situation est exprimée par l'option STORAGE dans la commande CREATE OPERATOR CLASS : nous aurons à écrire quelque chose comme

CREATE OPERATOR CLASS polygon_ops
    DEFAULT FOR TYPE polygon USING gist AS
        ...
        STORAGE box;

Actuellement, seule la méthode d'indexage GiST supporte un type STORAGE qui soit différent du type de donnée de la colonne. Les routines d'appui de GiST compress et decompress doivent s'occuper de la conversion du type de donnée quand STORAGE est utilisé.