Now I have problem with scale. I didn't think about the scale when designing and then my class structure made the search functionality runs really slow. Search functionality is the heart of my application, so it must be quick. To fix this I made a lookup table to cache the intermediate results of the search, so that only the first search runs slow and the following ones run faster. And I also break some of the abstractions to get better performance from the class library. This solution worked.

However, nothing ever runs according to plan. Apparently, when it gets too many requests, some SELECT queries starts timing out. And also, UPDATE and INSERT queries lock the SELECT queries out of the cache table, making the search performance much worse.

I don't see the point of caching on your own -- the database should be able to do this itself. The UPDATE and INSERT locking issue may be a sign that you don't have the correct indexes, so that the database can do row level locking, rather than table locking. Also, if you can speed up the individual SELECT queries, you might keep from getting too many backlogged requests.

From the issues you're mentioning, I'd look into database tuning, and making sure that I had indexes where they're useful, and didn't have them where they weren't. I'd also make sure that the tables were ANALYZEd as needed.