Disclosed herein are embodiments providing query validation with automated query modification. In particular, the embodiments provide a computing system that receives a query and determines the query is sensitive. The computing system iteratively modifies the query until the query is not sensitive by modifying the query to increase a scope of the query, updating estimated query results based on the query as modified, and determining whether the query as modified is sensitive based on the estimated query results as updated. Upon determining that the query as modified is not sensitive, the computing system proceeds with the query as modified. Accordingly, the computing system improves query efficiency by automatically modifying a sensitive query.