how to make this query run fast
This should help significantly (unless everything is cat 64):

INDEX(cat_id, deleted, published)


If 'they' won't add that index (or let you add it), warm up your resume.