The problem is that if your query takes more than 5 seconds, the snapshot of data it's looking at is out-of-date. So, you'll need to provide a solution to that problem.

I've worked with queries that looked at millions of rows crossed with millions of rows and the longest I've ever had a query take was 15 seconds - that was ok because it was looking at archived data. Normally, queries shouldn't take more than 1 second. Taking longer usually means you've written the query wrong. Have you looked at the execution plan?