How can we optimise this OR and ORDER BY query? We have a table with the following structure:

+----+----------+-------------+---------------------+-----------+---------+----------+
| id | Batch_id | Merchant_id |     ExpiryDate      | Allocated | MaxUses | IsBarred |
+----+----------+-------------+---------------------+-----------+---------+----------+
|  1 |        1 |        5793 | 2019-11-03 01:23:40 |         1 |       1 |        0 |
|  2 |        1 |        1238 | 2019-11-07 01:23:40 |         0 |       1 |        0 |
|  3 |        2 |        9427 | 2019-11-09 04:49:40 |         1 |       1 |        0 |
+----+----------+-------------+---------------------+-----------+---------+----------+


In DDL terms this is:

CREATE TABLE `merchant_coupon` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `ExpiryDate` datetime DEFAULT NULL,
  `MaxUses` int(11) NOT NULL,
  `Batch_id` int(11) DEFAULT NULL,
  `Merchant_id` int(11) DEFAULT NULL,
  `Allocated` int(11) NOT NULL,
  `IsBarred` tinyint(1) NOT NULL
  PRIMARY KEY (`id`),
  KEY `IDX_8C9078EBAF5CDCE0` (`Batch_id`),
  KEY `IDX_8C9078EBE10A5A83` (`Merchant_id`),
  CONSTRAINT `__FK_8C9078EBAF5CDCE0` FOREIGN KEY (`Batch_id`) REFERENCES `batch` (`id`),
  CONSTRAINT `__FK_8C9078EBE10A5A83` FOREIGN KEY (`Merchant_id`) REFERENCES `merchant` (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=10388795 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci


We would like to find the row which:


Is not Barred
Has Allocated &lt; Max Uses
Has an Expiry Date greater than a certain date
Is a member of one or more batches
Is the soonest expiring (i.e. ExpiryDate is closest to now)
We only need 1 of the rows.


Our query at the moment looks like this:


    SELECT mc.*
    FROM merchant_coupon mc
    WHERE 1 = 1
      AND mc.IsBarred = 0
      AND mc.AllocatedCount &lt; mc.MaxUses
      AND mc.ExpiryDate &gt; '2018-11-13 18:44:17'
      AND (mc.Batch_id = 288
               OR mc.Batch_id = 446 
               OR mc.Batch_id = 561 
               ... 
               OR mc.Batch_id = 4167
               OR mc.Batch_id = 5731
        )
    ORDER BY mc.ExpiryDate ASC
    LIMIT 1


This works, but we suspect there are opportunities to improve it.

The explain looks like this:

id,select_type,table,type,possible_keys,key,key_len,ref,rows,Extra
1,SIMPLE,mc,range,"IDX_8C9078EBAF5CDCE0,IDX_8C9078EBE10A5A83",IDX_8C9078EBAF5CDCE0,5,,184481,Using where; Using filesort


Some other things to note:


The database is MySQL
The IDX_8C9078EBAF5CDCE0 is on the Batch_id. We also have an index on the Merchant_id
The Batch_id normally groups the rows into groups of between 2-10,000 items
The Batch that the Batch_id refers to also refers to the Merchant_id, so we could eliminate the AND Merchant_id = &lt;x&gt;, but we keep it as a safety check, just in case
The table contains about ~10 million rows, and is growing in the order of ~20,000-60,000 a week atm.
Once a row is selected, the Allocated column will be incremented - we do a SELECT ... FOR UPDATE in fact.
IsBarred is mostly 0.
In most cases MaxUses is 1, but in some it can be a number in the range of 1-1000.


What indexes would most likely optimise the query? Or, what changes could we make to the query to optimise it?
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!