"next record" - comment profiter d'un index?

Bonjour

Je voudrais trouver la solution à un problème qui se trouve à la base de beaucoup de questions soulevées par les utilisateurs de SQL.
En gros on peut le réduire à la question suivante :

Comment formuler la requête SQL pour extraire un enregistrement qui est le suivant par rapport à un autre enregistrement point de vue d’un index ?

Pour être plus clair je vais me servir d’un exemple.

J’ai une table "matable" avec l’index "monindex".
"monindex" est composé de deux champs (champ_clef1,champ_clef2).
champ_clef1, champ_clef2 sont de type INTEGER (pour simplifier).
"matable" contient les enregistrements suivants (triés selon "monindex") :

champ_clef1 -- champ_clef2
----- 1 --------- 1 --------
----- 1 --------- 2 --------
----- 1 --------- 3 --------
----- 2 --------- 1 --------
----- 2 --------- 2 --------
----- 2 --------- 3 --------
----- 3 --------- 1 --------
----- 3 --------- 2 --------
----- 3 --------- 3 --------

Je veux récupérer l’enregistrement qui se trouve juste après (1,3) - donc (2,1)…

J’ai essayé la requête :

Code:

---

1 2 3

SELECT * FROM matable FORCE INDEX monindex WHERE (champ_clef1,champ_clef2) > (1,3) LIMIT 1;

---

A première vue ça marche mais en ajoutant "EXPLAIN" devant j’ai constaté que :

1. aucun index était utilisé (SQL analyse tous les enregistrements)
2. il y un risque que le résultat dépend du hasard. Comme l’index n’est pas utilisé, le premier enregistrement trouvé (je ne demande que un) pourrait être (3,3)

Ensuite j’ai essayé une autre requête :

Code:

---

1 2 3

SELECT * FROM matable WHERE champ_clef1=1 AND champ_clef2>3 OR champ_clef1>1 LIMIT 1;

---

Cette fois monindex était utilisé mais SQL malgré tout analysait plusieurs enregistrements au lieu de s’arrêter sur le premier trouvé. Après la lecture de la documentation j’ai compris que SQL a créé dans ce cas deux intervalles (à cause de "OR") et le résultat c’est la concaténation de ces intervalles ou plutôt le premier enregistrement de cette concaténation. Ici c’est pareil – ce n’est peut-être pas l’enregistrement que je cherche…
Pour être sûr il faudrait ajouter "ORDER BY champ_clef1, champ_clef2" à cette requête…
Bien, mais dans ce cas, SQL en interne va faire probablement un travail énorme (chaque intervalle peut comporter beaucoup d’enregistrements et tout ça il faut trier à la fin).
En bref, pour quelque chose qui paraît assez simple (en utilisant l’index il est théoriquement possible de trouver le bon enregistrement tout suite), on risque d’attendre la réponse longtemps.

Est-ce que quelqu’un pourrait m’aider ?

Rapidement (je reviendrai sur le fond du problème s'il y a besoin), ta requête

Code:

---

1 2 3 4

SELECT * FROM matable WHERE champ_clef1=1 AND champ_clef2>3 OR champ_clef1>1 LIMIT 1;

---

peut s'écrire avec un row constructor :

Code:

---

1 2 3 4

SELECT * FROM matable WHERE (champ_clef1, champ_clef2) > (1, 3) LIMIT 1;

---

Tu testerais ce que ça donne pour ton index ?

au passage, :tagcode:

Question subsidaire : combien y a-t-il de lignes dans ta table ?

Salut Antoun,

Je crois que tu as loupé ma première requête dans laquelle j'utilise "row constructor" (à une différence près: j'ai essayé en même temps de forcer l'utilisation d'index).:P
Comme tu peux lire dans le commentaire, SQL ne veut pas tenir compte de l'existence d'index.

Pour le nombre d'enregistrements - on peut supposer qu'il y en a 500000. Ma question est plutôt théorique. Je suis à la recherche de bonnes méthodes pour faire de différentes choses avant de me lancer vraiment dans la programmation...

Merci pour la mise en forme…

Effectivement, j'avais complètement raté ta première requête :oops:
(à ma décharge, je postais depuis mon PDA).

