I have developed a Visualforce page that needs to display a fairly complicated report. Data needs to be pulled from a variety of objects, and because the filter criteria may vary, I have to use dynamic SOQL.

The problem is that when the report is first run, it takes inordinately long. 2-3 minutes are not uncommon, and lately we've even encountered complete timeouts. Neither the amount of data (less than 5000 rows per query) nor the complexity of the queries (less than 10 columns, one level of joining per query) warrants this.

What's more, this slowness only occurs when the page is first loaded in one session. If the user changes the filter and re-runs the same report, it is much faster, no more than a few seconds. I did two runs of the same report with Apex/SOQL profiling turned on, and the result is abundantly clear.
Here's the profiling info for the first query of the first run:

Class.MyReport.rewardsReport: line 419, column 1: [
	SELECT Visit__r.Client__c, Value__c, Visit__r.Year__c
	FROM Reward__c
	WHERE Visit__r.Ev__c >= :minYear AND Visit__r.Type__c = 'Settlement' AND Visit__r.Client__c IN :clientIds
]: executed 4603 times in 134160 ms

And then, here's the same query when I changed the filter and re-ran the report from the page:

Class.MyReport.rewardsReport: line 419, column 1: [
	SELECT Visit__r.Client__c, Value__c, Visit__r.Year__c
	FROM Reward__c
	WHERE Visit__r.Ev__c >= :minYear AND Visit__r.Type__c = 'Settlement' AND Visit__r.Client__c IN :clientIds
]: executed 6565 times in 1917 ms

(note: I'm not sure why it says "executed x times", I don't run the query that many times, I presume that refers to the number of rows returned by the query)

I have no idea if SF does any caching for SOQL queries (and if yes then how) but to me it would seem so. The problem is, "the report works fine once you wait out the first 3 minutes" is not a solution my client is ready to accept. Does anyone have any experience with this problem, and/or an idea for how to improve performance?