1. A computer-implemented method, comprising: receiving a query from a user device as input for a search operation that uses the received query to identify search results responsive to the received query; determining a transformation cost score for each of a plurality of candidate augmentation queries for the received query, the transformation cost score being based on a transformation cost value for each of one or more terms of the received query, the transformation cost value for a term of the received query being proportional to a term weight that measures an importance of the term in the received query; selecting a candidate augmentation query from among the candidate augmentation queries based on the transformation cost score of the selected candidate augmentation query, the selecting comprising: comparing each term of the received query to a set of non-transformable terms, each non-transformable term of the set of non-transformable terms being a term for which a matching term in the received query should not be transformed to another term; identifying a proper subset of candidate augmentation queries from among the candidate augmentation queries, each candidate augmentation query identified for the proper subset being identified in response to a determination that the candidate augmentation query includes each term of the received query that matches a non-transformable term; ranking the proper subset of candidate augmentation queries according to the transformation cost score of each candidate augmentation query of the proper subset; and selecting the candidate augmentation query from among the proper subset of candidate augmentation queries based on the ranking of the proper subset; identifying search results responsive to the selected candidate augmentation query; augmenting the search results responsive to the received query with the search results responsive to the selected candidate augmentation query to form an augmented set of search results; and providing the augmented set of search results to the user device as a set of search results responsive to the received query.