В БД 3 таблицы: 2 сущности и связь многие-ко-многим.
В таблице связей - 50 млн. строк и их количество не спеша растет (условное ограничение сверху в 500 млн.)
При том количестве, что есть сейчас, начинают тормозить запросы выборки (в запросах приходится 2 раза join'ить пусть и ограниченную, но объемную таблицу связей). Требуется оптимизировать базу.

Структура данных такова, что привязки от одной таблицы сущностей к другой типизированы, и каждого типа может быть одна связь. Число типов привязок порядка 1000, но в среднем 50. Связь многие-ко-многим хорошо хранит достаточно разряженные данные и более проста, но работала при меньшем количестве данных.

Размышляю над тремя подходами оптимизации (которые можно комбинировать):
1. Разбить таблицу связей на несколько таблиц, выделив в каждую свой блок связей.
2. Добавить в одну таблицу сущностей много-много колонок (для каждого типа связи), и ставить ссылку напрямую.
3. Формировать по мере заведения данных дополнительные таблицы для отчетов (набор полей заранее известен). В случае изменения набора данных (которое будет предположительно не частым) их придется пересоздавать.

Объем работы не существенен. Важно, чтобы решение надолго обеспечило хорошую производительность.

Кто сталкивался с подобной задачей, какой подход более серьезный?

ps. БД Oracle 10g, Standard Edition

Все индексы есть. Среднее время выполнения запросов на локальной машине 1-5 минут. Требуется быстрее. Какой будет сервер неизвестно, возможно слабый.