Gestion des prérequis

[Jeckel]

Bon, pour commencer, optimiser la base de données :

Je suis un peu maniaque sur les bords, donc j'ai supprimé la clé inutile sur bati_user pour la remplacer par une clé double (user / bati), les clés, sont en bigint et non-singé (vous n'aurez jamais de clé négative), enfin j'ai renommé les champs pour facilité les jointures (vous verrez plus bas).

Bon, j'aurais pu aussi rajouter les contraintes de clé étrangère, mais ça n'optimise en rien les select, ça sécurise juste les insert et update, donc je vous les laisse.

La nouvelle base de test :

--

-- Structure de la table `bati`

--



CREATE TABLE `bati` (

  `bati_id` bigint(20) unsigned NOT NULL auto_increment,

  `nom` varchar(100) collate utf8_unicode_ci NOT NULL,

  PRIMARY KEY  (`bati_id`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci AUTO_INCREMENT=7 ;



--

-- Contenu de la table `bati`

--



INSERT INTO `bati` VALUES(1, 'bati 1');

INSERT INTO `bati` VALUES(2, 'bati 2');

INSERT INTO `bati` VALUES(3, 'bati 3');

INSERT INTO `bati` VALUES(4, 'bati 4');

INSERT INTO `bati` VALUES(5, 'bati 5');

INSERT INTO `bati` VALUES(6, 'bati 6');



-- --------------------------------------------------------



--

-- Structure de la table `bati_user`

--



CREATE TABLE `bati_user` (

  `bati_id` bigint(20) unsigned NOT NULL,

  `user_id` bigint(20) unsigned NOT NULL,

  `niveau` int(11) NOT NULL,

  PRIMARY KEY  (`bati_id`,`user_id`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;



--

-- Contenu de la table `bati_user`

--



INSERT INTO `bati_user` VALUES(1, 1, 5);

INSERT INTO `bati_user` VALUES(4, 1, 2);



-- --------------------------------------------------------



--

-- Structure de la table `prerequis`

--



CREATE TABLE `prerequis` (

  `prerequis_id` bigint(20) unsigned NOT NULL auto_increment,

  `bati_id` bigint(20) unsigned NOT NULL,

  `bati_requis_id` bigint(20) unsigned NOT NULL,

  `niveau_prerequis` int(11) NOT NULL,

  UNIQUE KEY `id` (`prerequis_id`),

  UNIQUE KEY `bati_id_2` (`bati_id`,`bati_requis_id`),

  KEY `bati_id` (`bati_id`),

  KEY `bati_requis_id` (`bati_requis_id`)

) ENGINE=MyISAM  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci AUTO_INCREMENT=6 ;



--

-- Contenu de la table `prerequis`

--



INSERT INTO `prerequis` VALUES(1, 2, 1, 1);

INSERT INTO `prerequis` VALUES(2, 3, 1, 10);

INSERT INTO `prerequis` VALUES(3, 4, 1, 5);

INSERT INTO `prerequis` VALUES(4, 5, 1, 1);

INSERT INTO `prerequis` VALUES(5, 5, 2, 1);

Bon ensuite, deux petites choses :
1. le SELECT * c'est bien quand on est sûr de vouloir vraiment tous les champs, mais avec un *, on ne sait jamais ce qu'on remonte, et s'il y a trop de champs, ça ralenti le résultat, il vaut donc mieux préciser à chaque fois les champs que l'on souhaite récupérer.

2. Les requêtes imbriqués c'est lent, terriblement lent, car selon comment elles sont mise en place, elle peuvent être chacune appelée pour chaque ligne du premier select... donc à supprimer.

Ca donne ceci :

Les bâtiments déjà construit pour l'utilisateur 1 :

SELECT bati.bati_id, bati.nom, niveau

FROM bati

INNER JOIN bati_user USING (bati_id)

WHERE user_id = 1

Les bâtiments qui restent à construire :

SELECT bati.bati_id, bati.nom 

FROM bati

LEFT JOIN bati_user ON (bati.bati_id = bati_user.bati_id AND user_id = 1)

WHERE bati_user.bati_id IS NULL

La requête se traduisant par "les bâtiments qui n'existent pas chez l'utilisateur", plutôt que le NOT IN(SELECT …) utilisez le LEFT JOIN … WHERE id IS NULL

Enfin les bâtiments dont les prérequis (s'il y en a) peuvent être construit :

SELECT bati.bati_id, nom

FROM bati

LEFT JOIN bati_user 

    ON (bati.bati_id = bati_user.bati_id AND user_id = 1)

LEFT JOIN prerequis 

    ON (bati.bati_id = prerequis.bati_id)

LEFT JOIN bati_user AS bati_user_exist 

    ON (prerequis.bati_requis_id = bati_user_exist.bati_id AND bati_user_exist.user_id = 1 AND bati_user_exist.niveau >= prerequis.niveau_prerequis)

WHERE bati_user.bati_id IS NULL AND (prerequis_id IS NULL OR prerequis_id IS NOT NULL AND bati_user_exist.bati_id IS NOT NULL)

Un dernier point, le OR dans la clause WHERE, c'est aussi un truc qui a tendance à ralentir, alors on va essayer de l'enlever en faisant l'Union de deux requêtes, les bâtiments sans prérequis et ceux dont les prérequis sont valide :

SELECT bati.bati_id, nom

FROM bati

LEFT JOIN bati_user 

    ON (bati.bati_id = bati_user.bati_id AND user_id = 1)

LEFT JOIN prerequis 

    ON (bati.bati_id = prerequis.bati_id)

WHERE bati_user.bati_id IS NULL AND prerequis_id IS NULL



UNION



SELECT bati.bati_id, nom

FROM bati

LEFT JOIN bati_user 

    ON (bati.bati_id = bati_user.bati_id AND user_id = 1)

LEFT JOIN prerequis 

    ON (bati.bati_id = prerequis.bati_id)

LEFT JOIN bati_user AS bati_user_exist 

    ON (prerequis.bati_requis_id = bati_user_exist.bati_id AND bati_user_exist.user_id = 1 AND bati_user_exist.niveau >= prerequis.niveau_prerequis)

WHERE bati_user.bati_id IS NULL AND prerequis_id IS NOT NULL AND bati_user_exist.bati_id IS NOT NULL

Voilà, on pourra difficilement faire plus rapide…

Ensuite, histoire d'essayer d'utiliser le cache de la base de données, je conseillerai de créer une vue avec cette requête (en ajoutant l'utilisateur dans le résultat)

Reste un cas qui n'est pas pris en compte dans cette requête : le cas où deux bâtiments sont requis pour la construction d'un troisième !

---

Après relecture, le seul point de ralentissement qui reste dans la requête c'est ce morceau là :

bati_user_exist.niveau >= prerequis.niveau_prerequis

[Myrina]

Reste un cas qui n'est pas pris en compte dans cette requête : le cas où deux bâtiments sont requis pour la construction d'un troisième

Donc, avec le jeu d'essai, le bâtiment 5 est dit constructible ou non avec ta requête?

[Jeckel]

Haha, je n'avais pas vu qu'il était là celui-là...
Heu, là j'en sais rien, je ne peux pas faire de test ici (au taf)

Mais à vu de nez, vu qu'au moins un des prérequis est bon, je pense que le bâtiment ressort comme constructible...
Ce cas là, sans requête imbriqué, je crois que ce n'est pas faisable... (ou alors avec des fonctions stockées, mais c'est pas toujours mieux)

---

Bon, j'aime pas rester sur une colle, j'vais y réfléchir et je vous file ce que j'ai trouvé dans les jours qui viennent, de toute façon, c'est le genre de truc que je dois résoudre pour mon propre projet, vu que j'ai une évol similaire pour la prochaine version d'Eden-5.

[Myrina]

Bon, j'aime pas rester sur une colle, j'vais y réfléchir et je vous file ce que j'ai trouvé dans les jours qui viennent, de toute façon, c'est le genre de truc que je dois résoudre pour mon propre projet, vu que j'ai une évol similaire pour la prochaine version d'Eden-5.

Vivement à dans quelques jours alors

[Jeckel]

Sinon, si on veut être complet, il faudrait rajouter le fait que, souvent, les prérequis ne sont pas tous de même nature..

Ici, la construction d'un bâtiment n'a de pré-requis que d'autres bâtiments, mais il peut y avoir aussi des recherches par exemple, ou encore des tokens...

Pour construire le bâtiment du pouvoir absolu il faut avoir construire 3 autres bâtiments, terminé la recherche du savoir absolu et être en possession du Talisman de Rocledur... par exemple ;-) (et tout ça en SQL ? heu... p'tet pas quand même, encore que.. ;-))

[Myrina]

(et tout ça en SQL ? heu... p'tet pas quand même, encore que.. ;-))

Bin si, j'ai prévu, avec le même SELECT, d'avoir comme prérequis:
- un bâtiment,
- un recherche,
- un résultat de quête,
- un personnage, ...

[Jeckel]

Je précise : sans requête imbriquée

[Ter Rowan]

Sinon, si on veut être complet, il faudrait rajouter le fait que, souvent, les prérequis ne sont pas tous de même nature..

Ici, la construction d'un bâtiment n'a de pré-requis que d'autres bâtiments, mais il peut y avoir aussi des recherches par exemple, ou encore des tokens...

Pour construire le bâtiment du pouvoir absolu il faut avoir construire 3 autres bâtiments, terminé la recherche du savoir absolu et être en possession du Talisman de Rocledur... par exemple ;-) (et tout ça en SQL ? heu... p'tet pas quand même, encore que.. ;-))

y a encore plus compliqué (et je planche dessus)

là tu ne décris que des ET (il faut A et B et C ...)

mais on peut aussi avoir des OU :

il faut avoir construit 3 autres bâtiments Et (avoir trouvé le savoir absolu ou être en possession du Talisman de Rocledur)
et là c'est le drame... Je pense qu'on sort du SQL pour passer au langage... Eventuellement on pourrait même mettre en base les éléments répondant au prérequis par utilisateur, pour éviter les calculs, avec une mise à jour lorsqu'un prérequis est validé

[niahoo]

ça demanderait une table avec une ligne pour chaque joueur * chaque bâtiment.

Et pouruqoi pas faire deux requêtes ?

la première sur une table
id_batiment | id_type_de_prerequis | id_correspondant

et la suivante, construite dynamiquement avec les jointures qui vont bien.

C'est simple, évolutif et ça vous permet de faire peu de requêtes puisque vous semblez vouloir en faire le moins possible :p

[Jeckel]

@Ter Rowan : j'osais pas en parler, je risque d'avoir des trucs dans ce genre là aussi, mais entre le stockage de la règle en base de donnée (comme ici la table des prérequis) et la validation, je pense qu'effectivement, en pur SQL ça risque d'être chaud... à moins de passer par des tables intermédiaires, des triggers pour mettre à jour ces tables quand un bâtiment est construit, etc...

@niahoo : le but n'est pas spécialement de faire le moins de requête possible, mais plutôt de faire l'opération avec un temps le plus court possible.
Pour ça, il y a des choses a éviter en SQL :
- les OR dans un WHERE par exemple font perdre une bonne partie des avantages liés aux index,
- les requêtes imbriqués sont générale exécuté pour chaque enregistrement de la requête parente (donc gros ralentissement),
- enfin les jointure gauche (LEFT JOIN) sont à utiliser judicieusement car elles ont tendance à multiplier énormément le nombre d'enregistrement à traiter par le WHERE, il faut donc les utiliser sur des index et de manière à limiter les résultats.
- dernier point, l'ordre des tables peut aussi jouer sur les perfs.

Dans mon dernier exemple par exemple, faire un UNION, c'est presque comme faire deux requêtes finalement.

Sinon, personnellement, je ne suis pas partisan de la requête construite dynamiquement, c'est en général source de failles de sécurité, peu performant, et souvent tu perds plus de temps à construire cette requête, en plus tu contrôles du coup beaucoup les performances de ta requête. C'est valable pour des petits trucs, mais là, si l'on prend l'exemple de Ter Rowan, tu peux rapidement généré une requête usine à gaz je pense. Mais bon, c'est plus un avis personnel là.