The invention notably relates to a computer-implemented method of clustering reference queries in a database for prediction of the runtime of a target query in the database based on similarity of the target query with the reference queries. The method comprises the steps of providing (S10) a number of numerical values that represent the runtimes of the reference queries; computing the optimal K-means clustering of the numerical values for a predetermined number of clusters, wherein the computing step (S20) includes iterating, a number of times corresponding to the predetermined number of clusters, a linear-time Row Minima Searching algorithm applied to a square matrix of order equal to the number of numerical values; and clustering the reference queries according to the computed clustering of the numerical values. Such a method improves the field of database query runtime prediction.