RDBMSのテーブルにINDEX（セカンダリINDEX）を作成する場合、よく「カーディナリティが低いカラムには作るな」と言われます。
どんな場合でも当てはまるのか、少し実験して確かめてみます。
カーディナリティとは
今さら解説するまでもないかもしれませんが、「あるカラムにおける、取りうる値の種類」のことです。
ER図など、DBに絡む場面で別の意味で使われることもありますが、ここではこの意味で使います。
例えば、性別を表すカラムがあり、必須で値を入れなければならない場合は、「男性」「女性」の2種類、です。
「カーディナリティが低いカラムにINDEXを張るな」の意味
先に挙げた「性別」の場合、もし対象となる全レコードで男女の比率がほぼ１：１であれば、INDEXで絞り込める範囲は1/2程度です。絞り込みの効果があまりありません。
このような場合は、わざわざセカンダリINDEXを使うのではなく、テーブル全体（MySQLで言えば主キー＝PRYMARY KEYのINDEX全体）をスキャンして対象を見つけて行ったほうが効率が良い可能性が高いです。
ただ、ここで挙げた例は「それぞれの値の比率がほぼ等しい」場合です。「男性」の比率が極端に高い中から「女性」を見つけたい、という場合はどうでしょうか？
MySQLのクエリ実行計画について
少し古いですが、Oracle ACEのSH2さんが「MySQL SQLオプティマイザのコスト計算アルゴリズム」という資料を公開されています。
MySQL SQLオプティマイザのコスト計算アルゴリズム（PDF資料）
ここで挙げられている例は、「UNIQUEなINDEX（PRIMARY KEY）から範囲検索する」ですが、非UNIQUEなセカンダリINDEXから特定の値を検索する場合も、一種の範囲（RANGE）検索になります。
資料に示されているとおり、MySQL（InnoDB）は、INDEX統計情報をそのまま利用するのではなく、利用できそうなINDEXのページを実際にスキャンして、対象となるレコードの数を見積もります。
カーディナリティが低いカラムのINDEXから特定の値をスキャンする場合、
- 「特定の値を持つ最初のレコード」を保持するINDEXページ と
- 「特定の値を持つ最後のレコード」を保持するINDEXページ
の間をスキャンすることで（多すぎる場合は途中で打ち切る）、レコード数を推計します。
推計の結果、テーブル（主キーのINDEX）全体をスキャンするよりも効率的であれば、カーディナリティが低いカラムのINDEXが使われる、ということになるようです。
※このあたりの処理は、バージョンが上がるごとに「進化」してきているようです。
- MySQL 5.1：「ルートページ」と「最初のレコードを持つページ」・「最後のレコードを持つページ」だけを使って推計
- MySQL 5.5：途中のページも9ページまで使って推計
- MySQL 5.6：複数の範囲を一度に検索しなければならない場合（非UNIQUEなINDEXでIN句にたくさんの定数を指定する等）INDEX統計情報を使う
- MySQL 5.7：コスト計算アルゴリズムの間違いの修正と係数調整機能の追加
MySQL InnoDB Deep Talk #1 復習（SH2さん）
MySQL 5.6 リファレンスマニュアル rangeの最適化（8.2.1.3.3 複数値比較の等価範囲の最適化）
漢のコンピュータ道 MySQL User Conference Tokyo 2015で発表しました：MySQL 5.7におけるオプティマイザの改良点（Oracle奥野さん）
実験
主キー（id）、商品名（name：NOT NULL）、フラグ（flag：NOT NULL）からなる単純なテーブルを作成し、
- flagにINDEXを作成
- 10,000行のレコードを挿入
- うち、10行だけ、flagを「0」に（ほかは「1」）
します。
mysql> DESC test_data;
+-------+-------------+------+-----+---------+-------+
| Field | Type | Null | Key | Default | Extra |
+-------+-------------+------+-----+---------+-------+
| id | bigint(20) | NO | PRI | NULL | |
| name | varchar(40) | NO | | NULL | |
| flag | int(1) | NO | MUL | NULL | |
+-------+-------------+------+-----+---------+-------+
3 rows in set (0.00 sec)
mysql> SELECT * FROM test_data;
+-------+--------------+------+
| id | name | flag |
+-------+--------------+------+
| 1 | shouhin00001 | 1 |
| 2 | shouhin00002 | 1 |
| 3 | shouhin00003 | 1 |
| 4 | shouhin00004 | 1 |
| 5 | shouhin00005 | 1 |
| 6 | shouhin00006 | 1 |
| 7 | shouhin00007 | 1 |
| 8 | shouhin00008 | 1 |
| 9 | shouhin00009 | 1 |
| 10 | shouhin00010 | 1 |
| 11 | shouhin00011 | 1 |
| 12 | shouhin00012 | 1 |
| 13 | shouhin00013 | 1 |
| 14 | shouhin00014 | 1 |
| 15 | shouhin00015 | 1 |
（中略）
| 9986 | shouhin09986 | 1 |
| 9987 | shouhin09987 | 1 |
| 9988 | shouhin09988 | 1 |
| 9989 | shouhin09989 | 1 |
| 9990 | shouhin09990 | 1 |
| 9991 | shouhin09991 | 0 |
| 9992 | shouhin09992 | 0 |
| 9993 | shouhin09993 | 0 |
| 9994 | shouhin09994 | 0 |
| 9995 | shouhin09995 | 0 |
| 9996 | shouhin09996 | 0 |
| 9997 | shouhin09997 | 0 |
| 9998 | shouhin09998 | 0 |
| 9999 | shouhin09999 | 0 |
| 10000 | shouhin10000 | 0 |
+-------+--------------+------+
10000 rows in set (0.00 sec)
mysql> SHOW INDEX FROM test_data\G
*************************** 1. row ***************************
Table: test_data
Non_unique: 0
Key_name: PRIMARY
Seq_in_index: 1
Column_name: id
Collation: A
Cardinality: 10207
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
*************************** 2. row ***************************
Table: test_data
Non_unique: 1
Key_name: idx_flag
Seq_in_index: 1
Column_name: flag
Collation: A
Cardinality: 2
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
2 rows in set (0.00 sec)
セカンダリINDEX「idx_flag」のカーディナリティが「2」になっています。
この状態で、「flagが0のレコードを1に更新する」UPDATE文のEXPLAINを取ってみます（未処理を処理済みにする、みたいなイメージです）。
mysql> EXPLAIN UPDATE test_data SET flag = 1 WHERE flag = 0;
+----+-------------+-----------+------------+-------+---------------+----------+---------+-------+------+----------+------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-----------+------------+-------+---------------+----------+---------+-------+------+----------+------------------------------+
| 1 | UPDATE | test_data | NULL | range | idx_flag | idx_flag | 4 | const | 10 | 100.00 | Using where; Using temporary |
+----+-------------+-----------+------------+-------+---------------+----------+---------+-------+------+----------+------------------------------+
1 row in set (0.00 sec)
「idx_flag」が選択され、行数（rows）も「10」と見積もられています。カーディナリティが低くても、セカンダリINDEXが利用されるようです。
逆に、「flagが1のレコードを0に更新する」UPDATE文はどうでしょうか？
mysql> EXPLAIN UPDATE test_data SET flag = 0 WHERE flag = 1;
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------+
| 1 | UPDATE | test_data | NULL | index | idx_flag | PRIMARY | 8 | NULL | 10207 | 100.00 | Using where; Using temporary |
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------+
1 row in set (0.00 sec)
「PRIMARY」が選択され、行数も「10207」（⇒全行スキャン、但し統計情報からの取得なので不正確）です。
まとめ
このように、「未処理のデータを抽出して更新するとともに、処理済みのフラグを立てたい」というような場合には、カーディナリティの低いカラムにINDEXを張ることは「無駄」ではありません。ちゃんと使えます。
OracleやPostgreSQLでは、統計情報として、カーディナリティ以外にヒストグラム（値の分布）も持っているため、カーディナリティが低くても値の分布が偏っている場合には、INDEXが使える可能性があります。
結局、
「カーディナリティが低いカラムにINDEXを張るな」
は必ずしも正しいことではなく、
「絞り込み効果が低いカラムにINDEXを張るな」
というのが正しいです。
2017/10/01追記：
MySQL 8.0.3 RCでは、オプティマイザでヒストグラム統計が使えるようになりました。
こちらで取り上げた目的で使うのであれば、INDEXよりもヒストグラム統計を使うほうが良いケースもありそうです（8.0がGAになった後、旧バージョンからの移行ができれば、の話ですが）。
おまけ
先のケースではUPDATE文で実験してみましたが、SELECT文では…
mysql> EXPLAIN SELECT * FROM test_data WHERE flag = 0;
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
| 1 | SIMPLE | test_data | NULL | ref | idx_flag | idx_flag | 4 | const | 10 | 100.00 | NULL |
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
1 row in set, 1 warnings (0.00 sec)
mysql> EXPLAIN SELECT * FROM test_data WHERE flag = 1;
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
| 1 | SIMPLE | test_data | NULL | ref | idx_flag | idx_flag | 4 | const | 5103 | 100.00 | NULL |
+----+-------------+-----------+------------+------+---------------+----------+---------+-------+------+----------+-------+
1 row in set, 1 warnings (0.00 sec)
あれ、なんだか変ですね。
前者はいいとして、後者は…？
半分にしか絞り込めなくても、セカンダリINDEXを使う…？
まあ、EXPLAINなので、実際の実行計画がこの通りになるとは限りませんが…。
※warningが出ていますね。「SHOW WARNINGS\G」もしてみましょう。