Cet article est publié sous licence CC BY-NC-SA
Voici la situation : il arrive régulièrement d’avoir à filtrer des informations en base de données dans le but, par exemple, de restreindre une liste quelconque en fonction de certains critères. Cela peut être une liste de pays à présenter dans un formulaire d’inscription, ou encore le listing des utilisateurs de notre application prénommés Pierre.
Prenons ce dernier exemple comme base de réflexion. Et pour nous mettre en
conditions réelles, admettons que notre table se nomme users
et contienne
855118 entrées.
SELECT COUNT(*) FROM users;
-- +---------+
-- | count |
-- |---------|
-- | 855118 |
-- +---------+
En SQL, pour récupérer la liste des utilisateurs prénommés Pierre, nous ferions quelque chose comme ça :
SELECT * FROM users WHERE first_name = 'pierre';
-- +--------+--------------+-------------+
-- | id | first_name | last_name |
-- |--------+--------------+-------------|
-- | 360054 | pierre | TBQRG |
-- | 520379 | pierre | ebffv |
-- | 753433 | pierre | ynonyrggr |
-- | 800251 | pierre | pnggvnh |
-- +--------+--------------+-------------+
-- SELECT 4
-- Time: 0.176s
Afin d’avoir un élément de comparaison pour les exemples à venir, voici le
résultat de l’exécution de cette requête avec pgbench
. Dans toutes les
utilisations que je ferai de pgbench
au sein de cet article, la requête sera
exécutée en boucle durant 1 minute, sur 4 threads et par 10 clients.
pgbench duration: 60 s
number of transactions actually processed: 1544
latency average = 390.442 ms
tps = 25.612023 (including connections establishing)
tps = 25.613680 (excluding connections establishing)
La ligne qui nous intéresse ici est la seconde. Elle comptabilise le nombre de transactions effectivement réalisées, soit le nombre de fois où notre requête a pu être exécutée. Ici il y en a eu 1544.
Soit, mais nous ne récupérons que les utilisateurs dont le prénom est exactement « pierre ». Voyons pour récupérer les « Jean Pierre » et autres « Pierre-Yves ».
SELECT * FROM users WHERE first_name LIKE '%pierre%';
-- +--------+-----------------+-------------+
-- | id | first_name | last_name |
-- |--------+-----------------+-------------|
-- | 94318 | pierrette | Wryzbav |
-- | 102431 | Marie pierre | ZRHAVRE |
-- | 156805 | jean pierre | treyrf |
-- | 170391 | pierre philippe | ORFNAPBA |
-- | 342009 | marie pierre | Tbheerg |
-- ⋮ ⋮ ⋮ ⋮
-- | 360054 | pierre | TBQRG |
-- | 520379 | pierre | ebffv |
-- | 718678 | jean pierre | tenatnhq |
-- | 753433 | pierre | ynonyrggr |
-- | 800251 | pierre | pnggvnh |
-- +--------+-----------------+-------------+
-- SELECT 21
-- Time: 0.172s
pgbench duration: 60 s
number of transactions actually processed: 1266
latency average = 476.531 ms
tps = 20.984975 (including connections establishing)
tps = 20.986500 (excluding connections establishing)
Un peu mieux, mais pas suffisant. En effet, cette recherche est sensible à la
casse et ne fera donc ressortir ni PIERRE
ni Jean-Pierre
. Tâchons d’être
plus souples.
SELECT * FROM users WHERE first_name ILIKE '%pierre%';
-- +--------+--------------+-------------+
-- | id | first_name | last_name |
-- |--------+--------------+-------------|
-- | 94318 | pierrette | Wryzbav |
-- | 10908 | JEAN PIERRE | OENPPVAV |
-- | 10910 | PIERRETTE | SYNAQER |
-- | 102431 | Marie pierre | ZRHAVRE |
-- | 11523 | PIERRE-MARIE | TRENAQV |
-- | 11877 | PIERRE | WNPDHRF |
-- | 12193 | JEAN-PIERRE | PHIRYVRE |
-- | 156805 | jean pierre | treyrf |
-- ⋮ ⋮ ⋮ ⋮
-- | 360054 | pierre | TBQRG |
-- | 12646 | PIERRETTE | YRMVA |
-- | 342009 | marie pierre | Tbheerg |
-- | 13003 | JEAN-PIERRE | ORENATRE. |
-- | 13300 | MARIE PIERRE | ZBAVR |
-- | 13404 | PIERRE | ONONHQ |
-- +--------+--------------+-------------+
-- SELECT 5887
-- Time: 0.591s
pgbench duration: 60 s
number of transactions actually processed: 290
latency average = 2112.792 ms
tps = 4.733073 (including connections establishing)
tps = 4.733406 (excluding connections establishing)
Voilà un résultat qui semble plus plausible. Nous pouvons dès à présent noter
que le temps de requêtage va croissant au fur et à mesure que nous
assouplissons notre recherche. ILIKE
notamment a un impact fort sur le temps
de requêtage et mieux vaut s’en passer lorsque cela nous est possible.
Une possibilité que nous offre PostgreSQL est l’utilisation de fonctions. En ce
qui nous concerne, il s’agit de la fonction lower()
. Ainsi nous pouvons
écrire :
SELECT * FROM users WHERE lower(first_name) LIKE '%pierre%';
-- SELECT 5887
-- Time: 0.421s
pgbench duration: 60 s
number of transactions actually processed: 439
latency average = 1387.854 ms
tps = 7.205370 (including connections establishing)
tps = 7.205896 (excluding connections establishing)
Bien évidemment, si nous avions pu nous contenter d’une simple égalité au lieu
du LIKE
, le requêtage en aurait été grandement accéléré.
Tout ceci est très bien, mais encore loin d’être suffisant ! En effet, quid des « Pierre André » et autres « Pierre François » ? Vous l’aurez compris, il s’agit ici de prendre en compte les diacritiques.
Pour simplifier l’exemple, tâchons de retrouver tous les « François », qu’ils soient enregistrés en base avec ou sans la cédille.
Pour ce faire, PostgreSQL met à notre disposition la fonction unaccent()
à
travers l’extension éponyme. Il nous faut donc tout d’abord activer cette
extension.
Voici la requête SQL activant l’extension unaccent
.
CREATE EXTENSION IF NOT EXISTS unaccent;
Ou si vous êtes au sein d’un projet Rails, voici la migration appropriée.
class EnableUnaccentExtension < ActiveRecord::Migration[5.0]
def change
enable_extension 'unaccent'
end
end
Ainsi, nous avons désormais la possibilité de rechercher tous les « François », diacritiques ou pas.
SELECT * FROM users WHERE lower(first_name) LIKE '%francois%';
-- SELECT 16742
-- Time: 0.432ms
SELECT * FROM users WHERE unaccent(lower(first_name)) LIKE '%francois%';
-- SELECT 16939
-- Time: 0.938ms
pgbench duration: 60 s
number of transactions actually processed: 200
latency average = 3142.569 ms
tps = 3.182110 (including connections establishing)
tps = 3.182339 (excluding connections establishing)
Parfait ! Nous gérons à présent tous les cas et ne laissons de côté aucun de nos utilisateurs, qu’ils aient renseigné leur nom avec ou sans majuscule ou qu’ils aient un prénom slave comme « Mikuláš » ou « Alžběta ».
À noter que depuis PostgreSQL 9.6, l’extension unaccent
supporte correctement
les ligatures !
-- PostgreSQL 9.5
SELECT unaccent('Œ Æ œ æ ß');
-- +-----------+
-- | unaccent |
-- |-----------|
-- | E A e a S |
-- +-----------+
-- PostgreSQL 9.6
SELECT unaccent('Œ Æ œ æ ß');
-- +----------------+
-- | unaccent |
-- |----------------|
-- | OE AE oe ae ss |
-- +----------------+
Mais les plus attentifs d’entre vous restent cependant sceptiques au vu des piètres performances de notre dernière requête, si simple soit-elle !
Et ils auront raison ! C’est pourquoi nous allons à présent aborder la question des index. Que sont-ils ? À quoi servent-ils ? Et comment peuvent-ils nous sauver la mise dans le cas qui nous concerne ?
Je me propose de passer rapidement sur les notions élémentaires pour pouvoir m’attarder d’avantage sur les choses plus complexes qui nous intéressent.
En informatique, un index est une liste ordonnée qui permet un accès plus rapide à une ligne spécifique d’une table d’une base de données à partir de la valeur d’une ou de plusieurs colonnes de cette ligne. — Wikipedia
On peut préciser qu’il existe différents types d’index ayant chacun ses avantages et ses faiblesses. Ainsi il convient de savoir quand les employer et comment les mettre en place.
La présence d’index impliquant forcément la mise à jour de ceux-ci lors de l’ajout ou de l’altération d’une donnée, il convient également d’en user avec parcimonie.
Il est à noter que nous n’avons aucun contrôle sur la manière dont PostgreSQL choisira d’utiliser ou non nos index. Il va simplement se servir de celui —ou ceux, car il peut combiner très efficacement plusieurs d’entre eux— qui lui semble le plus approprié. Ensuite il filtrera le reste des données pour en extraire le résultat de notre requête.
EXPLAIN
est un outil intéressant pour savoir quels index sont utilisés
lorsqu’on exécute une requête. Reprenons notre exemple initial et voyons comment
cela se présente.
EXPLAIN SELECT * FROM users WHERE first_name = 'pierre';
-- +-------------------------------------------------------------+
-- | QUERY PLAN |
-- |-------------------------------------------------------------|
-- | Seq Scan on users (cost=0.00..30716.97 rows=100 width=675) |
-- | Filter: ((first_name)::text = 'pierre'::text) |
-- +-------------------------------------------------------------+
On voit ici qu’un balayage est fait de la table users
et qu’un simple filtre a
été appliqué. Il n’est fait mention d’aucun index. Et pour cause, le seul index
dont nous disposons est défini sur la clé primaire de notre table et non sur le
champ first_name
sur lequel nous appliquons une contrainte.
\di users*
-- +----------+------------+--------+----------+
-- | Schema | Name | Type | Owner |
-- |----------+------------+--------+----------|
-- | public | users_pkey | index | synbioz |
-- +----------+------------+--------+----------+
Ajoutons dès lors un index sur le champ first_name
et voyons ce que ça donne.
CREATE INDEX users_fname_idx ON users (first_name);
La même chose via une migration Rails :
class AddIndexFirstNameToUsers < ActiveRecord::Migration[5.0]
def change
add_index :users, :first_name
end
end
Il existe différentes méthodes d’indexation : btree
, hash
, gist
, spgist
,
gin
, et brin
. Par défaut, si aucune méthode n’est précisée, PostgreSQL
créera un index de type btree
. Il s’agit d’une structure sous forme d’arbre.
Maintenant que nous disposons d’un index sur le champ utilisé dans la clause
WHERE
de notre requête, voyons quel en est l’impact.
EXPLAIN SELECT * FROM users WHERE first_name = 'pierre';
-- +------------------------------------------------------------------------------+
-- | QUERY PLAN |
-- |------------------------------------------------------------------------------|
-- | Bitmap Heap Scan on users (cost=5.20..385.25 rows=100 width=675) |
-- | Recheck Cond: ((first_name)::text = 'pierre'::text) |
-- | -> Bitmap Index Scan on users_fname_idx (cost=0.00..5.17 rows=100 width=0) |
-- | Index Cond: ((first_name)::text = 'pierre'::text) |
-- +------------------------------------------------------------------------------+
SELECT * FROM users WHERE first_name = 'pierre';
-- SELECT 4
-- Time: 0.016s
pgbench duration: 60 s
number of transactions actually processed: 1032939
latency average = 0.581 ms
tps = 17215.122643 (including connections establishing)
tps = 17216.682857 (excluding connections establishing)
Voilà qui change la donne ! Un million de transaction à la minute c’est tout de même bien plus satisfaisant que 1544.
On voit ici qu’il a été fait usage de notre index users_fname_idx
, et cela se
ressent ! Voyons maintenant si l’on peut faire aussi bien en complexifiant notre
requête.
EXPLAIN SELECT * FROM users WHERE first_name LIKE '%pierre%';
-- +------------------------------------------------------------+
-- | QUERY PLAN |
-- |------------------------------------------------------------|
-- | Seq Scan on users (cost=0.00..30716.97 rows=39 width=675) |
-- | Filter: ((first_name)::text ~~ '%pierre%'::text) |
-- +------------------------------------------------------------+
Ce que l’on soupçonnait s’est produit… PostgreSQL n’est pas capable d’utiliser
notre index car nous n’avons plus affaire ici à une simple égalité de valeur
mais à une comparaison au pattern %pierre%
.
Il nous faut donc trouver une alternative à notre index de type btree
. La
solution se trouve du côté de gin
et gist
.
En effet, l’activation de l’extension pg_trgm
nous offrira la possibilité de
déclarer des index supportant tout style de pattern lors de l’utilisation de
LIKE
et ILIKE
. Voyons cela ensemble.
Tout d’abord, activons l’extension pg_trgm
.
CREATE EXTENSION IF NOT EXISTS pg_trgm;
Je ne vous fais pas l’affront de détailler à nouveau la migration Rails à créer et à exécuter, vous avez saisi l’idée.
Créons à présent un index. Oui mais lequel, me direz-vous ! En effet, nous avons le choix entre GIN (Generalized Inverted Index) et GiST (Generalized Search Tree), alors qu’est ce qui les diffère ?
La différence entre ces deux méthodes tient principalement des performances dues à leurs caractéristiques. La documentation de PostgreSQL 9.4 nous aiguille là dessus :
In choosing which index type to use, GiST or GIN, consider these performance differences:
- GIN index lookups are about three times faster than GiST
- GIN indexes take about three times longer to build than GiST
- GIN indexes are moderately slower to update than GiST indexes, but about 10 times slower if fast-update support was disabled […]
- GIN indexes are two-to-three times larger than GiST indexes
Depuis les améliorations apportées par la version 9.4, à la fois sur la taille en mémoire des index GIN et les gains en performance des index multi-clés, la balance penche plutôt du côté de ce dernier dans la majorité des cas.
Ajoutons donc un index GIN et voyons où ça nous mène.
CREATE INDEX users_fname_gin ON users USING gin (first_name gin_trgm_ops);
Quelques précisions s’imposent à cette étape. gin_trgm_ops
est ce que l’on
appelle l’operator class. Celle-ci nous est justement fournie par l’extension
que nous venons d’activer.
Si nous avions la possibilité d’utiliser pour l’opérande droite de LIKE
un
pattern ancré à gauche (ex: foo%
), alors nous pourrions nous passer de cette
extension et utiliser l’operator class varchar_pattern_ops
ou
text_pattern_ops
avec un bête index de type btree
.
Bref. Voyons donc l’impact de notre index nouvellement créé.
EXPLAIN SELECT * FROM users WHERE first_name LIKE '%pierre%';
-- +------------------------------------------------------------------------------+
-- | QUERY PLAN |
-- |------------------------------------------------------------------------------|
-- | Bitmap Heap Scan on users (cost=36.30..187.63 rows=39 width=675) |
-- | Recheck Cond: ((first_name)::text ~~ '%pierre%'::text) |
-- | -> Bitmap Index Scan on users_fname_gin (cost=0.00..36.29 rows=39 width=0) |
-- | Index Cond: ((first_name)::text ~~ '%pierre%'::text) |
-- +------------------------------------------------------------------------------+
SELECT * FROM users WHERE first_name LIKE '%pierre%';
-- SELECT 21
-- Time: 0.032s
pgbench duration: 60 s
number of transactions actually processed: 38055
latency average = 15.773 ms
tps = 634.006732 (including connections establishing)
tps = 634.050688 (excluding connections establishing)
Ici nous sommes déjà loin du million de transactions à la minute, mais 38055 au lieu de 1266 c’est tout de même 30 fois plus !
De même, nous observons de nets gains de performance avec ILIKE
.
EXPLAIN SELECT * FROM users WHERE first_name ILIKE '%pierre%';
-- +------------------------------------------------------------------------------+
-- | QUERY PLAN |
-- |------------------------------------------------------------------------------|
-- | Bitmap Heap Scan on users (cost=104.80..15181.20 rows=7846 width=675) |
-- | Recheck Cond: ((first_name)::text ~~* '%pierre%'::text) |
-- | -> Bitmap Index Scan on users_fname_gin (cost=0.00..102.84 rows=7846 wh=0) |
-- | Index Cond: ((first_name)::text ~~* '%pierre%'::text) |
-- +------------------------------------------------------------------------------+
SELECT * FROM users WHERE first_name ILIKE '%pierre%';
-- SELECT 5887
-- Time: 0.056s
pgbench duration: 60 s
number of transactions actually processed: 7461
latency average = 80.470 ms
tps = 124.270289 (including connections establishing)
tps = 124.283756 (excluding connections establishing)
Là où on mettait plus d’une demie seconde pour effectuer notre requête, cela ne nous en demande plus que le dixième du temps ! De 290 transactions à la minute, on passe à plus de 7400. Ici aussi le gain est appréciable.
Notre nouvel index a cependant ses limitations. En effet, lors de l’utilisation
de fonctions telles que lower()
vu précédemment, ce dernier ne nous sera
d’aucune utilité.
EXPLAIN SELECT * FROM users WHERE lower(first_name) LIKE '%pierre%';
-- +-------------------------------------------------------------+
-- | QUERY PLAN |
-- |-------------------------------------------------------------|
-- | Seq Scan on users (cost=0.00..32854.77 rows=274 width=675) |
-- | Filter: (lower((first_name)::text) ~~ '%pierre%'::text) |
-- +-------------------------------------------------------------+
On peut néanmoins s’en sortir avec des index un tantinet plus complexes. En effet, il est possible de déclarer des index utilisant des fonctions. Voyons voir.
CREATE INDEX users_fname_low ON users USING GIN (lower(first_name) gin_trgm_ops);
EXPLAIN SELECT * FROM users WHERE lower(first_name) LIKE '%pierre%';
-- +------------------------------------------------------------------------------+
-- | QUERY PLAN |
-- |------------------------------------------------------------------------------|
-- | Bitmap Heap Scan on users (cost=38.12..1038.61 rows=274 width=675) |
-- | Recheck Cond: (lower((first_name)::text) ~~ '%pierre%'::text) |
-- | -> Bitmap Index Scan on users_fname_low (cost=0.00..38.05 rows=274 wh=0) |
-- | Index Cond: (lower((first_name)::text) ~~ '%pierre%'::text) |
-- +------------------------------------------------------------------------------+
SELECT * FROM users WHERE lower(first_name) LIKE '%pierre%';
-- SELECT 5887
-- Time: 0.034s
pgbench duration: 60 s
number of transactions actually processed: 7861
latency average = 76.405 ms
tps = 130.881965 (including connections establishing)
tps = 130.893109 (excluding connections establishing)
Voilà qui est très encourageant ! Il ne nous reste qu’à déclarer notre index
avec la fonction unaccent()
et le tour sera joué !
CREATE INDEX users_fname_una ON users USING GIN (unaccent(lower(first_name)) gin_trgm_ops);
-- ERROR: functions in index expression must be marked IMMUTABLE
Outch ! Que vient faire cette erreur alors que nous étions à deux doigts
d’atteindre notre but !? Et puis d’ailleurs qu’est-ce qu’une fonction
immutable et pourquoi unaccent()
ne l’est pas ?
Il est question ici de la volatilité d’une fonction. Il en existe de 3 types :
volatile
, stable
et immutable
.
Voici ce que nous dit la documentation :
A VOLATILE function can do anything, including modifying the database. It can return different results on successive calls with the same arguments. […]
A STABLE function cannot modify the database and is guaranteed to return the same results given the same arguments for all rows within a single statement. This category allows the optimizer to optimize multiple calls of the function to a single call. […]
An IMMUTABLE function cannot modify the database and is guaranteed to return the same results given the same arguments forever. This category allows the optimizer to pre-evaluate the function when a query calls it with constant arguments. […]
En substance, pour avoir la possibilité d’utiliser une fonction dans un index, celle-ci se doit de toujours retourner le même résultat à chaque appel avec les mêmes arguments et ne doit pas avoir d’effet de bord. Pour reprendre la terminologie en usage en programmation fonctionnelle, cette fonction doit être pure.
La méthode unaccent()
n’est pas marquée comme immutable pour les trois
raisons suivantes :
search_path
, ce qui n’est pas acceptable pour une
fonction immutable.Il y a plusieurs débats au sein de la communauté PostgreSQL à ce sujet. Certains proposent de marquer cette fonction immutable lorsque ses deux arguments sont précisés (le dictionnaire à utiliser et le texte impliqué). En attendant que l’on statue sur la question, d’autres, comme Lukáš Lalinský de MusicBrainz, proposent une extension dédiée.
La solution pour laquelle j’ai opté est celle d’Erwin Brandstetter, très actif
sur StackOverflow. Il
s’agit de rendre cette fonction unaccent()
immutable en créant une fonction
enveloppant celle-ci et au sein de laquelle seront explicitement précisés le
dictionnaire utilisé ainsi que le schéma. La voici :
CREATE OR REPLACE FUNCTION f_unaccent(text)
RETURNS text AS
$func$
SELECT public.unaccent('public.unaccent', $1) -- schema-qualify function and dictionary
$func$ LANGUAGE sql IMMUTABLE;
Note : public
étant le schéma où réside votre extension.
Nous pouvons à présent créer un index basé sur cette fonction.
CREATE INDEX users_fname_una ON users USING GIN (f_unaccent(lower(first_name)) gin_trgm_ops);
EXPLAIN SELECT * FROM users WHERE unaccent(lower(first_name)) LIKE '%pierre%';
-- +---------------------------------------------------------------------+
-- | QUERY PLAN |
-- |---------------------------------------------------------------------|
-- | Seq Scan on users (cost=0.00..34992.57 rows=274 width=675) |
-- | Filter: (unaccent(lower((first_name)::text)) ~~ '%pierre%'::text) |
-- +---------------------------------------------------------------------+
EXPLAIN SELECT * FROM users WHERE f_unaccent(lower(first_name)) LIKE '%pierre%';
-- +------------------------------------------------------------------------------+
-- | QUERY PLAN |
-- |------------------------------------------------------------------------------|
-- | Bitmap Heap Scan on users (cost=42.12..1111.11 rows=274 width=675) |
-- | Recheck Cond: (f_unaccent(lower((first_name)::text)) ~~ '%pierre%'::text) |
-- | -> Bitmap Index Scan on users_fname_una (cost=0.00..42.05 rows=274 width=0) |
-- | Index Cond: (f_unaccent(lower((first_name)::text)) ~~ '%pierre%'::text) |
-- +------------------------------------------------------------------------------+
SELECT * FROM users WHERE f_unaccent(lower(first_name)) LIKE '%francois%';
-- SELECT 16939
-- Time: 0.132s
pgbench duration: 60 s
number of transactions actually processed: 1707
latency average = 353.557 ms
tps = 28.284000 (including connections establishing)
tps = 28.287094 (excluding connections establishing)
Nous retrouvons des performances correctes ! 1707 transactions à la minute au lieu de 200, c’est tout de même 8.5 fois plus. Ça se prend.
L’ajout d’index peut améliorer grandement les performances et la réactivité de votre application. Cela peut valoir le coup de garder un œil sur les requêtes les plus lentes et de se demander si un ou deux index bien choisis n’amélioreraient pas tout ça.
Bien évidemment, nous sommes loin d’avoir fait le tour de toutes les possibilités que nous offre PostgreSQL en terme d’indexation. Et je vous invite à parcourir la documentation en ligne qui est généralement bien fournie en explications et en exemples.
Je tiens à préciser que pour l’exercice nous avons créé de multiples index. Il convient cependant d’en garder un nombre restreint car ceux-ci ont un impact sur la réactivité de votre base de données.
Voici pour finir quelques recommandations qui synthétisent ce qui s’est dit dans cet article :
LIKE
ou ILIKE
LIKE
vous fera économiser de précieuses millisecondes.foo%
) qui
permettront l’utilisation d’index de type btree
avec l’operator class
text_pattern_ops
ou varchar_pattern_ops
.unaccent
et volatilitéL’équipe Synbioz.
Libres d’être ensemble.
Nos conseils et ressources pour vos développements produit.