A computer-implemented method for proving complete query suggestions, performed by a server system, includes receiving a partial search query from a client system. A database of complete search queries is searched to identify a first set of matching complete search queries. If the first set of matching complete search queries fails to satisfy predefined criteria (e.g., with respect to the quantity and/or quality of the matching complete search queries), a rewrite of the received partial search query is performed to produce a first set of rewritten partial search queries. The database of complete search queries is searched to identify a second set of complete search queries matching any of the first set of rewritten partial search queries. At least a subset of the second set of matching complete queries are sent to the client system.