1. A non-transitory computer-readable storage medium encoded with instructions, wherein the instructions when executed comprise: generating a plurality of query plans, each plan for executing a respective query against data in a database; with respect to each query plan of said plurality of query plans, selectively determining whether the respective query plan should be stored to data in a cache in a compressed form; with respect to each query plan of said plurality of query plans for which it is selectively determined that the respective query plan should be stored to data in a cache in a compressed form, storing the query plan to data in the cache in a compressed form, the compressed form being a form produced by compressing the respective query plan using lossless data compression; and with respect to each query plan of said plurality of query plans for which it is selectively determined that the respective query plan should not be stored to data in a cache in a compressed form, storing the query plan to data in the cache in an uncompressed form; wherein said selectively determining whether the respective query plan should be stored to data in a cache in a compressed form comprises making the selective determination using at least one parameter from: (a) an estimated runtime of the respective query plan; (b) an estimated frequency of execution of the respective query plan; (c) a cache utilization of said cache; (d) a memory utilization; (e) a concurrency level; and (f) a CPU utilization.