4. The method as recited in claim 1 , wherein said building a prediction of query runtime tree from historical query information comprises: grouping an historical database query of said historical query information into an element of a binary decision tree based upon an execution time of said historical database query; and terminating construction of said element based upon a pre-defined termination condition.
4. The method as recited in claim 1 , wherein said building a prediction of query runtime tree from historical query information comprises: grouping an historical database query of said historical query information into an element of a binary decision tree based upon an execution time of said historical database query; and terminating construction of said element based upon a pre-defined termination condition. 5. The method as recited in claim 4 , wherein said terminating construction of an element of said prediction of query runtime tree based upon a pre-defined termination condition comprises: terminating construction of said element of said prediction of query runtime tree upon satisfying a termination condition from the group of termination conditions consisting of: dropping below a predetermined time range threshold for said element; dropping below a predetermined threshold number of historical database queries grouped in said element; and dropping below a predetermined accuracy of time estimation for said element.