Если столбцов много (миллионы-миллиарды), то обычный подход с индексами и WHERE не подойдет. Не так давно я сталкивался с подобной проблемой. Варианты я вижу такие:
1. Sphinx. Предназначен для полнотекстового поиска, но может искать и только по числовым полям (при docinfo=extern). Если записей в базе много, то он сильно расходует память. Работает быстро.
2. Таблицы в памяти. Аналогично п. 1.
3. EAV или хранение каждого поля в отдельной таблице. Немного медленнее, если пользователь задал мало параметров, и намного — если много.
4. OLAP-подобные способы. Самые большие требования к памяти и к дисковому пространству (при большом количестве вариантов — запредельные), но быстрый поиск по большому количеству параметров.
Для себя я решил, что оптимальный вариант — это Sphinx (docinfo=inline) при необходимости текстового поиска, а при отсутствии такой необходимости — комбинированный вариант п. 3 и 4, т.е. OLAP-подобная индексация работает только для наиболее частых вариантов полей.