@e4c5 е прав, че нито един от индексите няма да помогне с текущата заявка. Можете да започнете, като добавите следните индекси и промените заявката с допълнителни условия, така че индексите да се използват:
ALTER TABLE myTable
ADD INDEX(categoryId, value1),
ADD INDEX(categoryId, value2),
ADD INDEX(categoryId, value3),
ADD INDEX(categoryId, value4);
И актуализирайте заявката по този начин:
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;
Допълнителните условия помагат да се стесни броят на редовете за обработка. Добавянето на индекси към повече колони би ускорило това допълнително, но предлагам първо да опитате това.