1. A computer-implemented method comprising: selecting an original query from records of previously received user queries; rewriting the original query to generate a rewritten query; determining, based on records of user interactions with first search results obtained using the original query and second search results obtained using the rewritten query, that a preference is indicated among users for search results obtained using the rewritten query over search results obtained using the original query; in response to determining that the preference is indicated among users for search results obtained using the rewritten query over search results obtained using the original query, generating mapping data that maps the original query to the rewritten query to cause subsequently received user queries that include the original query to be rewritten using the rewritten query; and at a later time, receiving a first user query, determining that the first user query or a substring of the first user query matches the original query, and in response, identifying the rewritten query from the mapping data, obtaining search results using a substitute query that includes the rewritten query, and returning the search results obtained using the substitute query in a response to the first user query.