Rendre une requête SQL plus rapide

Bonjour à tous !

Petite mise en situation...
Je programme un MMORPG. Mon problème concerne la "map" du jeu, qui est en trois dimensions. Donc chaque "case" ou "point" de référence possède une position sur trois axes (x, y et z).
Si on compte tous les points possibles sur la carte, on arrive à près de 2 millions de possibilités (1 800 000 pour être précis) dans la même table. J'ai besoin régulièrement d'aller chercher de l'information sur les différents points, et bien que chaque requête ne me retourne typiquement que 10 résultats environ, on se doute que sortir le résultat peut être long. En fait, en moyenne, une requête prend près de 0,8 seconde.
Considérant que je compte avoir des centaines, voire des milliers d'utilisateurs sur mon jeu, c'est énorme.

Quelqu'un aurait-il quelques conseils pour m'aider à rendre mes requêtes plus rapides ?

Jusque là, j'ai essayé de faire des subqueries pour d'abord pré-limiter le nombre de réponses possibles (en demandant, par exemple, de me sortir uniquement les espaces de la carte possédant le même point Z que la ville "capitale" du joueur) puis de faire la requête principale parmi ces résultats, mais c'est encore plus long. Je commence à considérer de diviser la table "map" en neuf tables (puisque l'axe Z n'a que neuf unités en tout), mais je voulais savoir s'il existait une autre solution auparavant.

Merci à tous !