Was it indexing the faux-enum columns? First thing I would do would be to drop the index if there is one considering it will add very little to the selectivity

Was it indexing the faux-enum columns? First thing I would do would be to drop the index if there is one considering it will add very little to the selectivity of the query.