1. A computer-based method of determining a cost model, said cost model modeling the cost of executing a query operator, said query operator in a user query to be executed against a database, said method comprising: a. determining at least one input feature of a plurality of training queries, said at least one input feature, for which values are either known or unknown, which is assumed to be relevant to said cost model; b. estimating values for said at least one input feature based on statistics stored by said database, if values for said at least one input feature are unknown; c. executing said plurality of training queries containing said query operator and said at least one input feature and determining whether cost of executing said query operator changes as values of said at least one input feature are varied and if so, statistically fitting a model to correlate observed costs of executing said query operator with said at least one input feature; and d. estimating, based on said model and said at least one input feature, a cost for executing said query operator in said user query.