The branch is preview-10.10-optimizer

The final version of the patch to the last known bug related to the feature is here: bb-10.10-mdev28929-v4

I have no arguments against pushing the feature as of bb-10.10-mdev28929-v4 ac3b3807cc into 10.10 main and releasing with 10.10.1.

Minority report

As discussed on different occasions before, I disagree with the line our optimizer takes for distinguishing use cases of interest from ignorable ones, bug-wise. There is a lot of confusion in regard to what is a "realistic" use case, and it becomes especially extreme when performance is concerned.

We do run lots of truly unrealistic queries in our tests, like when a bit column would be compared to a timestamp, or a meaningless chain of functions would be used, and so on. But I'm not talking about those.

What optimizer tends to demand for "realistic", when the data is nearly normally distributed, all tables are populated with a suitable number of rows, all needed indexes exist, and all join conditions are fulfilled, is not a realistic use case, it is an ideal use case. They do exist of course, but in the real world, for every ideal setup there will probably be hundreds of non-ideal ones. There are plenty of empty tables out there, the data is distributed in all possible ways, indexes are missing or misused, statistics aren't up-to-date, and filtering conditions miss the mark. It doesn't make them unrealistic or corner cases.

While it is totally fine to limit new improvements and fine-tuning to as narrow of a scope as we want, and use the ideal setup for demonstrating our superiority, it cannot be applied the same way to regression considerations. Small regressions can probably be tolerated, or at least it can be reasonably argued that if an application is so sensitive to performance fluctuations, it should be first of all optimized itself. But if an application had been doing the same things the same way for years and was performing reasonably well, and suddenly the latency of its query jumps from milliseconds to tens of minutes, there is no justification which can convince the affected users that it's not a bug but their fault. As we would consider a new crash or a wrong result on such a query to be a real regression and wouldn't claim that the user needs to rewrite the query, severe performance degradations should be treated the same way.

So, while officially testing the feature for wrong results and stability regressions, I was also taking sideline notes in regard to the performance (latency) comparison between the feature tree and the baseline. Unlike official benchmark and other "good" test configurations, mine is in no way tuned to highlight the strengths of the optimizer, if anything it's the contrary.
The good news is that even on my unfriendly test input, the supermajority of measurable results have shown improvement in the feature tree vs the baseline.
However, there has been a noticeable number of cases where the latency on the feature tree was dozens, hundreds or thousands times worse than on the baseline. A few samples provided for investigation were disqualified as non-bugs, because the optimizer isn't capable of handling them due to their deviations from the criteria for realistic queries, as described above, and thus they are not cases of interest.
Examples: MDEV-29072, MDEV-29073 (I stopped filing after that; a few more were discussed outside JIRA and ruled out on the same reasons).

I expect this approach to backfire when/if similar problems start affecting real users, but since that's the reality – the cases are not going to be fixed at least until real users complain – and the new feature seems to be doing more good than harm on average, I see no valid reasons to object against releasing it. Performance testing is not my specialty anyway, I cannot claim any expertise and have a decisive opinion on the subject.

one customer, impacted by same issue when there are good no. of tables to join then queries are stuck in "statistics" state and take long to generate EXPLAIN output. Lowering optimizer_search_depth to small value worked well and setting optimizer_search_depth=0 result as good workaround.

https://mariadb.com/kb/en/server-system-variables/#optimizer_search_depth
"Note that the value 0 (zero) is a special case where the optimiser chooses and sets the optimal search depth for each query, thus adding a bit of overhead to the optimisation process."

One of our customers, also having this problem at 10.6.10 release. Locally, I can repro this case, with their shared data and query.
The query looks to be having many tables involved in the join, executing this query getting stuck in the STATISTIC state forever.

For now, asked to set optimizer_search_depth=0 as a workaround, which made the query to execute faster though.

ralf.gebhardt, I've checked.

There were multiple commits pushed that were marked with MDEV-28073.

The fix for MDEV-28073, pushed into 10.6+:

commit b729896d00e022f6205399376c0cc107e1ee0704

Author: Monty <monty@mariadb.org>

Date:   Tue May 10 11:47:20 2022 +0300

    MDEV-28073 Query performance degradation in newer MariaDB versions when using many tables

    The issue was that best_extension_by_limited_search() had to go through

    too many plans with the same cost as there where many EQ_REF tables.

    Fixed by shortcutting EQ_REF (AND REF) when the result only contains one

    row. This got the optimization time down from hours to sub seconds.

Then, there were a series of commits pushed into 10.10.1+:

commit b3c74bdc1f09b2b8babd7f2bd9d52df2749ddcc3

Author: Monty <monty@mariadb.org>

Date:   Tue May 31 17:36:32 2022 +0300

    Improve pruning in greedy_search by sorting tables during search

    MDEV-28073 Slow query performance in MariaDB when using many tables

...

... a few more related commits follow, until this one:

commit 515b9ad05a6de9dac3871ef2769dde1b5834c6e3

Author: Monty <monty@mariadb.org>

Date:   Thu Jun 2 19:47:23 2022 +0300

    Added EQ_REF chaining to the greedy_optimizer

    MDEV-28073 Slow query performance in MariaDB when using many table

    The idea is to prefer and chain EQ_REF tables (tables that uses an

    unique key to find a row) when searching for the best table combination.

    This significantly reduces row combinations that has to be examined.

    This is optimization is enabled when setting optimizer_prune_level=2

    (which is now default).

    Implementation:

    - optimizer_prune_level has a new level, 2, which enables EQ_REF

      optimization in addition to the pruning done by level 1.

    ...

Then, there is this commit (also in 10.10.1+) which is a fix for patch for this MDEV and is the only one mentioning MDEV-28929:

commit 8c2faad576d6a77314e92755a389de2c41e21242

Author: Sergei Petrunia <sergey@mariadb.com>

Date:   Tue Jul 19 14:13:17 2022 +0300

    MDEV-28929: Plan selection takes forever with MDEV-28852 ...

    Part #2: Extend heuristic pruning to use multiple tables as the

    "Model tables".

The commits that fix this MDEV are b3c74bdc1f09b2b8babd7f2bd9d52df2749ddcc3..515b9ad05a6de9dac3871ef2769dde1b5834c6e3 , endpoints inclusive.