Requêtes rapides de correspondance de modèles dans PostgreSQL et YugabyteDB

Ce didacticiel montre comment optimiser les requêtes de correspondance de modèles dans PostgreSQL et YugabyteDB en appliquant plusieurs stratégies d’indexation. Étant donné que YugabyteDB est construit sur le code source PostgreSQL, les stratégies fonctionnent à la fois pour les déploiements PostgreSQL à serveur unique et les clusters YugabyteDB multi-nœuds.

Chargement des exemples de données

Commençons par construire un exemple. Supposons que vous disposiez d’une table qui stocke les profils d’utilisateurs. L’une des colonnes est le prénom de l’utilisateur. Ensuite, recherchons tous les utilisateurs dont le nom commence par An et est une longueur arbitraire. Pour cela, nous pouvons utiliser une requête de correspondance de modèle comme WHERE firstname LIKE ‘An%’.

Commençons par créer un tableau avec des exemples de données.

1. Commencez par vous connecter à votre instance PostgreSQL ou YugabyteDB en utilisant votre méthode préférée. En option, vous pouvez le faire dans Docker en une minute.

2. Créez une table qui stockera les noms et la fréquence à laquelle un nom a été utilisé pour les nouveau-nés :

create table firstname (
  name text, 
  frequency int
);

3. Téléchargez des exemples de données à partir d’ici avec plus de 32 000 prénoms.

4. Chargez les exemples de données dans la table :

\copy firstname FROM '{path_to_file}/us_first_names.csv' csv header;

Si vous recherchez tous les noms commençant par Anles bases de données effectueront une analyse complète de la table de plus de 32 000 enregistrements et renverront 665 enregistrements répondant aux critères de recherche :

explain analyze select name, frequency from firstname where name like 'An%';

 Seq Scan on firstname  (rows=665 loops=1)
    Filter: (name ~~ 'An%'::text)
   Rows Removed by Filter: 32287

Remarque : tous les plans d’exécution sont raccourcis pour plus de clarté et fournis uniquement pour PostgreSQL. Les plans d’exécution de YugabyteDB peuvent apparaître ou être formatés différemment car son moteur de stockage est distribué et utilise l’arbre LSM au lieu de l’arbre B (utilisé dans PostgreSQL).

L’analyse complète de la table ne semble plus être un problème maintenant. Mais imaginez que de nouveaux utilisateurs continuent de s’inscrire à votre service, rendant la table de plus en plus grande.

Donc, vous avez maintenant des milliers d’utilisateurs, mais dans trois mois, vous pourriez avoir des dizaines de milliers de clients actifs. En un an ou deux, le nombre peut croître de façon exponentielle. Pour que la latence de la requête de correspondance de modèle précédente reste prévisible et faible, quel que soit le volume de données, vous devez utiliser un index de base de données approprié.

Rechercher avec l’index par défaut

Essayons d’améliorer la recherche en créant un index avec des paramètres par défaut pour le firstname colonne:

1. Créez l’index et mettez à jour les statistiques pour PostgreSQL. YugabyteDB n’a pas (et n’a pas besoin) du vacuum analyze tant que son stockage distribué fonctionne différemment :

create index name_idx on firstname(name);
vacuum analyze; /* PostgreSQL only. */

2. Confirmez que l’index est sélectionné pour une requête simple à l’aide de l’opérateur d’égalité :

explain analyze select name, frequency from firstname where name like 'Andrew';

 Index Scan using name_idx on firstname  (rows=2 loops=1)
    Index Cond: (name="Andrew"::text)
   Filter: (name ~~ 'Andrew'::text)

3. Enfin, recherchez les noms commençant par An:

explain analyze select name, frequency from firstname where name like 'An%';

Seq Scan on firstname  (rows=665 loops=1)
   Filter: (name ~~ 'An%'::text)
   Rows Removed by Filter: 32287

Comme le montre le plan d’exécution final, la solution actuelle n’a pas réussi à utiliser l’index sur mon ordinateur portable macOS. Il est fort probable que l’index créé ne sera pas également utilisé sur votre machine. Voyons pourquoi.

Rechercher avec le classement « C »

PostgreSQL et YugabyteDB s’appuient sur les classements pour l’indexation des types de données de chaîne de caractères. Un classement est un ensemble de règles qui définissent comment comparer et trier des chaînes de caractères (reportez-vous à cet article ou à cette vidéo pour plus de détails sur le sujet).

Parlons d’abord de PostgreSQL. Par défaut, PostgreSQL utilise les règles de classement spécifiques aux paramètres régionaux de votre système d’exploitation. Habituellement, ces règles ne fonctionnent pas pour les requêtes impliquant les opérateurs LIKE ou similaires. Ma collation par défaut sur PostgreSQL est en_US.utf8et il n’est pas adapté aux requêtes de correspondance de modèle :

show lc_collate;

 lc_collate
------------
 en_US.utf8

Une solution suggérée consiste à utiliser le classement « C » qui trie et compare les chaînes de caractères strictement octet par octet. Vous pouvez spécifier ce classement pour l’ensemble de la base de données, au niveau de chaque colonne ou lors de la création d’un index. Utilisons-le pour l’index dans PostgreSQL :

1. Supprimez l’index actuel avec la classe d’opérateur par défaut :

2. Créez un nouvel index en utilisant le classement « C »:

create index name_idx on firstname(name collate "C");
vacuum analyze;

3. Recherchez tous les noms commençant par An:

