Another thing I was thinking this morning was having a fourth table with all the pre-calculated results:
Code:
table4:
text html;
int (1) category;
Then precalculate that table with the results of all possible joins from your original SELECT:
Code:
INSERT INTO table 4 (SELECT all possible ads blah blah)
Then just grab random ads from table4 based on category. No unions, no joins, no lookups, no nothing.
Every time you add or delete an affiliate or advertisement, you re-run the calculation for table 4 and re-populate it.