Some embodiments provide a non-transitory machine-readable medium that stores a program. In response to receiving a first query for a set of data, the program generates a first query execution plan based on the first query. The program further executes the first query execution plan in order to generate a first result set comprising the set of data. The program also stores the first query execution plan in a cache. The program further replaces the first query execution plan in the cache with a second query execution plan. The second query execution plan includes a query hint applied to the first query execution plan. In response to receiving a second query for the set of data, the program also retrieves the second query execution plan from the cache. The program further executes the second query execution plan in order to generate a second result set comprising the set of data.