1) make sure to use limit and only return a couple of rows at a time
2) make sure all of the rows have an auto_increment primary key and reference any row using the id where possible
3) use "EXPLAIN SELECT ..." on your select statement and try to optimize them so that the indexes are being used.
4) only index rows that are being used to search, not all rows.
5) and if all else fails, simplify your queries or run them once every hour or so and just show users the cached query results.