Смотря что за where, какие поля часто используются, какие редко, какие значения.
В целом — бить на части 2 способами
1) На несколько таблиц по «строкам». К примеру на две — в одной a от 0 до 127, в другой от 128 до 256.
2) На несколько таблиц по «столбцам». К примеру ace и bdf и может быть даже acdf — в зависимости от того, поиск по каким полям идет чаще или в группах.
По сути это те же индексы, но поскольку Вы уменьшаете объем для raw поиска, производительность может повыситься.
Так же может иметь смысл сделать не 4 поля abcd, а скукожить их в одно поле int типа допустим, и навесить индекс на него (может оказаться лучше чем составной по abcd).
И наконец, если не слишком жалко памяти, даже при 100 миллионах записей, можно попытаться пихнуть таблицы в память:) Смотря насколько толстые строки.