An auto-parameterization process transforms a database query into a parameterized basic query form by replacing any constant values in the query with parameters. The auto-parameterization process attempts to generate a safe execution plan from the basic query form if there is currently no such plan available. A safe execution plan is defined as an execution plan that is optimal over a range of values for the parameters. If a safe execution plan can be generated, it is passed for execution, along with the constant values that were present in the query. If a safe execution plan cannot be generated, the auto-parameterization process passes a specific execution plan for execution. The safe execution plan is cached either at the time it is created or at the time it is executed. The cache is searched each time a parameterized basic query plan is generated by the auto-parameterization process. The auto-parameterization process also evaluates the query before creating the corresponding parameterized basic query form to determine if it is likely that a safe execution plan can be generated for the query.