How can we optimise this OR and ORDER BY query?
I've been reading dba stackexchange for a while now, and these kind of questions come up often, and they always kind of frustrate me.

People often seem to go straight to explain plans, and or looking for special indexes like they're magic bullets - but they're really not.

What you should get into doing (everybody) is thinking these problems through from a logical standpoint - if you, as a human, wanted to search through ~10 million lines of data to achieve this, how would you best organise the data to help you do this? That's all an index is, basically, is an ordering of the data. The computer does the work a bit faster than you, that's all.

By all means use those other tools and experimentation to help you with your understanding and refinement of yours skills, but don't use it as the primary go-to. That's a crutch.

Maybe I'm a bit of a idealist, and anyone who is more than a couple of years younger than me just isn't used to manually dealing with these kind of tasks, you just type them in to google - but think of how you might use a phonebook* 


you don't open it at page 1, find Andrew Aardvark, ask youself "is this Walter Williams?" . no... next
line 2 - Arthur Abraham - is that Walter Williams? ... no. 
line 3 - Alex Acer - Walter Williams? no
And so on.


No, you use an algorithm. 


these were big fat books, made of paper, with everyone's phone number in. We had them in the 20th century.


So anyway, here's how I always approach your problem. 

[1] Continue thinking of this problem like a phonebook.

[2] What columns could I sort the book by to help me search the data? - you're right in that it's those columns affecting the selection - columns in the WHERE clause, and columns in the ORDER BY

[3] So systematically... column by column

[4] mc.IsBarred - I didn't get as far reading your notes (IsBarred is mostly 0) before I disounted this. The name gave me the clue - this is presumably effectively a binary flag - Low cardinality data is generally not a good sorting column

Think of the phonebook. If we sorted the phonebook not by name, but by hair colour - even if we knew Walter Williams had red hair, and could home straight in on the 10% of the book containing just those guys (me included) it'd still take a while to search them one by one.

[5] mc.AllocatedCount or mc.MaxUses - no. The problem here comes from your comparing one column against the other. There's no ordering you could apply to the list by either column, or one then the other, which could zero you in quickly on to a small subset of data.

[6] mc.BatchID - this doesn' appear to be an unreasonable candidate. Although your code doeesn't actually show exactly how many values you're selecting from, or the cardinality of the data.

If you could search through just those sections of the phonebook relating to batch 446, and then those for batch 561, etc. That would certainly narrow the amount of searching you did - but you would still have to search through and compare every single row in that set, and then find the one which matches the rest of the clause, AND has the earliest date.

OK, we'll pencil it that column as a possible...

[7] mc.ExpiryDate - appears in both your where clause AND your order by ...

interesting...

If you sorted your phonebook by expiry date, you could turn to the page corresponding to 18:44 on 2018-11-13, and find the first record. If it matched all of your where criteria - you would have to look no further. Since it is by definition the earliest expiring date after that date - you know this is the record you're looking for.

If it's not, you have to look at the second row, then rinse and repeat. AS soon as you find a matching row, you know it's got the earliest expiry date and can stop.

This is the only potential indexing which can find you your single row in one attempt.

mc.ExpiryDate IS YOUR CANDIDATE FOR INDEXING

I have a few caveats. 

[A] I'm not overly familiar with MySQL. Exactly how the query engine will interpret your code telling it to ORDER BY and then LIMIT, I don't know for sure. As a human I can think this through as detailed above - but whether MySQL will attempt to fetch all matching rows before finding earliest I can't say. I sesiously doubt it'd be that silly, but have no firm evidence.

[B] If you're adding 60,000 rows of data to the table in a week - that's 60,000 operations which will run marginally slower each time, as they have to maintain an extra index. Think through the implications of that.

There are always thade-offs with these things...

[C] If your where clause still filters out many many rows, the query may still have to search through many records. It depends a lot on the actual data. But that's where your own knowledge is key in this kind of situation. Use that!