Я не считаю таблицу с 20 миллионами записей слишком большой для поиска. Вы можете выполнить некоторую фильтрацию и, выбрав в поиске только необходимые столбцы, вы можете оптимизировать его для использования небольшого объема памяти.
Например, если у вас есть ключевой столбец типа int и столбец varchar размера 10, необходимый для поиска, запись займет 4 + 10 байт, а 20 миллионов перейдет к 20Mx (4 + 10) ~ = 280 МБ, что нельзя считать как слишком высоко.
Тем не менее, если вы хотите сократить использование памяти, вам придется использовать объединения.