mySQL 5.6.11

EXPLAIN SELECT DISTINCT T2.tid, T1.data, T2.data, T1.ordrenr, T1.nr, T4.data, T3.data, T1.ordretype, T5.aendret, T5.info
FROM `ordrer` AS T1
INNER JOIN `ordrer` AS T2 ON T1.ordrenr = T2.ordrenr
AND T1.ordretype = T2.ordretype
AND T2.datanavn = 'emnefelt'
AND T2.data LIKE '%%%'
LEFT JOIN `ordrer` AS T3 ON T1.ordrenr = T3.ordrenr
AND T1.ordretype = T3.ordretype
AND (
T3.datanavn LIKE 'domaene%'
OR (
T3.datanavn = 'varenavn'
AND T3.data = 'SMS'
)
)
LEFT JOIN `ordrer` AS T4 ON T1.ordrenr = T4.ordrenr
AND T4.datanavn = 'pris'
LEFT JOIN jthnet.`sag` AS T5 ON T5.id = (
SELECT MAX( id )
FROM jthnet.`sag`
WHERE T3.data = navn
AND T3.nr = nr )
WHERE T1.datanavn = 'status'
AND T1.ordretype = 'F'
AND (
(
T2.tid >= '2008-04-20 00:00:00'
AND T2.tid <= '2008-04-20 23:59:59'
AND T1.data LIKE '%'
)
OR (
T1.data LIKE 'ny.authent%'
)
)
ORDER BY T2.tid
LIMIT 5000

2-8 million records in ordrer

+----+--------------------+-------+--------+----------------------------------------------+------------+---------+-------------------------+------+------------------------------------+
| id | select_type        | table | type   | possible_keys                                | key        | key_len | ref                     | rows | Extra                              |
+----+--------------------+-------+--------+----------------------------------------------+------------+---------+-------------------------+------+------------------------------------+
|  1 | PRIMARY            | T2    | index  | dnavnordre,ordrenr,ordretype,tid,datanplusd  | tid        | 54      | NULL                    | 8709 | Using where; Using temporary       |
|  1 | PRIMARY            | T1    | ref    | dnavnordre,ordrenr,data,ordretype,datanplusd | dnavnordre | 148     | const,test.T2.ordrenr   |    1 | Using index condition; Using where |
|  1 | PRIMARY            | T3    | ref    | dnavnordre,ordrenr,data,ordretype,datanplusd | ordrenr    | 50      | test.T2.ordrenr         |   33 | Using where                        |
|  1 | PRIMARY            | T4    | ref    | dnavnordre,ordrenr,datanplusd                | dnavnordre | 148     | const,test.T2.ordrenr   |    1 | Using where                        |
|  1 | PRIMARY            | T5    | eq_ref | id                                           | id         | 4       | func                    |    1 | Using where                        |
|  2 | DEPENDENT SUBQUERY | sag   | ref    | navn,kunnavn,kunde,navnnr                    | navnnr     | 295     | test.T3.data,test.T3.nr |   15 | Using where; Using index           |
+----+--------------------+-------+--------+----------------------------------------------+------------+---------+-------------------------+------+------------------------------------+

1.2 million records in ordrer

+----+--------------------+-------+--------+----------------------------------------------+------------+---------+-------------------------+-------+----------------------------------------------+
| id | select_type        | table | type   | possible_keys                                | key        | key_len | ref                     | rows  | Extra                                        |
+----+--------------------+-------+--------+----------------------------------------------+------------+---------+-------------------------+-------+----------------------------------------------+
|  1 | PRIMARY            | T1    | ref    | dnavnordre,ordrenr,data,ordretype,datanplusd | datanplusd | 98      | const                   | 13725 | Using where; Using temporary; Using filesort |
|  1 | PRIMARY            | T2    | ref    | dnavnordre,ordrenr,ordretype,tid,datanplusd  | dnavnordre | 148     | const,test.T1.ordrenr   |     1 | Using index condition; Using where           |
|  1 | PRIMARY            | T3    | ref    | dnavnordre,ordrenr,data,ordretype,datanplusd | ordrenr    | 50      | test.T1.ordrenr         |    33 | Using where                                  |
|  1 | PRIMARY            | T4    | ref    | dnavnordre,ordrenr,datanplusd                | dnavnordre | 148     | const,test.T1.ordrenr   |     1 | Using where                                  |
|  1 | PRIMARY            | T5    | eq_ref | id                                           | id         | 4       | func                    |     1 | Using where                                  |
|  2 | DEPENDENT SUBQUERY | sag   | ref    | navn,kunnavn,kunde,navnnr                    | navnnr     | 295     | test.T3.data,test.T3.nr |    15 | Using where; Using index                     |
+----+--------------------+-------+--------+----------------------------------------------+------------+---------+-------------------------+-------+----------------------------------------------+

It may not be a direct number of records issue e.g. more than X records. I think I have seen  the NULL ref at lower numbers too, but not sure about this.