On va déjà commencer par ajouter le ORDER BY, sinon le LIMIT est aléatoire et ça n'aide pas l'optimiseur à comprendre :aie: :

Code:

---

1 2 3 4 5

SELECT * FROM matable WHERE (champ_clef1,champ_clef2) > (1,3) ORDER BY champ_clef1,champ_clef2 LIMIT 1;

---

C'est vrai qu'il faut ajouter "ORDER BY" pour trouver ce qu'on cherche. Malheureusement (comme je l'ai écrit dans mon commentaire) SQL n'a pas l'intention d'utiliser l'index. Ceci veut dire qu'on va trier pratiquement (si on veut localiser la deuxième ligne) la table entière...:cry: Avec 500000 lignes ça fait du boulot...

Pour être plus précis (je viens de faire un test): avec "ORDER BY" l'index est quand même utilisé mais SQL analyse tous les enregistrements. Autrement dit, SQL parcourt la table entière en utilisant l'index (du coup le tri à la fin n'est pas nécessaire) - et tout ça pour me présenter un enregistrement qui se trouve tout au début...:evilred:

Ton index est bien une combinaison de tes deux clés ?

Voici la commande SQL pour créer matable:

Code:

---

1 2 3 4 5 6 7 8

CREATE TABLE matable ( id int(11) NOT NULL auto_increment, champ_clef1 int(11) NOT NULL, champ_clef2 int(11) NOT NULL, texte varchar(40) collate dec8_bin NOT NULL, PRIMARY KEY (id), KEY monindex (champ_clef1,champ_clef2) ) ENGINE=InnoDB DEFAULT CHARSET=dec8 COLLATE=dec8_bin;

---

J'ai essayé la requête suivante:

Code:

---

1 2 3 4 5

explain SELECT * FROM matable WHERE (champ_clef1,champ_clef2) > (1,3) order by champ_clef1,champ_clef2 limit 1;

---

...et voici le résultat de cette requête:

id------------->1
select_type---->SIMPLE
table---------->matable
type----------->index
possible_keys-->NULL
key------------>monindex
key_len-------->8
ref------------>NULL
rows----------->8
Extra---------->Using where

Pour que ça soit plus clair: il y a seulement 8 lignes dans cette table (ce n'est qu'un test). "rows=8" et "Extra=Using where" suggèrent que SQL analyse toutes les lignes (au moins dans le pire de cas)
Il est possible que j'interprète ce résultat d'une fausse manière...

Citation:

---

Envoyé par tom-k

Pour que ça soit plus clair: il y a seulement 8 lignes dans cette table (ce n'est qu'un test). "rows=8" et "Extra=Using where" suggèrent que SQL analyse toutes les lignes (au moins dans le pire de cas)
Il est possible que j'interprète ce résultat d'une fausse manière...

---

En fait, faire des tests sur 8 lignes n'a aucune signification (d'où ma question sur le nombre de lignes un peu plus haut). En effet, l'optimiseur n'a rien à gagner sur 8 lignes, donc il fait un scan complet... dit autrement, il considère que c'est contre-productif de louer un hélico pour traverser la rue ;).

De manière générale, les tests d'optimisation doivent toujours se faire en vraie grandeur, parce que rien n'est linéaire là-dedans...

Ok…j’ai compris.
Tout de même je voudrais avoir un moyen pour savoir selon quelles règles procède l’optimiseur. C’est très embêtant de devoir créer une table de 500000 enregistrements si on veut prévoir son comportement. Il faut dire que ces règles sont assez obscures. Avec les outils que j’utilisais jusqu’au présent c’était le programmeur qui jouait le rôle d’optimiseur. Tu vas peut-être me dire que c’est mieux si SQL le fait à ma place. Eh bien…je préfère, au moins parfois, décider moi-même. Je suis très méfiant… Je ne veux pas constater plus tard que mes programmes commencent à ramer parce que SQL travaille autrement par rapport à ce que je croyais.

D’où ma question:

Est-ce que les règles d’optimisation sont décrites quelque part d’une manière claire et nette?

Il y a tout un chapitre de la doc MySQL consacré à l'optimisation. Tu y trouveras peut-être ton bonheur.

Merci pour le tuyau…

Citation:

---

Envoyé par tom-k

