Techniques for rewriting queries submitted to a query engine are provided. A query is submitted by a user and sent to a search mechanism. Based on the query, one or more query suggestions are generated. Features are generated based on the query and the query suggestions. Those features are input to a trained machine learning mechanism that generates a rewrite score. The rewrite score signifies a confidence score that indicates how confident the search mechanism is that the user intended to submit the original query. If the rewrite score is below a certain threshold, then the original query is rewritten to a second query. Results of executing the original query may be sent to the user along with a reference to the second query. Additionally or alternatively, results of executing the second query are sent to the user.