箕畑＠旭紙業です。
既に誰かが同じことを投稿されたかもしれませんが、

> ■OR連結の場合のEXPLAINの結果
> +---------+------+-------------------+------+---------+------+--------+------------+
> | table   | type | possible_keys     | key  | key_len | ref  | rows   | Extra      |
> +---------+------+-------------------+------+---------+------+--------+------------+
> | keytbls | ALL  | key01,key02,key03 | NULL |    NULL | NULL | 195744 | where used |
> +---------+------+-------------------+------+---------+------+--------+------------+

を見ると、どうやらMySQLは
「インデックス使っても効果なさそうだから使わない」
ということで結審しちゃったようですね。
# 間違ってたらごめんなさい。
この判決を覆すには、多分MySQLのソースに手を加えるしかなさそうです。
その代わりに、次のようにテーブルの定義から見直されると如何でしょう。


main
+--+--------+
|id|  data  |
+--+--------+
| 1|     ***|
| 2|     ???|
| 3|     +++|
...

keywords
+--+-----------+
|id|  keyword  |
+--+-----------+
| 1|       Perl|
| 1|         is|
| 2|         an|
| 3|interpreted|
| 3|   language|
| 3|  optimized|
...

というふうに2つのテーブルに分割して、
キーワード検索の場合は、

SELECT DISTINCT main.data
   FROM main, keywords
   WHERE keywords.keyword LIKE 'i%' AND keywords.id=main.id

というふうにテーブルを結合するようにすれば、
1レコードあたりのキーワード数を3個(あるいは12個と)
固定する必要がなくなります。

また、検索に必要なインデックスは
  mainテーブルの id項(UNIQUE)
  keywordsテーブルの keyword項
の2つです。
# 頻繁にDELETEやUPDATEする場合は、
# keywordsテーブルのid項 にもインデックスを
# 作っておいた方がいいでしょう。


--
有限会社アイピーシー/旭紙業株式会社
箕畑典男
minohata@xxxxxxxxxx