Plan Caching Using Density-Based Clustering

A query plan predictor receives a query instance according to a query template having a set of parameters. The query plan predictor determines a plan space point for the query instance which is based upon the set of parameters. The query plan predictor predicts a predicted query plan for the plan space point, which is selected from a map of query plans according to a confidence threshold from a plan cache that includes at least one histogram. Each histogram is representative of a cached query plan in the plan cache combined with a previously-selected locality-sensitive hashing function. The histogram stores a frequency distribution of a mapping of sample plan points for the cached query plan by the locality-sensitive hashing function.