A cost-based optimizer is responsible for exploring different query evaluation plans and selecting the one that minimizes the estimated cost. It evaluates the cost of different execution strategies based on factors such as the amount of data and the number of joins involved.