Optimisation par index?

**Niak74** · 27/11/2009, 11h12

Bonjour,

J'utilise depuis pas mal de temps des bases de données type SQLite, mais j'ai toujours du mal à comprendre comment fonctionnent les optimisations par index. Aussi, je ne sais pas si celle que je souhaite mettre en place en est réellement une.

J'ai une table qui correspond à un dictionnaire pondéré (table Dictionnaire, trois colonnes : id, mot, compteur). Chaque mot du dictionnaire possède un compteur qui est régulièrement incrémenté (à chaque utilisation du mot dans un logiciel). Ce dictionnaire me permet de récupérer les listes d'autocomplétion triées par poids (via le compteur) et par ordre alphabétique pour les items de poids identique (pas encore en place).
Par exemple, on cherche les mots commençant par "bon", on exécute la requête prévue : SELECT mot, compteur FROM Dictionnaire WHERE mot LIKE "bon%" ORDER BY compteur DESC;
C'est cette requête que je souhaite optimiser. J'ai pensé à créer un index descendant sur la colonne compteur, est-ce une solution viable?
Y a-t-il une solution plus simple ou performante pour optimiser mon process?
Est-il possible d'intégrer de manière performante un tri alphabétique additionnel sur les items de poids similaire ?

Merci !

**bigane** · 29/11/2009, 18h24

Bonjour,

Normalement, je te dirais de prendre le champ texte comme premier index. En effet, la première requête :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

SELECT mot, compteur FROM Dictionnaire WHERE mot LIKE "bon%" ORDER BY compteur DESC;

commence par retrouver quelques lignes commençant par "bon" puis applique un tri sur le compteur. Utiliser un index sur le compteur ne sert à rien dans ce cas là, sauf si tu as des milliers de mots commençant par "bon".

Mais (car il y a un mais), comme tu utilises le mot clé LIKE, tu fais sauter l'index de la colonne "mot" dans ta requête et c'est la plus importante.

Si tu as réellement des problèmes de performance, il faut réétudier ta table ou ta requête, voir les deux.
Si par exemple, tu ne déclenches la recherche qu'à partir de 3 caractères, tu pourrai indexer ces caractères :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
CREATE TABLE dictionnaire (
mot text primary key,
cle text,
compteur integer);
 
CREATE INDEX idx_cle on dictionnaire (cle);

Tu aurais alors une requête de sélection d'un ensemble de mots commençant par la clé sur 3 caractères :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
SELECT mot, compteur FROM dictionnaire 
WHERE cle = lower(substr('bon', 1,3));

NB: le "lower" est optionnel, c'est seulement si tu stockes les clés en minuscules et si tu veux retourner les "Bon" et "bOn" par exemple.

Il te faudrait encadrer cette requête pour effectuer la véritable sélection qui pourrait aller au delà des 3 premiers caractères (exemple avec le mot "bonjour"

Pour bien comprendre le principe, je te propose de télécharger un dictionnaire de près de 23.000 mots ici :
http://www.freelang.com/download/mis...e_francais.zip

Ensuite, tu lances ces scripts depuis sqlite3 en ligne de commande :

1 ) création du jeu test de 5.900.000 mots (quelques secondes) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
begin transaction;
drop table if exists dictionnaire;
create table dictionnaire (
    id integer primary key,
    mot text,
    cle text,
    compteur integer);
 
create index idx_cle on dictionnaire (cle);
 
-- créer une table de 260 lignes :
drop table if exists loop ;
create table loop (i integer );
insert into loop values ( 1 );
insert into loop values ( 2 );
insert into loop values ( 3 );
insert into loop values ( 4 );
insert into loop select a.i from loop a, loop, loop, loop;
 
drop table if exists liste;
create table liste ( mot text);
 
end transaction;
 
.import liste_francais.txt liste
 
begin transaction;
 
-- charger le dico avec 260*23.000 mots (presque 6.000.000 de mots)
insert into dictionnaire (mot, cle, compteur) select 
    mot as mot, 
    lower(trim(substr(mot,1,3))) as cle, 
    substr(abs(random())||'0',1,2) as compteur
from liste, loop;
 
end transaction;

2) recherche de plusieurs mots commençant par "mand" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
.mod tab
 
SELECT mot, compteur FROM (
  SELECT mot, compteur
  FROM dictionnaire 
  WHERE cle = lower(substr('mand', 1,3))
) WHERE mot LIKE 'mand%'
ORDER BY compteur DESC, mot ASC;

Le résultat est de quelques dixièmes de secondes (peut-être moins) et tu peux recommencer le test sans l'index sur la clé (résultat en deux secondes environ).

Tu peux très bien remplir la colonne clé par un trigger qui ajoute cette donnée (en minuscules) lors des inserts.

L'intérêt de cette méthode, c'est que tu utilises l'index sur la colonne "cle" pour trouver un premier lot de mots et la seconde requête ne se fait qu'en mémoire : ultra rapide.

voili, voilà,
a+

