小岩です。
ちょうど私もとある実験のために500万件のダミーデータを作ってこれからテストに
入るところだったんです。

>(1)select count(*) from Test_all_tab where lotno like 'D15A0%'
>この時、該当レコードは717505件あります。検索時間(3回の平均)は
> Empress:37.5 sec    MySQL:553.36 sec

これはひどいですねー。私のところでは

>mysql> desc sample;
>+----------+---------+------+-----+---------+-------+
>| Field    | Type    | Null | Key | Default | Extra |
>+----------+---------+------+-----+---------+-------+
>| slip_no  | char(8) |      | PRI |         |       |
>| reg_time | char(2) | YES  |     | NULL    |       |
>| wday     | char(1) | YES  |     | NULL    |       |
>| item_no  | char(6) | YES  |     | NULL    |       |
>| sex      | char(1) | YES  |     | NULL    |       |
>| age      | int(11) | YES  |     | NULL    |       |
>| weather  | char(1) | YES  |     | NULL    |       |
>| max_temp | int(11) | YES  |     | NULL    |       |
>| min_temp | int(11) | YES  |     | NULL    |       |
>+----------+---------+------+-----+---------+-------+
>9 rows in set (0.00 sec)
>
>mysql> select count(*) from sample;
>+----------+
>| count(*) |
>+----------+
>|  5000000 |
>+----------+
>1 row in set (0.02 sec)
>
>mysql>

となります。ちなみにMMX Pentium 200MHzのLinuxBoxです。

>(2)select count(*) from Test_all_tab where stop_day between '1998/11/14 
>00:00:00' \
>   and '1998/12/14 23:59:59'
>この時、該当レコードは1118730件あります。検索時間(3回の平均)は
> Empress:6.5 sec     MySQL:385.8 sec

これと同様に、全くインデックスをはっていないフィールドを対象にしてbetweenで
検索かけてみますと

>mysql> select count(*) from sample where age between '10' and '30';
>+----------+
>| count(*) |
>+----------+
>|  1105283 |
>+----------+
>1 row in set (55.09 sec)
>
>mysql>

という結果になりました。何かが根本的におかしいんじゃないかと思います。
mysqldの起動時には自慢じゃないですが --skip-locking 以外はな〜んにもオプシ
ョンをつけてません。

 ちなみにまだチューニングに入っていないんですが、ODBC経由で500万件から多次
元分析しようとすると気が狂いそうな遅さではありますが……。商用な話なんで、
デモった結果によっては村上さんのところにお世話になりそうです。よろしくお願
いします。