A method, system and article of manufacture for query execution management and, more particularly, for managing execution of queries against database samples. One embodiment provides a computer-implemented method for managing execution of a query against a database having a multiplicity of data records. The method comprises receiving, from a requesting entity, a query against the database, and performing an automated execution process, comprising: (i) iteratively executing the query against samples of the database, each sample including a subset of the multiplicity of data records, (ii) after each iterative execution of the query, determining whether a query result obtained for the iterative execution satisfies a predefined condition, and (iii) if the predefined condition is not satisfied, performing a predefined action.