Индексът на categoryId няма да помогне в този случай, IN (...) заявките така или иначе ще доведат до сканиране на последователност вместо търсене в индекс.
Бих обмислил първо да преработя системата, за да се отърва от избирането на множество категории и ако не е подходящо, да кеширам резултатите от заявката.
Например, можете да създадете помощна таблица items_category_groups(hash, item_id) и след клиентска заявка за множество категории хеширайте техните комбинирани идентификатори и потърсете тази таблица. Ако не бъде намерен, направете скъпо запитване и попълнете тази таблица. Ако се намери, направете евтина заявка, съединяваща тези таблици. Други инструменти за кеширане като memcached също ще работят.