Monty says: I want to wish you a happy new year with MariaDB 11.0!
When I created the original MySQL optimizer in 1995, it was quite simple. A big part of the plans were based on costs, but there where also a lot of rule based choices. The original 'base of cost' was "one disk seek". The cost of key read was also a disk seek.
Over time a lot of developers have worked on the optimizer and added many new features, but the original cost model has stayed the same (until now). Most new features was done with based on a cost model, but still some new things (like deciding which index to use for sorting) were still partly rule based.
If there was only one or a few choices for a plan, the old optimizer was reasonably good in finding a good plan. But the more complex the queries got (complex = a lot of different choices could be made for each table) the more chance that it would not find the optimal plan. This goes all back to the original cost model not being 'good enough'.
The main developers of the 11.0 optimizer changes in MariaDB 11.0 are Sergei Petrunia and me. Vicențiu Ciorbaru has also provided some code and help.
The optimizer changes consist of more than 100 commits, starting from October 2021!
It has been a long project!