Mysql query grouping by two columns for max date takes too long
EDIT 1: The query below is quite like the original query. It very much depends on how strict are the other conditions, i.e. how many rows can be ignored with those conditions. I think the index should contain the group-max-triple (l_a, l_b, timestamp), but if l_act='q' is a strong reduction and the condition is always there then l_act should come before l_a.

Origin:
I would write it as 

select tmp.* 
from tmp inner join (
    select l_a, l_b, max(timestamp) as max_time 
    from tmp where timestamp &lt; cast('2013-01-01T00:00:00Z' as binary) 
    group by l_a, l_b
) as selmax 
on selmax.l_a = tmp.l_a 
   and selmax.l_b = tmp.l_b 
   and selmax.max_time = tmp.timestamp
; 


and give tmp an index on (l_a, l_b, timestamp).

And also: what says explain?

EDIT 2: 

Seeing the explain and looking at the indices clears the case. l_project starts the primary key but you give no restriction on that in your inner query.

The second index needs name as a second field.

If l_act is a strong restriction (All of the queries give a l_act - condition which meets less than  1/3 of the table), you should make an index 

l_act, l_a, l_b, timestamp


otherwise

l_a, l_b, timestamp


If the 4-part-index is used, it should be very fast.

I wish much fun adding the index. ;-)

If you use the 4-part-index, then you must add the l_act-condition in the inner AND the outer join.