お世話になります。

商品数500、カテゴリ数130（3階層）のショップをセットアップしましたが、トップを含む各ページのレスポンスが5-10秒と非常に遅い状態です。
mysqlにlog-slow-queriesをつけてクエリの状況を見ると、商品一覧取得のクエリ１つのRows_examinedが100万以上あり、これだけで5秒かかっていました。
インデックスもいろいろ試していますが効果が出ていません。
このパターンのインデックスを張ると効果的、といった何か良い対策がありましたらお教えください。

環境は以下の通りです。
[EC-CUBE] 2.1.2
[サーバ] 単独
[OS] CentOS5
[PHP] PHP 5.1.6
[データベース] MySQL 5.0.45
[WEBサーバ] apache2.2.3
[ブラウザ] IE7

よろしくお願いいたします。