Ok…j’ai compris.
Tout de même je voudrais avoir un moyen pour savoir selon quelles règles procède l’optimiseur. C’est très embêtant de devoir créer une table de 500000 enregistrements si on veut prévoir son comportement.

---

Non, c'est très facile :

Code:

---

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

-- création de la table annexe CREATE TABLE chiffres ( Num tinyint(1) unsigned NOT NULL) ;   INSERT INTO chiffres(Num) VALUES (0); INSERT INTO chiffres(Num) VALUES (1); INSERT INTO chiffres(Num) VALUES (2); INSERT INTO chiffres(Num) VALUES (3); INSERT INTO chiffres(Num) VALUES (4); INSERT INTO chiffres(Num) VALUES (5); INSERT INTO chiffres(Num) VALUES (6); INSERT INTO chiffres(Num) VALUES (7); INSERT INTO chiffres(Num) VALUES (8); INSERT INTO chiffres(Num) VALUES (9);   -- insertion de 500 000 lignes aléatoires par un produit cartésien -- Unités, Dizaines, Centaines, Milliers, etc. INSERT INTO matable (champ_clef1, champ_clef2, texte) SELECT RAND() * 1000, RAND() * 1000, 'blabla' FROM chiffres U CROSS JOIN chiffres D CROSS JOIN chiffres C CROSS JOIN chiffres M CROSS JOIN chiffres DM CROSS JOIN chiffres CM WHERE U.Num + 10 * D.Num + 100 * C.Num + 1000 * M.Num + 10000 * DM.Num + 100000 * CM.Num < 500000 ;

---

Tout ça s'exécute en une vingtaine de secondes sur mon petit laptop.

La table chiffres est à garder, elle est très pratique pour plein de belles astuces ensemblistes (cf notamment http://sqlpro.developpez.com/cours/jointuremanquante/).

A noter aussi que certains ETL, notamment Talend qui est open source, comportent des moulinettes de génération de données aléatoires.

Citation:

---

Envoyé par tom-k

Il faut dire que ces règles sont assez obscures. Avec les outils que j’utilisais jusqu’au présent c’était le programmeur qui jouait le rôle d’optimiseur. Tu vas peut-être me dire que c’est mieux si SQL le fait à ma place.

---

Je ne me permettrais pas de juger de tes compétences d'optimiseur. Mais j'ai pu remarquer qu'en tout cas, l'optimiseur le fait bcp mieux que moi 8-)

Citation:

---

Envoyé par tom-k

Eh bien…je préfère, au moins parfois, décider moi-même. Je suis très méfiant… Je ne veux pas constater plus tard que mes programmes commencent à ramer parce que SQL travaille autrement par rapport à ce que je croyais.

---

De manière générale, la meilleure politique d'optimisation est précisément celle qui ne te plaît pas : appliquer les règles de base (créer des index sur les colonnes utilisées dans les jointures et les conditions), laisser le SGBD se débrouiller (il est là pour ça), et intervenir quand ça commence à ramer. ça a sans doute l'air très crado, mais en fait ça répond au fait que l'optimisation est un problème complexe et contradictoire. Aussi, lorsque le développeur intervient avant qu'un problème ne soit détecté, il a bcp plus de chance de plomber un truc qui marchait bien sans lui que de corriger...

Pour un peu de lecture sur l'optimisation : http://sqlpro.developpez.com/optimisation/
(c'est du SQL Server, mais ça pose bien les principes et ça t'aidera sans doute à comprendre le chapitre Optimisation de la doc MySQL).

J'ai ajouté 500000 enregistrements dans matable en utilisant ton code.
Ensuite, j'ai fait quelques tests.
D'abord la requête:

Code:

---

1 2 3 4

SELECT * FROM `matable` WHERE (champ_clef1,champ_clef2) > (0,0) ORDER BY champ_clef1,champ_clef2 LIMIT 1

---

Temps de réponse: 0.0008 sec.

Ensuite:

Code:

---

1 2 3 4

SELECT * FROM `matable` WHERE (champ_clef1,champ_clef2) > (1000,990) ORDER BY champ_clef1,champ_clef2 LIMIT 1

---

Temps de réponse: 1.0079 sec.

