Sélectionner les cases cotières d'une carte

[Ter Rowan]

je n'ai pas osé proposer cela car je ne savais pas si c'était une optimisation
Je suis bien content, j'ai aussi fait ma carte avec des colonnes voisins (bon sauf que j'en ai 6 et pas 4) mais cool comme info !

[Argorate]

La remarque sur l'id unique, j'ai failli te le dire (c'est la proposition que j'ai faite durant mon stage là^^) mais je savais pas si c'était pertinent pour ce problème là.

Content que tu es trouvé

PS: la solution que je t'ai proposé comprenait un seul champs "estCotiere" au lieu de quoi tu t'ai fais chier à rajouter 5 champs (si on compte l'id), je sais pas si c'est le plus simple^^

Tu as tester avec la méthode du précalcule comme je t'ai dis? ça vaut peut être le coup de comparer les résultats?


bon courage !

[Xenos]

@Ter Rowan: Stocker les liens dans la BDD ne me semble pas être de l'optimisation, c'est seulement un changement d'approche. Passer d'une table de liens à 4 (ou 6) colonnes supplémentaires dans la table des cases peut être vu comme de l'optimisation, mais ce n'est pas de la bidouille pour autant: la table de liens représente des relations type "*" (0 ou plus), alors que les colonnes représentent plutôt des relations "N", avec N fixé à l'avance (6 dans ton cas, 4 dans le mien), ou "0..N" si on autorise la valeur "NULL" à la colonne.
Tout dépend si on considère le lien entre les cases comme étant une entité à part (en ce cas, table supplémentaire obligée), ou comme faisant partie de l'entité "case" (ajout de nouvelles colonnes possible).

Si les liens peuvent être ajoutés et retirés sans limite, alors il faut passer par une table de liens.
Si les liens sont limités à 0..N, avec N fixé au lancement du jeu (ou N très peu évolutif), alors ajouter N colonnes est négociable, tant que N n'est pas "trop" grand.

---

@Argorate: En fait, j'aurai pu me passer de ce champ "Id": au lieu d'ajout 4 colonnes IdVoisinN, j'aurai pu ajouter 8 colonnes IdVoisinNx et IdVoisinNy, mais la flemme l'a un peu emportée ^^ Autant considérer que l'objet "case" est identifié par un champ "id" et non plus par ses coordonnées "x,y" (ce qui, en un sens, autorise potentiellement deux cases à se superposer, aka à avoir les mêmes coordonnées x,y).

"estCotiere" est un champ de cache. "IdVoisinN" est un champ de structure.
Avant, cela revenait à stocker la structure de la carte dans le PHP et à considérer que la BDD stocke les cases noires d'un échiquier.
Après, avec IdVoisinN, cela revient à stocker un graphe dans la BDD et ses liens (dommage que MySQL ne stocke pas certaines "tables" comme des graphes).
C'est donc plus simple au sens où idVoisinN n'a pas besoin d'être mis à jour quand les données de la BDD changent, alors que "estCotiere" devra être changé si une autre case est noyée sous la mer par exemple.

Le précalcul n'est maintenant plus nécessaire, car le calcul direct est suffisamment rapide.

---

Données spatiales

Le test avec les données spatiales n'est pas concluant du tout (d'autant que l'extension spatiale n'est pas disponible sur MySQL en mutualisé chez OVH). J'ai tenté de:

• Créer une colonne "geometrieCase" de type "POLYGON" (géométrique)
  
• Remplir cette colonne avec la forme de chaque case
  
• Poser un index spatial sur la colonne
  
• Récupérer les cases côtières via TOUCHES() dans la clause WHERE
  

Ignoblement long, je n'ai même pas eu le courage d'attendre la fin, et j'ai rebooté MySQL après 10 minutes de calcul...

Merci pour votre aide à tous
Je vais surement en avoir d'autres dans ce goût-là à vous soumettre

[niahoo]

Si tu dois gérer des cases toutes de la même taille et alignées de façon régulière (typiquement une grille ou un damier) il vaudrait mieux utiliser un type point qu'un polygone.

---

Mais tant qu'à faire autant utiliser PostGIS.

[Roworll]

Il y a peut être quelques optimisations SQL à tenter avant de penser à changer ton modèle.
As-tu regardé la manière dont MySQL traite la requête (EXPLAIN)

A vue de nez, il y a des chance qu'il parte sur un bon vieux Table Scan, vérifiant chacune de tes 512K cases.
Un petit index supplémentaire sur 'mer' et 'altitude' pourrait simplifier les choses.

As-tu essayé également d'utiliser la clause EXISTS avec un truc du genre

SELECT 

	c.x, c.y

FROM 

	cases c

WHERE 

	c.mer=0 

	AND c.altitude <= 0

	AND EXISTS (

			SELECT 1 

			FROM 

				cases m 

			WHERE 

				m.mer = 1 

				AND (m.x between c.x -1 AND c.x +1) 

				AND (m.y between c.y -1 AND c.y +1)

		)

Si MySQL est pas trop bête, la première partie de la requête devrait utiliser l'index proposé au dessus et la deuxième partie devrait pouvoir s'appuyer en partie sur ta clé primaire.

Tu peux éventuellement rajouter un index mer,x,y qui pourrait booster les perfs de la sous requête (efficacité variable en fonction de la cardinalité des valeurs)

