A Database Query Time Estimator (DQTE) module as a run-time tool to estimate and display the total time to complete a database query while the query is executing. The DQTE module invokes a runtime algorithm to compute the set of rows or blocks in a database that will be resulted at each step of a query's execution plan. The DQTE module may optimize the current execution plan to create one or more parent-child processes and may assign tasks to these processes to monitor the progress of each step in the execution plan. The progress of the child processes is then rolled up to the root parent level to come up with a time value, which is the Estimated Time of Arrival (ETA) to complete the whole execution of the query. The DQTE module may read only the header information of the database objects for a complete snapshot of the object.