Rendimiento de MySQL de la consulta al agregar columnas en la cláusula where

@e4c5 tiene razón en que ninguno de los índices ayudará con la consulta actual. Puede comenzar agregando los siguientes índices y modificar la consulta con condiciones adicionales para que se utilicen los índices:

ALTER TABLE myTable
ADD INDEX(categoryId, value1),
ADD INDEX(categoryId, value2),
ADD INDEX(categoryId, value3),
ADD INDEX(categoryId, value4);

Y actualice la consulta de esta manera:

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;

Las condiciones adicionales ayudan a reducir el número de filas a procesar. Agregar índices en más columnas aceleraría esto aún más, pero sugiero probar esto primero.