Be careful... you really don't want to create anymore indexes than necessary. Even though you might see a performance increase in your test by building a bunch of extra indexes you might end up causing performance problems in other parts of the system. Remember, that whenever a rows are inserted or deleted there is an additional work that has to be for each index. Just like everything else in programming you have to strike a balance.

Looking at the query you had problems with I am guessing that the only indexes that are going to help are to build an index for user_id and characteristic_id for both tables. Generally, columns that appear in join conditions are good candidates for building an index.