A computer-implemented method for training a regression model to estimate query selectivity for use in a query optimizer of a database system, the regression model achieving a target accuracy, the method comprising: training the regression model on training data using cross-validation, wherein the training data has a size and the size equals a number of labeled examples in the training data; computing a confidence interval estimating an accuracy of the model, wherein the confidence interval has a lower bound and an upper bound; determining whether the target accuracy is less than or equal to the lower bound; returning the regression model if the target accuracy is less than or equal to the lower bound; determining a geometric step size for increasing the size of the training data, wherein the geometric step size minimizes a total time spent on model construction and determining the geometric step size comprises: determining a labeling cost, wherein the labeling cost is a time required to compute a label for one example; determining a cross-validation cost, wherein the cross-validation cost is a time required to run a cross-validation for one example; computing a ratio of the labeling cost to the cross-validation cost; and determining the geometric step size based on the ratio; adding, if the target accuracy falls between the upper bound and the lower bound, additional labeled examples to the training data to generate updated training data, wherein the updated training data has an updated size equal to the size plus a number of the additional labeled examples and wherein the number of the additional labeled examples is based on the geometric step size; training the regression model on the updated training data using cross-validation; computing, after training the model regression on the updated training data, an updated confidence interval for the regression model, wherein the updated confidence interval has an updated lower bound and an updated upper bound; determining, after training the regression model on the updated training data, whether the target accuracy is less than or equal to the updated lower bound; and returning the regression model if the target accuracy is less than or equal to the updated lower bound; wherein the confidence interval is an estimate of a range of values for a parameter that has an unknown value. training the regression model on training data using cross-validation, wherein the training data has a size and the size equals a number of labeled examples in the training data; computing a confidence interval estimating an accuracy of the model, wherein the confidence interval has a lower bound and an upper bound; determining whether the target accuracy is less than or equal to the lower bound; returning the regression model if the target accuracy is less than or equal to the lower bound; determining a geometric step size for increasing the size of the training data, wherein the geometric step size minimizes a total time spent on model construction and determining the geometric step size comprises: determining a labeling cost, wherein the labeling cost is a time required to compute a label for one example; determining a cross-validation cost, wherein the cross-validation cost is a time required to run a cross-validation for one example; computing a ratio of the labeling cost to the cross-validation cost; and determining the geometric step size based on the ratio; determining a labeling cost, wherein the labeling cost is a time required to compute a label for one example; determining a cross-validation cost, wherein the cross-validation cost is a time required to run a cross-validation for one example; computing a ratio of the labeling cost to the cross-validation cost; and determining the geometric step size based on the ratio; adding, if the target accuracy falls between the upper bound and the lower bound, additional labeled examples to the training data to generate updated training data, wherein the updated training data has an updated size equal to the size plus a number of the additional labeled examples and wherein the number of the additional labeled examples is based on the geometric step size; training the regression model on the updated training data using cross-validation; computing, after training the model regression on the updated training data, an updated confidence interval for the regression model, wherein the updated confidence interval has an updated lower bound and an updated upper bound; determining, after training the regression model on the updated training data, whether the target accuracy is less than or equal to the updated lower bound; and returning the regression model if the target accuracy is less than or equal to the updated lower bound; wherein the confidence interval is an estimate of a range of values for a parameter that has an unknown value.