1 ) A method, comprising: generating performance characteristic metric vectors representing query execution metrics in a database; given a point in a compile-time feature input space that corresponds to a compile-time vector, identifying nearest neighbors of the point and corresponding points in a performance metric feature space; determining a generated point that represents a cluster represented by the corresponding points; and using the performance characteristic metric vectors that correspond to the generated point to predict performance of a query before the query executes in the database.