CLUSTERING DATABASE QUERIES FOR RUNTIME PREDICTION

摘要

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 providing 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 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.

主权项

1. 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 comprising:
providing a number (n) of numerical values (x1, . . . ,xn) that represent the runtimes of the reference queries; computing the optimal K-means clustering of the numerical values for a predetermined number (K) of clusters, wherein the computing 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 (H) of order equal to the number of numerical values; and clustering the reference queries according to the computed clustering of the numerical values.