Я бы попробовал следующее: хранить все 4 бита совместно в одном индексированном поле (назовем его bits), имеющем тип TINYINT UNSIGNED (либо BIT(4), либо SET).
А запросы бы делал в виде:
SELECT * FROM table WHERE bits IN (...)
Где вместо многоточия должны быть перечислены те значения, которые удовлетворяют маске. Для маски, указанной вами в примере, запрос примет вид:
SELECT * FROM table WHERE bits IN (b'1001', b'1011')
На мой взгляд, при таком подходе и место экономится, и производительность будет наилучшей.
