Какая селективность индекса?
Не равно тяжёлый запрос
Пустота намекает на текстовое поле. Добавьте ещё столбец типа tinyint если поле пустое текстовое, то заносите в него 0, если не пустое то 1. Далее ищете все строки где столбец=1 Работать будет не особо быстро но лучше.