La différence prouve que SQL ne profite pas vraiment de l'index. J'avoue que parcourir la table de 500000 lignes en 1.0079 sec. ce n'est pas mal...mais c’est quand même médiocre si on sait que l’index existe…
D'ailleurs, pour être sûr que je ne me trompe pas, j'ai essayé encore de mettre "EXPLAIN" devant le dernier code. Le résultat était identique comme avant (le test avec 8 lignes) - la seule différence c'est évidemment la colonne "rows" qui cette fois-ci indiquait 500607.
Est-ce que cet exemple ne prouve pas que dans certains cas c'est l'homme qui doit décider comment faire...? ;)

Pour le reste - je vais naturellement étudier toutes les infos concernant l'optimistation. Merci pour le link...

Citation:

---

Envoyé par tom-k

La différence prouve que SQL ne profite pas vraiment de l'index. J'avoue que parcourir la table de 500000 lignes en 1.0079 sec. ce n'est pas mal...mais c’est quand même médiocre si on sait que l’index existe…

---

En fait, il ne lit pas les 500 000 lignes de la table, mais les 500 000 entrées d'index. C'est la signification du type : index (principe de l'index couvrant). J'ai testé sans index, ça a plutôt l'air plus rapide :rire:.

Citation:

---

Envoyé par tom-k

Est-ce que cet exemple ne prouve pas que dans certains cas c'est l'homme qui doit décider comment faire...? ;)

---

Dans certains cas, c'est certain ! je disais d'ailleurs :

Citation:

---

Envoyé par Antoun

... laisser le SGBD se débrouiller (il est là pour ça), et intervenir quand ça commence à ramer.

---

Il semblerait que le ROW CONSTRUCTOR n'est pas pris en compte par l'optimiseur (c'est une syntaxe assez méconnue). Par contre, la version avec OR et ORBER BY utilise l'index :

Code:

---

1 2 3 4 5 6 7 8

explain SELECT * FROM `matable` WHERE (champ_clef1,champ_clef2) < (1000, 990) WHERE champ_clef1 < 1000 or champ_clef1 = 1000 and champ_clef2 < 990 ORDER BY champ_clef1,champ_clef2 LIMIT 1;

---

Code:

---

1 2 3 4

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+---------+-------+---------------+----------+---------+------+--------+-------------+ | 1 | SIMPLE | matable | range | monindex | monindex | 8 | NULL | 250546 | Using where | +----+-------------+---------+-------+---------------+----------+---------+------+--------+-------------+

---

Au passage, pour les tests d'optimisation, il est utile de faire un FLUSH QUERY CACHE puis d'utiliser SQL_NO_CACHE dans les requêtes.

En gros tu as raison mais je pense que tu voulais me proposer ceci:

Code:

---

1 2 3 4 5

EXPLAIN SELECT * FROM matable WHERE champ_clef1=1000 and champ_clef2>990 OR champ_clef1>1000 ORDER BY champ_clef1,champ_clef2 LIMIT 1;

---

La requête avec 2 WHERE à l'intérieure ne marche pas trop bien...
Les comparaisons n'étaient pas dans le bon sens non plus...:mouarf:
Le résultat du code ci-dessus:

Code:

---

1 2 3 4

| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra | +----+-------------+---------+-------+---------------+----------+---------+------+--------+-------------+ | 1 | SIMPLE | matable | range | monindex | monindex | 8 | NULL | 3 | USING WHERE | +----+-------------+---------+-------+---------------+----------+---------+------+--------+-------------+

---

...et c'est vrai - dans ce cas l'index est utilisé!
Le même code, mais sans "EXPLAIN", a besoin de 0.0006 sec pour faire ce qu'il faut. (et ceci dépend très peu de l'endroit où on veut être positionné)

Je ne suis qu'un débutant en SQL et pourtant j'ai trouvé l'utilisation de "row constructor" très naturelle. On voit bien maintenant que ce n'était pas la bonne solution (c'est dommage d'ailleurs). C'est pour ça que je préfère prévenir que guérir...

désolé pour les coquilles (j'ai fait un peu trop de copiers-collers dans tous le sens), et bravo d'avoir rétabli toi-même !

si tu estimes que c'est bon, merci de cliquer sur le bouton :resolu: un peu plus bas.