A query difficulty prediction unit includes a query difficulty predictor to determine the extent of overlap between query documents received from a search engine operating on an input query and sub-query documents received from the search engine operating on sub-queries of the input query. The unit generates a query difficulty prediction from the extent of overlap.