Patent ID: 8499001

Claim:
A method for finding an index configuration for a database, the method comprising: under control of a computing system comprising one or more physical computing devices, determining, from a set of structured query language (SQL) statements for a database, a set of index candidates for the database, the index candidates comprising at least one of: (1) a column in a table in the database, (2) disabling an index associated with a table in the database, and (3) a composite index for the database, the composite index comprising a plurality of columns from at least one table in the database; forming a gene pool comprising a plurality of genes associated with the set of index candidates for the database based on the set of SQL statements, wherein each gene in the gene pool is a representation of an associated index candidate from the set of index candidates, the representation comprising an identifier for the associated index candidate; determining a participation probability for each gene in the gene pool, the participation probability for a gene based at least in part on: determining the individual change in cost associated with using each gene in the gene pool; normalizing the individual change in cost associated with using each gene in the gene pool; determining a total change in cost of the gene pool by summing the individual costs of each gene in the gene pool; and dividing the individual change in cost for each gene by the total change in cost of the gene pool; generating an initial population of one or more chromosomes, wherein each chromosome is an index configuration for the database that comprises one or more of the genes from the gene pool, wherein the generating comprises filling the one or more genes in a chromosome based at least in part on the participation probability for that gene; evolving the initial population of chromosomes to form an offspring population of chromosomes, wherein the evolving comprises applying at least one of a crossover operator and a mutation operator to at least some of the chromosomes in the initial population; determining a fitness of each of the chromosomes in the offspring population; evaluating whether to terminate the evolving based at least in part on a termination criterion; and providing information associated with one or more of the chromosomes in the offspring population.