Systems and methods for index selection in collections of data
View Patent ↗Systems and methods are disclosed that utilize a genetic algorithm to search for an index configuration for a collection of data such as, e.g., a database. Genetic algorithms can include stochastic search heuristics that mimic processes of natural evolution including inheritance, mutation, crossover, and selection. A population of chromosomes representing candidate index configurations can evolve to increase or optimize the fitness of the population and to identify the best (e.g., most fit) index configuration. Fitness of a chromosome may be measured based at least in part on the cost of computer resources used for executing Structured Query Language (SQL) statements in the indexed database. In various implementations, virtual indexing may be used to simulate building an index, chromosomes may be encoded using non-bitmapped representations of index configurations, chromosomes may include genes representing a column in a table in a database, dropping an index from a table in a database, or a composite index for a database, and/or a participation pool may be used to select fitter genes for an initial population of chromosomes.
1. 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.
2. The method of claim 1 , wherein the database comprises a relational database.
3. The method of claim 1 , wherein the identifier comprises alphanumeric information identifying a table of the database and a column of the table.
4. The method of claim 1 , wherein the identifier comprises alphanumeric information identifying the disabled index.
5. The method of claim 1 , wherein determining the participation probability for each gene comprises:
calculating a first cost of the set of SQL statements for the database before the index candidate associated with the gene is virtually built;
virtually building the index candidate associated with the gene; and
calculating a second cost of the set of SQL statements for the database after the index candidate associated with the gene is virtually built.
6. The method of claim 5 , wherein the total change in cost of the set of SQL statements for the index candidate associated with the gene is based at least in part on a difference between the second cost and the first cost.
7. The method of claim 1 , wherein the participation probability for each gene in the gene pool is greater than or equal to a minimum participation probability.
8. The method of claim 1 , wherein evolving the initial population of chromosomes to form the offspring population of chromosomes further comprises including at least one of the chromosomes in the initial population in the offspring population.
9. The method of claim 1 , wherein determining a fitness of each of the chromosomes in the offspring population comprises determining a cost of the set of SQL statements for an index configuration for the database, the index configuration comprising the index candidates associated with the genes in the chromosome.
10. The method of claim 9 , wherein determining the fitness of each of the chromosomes in the offspring population comprises:
calculating a first cost of the set of SQL statements for the database before the index configuration associated with the chromosome is virtually built;
virtually building the index configuration associated with the chromosome; and
calculating a second cost of the set of SQL statements for the database after the index configuration associated with the chromosome is virtually built.
11. The method of claim 10 , wherein the cost of the set of SQL statements for the index configuration is based at least in part on a difference between the second cost and the first cost.
12. The method of claim 1 , further comprising repeating one or more times: (1) evolving the initial population of chromosomes to form the offspring population of chromosomes, (2) determining the fitness of each of the chromosomes in the offspring population, and (3) evaluating whether to terminate the evolving.
13. The method of claim 1 , wherein the termination criterion comprises: (1) a number of generations of the offspring population, (2) a maximum elapsed time, (3) a time-of-day, (4) a maximum computer processing time, (5) a maximum amount of computer resource usage, or (6) a threshold level of fitness.
14. The method of claim 1 , wherein providing information associated with one or more of the chromosomes in the offspring population comprises providing information associated with the chromosome having the largest fitness in the offspring population.
15. The method of claim 1 , wherein forming the gene pool comprises, for a gene associated with a composite index candidate,
determining, based at least in part on a probability distribution for lengths of composite index candidates, a length L≧2 for a composite index associated with the gene;
selecting L columns from tables in the database for inclusion in the composite index associated with the gene, wherein a column is selected based at least in part on a participation probability associated with the column.
16. The method of claim 15 , wherein the participation probability for the column is based at least in part on a cost of the set of SQL statements for a virtual index comprising the column.
17. The method of claim 15 , wherein the probability distribution for lengths of the composite index candidates decreases with length for at least a range of lengths.
18. The method of claim 1 , wherein evolving the initial population of chromosomes to form the offspring population of chromosomes further comprises one or both of: (1) determining whether to increase the length of at least some of the chromosomes in the offspring population by adding one or more new genes to the at least some of the chromosomes and (2) determining whether to increase the size of the offspring population by adding one or more new chromosomes to the offspring population.
19. The method of claim 18 , wherein if it is determined to increase the length of at least some of the chromosomes in the offspring population or to increase the size of the offspring population, the method further comprises:
selecting a gene from the gene pool based at least in part on the participation probability of the gene; and
adding the gene to a chromosome having its length extended or to a new chromosome that increases the size of the population pool.
20. The method of claim 18 , wherein determining whether to increase the size of the offspring population by adding one or more new chromosomes to the offspring population comprises determining whether increasing the length of the chromosomes in a prior offspring population led to a significant fitness improvement after a threshold number of generations of evolution.
21. The method of claim 18 , wherein determining whether to increase the length of at least some of the chromosomes in the offspring population by adding one or more new genes to the at least some of the chromosomes comprises determining whether increasing the number of chromosomes in a prior offspring population led to a significant fitness improvement after a threshold number of generations of evolution.
22. A system for managing index configurations for a database, the system comprising:
an index selection subsystem configured to communicate with a data repository configured to store a database, the index selection subsystem configured to execute one or more modules on a computing device, the index selection subsystem comprising:
a population module configured to provide a population of chromosomes, wherein each chromosome in the population of chromosomes is an index configuration for the database, wherein each chromosome further comprises one or more genes, wherein each gene comprises an associated index candidate for the database;
a fitness module configured to provide a fitness for each of the chromosomes in the population, wherein the fitness module determines a participation probability by being configured to:
determine the individual change in cost associated with using each gene in a gene pool, the gene pool based on a set of SQL statements;
determine a total change in cost of the gene pool by summing the individual costs of each gene in the gene pool; and
divide the individual change in cost for each gene by the total change in cost of the gene pool; and
select one or more genes from an initial population of one or more chromosomes based at least in part on the participation probability for each gene in the gene pool;
an evolution module configured to evolve an initial population of chromosomes based at least in part on one or more genetic operators, the evolution module further configured to (1) increase the number of chromosomes in an offspring population in response to a first criterion or (2) increase the length of at least some of the chromosomes in the initial population in response to a second criterion; and
an interface module configured to provide information associated with one or more of the chromosomes in the offspring population.
23. The system of claim 22 , wherein the population module is configured to represent an index candidate in a gene based at least in part on an alphanumeric identifier for the index candidate.
24. The system of claim 22 , wherein the population module is configured to provide the offspring population of chromosomes by retrieving from the data repository information related to a prior evolution of chromosomes for the database.
25. The system of claim 22 , wherein the evolution module is further configured to terminate the evolution of the population based on one or more termination criteria, the termination criteria comprising one or more of: (1) a number of generations of the offspring population, (2) an elapsed time, (3) a time-of-day, (4) an amount of computer processing time, (5) an amount of computer resources used by the system, and (6) a threshold level of fitness.
26. The system of claim 25 , wherein the interface module is configured to provide information associated with a chromosome having the greatest fitness in the population when the evolution is terminated.
27. The system of claim 22 , wherein the first criterion comprises determining whether increasing the length of at least some of the chromosomes in a prior population led to a significant fitness improvement after a threshold number of generations of evolution.
28. The system of claim 22 , wherein the second criterion comprises determining whether increasing the number of chromosomes in a prior population led to a significant fitness improvement after a threshold number of generations of evolution.
29. The system of claim 22 , wherein the database comprises a plurality of tables, each of the tables comprising one or more columns of data, and the index candidates comprise (1) a column in one of the plurality of tables in the database, (2) dropping an index from one of the plurality of tables in the database, and (3) a composite index for the database, the composite index comprising a plurality of columns from one or more of the plurality of tables in the database.
30. The system of claim 29 , wherein, for an index candidate comprising a composite index for the database, the population module is configured to determine a length for the composite index based at least in part on a probability distribution for lengths of composite index candidates.
31. The system of claim 30 , wherein the population module is further configured to select columns for the composite index based at least in part on a participation probability for the column.