High performance MySQL random non-sequential row

Question

I'm trying to grab a random row from a table where the data doesn't change. I've read that people try ORDER BY RAND() which is terrible for large datasets and doesn't scale well.

I've also seen the solution that is to get SQL to get a random row between a minimum/maximum range like so: FLOOR(MAX(needed_id) * RAND) but this would only work when the rows are sequential: 1,2,3,4,5,6,7,8,9,10.

The data I need to pull out isn't sequential, for example: 1,2,3,4,10,11,12,13

So I'm thinking there are two solutions:

1st Solution: Keep running this: FLOOR(MAX(needed_id) * RAND) until I receive a row of the right type (1/6 chance)

2nd Solution: Create a duplicate table (as my data never changes) like so:

temp_id | needed_id | type 
1            1          1
2            4          1
3            7          2
3            8          2

So I can pull out a random temp_id using this method: FLOOR(MAX(temp_id) * RAND) - WHERE type = 1

What do you think? I'm likely to run the 1st solution about 6 times until I receive the correct row, but in the 2nd solution it would work straight away but requires another table.