Есть большая таблица с десятью колонками на 2 миллиона записей.
Семь из десяти колонок могут использоваться для фильтрации записей, 4 из которых соединяются условием AND, и 3 условием OR. Одна колонка используется для сортировки
Также должен поддерживаться pagination

Пример запроса:

SELECT *
FROM Table
WHERE
(ColA = @colA OR ColB = @colB OR ColC = @colC)
AND ColD = @colD
AND ColE = @colE
AND ColF = @colF
AND ColG = @colG
ORDER BY ColZ DESC LIMIT 10,100

Запрос строится динамически в зависимости от наличия параметров фильтрации. Могут использоваться как все 7 параметров фильтрации, так и ни одного.

При отсутствии фильтров на колонки ColA-C (которые соединяются условием OR) запрос работает очень быстро благодаря индексам для колонок ColD-G
Но как только появляется фильтр на одну из колонок ColA-C, то mysql начинает делать скан таблицы

Одиночные индексы на колонки ColA-C не помогают (mysql их просто игнорирует), что в вцелом понятно.

Была идея разбить на три запроса чтобы избежать условий OR. Работает быстро, но тогда накрывается pagination (LIMIT 10,100).
Несколько SELECT запросов, объекдиненных UNION работают хорошо до тех пор пока эти запросы не начинают вычитывать из быза большую часть записей

Как правильно оптимизировать этот запрос?