A method executed by a DBMS, the method comprising: selecting a working set of queries; monitoring column usage of said working set of queries; based on said column usage, selecting a certain set of one or more auto indexes, wherein selecting said certain set of one or more auto indexes includes, for each auto index of a set of one or more potential auto indexes: materializing said each auto index in a state that makes said each auto index not used for queries not in said working set; performing test-execute verification of said each auto index for a respective test-execute set of queries from the working set of queries; if said test-execute verification shows that use of said each auto index improves query execution performance for at least a threshold number of queries from the respective test-execute set of queries, then including said each auto index in said certain set of one or more auto indexes; in response to selecting said certain set of one or more auto indexes, making said certain set of one or more auto indexes available (135, 460) for executing queries not in said working set; after making said certain set of one or more auto indexes available (135, 460) for executing queries not in said working set: compiling a particular query not in the working set of queries thereby generating a first execution plan, said first execution plan using a particular auto index of said certain set of one or more auto indexes; compiling said particular query thereby generating a second execution plan, wherein use of said particular auto index is prevented for said second execution plan; monitoring query execution performance, and determining whether query execution performance of said first execution plan is degraded compared to query execution performance of said second execution plan; and if said query execution performance of said first execution plan is degraded, then locking down said particular auto index for said particular query, thereby preventing use of said particular auto index in execution of said particular query by other database sessions. selecting a working set of queries; monitoring column usage of said working set of queries; based on said column usage, selecting a certain set of one or more auto indexes, wherein selecting said certain set of one or more auto indexes includes, for each auto index of a set of one or more potential auto indexes: materializing said each auto index in a state that makes said each auto index not used for queries not in said working set; performing test-execute verification of said each auto index for a respective test-execute set of queries from the working set of queries; if said test-execute verification shows that use of said each auto index improves query execution performance for at least a threshold number of queries from the respective test-execute set of queries, then including said each auto index in said certain set of one or more auto indexes; materializing said each auto index in a state that makes said each auto index not used for queries not in said working set; performing test-execute verification of said each auto index for a respective test-execute set of queries from the working set of queries; if said test-execute verification shows that use of said each auto index improves query execution performance for at least a threshold number of queries from the respective test-execute set of queries, then including said each auto index in said certain set of one or more auto indexes; in response to selecting said certain set of one or more auto indexes, making said certain set of one or more auto indexes available (135, 460) for executing queries not in said working set; after making said certain set of one or more auto indexes available (135, 460) for executing queries not in said working set: compiling a particular query not in the working set of queries thereby generating a first execution plan, said first execution plan using a particular auto index of said certain set of one or more auto indexes; compiling said particular query thereby generating a second execution plan, wherein use of said particular auto index is prevented for said second execution plan; monitoring query execution performance, and determining whether query execution performance of said first execution plan is degraded compared to query execution performance of said second execution plan; and if said query execution performance of said first execution plan is degraded, then locking down said particular auto index for said particular query, thereby preventing use of said particular auto index in execution of said particular query by other database sessions. compiling a particular query not in the working set of queries thereby generating a first execution plan, said first execution plan using a particular auto index of said certain set of one or more auto indexes; compiling said particular query thereby generating a second execution plan, wherein use of said particular auto index is prevented for said second execution plan; monitoring query execution performance, and determining whether query execution performance of said first execution plan is degraded compared to query execution performance of said second execution plan; and if said query execution performance of said first execution plan is degraded, then locking down said particular auto index for said particular query, thereby preventing use of said particular auto index in execution of said particular query by other database sessions.