The claimed subject matter is directed to constructing query hierarchies in response to a query request. To construct a query hierarchy, a list of related candidate queries is generated in response to the received query request. The list of related candidate queries is generated by determining the relative coverage of information shared by the candidate queries and the query request. Relationships between the submitted query request and the candidate queries in the list are determined based upon the extent of relative coverage of information shared by the candidate queries and the query request. A query hierarchy is then constructed to reflect the determined relationships between the query request and the candidate queries.