Why would you want to disable caching? The first time the query is executed is only so slow because it cannot use an existing cache entry and has to fetch a lot of data from the database. If you were to disable the cache then the second time you call the query would also take 20 minutes.
Most caches in Alfresco are global, so if one user found a specific search result than another user that finds the same result will generally profit from it performance-wise.
It is very likely that your query is simply too complex / retrieves too many records (more than what would be recommended) or that either your data model or database is not properly maintained / optimised for query performance. If you were to provide an example query (incl pagination / scope parameters) it would at least help to evaluate that...