Как организовать хранение товаров-замен для оптимизации поиска?
Если замены двунаправлены независимо от уровня, то есть (по приведённому Вами примеру) A является заменой для E, то можно просто ввести ещё одно поле, которое будет одинаковым для всех товаров в одной группе замены. Что-то вроде связи многие-к-одному, но без дополнительной таблицы. Хотя никто не мешает ввести и дополнительную таблицу, чтобы дать имя группе замены.
Ну и, само собой, индекс по этому дополнительному полю.
Тут надо смотреть, насколько часто меняется список замен. Если не часто, то держать две таблицы - основной набор, как у Вас сейчас, и кэшированный список вида ('A' - 'B,C,D,E'), перестраивая его при изменении основного набора.