PS: j'ai testé avec ta requête d'origine et un index sur la colonne 'mot' : deux à trois secondes ... donc moins performante et n'utilise pas l'index (comme prévu).

**Niak74** · 30/11/2009, 11h27

Très intéressant tout ça.

Le préfixe à 3 caractères était sensé être modifiable (1 à 4 caractères, mais je pense que je vais le forcer à 2 ou 3 pour ce soucis d'index).

J'ai quelques questions :

- Ajouter un nouveau mot dans le dico avec ta méthode se fera bien? Il faudra faire un INSERT INTO en précisant le mot, la cle et le compteur (0)? Pas besoin de redéfinir l'index? Pour ce qui est des triggers, je ne sais pas trop comment ça marche, je vais voir ça de suite =)

- Je vois que tu entoures toutes tes requêtes par begin transaction; et end transaction;. C'est pour un soucis de synchronisation ?

- Que fait .mod tab ? Dans le help de sqlite3 je ne vois que .mode avec comme option csv, column, html, insert, line, list, tabs, tcl. Est-ce un équivalent à .mode tabs ?

Merci pour ces éclaircissements !

**bigane** · 30/11/2009, 16h08

Bonjour,

Envoyé par Niak74

Très intéressant tout ça.

Le préfixe à 3 caractères était sensé être modifiable (1 à 4 caractères, mais je pense que je vais le forcer à 2 ou 3 pour ce soucis d'index).

Rien ne t'empêche de créer des colonnes supplémentaires et d'utiliser une astuce de codage pour utiliser ces quatres colonnes. (NB: selon le volume de ton dico, je pense qu'un déclenchement sur deux lettres est suffisamment discriminent alors qu'une seule rapporte trop d'enregistrements).

Exemple soient c1 text, c2 text, c3 text et c4 text les quatre colonnes, ta requête interne pourrait faire un "OR" comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
WHERE 
  c1 = lower(substr('mand', 1,1)) or
  c2 = lower(substr('mand', 1,2)) or
  c3 = lower(substr('mand', 1,3)) or
  c4 = lower(substr('mand', 1,4))

La requête externe faisant le tri et l'épuration des doublons, on devrait rester efficace.

Envoyé par Niak74

- Ajouter un nouveau mot dans le dico avec ta méthode se fera bien? Il faudra faire un INSERT INTO en précisant le mot, la cle et le compteur (0)? Pas besoin de redéfinir l'index? Pour ce qui est des triggers, je ne sais pas trop comment ça marche, je vais voir ça de suite =)

Oui. Non (ce n'est pas forcé, cf. plus loin dans mon explication). Oui. et pour les triggers : l'INSERT peut avoir par exemple cette forme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

INSERT INTO Dictionnaire (mot) values ('lemot');

Mais il te faut deux triggers pour que cela fonctionne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
create trigger tai_dictionnaire after insert on Dictionnaire 
begin
  update dictionnaire set 
    compteur = 1,
    cle = lower(trim(substr(mot,1,3))) 
    where rowid = new.rowid;
end;
 
create trigger tau_dictionnaire after update of mot on Dictionnaire
begin
  update dictionnaire set cle =lower(trim(substr(mot,1,3))) 
  where rowid = new.rowid;
end;

Remarques :
1) le second trigger est optionnel, car normalement tu ne modifies pas les mots mais uniquement les compteurs.
2) le compteur est initialisé à 1, mais il peut l'être à 0.
Et voici le résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
sqlite> delete  from dictionnaire;
sqlite> insert into dictionnaire (mot) values ('bonjour');
sqlite> insert into dictionnaire (mot) values ('bonsoir');
sqlite> insert into dictionnaire (mot) values ('salut');
sqlite> select * from dictionnaire;
1       bonjour bon     1
2       bonsoir bon     1
3       salut   sal     1

Autre remarque, ton code va surement insérer un mot s'il n'existe pas encore, alors que s'il existe il va uniquement faire un +1 dans compteur.
Tu peux traiter ces éléments avec une astuce : ton code ne fait qu'ajouter des mots dans la table. C'est le moteur sql qui effectue l'ajout ou qui effectue le +1 si le mot existe déjà.
Cela donne un trigger supplémentaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
create trigger tbi_dictionnaire before insert on Dictionnaire 
when (select 1 from Dictionnaire where mot=new.mot) = 1 
begin
  update dictionnaire set 
    compteur = compteur + 1
    where mot=new.mot;
  select raise(IGNORE);
end;

Et le résultat suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
sqlite> delete  from dictionnaire;
sqlite> insert into dictionnaire (mot) values ('bonjour');
sqlite> insert into dictionnaire (mot) values ('bonsoir');
sqlite> insert into dictionnaire (mot) values ('salut');
sqlite> insert into dictionnaire (mot) values ('bonjour');
sqlite> insert into dictionnaire (mot) values ('bonjour');
sqlite> select * from dictionnaire;
1       bonjour bon     3
2       bonsoir bon     1
3       salut   sal     1

Envoyé par Niak74

- Je vois que tu entoures toutes tes requêtes par begin transaction; et end transaction;. C'est pour un soucis de synchronisation ?

Non, c'est pour accélérer les requêtes. Le moteur calcule tout en mémoire et quant tout est ok il écrit le total dans la base. Ainsi le disque gratte moins et c'est ultra rapide.

Envoyé par Niak74

- Que fait .mod tab ? Dans le help de sqlite3 je ne vois que .mode avec comme option csv, column, html, insert, line, list, tabs, tcl. Est-ce un équivalent à .mode tabs ?

Oui. En fait le programme sqlite3.exe comprend les début de mots dans ses commandes, donc .mod équivaut à .m ou .mo ou .mode et tab équivaut à t ou ta ou tabs.
On peut donc écrire ".m t" mais dans ce cas, on n'y comprend plus rien. Les puristes peuvent écrire ".mode tabs".

Envoyé par Niak74

Merci pour ces éclaircissements !

Merci pour ta demande qui me fait réfléchir et entretenir mes connaissances.
a+

**Niak74** · 01/12/2009, 09h39

Ça c'est de la réponse dis donc.

Merci beaucoup pour tes explications très détaillées. Je commence à vraiment palper la puissance et la richesse du moteur SQL.

La solution des triggers pour l'insertion/mise à jour est parfaite ! Ça simplifie l'applicatif et déporte l'intelligence et les responsabilités dans la base de données, je préfère cette solution.

Je repense toutefois à un détail. Il est vrai que le mécanisme se déclenche après la frappe de 3 caractères (préfixe minimal), mais ce même mécanisme est sensé marcher aussi ensuite (quelque soit la longueur du préfixe, et de la longueur du mot).

Exemple (avec un préfixe minimal à 3) :
On entre "s" => rien
On entre "sa" => rien
On entre "sal" => proposition : "salut", "salace", "salade", ect...
On entre "sala" => proposition : "salace", "salade", "salaire", ect...
On entre "salad" => proposition : "salade", "saladier", ect...
ect...

Il faut donc pouvoir utiliser ce mécanisme de clé pour 3 caractères, et plus. Quelle solution envisager ? créer x colonnes supplémentaires contenant toutes les clés possibles

**bigane** · 01/12/2009, 11h00

Bonjour,

Envoyé par Niak74

Je repense toutefois à un détail. Il est vrai que le mécanisme se déclenche après la frappe de 3 caractères (préfixe minimal), mais ce même mécanisme est sensé marcher aussi ensuite (quelque soit la longueur du préfixe, et de la longueur du mot).

Exemple (avec un préfixe minimal à 3) :
On entre "s" => rien
On entre "sa" => rien
On entre "sal" => proposition : "salut", "salace", "salade", ect...
On entre "sala" => proposition : "salace", "salade", "salaire", ect...
On entre "salad" => proposition : "salade", "saladier", ect...
ect...

Il faut donc pouvoir utiliser ce mécanisme de clé pour 3 caractères, et plus. Quelle solution envisager ? créer x colonnes supplémentaires contenant toutes les clés possibles

Si tu examines mieux mon premier exemple, c'est justement comme cela qu'il fonctionne. La requête interne pré-sélectionne un lot d'enregistrement basé sur les trois premiers caractères, ensuite la requête externe filtre ces réponses et ne laisse passer que les données répondant à un filtre plus précis.

Exemple, si on recherche le mot "sa" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
SELECT mot, compteur FROM (
  SELECT mot, compteur
  FROM dictionnaire 
  WHERE cle = lower(trim(substr('sa', 1,3)))
) WHERE mot LIKE 'sa%'
ORDER BY compteur DESC, mot ASC;

La requête ne retournera rien (ou uniquement les mots commençant par "sa" et "sa "). C'est normal, on ne déclenche la recherche qu'avec 3 caractères.

Exemple, si on recherche le mot "salad" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
SELECT mot, compteur FROM (
  SELECT mot, compteur
  FROM dictionnaire 
  WHERE cle = lower(trim(substr('salad', 1,3)))
) WHERE mot LIKE 'salad%'
ORDER BY compteur DESC, mot ASC;

La requête fonctionne parfaitement.
Il te suffit donc uniquement de remplacer le mot 'salad' par le mot de ton choix et de la longueur que tu veux pour obtenir le bon résultat.

a+

**Niak74** · 01/12/2009, 14h29

Ok d'accord, le pré tri se fait uniquement sur le préfixe (si il existe) d'un mot, ce qui permet de réduire la liste utilisée pour la suite du traitement.

Je n'avais pas tilté que ça suffisait amplement à optimiser l'opération, même sur des mots longs.

Je vais mettre tout ceci en place. Encore une fois, merci !

**Niak74** · 10/12/2009, 11h02

Testé et approuvé, c'est nickel.

Merci encore !

Optimisation par index?

SQLite

Discussions similaires

Partager

Partager