1. A method, performed by a server system having one or more processors and memory storing one or more programs for execution by the one or more processors, comprising: receiving from a client system a partial search query having a plurality of query terms; searching a database of complete search queries to identify a first set of matching complete queries; in accordance with a determination that the first set of matching complete queries fails to satisfy predefined criteria: performing a rewrite of the received partial search query to produce a first set of rewritten partial search queries, wherein the first set of rewritten partial search queries includes at least one rewritten partial search query that (A) includes a synonym of a respective query term of the received partial search query, or (B) includes fewer respective non-stop word query terms than the received partial search query, wherein performing the rewrite includes dropping no more than a maximum number of query terms, the maximum number of query terms being based on a difference between a number of query terms in the partial search query and one of the respective rewritten partial search queries rewritten based on (A) or (B); searching the database of complete search queries to identify a second set of matching complete queries that match any of the first set of rewritten partial search queries; and sending at least a subset of the second set of matching complete queries to the client system.