MySQL Join is taking too long

I need some help optimizing a MySQL query or table

When I run this query it return in .01s with 650 records:

  select mm, name, display, year
  from tbl d
  where active = 1 and tbl2_id = 'val' and lvl_id = 9
  order by mm;

When I run this query it return in over 15s with the same records:

  select d.mm, d.name, d.display, d.year, a.year year2
  from tbl d left join tbl a on d.mm = a.mm and a.tbl2_id = 'val2'
  where d.active = 1 and d.tbl2_id = 'val' and d.lvl_id = 9
  order by d.mm;

When I run it like this it also take over 15s:

  select mm, name, display, year, 
      (select a.year from tbl a where a.mm = mm and a.tbl2_id = 'val2') year2
  from tbl 
  where active = 1 and tbl2_id = 'val' and lvl_id = 9
  order by mm;

the table has multiple records for mm. I need to get all records where tbl2_id = 'val' and if there is a record for that mm where tbl2_id = 'val2', I need the value of "year" from the val2 record. tbl currently has 13k records in it and there are no more then 10 records for any given mm so I don't think think this query should be taking over 15s. I have indexes mm, active, tbl2_id and lvl_id.

I've done similar things in MSSQL with almost no delay.

You could start by introducing composite indexes on your table on (tbl2_id, lvl_id, active) and (tbl2_id, mm). That would likely speed up all three of your queries.

Whenever you use multiple fields in a WHERE clause, it makes sense to consider a composite index. In case only single-column indexes are present, the query can use only one of those indexes for a seek while having to resort to a slower scan to search the remaining subset. The difference between MySQL and MSSQL in this respect might be that MSSQL makes a better guess which of those three to use based on the cardinality of your data (the best one to use would be the one that leaves the smallest subset for the scan), although this is hard to say without examining the two query plans in detail.

Can you provide a DESCRIBE of the tables and the EXPLAIN of the query?

There is a known issue with using strings to lookup INT fields or ints to lookup CHAR/VARCHAR fields. Basically the INDEX is ignored.

If lvl_id or active are CHAR/VARCHAR this might be the reason. The same is valid for tbl2_id if this is of type INT.

EDIT

I must say that 13k entries is nothing that would explain the performance. However you should take into account the cardinality of your indexes. If the cardinality is below 30% (among other factors) your index will not be used.

This should be clear when using EXPLAIN to ask how is the query optimizer doing the query and what indexes is it using. In some cases you might want to use the FORCE INDEX syntax to explicitly use one or more indexes.

Also keep in mind that while adding composite indexes will help increase query speed (by increasing the cardinality of the index and therefore make the query optimizer use it automatically), it will also have a downside. More indexes mean more space used and reduced speed on UPDATE/INSERT since more things need to be updated. This is specially relevant if your tables become quite big (on the scale of millions of rows).

Indexing the columns used in the join condition (mm) should help.