Как оптимизировать NOT IN (SELECT)?
SELECT `item_id`, ... 
FROM `items_table` AS t1
LEFT JOIN `shown_table` AS t2 on t1.`item_id`=t2.`shown_id`
WHERE [сложное условие для поиска] 
AND  t2.`user_id`=$user_id AND t2.`item_id` IS NULL
LIMIT 1;
Это может тормозить, если записей в таблице shown_table у одного пользователя будут десятки или сотни тысяч строк. Чтобы такого не было, удаляй старые, например. А вообще вряд ли столько накопится.

Индексы тут только усугубят ситуацию, потому что это не серебряная пуля, у них есть плюсы и минусы свои.  Лишние индексы раздувают размер таблицы и тормозят вставку/обновление.

Вам хватит индекса на shown_table.user_id и items_table.item_id