Techniques are described for re-starting queries based on an expected amount of data to be changed in a database. Embodiments of the present disclosure may generally receive a first query to be executed against a database, and start execution of the first query against the database according to a first access plan. Upon detecting, during execution of the first query, that an amount of data to be changed in one or more tables of the database as a result of a second query satisfies a predetermined condition, embodiments of the present disclosure determine whether to re-start execution of the first query against the database with a second access plan different from the first access plan or wait a predetermined period of time before re-starting execution of the first query against the database with the first access plan.