I'm a big fan of Redis for solving this kind of problem: stick your database primary keys in a Redis set, then use the lightning fast SRANDMEMEBER command to grab a random ID. Keeping your Redis sets synchronized with your database IDs isn't a huge burden - I usually use a bit of custom code in the .save() and .delete() methods on the Django model, but you could also use Django's signals.
Comment
Wow! That's interesting. Considering how fast a primary key index table is, Redis goes to beat it. Thanks for the tip!
BTW. Check the update I added to the blog about selecting 100 random items instead of 10 ten times.
Parent comment
I'm a big fan of Redis for solving this kind of problem: stick your database primary keys in a Redis set, then use the lightning fast SRANDMEMEBER command to grab a random ID. Keeping your Redis sets synchronized with your database IDs isn't a huge burden - I usually use a bit of custom code in the .save() and .delete() methods on the Django model, but you could also use Django's signals.