explain analyze select name, frequency from firstname where name like 'An%';

 Bitmap Heap Scan on firstname  (rows=665 loops=1)
   Filter: (name ~~ 'An%'::text)
   Heap Blocks: exact=88
   ->  Bitmap Index Scan on name_idx (665 loops=1)
         Index Cond: ((name >= 'An'::text) AND (name < 'Ao'::text))

Succès! PostgreSQL a utilisé l’index et a trouvé les 665 noms qui satisfont le modèle de recherche.

Dans YugabyteDB, la situation est différente. YugabyteDB utilise déjà le classement « C » par défaut, il n’y a donc rien à changer ici :

show lc_collate;
 lc_collate
------------
 C
(1 row)

Cependant, l’index a été créé à l’aide de l’algorithme HASH qui n’est pas adapté aux requêtes de correspondance de modèles :

\d+ firstname;
                                   Table "public.firstname"
  Column   |  Type   | Collation | Nullable | Default | Storage  | Stats target | Description
-----------+---------+-----------+----------+---------+----------+--------------+-------------
 name      | text    |           |          |         | extended |              |
 frequency | integer |           |          |         | plain    |              |

Indexes:
    "name_idx" lsm (name HASH)

Pour obtenir l’index sélectionné pour les requêtes de correspondance de modèle dans YugabyteDB, nous devons créer l’index de plage :

1. Supprimez l’index actuel :

2. Créez un nouvel index en spécifiant l’opérateur ASC (ordre croissant). L’opérateur permet l’indexation par plage des données :

create index name_idx on firstname(name ASC);

3. Répétez la recherche de correspondance de modèle précédente :

explain analyze select name, frequency from firstname where name like 'An%';

 Index Scan using name_idx on firstname  (rows=665 loops=1)
 	Index Cond: ((name >= 'An'::text) AND (name < 'Ao'::text))
 Filter: (name ~~ 'An%'::text)

Travail terminé! Maintenant, notre requête de correspondance de modèle utilise l’index dans PostgreSQL et YugabyteDB.

Une chose à garder à l’esprit qui s’applique aux deux bases de données : l’accès à l’index n’est utilisé que pour les caractères précédant le premier caractère générique. Les caractères qui suivent le caractère générique seront utilisés pour un filtrage séquentiel supplémentaire sur un ensemble de résultats préparé pendant le parcours de l’index.

Par exemple, supposons que vous souhaitiez rechercher tous les noms commençant par An et terminer par a:

explain analyze select name, frequency from firstname where name like 'An%a';
 
Bitmap Heap Scan on firstname  (rows=220 loops=1)
   Filter: (name ~~ 'An%a'::text)
   Rows Removed by Filter: 445
   Heap Blocks: exact=85
   ->  Bitmap Index Scan on name_idx  (rows=665 loops=1)
         Index Cond: ((name ~>=~ 'An'::text) AND (name ~<~ 'Ao'::text))

L’index est utilisé pour les caractères avant le joker – voir la ligne Index Cond: ((name ~>=~ 'An'::text) AND (name ~<~ 'Ao'::text))
Ensuite, le jeu de résultats préparé sera filtré séquentiellement – voir la ligne Filter: (name ~~ 'An%a'::text)

Remarque sur l’opérateur pattern_ops

Une note rapide sur la classe d’opérateur text_pattern_ops (ou varchar_pattern_ops) qui est toujours suggéré par de nombreuses ressources Internet comme solution incontournable pour les requêtes de correspondance de modèles dans PostgreSQL.

Cette classe d’opérateur peut également être utilisée pour des recherches rapides via l’index :

1. Créez un nouvel index en spécifiant text_pattern_ops class:

/* In PostgreSQL */
create index name_idx on firstname(name text_pattern_ops);
vacuum analyze;


/*In YugabyteDB */
create index name_idx on firstname(name text_pattern_ops ASC);

2. Exécutez la requête avec le LIKE opérateur:

explain analyze select name, frequency from firstname where name like 'An%';

 Bitmap Heap Scan on firstname  (rows=665 loops=1)
   Filter: (name ~~ 'An%'::text)
   Heap Blocks: exact=85
   ->  Bitmap Index Scan on name_idx  (rows=665 loops=1)
         Index Cond: ((name ~>=~ 'An'::text) AND (name ~<~ 'Ao'::text))

Comme vous le voyez, le text_pattern_ops fonctionne, mais beaucoup le considèrent comme une solution héritée. Une limitation est que cette classe d’opérateur ne prend pas en charge les requêtes impliquant des <, <=, >ou alors >= comparaisons. Vous pouvez en savoir plus sur le sujet ici.

Recherche insensible à la casse

Que se passe-t-il si vous devez effectuer une recherche insensible à la casse à l’aide de l’opérateur ILIKE ou d’une autre méthode ? Ensuite, la solution discutée précédemment utilisant le classement « C » (ainsi que le text_pattern_ops class) ne suffira pas.

Comme précédemment, recherchons tous les noms commençant par An (ou alors an, AN, aN) en utilisant l’opérateur ILIKE insensible à la casse :

explain analyze select name, frequency from firstname where name ilike 'an%';

Seq Scan on firstname (rows=665 loops=1)
   Filter: (name ~~* 'an%'::text)
   Rows Removed by Filter: 32287

La requête renvoie le même prénom 665 mais n’a pas utilisé l’index existant. Il existe plusieurs solutions qui prennent en charge les recherches d’index insensibles à la casse. L’un d’eux est constitué de trigrammes qui sont soutenus par des index GiST ou GIN.

PostgreSQL (et intrinsèquement YugabyteDB) prend en charge les recherches basées sur les trigrammes via l’extension pg_trgm. Installons-le et utilisons l’extension pour les requêtes de correspondance de modèle insensibles à la casse :