MySQL SELECT slow, but only 2 x 300K rows and indexes
KEY brand_id etc (brand_id,shopid,last_seen,price,saleprice)

This index does not support this query well.
The first field in the index is brand_id, but you are only filtering by &quot;&gt; 0&quot;.
Since I doubt you have many brands with negative id's, this probably isn't going to help very much.
The next field in the index is shopid, which doesn't appear in your where clause at all.
Based on this cursory analysis (and MySQL will do a lot more than that), this index will probably be discounted and the table scanned serially instead.
A better discriminator for choosing the rows you want returned would be last_seen.  Consider adding an index on that (or with that as its first field) and you should see some improvement.