1. A method of estimating query progress, comprising: receiving a query; based on characteristics of the received query, determining a model of work to be performed during execution of the query; estimating a total amount of work that will be performed according to the model; iteratively estimating an amount of work performed according to the model at a given point during the execution of the query; iteratively estimating the progress of the query using the estimated amount of work performed and the estimated total amount of work; iteratively displaying estimated progress of the query to a user; and preventing decreasing progress estimations from being displayed to the user by using an upper bound on the total work that will be performed as an estimate of the total work that will be performed.