「北海道」の方が「長野県」よりデータが多いので……。
2値といっても分布は偏っています。

mysql> select flag1, count(*) from ken_all where ad1 = '北海道' group by
flag1;
+-------+----------+
| flag1 | count(*) |
+-------+----------+
| 0     |     7875 |
| 1     |      327 |
+-------+----------+
2 rows in set (1.67 sec)

で、下記のごとくなりました。flag1が0に対する検索と1に対する検索でそれこそ
「劇的」に違います。0の場合は「インデックスを張るだけ邪魔」状態です。
ちなみに他の列には一切インデックスは張ってません。


mysql> select count(*) from ken_all where flag1 = '0' and ad1 = '北海道';
+----------+
| count(*) |
+----------+
|     7875 |
+----------+
1 row in set (5.34 sec)

mysql> create index ken_all_01 on ken_all(ad1);
Query OK, 120162 rows affected (42.07 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql> select count(*) from ken_all where flag1 = '0' and ad1 = '北海道';
+----------+
| count(*) |
+----------+
|     7875 |
+----------+
1 row in set (1.05 sec)

mysql> drop index ken_all_01 on ken_all;
Query OK, 120162 rows affected (16.05 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql> create index ken_all_01 on ken_all(flag1);
Query OK, 120162 rows affected (42.98 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql> select count(*) from ken_all where flag1 = '0' and ad1 = '北海道';
+----------+
| count(*) |
+----------+
|     7875 |
+----------+
1 row in set (5.73 sec)

mysql> drop index ken_all_01 on ken_all;
Query OK, 120162 rows affected (14.50 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql> select count(*) from ken_all where flag1 = '1' and ad1 = '北海道';
+----------+
| count(*) |
+----------+
|      327 |
+----------+
1 row in set (6.49 sec)

mysql> create index ken_all_01 on ken_all(ad1);
Query OK, 120162 rows affected (42.47 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql> select count(*) from ken_all where flag1 = '1' and ad1 = '北海道';
+----------+
| count(*) |
+----------+
|      327 |
+----------+
1 row in set (0.95 sec)

mysql> drop index ken_all_01 on ken_all;
Query OK, 120162 rows affected (16.30 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql> create index ken_all_01 on ken_all(flag1);
Query OK, 120162 rows affected (44.24 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql> select count(*) from ken_all where flag1 = '1' and ad1 = '北海道';
+----------+
| count(*) |
+----------+
|      327 |
+----------+
1 row in set (0.30 sec)

mysql> drop index ken_all_01 on ken_all;
Query OK, 120162 rows affected (15.61 sec)
Records: 120162  Duplicates: 0  Warnings: 0

mysql>