Question: Is "genetic search algorithm" the correct description for Index Advisor?

[sgykfjsm]

Question

Documentation page
https://docs.pingcap.com/tidb/stable/index-advisor/#index-advisor

Current text

The Index Advisor analyzes queries to identify indexable columns from clauses such as WHERE, GROUP BY, and ORDER BY. Then, it generates index candidates and estimates their performance benefits using hypothetical indexes. TiDB uses a genetic search algorithm to select the optimal set of indexes starting with single-column indexes and iteratively exploring multi-column indexes, leveraging a "What-If" analysis to evaluate potential indexes based on their impact on optimizer plan costs. The advisor recommends indexes when they reduce the overall cost compared to executing queries without them.

Question

I'd like to ask about the phrase "TiDB uses a genetic search algorithm" in this description.

Looking at the source code comment in pkg/planner/indexadvisor/algorithm.go:

https://github.com/pingcap/tidb/blob/release-8.5-20260724-v8.5.7/pkg/planner/indexadvisor/algorithm.go#L26-L33

This algorithm resembles the index selection algorithm published in 1997 by Chaudhuri
and Narasayya. Details can be found in the original paper:
Surajit Chaudhuri, Vivek R. Narasayya: An Efficient Cost-Driven Index Selection
Tool for Microsoft Query Server. VLDB 1997: 146-155
This implementation is the Golang version of
https://github.com/hyrise/index_selection_evaluation/blob/refactoring/selection/algorithms/auto_admin_algorithm.py.

The implementation (calculateBestIndexes, enumerateNaive, enumerateGreedy, selectIndexCandidates) appears to enumerate small candidate sets exhaustively and extend larger ones greedily, guided by cost estimates from What-If analysis — which looks like the classic AutoAdmin algorithm (Chaudhuri & Narasayya, VLDB 1997) rather than a genetic algorithm in the usual sense (population, crossover, mutation, fitness-based selection across generations).

Could someone help clarify:

1. Is "genetic search algorithm" intended as a general/informal way of describing the iterative candidate-generation process, or does it refer to an actual genetic-algorithm technique used somewhere in the implementation?
2. If it's the former, would it make sense to update the wording to avoid confusion with the formal meaning of "genetic algorithm"?

Happy to help with a doc PR if that would be useful.

References

• S. Chaudhuri, V. R. Narasayya, "An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server," VLDB 1997, pp. 146–155.
• https://github.com/hyrise/index_selection_evaluation/blob/refactoring/selection/algorithms/auto_admin_algorithm.py

[qiancai]

Hi @qw4990, would you please help clarify? Thanks.