Systems, methods, and other embodiments associated with progressive relaxation across tiers of a search system are described. One system embodiment includes a first tier of computing components that stores search data that can be used to locate documents. The system embodiment may also include a second tier of computing components that also store search data that can be used to locate documents. The system may also include a query logic that receives a query and locates a set of items relevant to the query by selectively progressively relaxing a search across the search data stored at different levels until a threshold is met.