1. One or more computer readable media comprising computer executable instructions that, when executed, direct a computing device to: associate at least a respective lower-bound parameter with each node in an operator tree representing a database query; and estimate progress of the database query at a given point in the database query based at least in part upon the lower-bound parameters.