As search engine users get lazier, the search queries become shorter and muddier. There is no sense in making users ask only accurate queries, so the problem of query expansion and reformulating is getting more and more urgent. In principle query reformulation without semantic losses is often impossible, that’s why methods of finding near-synonyms that are sensitive to the query context should be employed. We show that very simple methods of synonym mining being applied to the very large corpora like Russian Internet are quite effective. The paper argues the importance of query logs or anchor texts as comparatively new linguistic resources. We discuss the ways query expansions improve search engine relevance or degrade it even if they seem to fit the query context.