約2000万レコードのDB(mysql)から、正規表現(REGEXP)で検索する際の高速化対応について

宜しくお願いいたします。

MysqlのREGEXP(正規表現)を用いて、2000万行の住所マスターから、特定のキーワードを含むレコードを検索する際、REGEXPの仕様でindexが効かず、結果取得にものすごい時間を要してしまいます。

likeを用いらない理由ですが、複数のキーワードで検索を行うために、REGEXPを用いております。

処理の時間を短縮する方法はありますでしょうか？
お知恵を拝借できますと幸いです。

サンプルとして、テーブル構造と、実行しているsqlを添付します。

■テーブル構造
ken_name city_name town_name aza_name address
北海道札幌市中央区北１条東１１丁目２２−４１

■SQL
SELECT DISTINCT CONCAT(IFNULL(ken_name,''),IFNULL(city_name,''),IFNULL(town_name,''),IFNULL(aza_name,''),IFNULL(address,'')), ken_name, city_name, town_name, aza_name , address
FROM phonebook_houzin
WHERE CONCAT(IFNULL(ken_name,''),IFNULL(city_name,''),IFNULL(town_name,''),IFNULL(aza_name,''),IFNULL(address,'')) REGEXP '.*北海.*中央.*北.*条.*東.*１?.4?.';