MYSQL, very slow order by

You need a separate index on uploaddate. This sort will take advantage of composite index only if uploaddate is first column in it. You can also try to add user_id to ORDER BY:

    ....      
    ORDER BY p0_.user_id, p0_.uploaddate

Seems you're suffering from MySQL's inability to do late row lookups:

• MySQL ORDER BY / LIMIT performance: late row lookups
• Late row lookups: InnoDB

Try this:

SELECT  p.*, u.*
FROM    (
        SELECT  id
        FROM    photo
        ORDER BY
                uploaddate DESC, id DESC
        LIMIT   10
        OFFSET  100000
        ) pi
JOIN    photo p
ON      p.id = pi.id
JOIN    user u
ON      u.user_id = p.user_id