O índice em categoryId não ajudará neste caso, as consultas IN (...) produzirão varredura de sequência em vez de pesquisa de índice de qualquer maneira.

Eu consideraria primeiro redesenhar o sistema para se livrar da seleção de várias categorias e, se não for apropriado, armazenar em cache os resultados da consulta.

Por exemplo, você pode criar uma tabela auxiliar items_category_groups(hash, item_id) e, após a consulta do cliente em várias categorias, fazer hash de seus IDs combinados e pesquisar esta tabela. Caso não encontre, faça uma consulta cara e preencha esta tabela. Se encontrado, faça uma consulta barata juntando essas tabelas. Outras ferramentas de cache, como o memcached, também funcionarão.