För att svara direkt på din fråga:ja, du kan indexera vänster(zip, 5).
alter table tblName add index (zip(5));
Och om du vill att frågan ska kunna använda indexet för att söka i alla kolumner:
alter table tblName add index (cat_id, subcat_id, zip(5));