@e4c5 har rätt att inget av indexen kommer att hjälpa med den aktuella frågan. Du kan börja med att lägga till följande index och ändra frågan med ytterligare villkor så att indexen används:
ALTER TABLE myTable
ADD INDEX(categoryId, value1),
ADD INDEX(categoryId, value2),
ADD INDEX(categoryId, value3),
ADD INDEX(categoryId, value4);
Och uppdatera frågan så här:
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;
De ytterligare villkoren hjälper till att minska antalet rader som ska bearbetas. Att lägga till index på fler kolumner skulle påskynda detta ytterligare, men jag föreslår att du provar detta först.