Techniques are described for modeling data query execution time based on a cost of data queries, where the cost provides a measure of the processing resources used by the data query while executing. Using regression analysis or other statistical methods, a model may be generated that enables the prediction of the query execution time based on the query cost. In some cases, the model may be generated based on a linear regression analysis of previously measured execution times and previously determined data query costs. The model may be stored and employed prior to, or during, the subsequent execution of a data query, to predict the execution time of the data query. Data queries that execute substantially longer than the predicted execution time may be terminated.