No, I did not post a wrong thing, funnily enough the EXPLAINs look exactly the same.
I applied the Index you suggested on nachname, user_id. Should/Could I delete my index on user_id or is it better to keep it? If I understood it correctly a search could not use only the second part of a multiple index, right? In this case I better have to keep both of them (which would be no problem. The table is updated seldomly).
In the explain below the only possible key he finds is the single user_id-index and not the new index on nachname, user_id. Why? Is it because the Join uses this key?
new EXPLAIN:
mysql> EXPLAIN SELECT user.id FROM user, person WHERE user.id = person.user_id AND person.nachname like '%heg%';
+----+-------------+--------+--------+---------------+---------+---------+--------------------------+-------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+--------+---------------+---------+---------+--------------------------+-------+--------------------------+
| 1 | SIMPLE | person | ALL | fk_user | NULL | NULL | NULL | 11391 | Using where |
| 1 | SIMPLE | user | eq_ref | PRIMARY | PRIMARY | 4 | mystudy13.person.user_id | 1 | Using where; Using index |
+----+-------------+--------+--------+---------------+---------+---------+--------------------------+-------+--------------------------+
2 rows in set (0.00 sec)
The query is faster indeed, but I am not yet entirely sure, whether it didn't got slow again because the last optimizing is not that far. In the afternoon I will know more about that.
Is it always better to have the tables on top of the EXPLAIN-output that contains the column I do my search on? Say the not "joined-only" tables?