adding ORDER BY decreases speed by 15x
Should it really take 15 fold time to order an indexed column?


Well it depends where this column is being used. Just because it's indexed (and presumably in some order) doesn't mean that using it in a query will magically make it fast.

Assume there are two indexes in the table, for id (ordered by id) and for user_id (ordered by user_id). If MySQL uses the latter to quickly look up the rows that satisfy the WHERE predicate then the result is that it might have all the rows in user_id order.

You want them in id order, so MySQL has to order them. Your previous query didn't have to do ordering. It should come as no surprise that more work == more time.


  What can I do to decrease such a performance hit?


Look at the execution plan. MySQL has EXPLAIN.

You should also make your queries as simple as you can. I assume your images table has a primary key, so the DISTINCT in SELECT DISTINCT images.* FROM images ... doesn't really make sense.

Also by taking all the columns (images.*) you're forcing MySQL to acquire every attribute for each row that is returned, whereas being more selective (no pun intended) with your columns might result in less data needing to be returned. Simplifying somewhat: less columns gives MySQL an opportunity to satisfy the query using only small indexes, rather than the table data.