@e4c5 está certo que nenhum dos índices ajudará na consulta atual. Você pode começar adicionando os seguintes índices e alterar a consulta com condições adicionais para que os índices sejam usados:
ALTER TABLE myTable
ADD INDEX(categoryId, value1),
ADD INDEX(categoryId, value2),
ADD INDEX(categoryId, value3),
ADD INDEX(categoryId, value4);
E atualize a consulta assim:
SELECT * FROM myTable WHERE categoryId = 1 AND (value1 <= 9) AND (value2 <= 9) AND (value3 <= 9) AND (value4 <= 9) AND (value1 + value2 + value3 + value4) > 9;
SELECT * FROM myTable WHERE categoryId = 1 AND (value1 <= 5) AND (value3 <= 5) AND (value4 <= 5) AND (value1 + value3 + value4) > 5;
As condições adicionais ajudam a restringir o número de linhas a serem processadas. Adicionar índices em mais colunas aceleraria ainda mais, mas sugiro tentar isso primeiro.
