Optimizing query for large table with `rand()` ordering I have a MySQL database running for a multiplayer game server and I've been trying to identify a performance bottleneck. I got the slow query logs and the slowest queries by time are like this (the matchmaking system):

select `accountID` from GameAccountProfile where `active`=1 and 
`lastActiveTime`&lt;1482549810 and `inTutorial`=0 and `defenseRating`&gt;0 and
`league`=4 and `protectedPeriod`&gt;1482550190 and `lastActiveTime`&gt;1481945090 and
`accountID`!=986702 and `accountID`!=10 and `accountID`!=10 and
`accountID`!=463126 and `accountID`!=184374 and `defenseRating`&gt;=3.3530639 and
`defenseRating`&lt;=6.2271186 and `level`&gt;=-8 and `level`&lt;=2
order by rand() limit 1;


There are currently about 1.3 million rows in this table. I read that the rand() sorting may be a serious performance hit and when I ran an explain on it in MySQL Workshop on the query, it did highlight it in red as being a performance hit.

Also, I realized that the only index for any of these where conditions is on the account ID column. I'm considering adding a composite index on the "active", "inTutorial", "level", and "league" columns as they don't change often (arranged starting with the least often changed).

How can I get a random account ID with these conditions without using rand() in an order clause? I need to ensure all accounts get targeted equally but rand() seems to be a clear performance hit.

Is there any other way I can improve the performance of this query?
There is no good way to do ORDER BY RAND() LIMIT 1, but this has several suggestions.  Some depend on AUTO_INCREMENT, some based on an extra column.