Autre avantage : tu vas éviter la tripotée de doublon qui apparaissent dans ta requête initiale.

[Xenos]

Je n'avais pas pensé à EXPLAIN... >.>
L'index accélère légèrement, mais ce n'est pas la panacée...

Je viens de tester ta proposition, mais les performances sont mauvaises (là encore, la durée dépassant les 30secondes, je n'ai pas attendu la fin de la requête pour connaitre sa durée réelle). Cela ne me surprend pas d'un coté, car mes souvenirs de cours me disent que les sous-requêtes sont bien plus longues que les jointures, même si on parle d'une seule sous-requête face à 4 jointures. Confirmé en pratique, puisque la requête avec jointures file vite, alors que celle-ci avec la sous-requête traine.

Il me semble d'ailleurs que MySQL exécute la sous-requête pour chaque ligne retournée par la requête parente. Donc, si la requête principale (mer=0 and altitude<=0) renvoie environ 5.000 lignes, le SQL va faire 5.000 fois la sous-requête (EXISTS), ce qui dure... une éternité dirons-nous ^^

Je garderai donc la requête précédente (avec 4 jointures).

Je n'ai pas saisis ton histoire de doublons en revanche. La requête utilisée ne fait pas de doublons?!
(rappel pour éviter de retourner à la page d'avant)

UPDATE `cases` `case0`

	LEFT JOIN `cases` `case1` ON (`case1`.`id`=`case0`.`idVoisin1`)

	LEFT JOIN `cases` `case2` ON (`case2`.`id`=`case0`.`idVoisin2`)

	LEFT JOIN `cases` `case3` ON (`case3`.`id`=`case0`.`idVoisin3`)

	LEFT JOIN `cases` `case4` ON (`case4`.`id`=`case0`.`idVoisin4`)

	SET `case0`.`mer`=1

	WHERE

	`case0`.`mer`=0

	AND `case0`.`altitude`<=0

	AND (

		`case1`.`mer`=1

		OR `case2`.`mer`=1

		OR `case3`.`mer`=1

		OR `case4`.`mer`=1

	)

Même principe si j'utilise un SELECT, en récupérant case0.id, case0.x, case0.y par exemple. Bien sûr, si je récupérai "*", j'aurai les données des cases voisins (case1..4), qui donc sont déjà "présentes" ailleurs, en tant que "case0", et j'ai une forme de doublons partiels (aka, des données qui apparaissent dans plusieurs lignes de résultat, mais pas des lignes en double).

Après, pour le changement de structure, ce n'est pas plus mal: je préfère finalement disposer d'une liste des voisins pour chaque case, stockée dans la BDD, plutôt que de me reposer sur des "x+/-1,y+/-1" dans le code PHP. Cela m'arrange d'ailleurs car les bords de carte doivent être gérés différemment. En gardant la structure de map dans le PHP, il me faudrait 1 classe pour les cases normales, 1 pour les cases de la ligne du haut (bord haut de la carte), 1 pour la ligne du bas, 1 à gauche, et 1 à droite...
Donc, changer un poil la structure des tables est plus une avancée qu'une contrainte

[Roworll]

Les comportements varient vraiment entre deux moteurs SQL différents.
J'ai fait un test sur un serveur SQL Server et la différence en une jointure sur deux tables avec des milliers d'enregistrements et une sous requête est flagrante : d'après les estimations du plan de requête, le coût en CPU est carrément divisé par 100.
Évidemment, ça dépends de la répartition des données. Dans mon exemple, j'avais environ 10% de côtes / 30% de terre.
Plus il y a de cases de côtes, plus le coût sera élevé et inversement.

Pour en revenir à ton choix, stocker l'ID sur la ligne simplifie effectivement le processus et par conséquent améliore les performances.
Par contre, pourquoi ne pas pousser un peu plus loin la dénormalisation en stockant par exemple, pour chaque case voisine un flag indiquant si c'est une case de mer ou non (merVoisin1, merVoisin2, etc). Ca supprimerait le besoin de faire des jointures.
En contrepartie, ça demanderait de resynchroniser les valeurs des colonnes merVoisin à chaque changement de niveau.
Ça pourrait être intéressant si tu as souvent besoin de trouver les cases de côtes mais que le niveau des eaux ne change que rarement.

Autre possibilité : l'altitude des cases de ta carte étant fixe, tu peux tout précalculer à l'avance et stocker sur la ligne le niveaux de montée des eaux nécessaire pour submerger la case en question.

En fait, tout dépends des opérations qui sont répétées souvent.

[Xenos]

Je ne vais piocher les cases côtières que rarement, donc, je ne rajouterai pas de colonnes dénormalisantes, surtout que je n'aime pas les données redondantes.
L'altitude n'est pas fixe, c'est ce qui rendra le jeu un peu amusant :p On pourra creuser les cases (pratique pour se faire un accès à la mer), ou ériger des montagnes.

Je suis surpris que SQL server soit ainsi construit. En tous cas, l'optimiseur MySQL traite mieux les jointures que les sous-requêtes.
Peut-être que SQL serveur fait les jointures avant de faire la première sélection, alors que MySQL fait peut-être d'abord la première sélection (mer=0 and altitude<=0) et seulement ensuite les jointures.