I need help in optimzing a order by clause in a join query

[George Maharis]

I need help in optimizing a order by clause in a join query

SCHEMA

messages
message_id, entity_id, message, timestamp

subscription
user_id, entity_id

users
user_id

entities
entity_id


There are two scenarios that yield different results, depending on the query used:

Scenario 1: Lots of message entries, and at least one relevant subscription entry
Scenario 2: Few message entries and/or few, or zero, subscription entries that are relevant

I am looking for a query that will work well in both scenarios


Indexes:

( subscription.user_id, subscription.entity_id )
( subscription.entity_id )
( messages.entity_id, messages.timestamp )
( messages.timestamp )
( messages.message_id )


CREATE TABLE STATEMENTS:

With ~5000 rows

subscription | CREATE TABLE `subscription` (
`user_id` bigint(20) unsigned NOT NULL,
`entity_id` bigint(20) unsigned NOT NULL,
PRIMARY KEY (`user_id`,`entity_id`),
KEY `entity_id` (`entity_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8


with ~255,000 rows

messages | CREATE TABLE `messages` (
`message_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
`entity_id` bigint(20) unsigned NOT NULL,
`message` varchar(255) NOT NULL DEFAULT '',
`timestamp` int(10) unsigned NOT NULL,
PRIMARY KEY (`message_id`),
KEY `entity_id` (`entity_id`,`timestamp`),
KEY `idx_timestamp` (`timestamp`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8



QUERIES:

SELECT messages.*
FROM messages
INNER JOIN subscription ON subscription.entity_id = messages.entity_id
WHERE subscription.user_id = 1
LIMIT 50


This query, without an order by, runs fast in any scenerio. However when
the order by is added ( on the column timestamp ), it only runs well in Scenario 2



SELECT messages.*
FROM messages
STRAIGHT_JOIN subscription ON subscription.entity_id = messages.entity_id
WHERE subscription.user_id = 1
ORDER BY messages.timestamp DESC
LIMIT 50

This query works well in scenario 1 (.000x seconds): Lots of message
entries, and at least one relevant subscription entry. this query will
take 1.7+ seconds in scenario 2.



EXPLAIN INFO

{ INNER JOIN }

LIMIT 15

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra
| 1 | SIMPLE | subscription | ref | PRIMARY | PRIMARY | 8 | CONST | 1883 | Using Index, Using Temporary, Using filesort
| 1 | SIMPLE | messages | ref | entity_id | entity_id | 8 | subscription.entity_id | 24 | Using where

{ STRAIGHT JOIN }

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
| 1 | SIMPLE | messages | index | idx_timestamp | idx_timestamp | 4 | NULL | 15 | Using Where |
| 1 | SIMPLE | subscription | eq_ref | PRIMARY,entity_id,user_id | PRIMARY | 16 | const, messages.entity_id | 1 | Using index |

{ WIHTOUT ORDER BY }

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra
| 1 | SIMPLE | subscription | ref | PRIMARY | PRIMARY | 8 | CONST | 1883 | Using Index
| 1 | SIMPLE | messages | ref | entity_id | entity_id | 8 | subscription.entity_id | 24 | Using where