Não, uma pesquisa de expressão regular não pode usar um índice. Se a coisa à qual você está aplicando o regex é um índice, pode ser um pouco mais rápido, mas você está essencialmente verificando a tabela.

A única solução que conheço é usar LIKE 'foo%' em vez de RLIKE 'foo.*' se esse é o seu regex. Um índice em tal coluna pode usar o LIKE, mas não o RLIKE