例

以下のようなテーブルがあるとします。

テーブル名	内容
report	報告書本体
report_user	各報告書の未読情報（ユーザ別）

report_userテーブル定義はこんな感じです（reportテーブルは、report_noカラムがPRIMARY KEY。他の列は省略）。

mysql> SHOW CREATE TABLE report_user\G
*************************** 1. row ***************************
       Table: report_user
Create Table: CREATE TABLE `report_user` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `report_no` bigint(20) NOT NULL,
  `report_user_no` bigint(20) NOT NULL,
  `read_flag` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_reportno` (`report_no`)
) ENGINE=InnoDB AUTO_INCREMENT=XXXXXXXX DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

これらを結合し、あるユーザについて、未読の報告書が何件あるか、抽出してみます。

※注意（言い訳）

シンプルな実行計画しか持たない、MySQL 5.5を使って実験しています。
「外部キー制約が正しく張られていてテーブル間のデータ不整合がなければ、JOINしなくてもreport_user側だけで未読件数が取得できるではないか」とツッコミが入るかもしれませんが、実際には「reportテーブルに結合すべきテーブルが他にもある」ものと思ってください（説明を簡単にするために排除しています）。
「report_userのレコードの有無だけで未読／既読の判断ができるじゃん」とのツッコミもありそうですが、「未読」にも複数の状態があるために、あえてread_flag列が設けられているものと思ってください。
「そんな方法で未読管理するのはけしからん」というツッコミも…（以下略）。

…段々言い訳が苦しくなってきた。

気を取り直して…

mysql> SELECT COUNT(r.report_no) AS report_count FROM report r INNER JOIN report_user ru ON r.report_no = ru.report_no AND ru.report_user_no = XXXX WHERE ru.read_flag = 0;
+--------------+
| report_count |
+--------------+
|        48850 |
+--------------+
1 row in set (4.89 sec)

5秒くらいかかりました。
EXPLAINで実行計画を見てみます。

mysql> EXPLAIN EXTENDED SELECT COUNT(r.report_no) AS report_count FROM report r INNER JOIN report_user ru ON r.report_no = ru.report_no AND ru.report_user_no = XXXX WHERE ru.read_flag = 0;
+----+-------------+-------+-------+---------------+--------------+---------+--------------------+-------+----------+-------------+
| id | select_type | table | type  | possible_keys | key          | key_len | ref                | rows  | filtered | Extra       |
+----+-------------+-------+-------+---------------+--------------+---------+--------------------+-------+----------+-------------+
|  1 | SIMPLE      | r     | index | PRIMARY       | idx_hogefuga | 3       | NULL               | 89790 |   100.00 | Using index |
|  1 | SIMPLE      | ru    | ref   | idx_reportno  | idx_reportno | 8       | r.report_no        |    40 |   100.00 | Using where |
+----+-------------+-------+-------+---------------+--------------+---------+--------------------+-------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)

※WARNINGが出ているのは「EXTENDED」を指定しているからです。気にしないでください。

idx_reportnoが非UNIQUEなので、typeがrefになっていて、rowsを見ても一意に選択されておらず、Extra列に「Using where」が出力されています。

これを、

report_noとreport_userの組み合わせで、一意に絞り込めるようにする（UNIQUEを指定）
さらに、read_flagもINDEXの列に追加することで、カバリングINDEXにしてみる（INDEX列だけで必要データが取得できるように）

と、どうなるのか、試してみます。

ALTER文

mysql> ALTER TABLE report_user DROP INDEX idx_reportno, ADD UNIQUE idx_reportno (report_no,report_user_no,read_flag);

変更後のテーブル定義

mysql> SHOW CREATE TABLE report_user\G
*************************** 1. row ***************************
       Table: report_user
Create Table: CREATE TABLE `report_user` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `report_no` bigint(20) NOT NULL,
  `report_user_no` bigint(20) NOT NULL,
  `read_flag` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_reportno` (`report_no`,`report_user_no`,`read_flag`)
) ENGINE=InnoDB AUTO_INCREMENT=XXXXXXXX DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

結果

mysql> SELECT COUNT(r.report_no) AS report_count FROM report r INNER JOIN report_user ru ON r.report_no = ru.report_no AND ru.report_user_no = XXXX WHERE ru.read_flag = 0;

+--------------+
| report_count |
+--------------+
|        48850 |
+--------------+
1 row in set (0.44 sec)

かなり短縮されました。

EXPLAINを見てみると、

mysql> EXPLAIN EXTENDED SELECT COUNT(r.report_no) AS report_count FROM report r INNER JOIN report_user ru ON r.report_no = ru.report_no AND ru.report_user_no = XXXX WHERE ru.read_flag = 0;
+----+-------------+-------+--------+---------------+--------------+---------+--------------------------------+-------+----------+-------------+
| id | select_type | table | type   | possible_keys | key          | key_len | ref                            | rows  | filtered | Extra       |
+----+-------------+-------+--------+---------------+--------------+---------+--------------------------------+-------+----------+-------------+
|  1 | SIMPLE      | r     | index  | PRIMARY       | idx_hogefuga | 3       | NULL                           | 68050 |   100.00 | Using index |
|  1 | SIMPLE      | ru    | eq_ref | idx_reportno  | idx_reportno | 20      | r.report_no,const,const        |     1 |   100.00 | Using index |
+----+-------------+-------+--------+---------------+--------------+---------+--------------------------------+-------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)

UNIQUEなINDEXで一意に絞り込んでJOINしているので、typeがeq_ref、rowsが1に変わりました。Extra列が「Using index」となり、カバリングINDEXが効いていることがわかります。
また、よく見ると、reportテーブル側の取得見積もり行数も減っています。

※それぞれの取得見積もり行数次第で、外部表と内部表が入れ替わる可能性もあります。

注意点

INDEX（セカンダリINDEX）を増やすと、当然ですが容量が増加します。また、挿入・更新性能も低下します。
あまり多くのカラムをカバリングINDEX化すると、かえって別の個所で性能低下しかねないので、注意しましょう。

MySQLでカバリングINDEXを使った例

例

結果

注意点