Per rispondere direttamente alla tua domanda:sì, puoi indicizzare a sinistra(zip, 5).
alter table tblName add index (zip(5));
E se vuoi che la query sia in grado di utilizzare l'indice per cercare tutte le colonne:
alter table tblName add index (cat_id, subcat_id, zip(5));
