Pour que les requêtes soient rapides, vous devez avoir une clef unique pour vos tables spatiales et un index sur cette clef unique.
Vous pouvez spécifier quelle clef unique doit être utilisée par Mapserver, en utilisant la clause : USING UNIQUE dans votre ligne DATA :
DATA "the_geom FROM geotable USING UNIQUE gid"
Si votre table n'a pas de colonne explicitement unique, vous pouvez "faire semblant" de rendre une colonne unique en utilisant la colonne PostgreSQL "oid" comme colonne unique. "oid" est la colonne unique par défaut si vous n'en déclarez pas une, donc pour améliorer le temps d'exécution de vos requêtes vous devez créer des indexes sur les valeurs oid de vos tables spatiales.
postgis# CREATE INDEX geotable_oid_idx ON geotable (oid);