Como todos os valores são preenchidos à esquerda, você pode fazer
SELECT RIGHT(MAX(customer_id), 4) max_val
FROM table1
WHERE customer_id LIKE 'HE%'
Verifique se você tem um índice em
customer_id que você provavelmente faz com base em um nome da coluna. LIKE provavelmente irá usá-lo. Aqui está SQLFiddle demonstração
