Why index is not used with order by?

I trying to get info about why MySQL does not using my index when I create a inner join and trying to ORDER BY on the end.

I have my SQL query here:

SELECT
    *           
FROM
    product p INNER JOIN productStore ps ON p.productUUID = ps.productUUID       
ORDER BY
    ps.storeTitle 
LIMIT 50;

When I'm using order by this select take over 3,5 sec, when i remove order by its taking like 1,6ms to run the same SQL, my explain SQL is follow

With ORDER BY:

id  select_type table   type    possible_keys   key key_len ref rows    Extra
1   SIMPLE  ps  ALL PRIMARY NULL    NULL    NULL    942187  Using filesort
1   SIMPLE  p   eq_ref  PRIMARY PRIMARY 16  foeniks_core.ps.productUUID 1   NULL

Without ORDER BY:

id  select_type table   type    possible_keys   key key_len ref rows    Extra
1   SIMPLE  ps  ALL PRIMARY NULL    NULL    NULL    942187  NULL
1   SIMPLE  p   eq_ref  PRIMARY PRIMARY 16  foeniks_core.ps.productUUID 1   NULL

the field there not are indexing right is a varchar on 282 length.

My table design is here:

``
CREATE TABLE productStore (
productUUID binary(16) NOT NULL,
storeUUID binary(16) NOT NULL,
distributorLastUsed binary(16) DEFAULT NULL,
storeTitle varchar(282) DEFAULT NULL,
storeUrl varchar(282) DEFAULT NULL,
storeDescription text,
storeDescriptionDemo text,
storePrice int(11) NOT NULL DEFAULT '0',
storePriceNext int(11) NOT NULL DEFAULT '0',
storePriceCost int(11) NOT NULL DEFAULT '0',
overwrites int(11) NOT NULL DEFAULT '0',
updated datetime NOT NULL DEFAULT '1000-01-01 00:00:00',
added datetime NOT NULL DEFAULT '1000-01-01 00:00:00',
allowDisplay tinyint(1) NOT NULL DEFAULT '0',
activated tinyint(1) NOT NULL DEFAULT '1',
PRIMARY KEY (productUUID,storeUUID),
KEY productStoreLanguageToStore_idx (storeUUID),
KEY productStoreToDistributor_idx (distributorLastUsed),
KEY storeUrl (storeUrl(180)) USING BTREE,
KEY testStoreTitle`

David Spillett's answer is correct in all points, except for the "encouraging" suggestion.

Here's a way to not only encourage but (in almost all versions) force the optimizer to choose a plan that uses the wanted index to find the 50 rows - and only after that perform the join. It can't always be used but the FOREIGN KEY constraint assures that in this case the two queries will produce identical results.

I call this technique "first LIMIT, then JOIN":

SELECT     p.*, ps.*           
FROM       ( SELECT     *
             FROM       productStore 
             ORDER BY   storeTitle 
             LIMIT 50 
           ) ps 
    INNER JOIN product p 
        ON p.productUUID = ps.productUUID       
ORDER BY   ps.storeTitle ;

StackExchange Database Administrators Q#109078, answer score: 7