I am quite new to learning about databases and I have come across the term "search space" in the context of query optimization. I am a little unsure of what the term means and why it is important? I have tried to search the web but haven't found any easy to understand answers.
Thanks in advance!
This search space is part of mathematical optimisation.
From Wikipedia's article on Feasible Region
(emphasis mine)
In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints.1 This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.
From Wikipedia's article on Search Algorithm
(emphasis mine)
Classes
[...]
For virtual search spaces
[...]
This class also includes various tree search algorithms, that view the elements as vertices of a tree, and traverse that tree in some special order. Examples of the latter include the exhaustive methods such as depth-first search and breadth-first search, as well as various heuristic-based search tree pruning methods such as backtracking and branch and bound. Unlike general metaheuristics, which at best work only in a probabilistic sense, many of these tree-search methods are guaranteed to find the exact or optimal solution, if given enough time. This is called "completeness".
I'm only including this answer, because it wouldn't fit in a comment and it's a Community wiki entry which can be improved upon by the community.
