MySQL의 한 테이블에 여러 column을 동시에 PRIMARY KEY로 잡아도 인댁스는 여러개가 생기지 않는군요. 심지어 중복된 값을 막아주는 PRIMARY KEY 본래의 역할마저 하지 않습니다. 성능이 너무 심하게 나빠서 별도로 인댁스를 추가했더니 그제서야 제 속도가 납니다.

http://dev.mysql.com/doc/refman/6.0/en/create-table.html

A PRIMARY KEY can be a multiple-column index. However, you cannot create a multiple-column index using the PRIMARY KEY key attribute in a column specification. Doing so only marks that single column as primary. You must use a separate PRIMARY KEY(index_col_name, ...) clause.