Hello,

As an attempt to fix this issue a PR is created – https://github.com/MariaDB/server/pull/1856.
Greatly appreciate your input on this PR.

Thank you
Thejaka

(To improve understanding of the patch, I'll study the testcase)

The query:

SELECT

  sysapproval_approver0.`sys_id`

FROM

  sysapproval_approver sysapproval_approver0,

  task task1,

  task task2

WHERE

  (

    sysapproval_approver0.`sys_domain_path` = '/' OR 

    sysapproval_approver0.`sys_domain_path` LIKE '!!!/!!#/!!$/%' OR 

    sysapproval_approver0.`sys_domain_path` LIKE '!!!/!!!/%'

  )

  AND

  (

    task2.`sys_domain_path` = '/' OR 

    task2.`sys_domain_path` LIKE '!!!/!!#/!!$/%' OR 

    task2.`sys_domain_path` LIKE '!!!/!!!/%'

  )

  AND

  (

    task1.`sys_domain_path` = '/' OR 

    task1.`sys_domain_path` LIKE '!!!/!!#/!!$/%' OR 

    task1.`sys_domain_path` LIKE '!!!/!!!/%'

  )

  AND

  task2.`sys_id` LIKE '8e7792a7dbfffb00fff8a345ca961934%' AND

  sysapproval_approver0.`sysapproval` = task1.`sys_id` AND

  task1.`parent` = task2.`sys_id`

ORDER BY

  sysapproval_approver0.`order`

LIMIT  0, 50 ;

query plan before the patch:

sysapproval_approver0 (type=ALL, rows=50)

task1 (type=eq_ref)

task2 (type=eq_ref)

query plan after the patch:

task2 (type=range, key=PRIMARY, used_key_part= sys_id, rows=1)

task1 (type=ref, key=task_parent, rows=1)

sysapproval_approver0 (type=ref, key=sysapproval_approver_ref5, used_key_parts= sysapproval, rows= 1

Optimizer trace differences, comparing the code before the patch with the code after the patch:

             "table": "task2",

                "range_analysis": {

                  "table_scan": {

                    "rows": 50,

                    "cost": 13.1

                  },

...

                  "analyzing_range_alternatives": {

                    "range_scan_alternatives": [

                        "index": "PRIMARY",

                        "rows": 1,

                        "index": "sys_class_name_2",

                        "rows": 49,

                        "index": "sys_domain_path",

                        "rows": 49,

...

              {

                "selectivity_for_indexes": [

                  {

                    "index_name": "sys_class_name_2",

                    "selectivity_from_index": 0.98

+                 },

+                 {

+                   "index_name": "PRIMARY",

+                   "selectivity_from_index": 0.02

                  }

                ],

                "selectivity_for_columns": [],

-                "cond_selectivity": 0.98

+                "cond_selectivity": 0.0196

              }

.. that is, before this patch, the optimizer was using selectivity from sys_class_name2:

              "index": "sys_class_name_2",

              "ranges": [

                "(!!!/!!!/\0...,8e7792a7dbfffb00fff8a345ca961934) <= 

                    (sys_domain_path,sys_id) <= 

                    (!!!/!!!/?..,8e7792a7dbfffb00fff8a345ca961934)",

                "(!!!/!!#/!!$/\0...,8e7792a7dbfffb00fff8a345ca961934) <=

                    (sys_domain_path,sys_id) <= 

                    (!!!/!!#/!!$/?...,8e7792a7dbfffb00fff8a345ca961934)",

                "(/,8e7792a7dbfffb00fff8a345ca961934) <= 

                    (sys_domain_path,sys_id) <= 

                    (/,8e7792a7dbfffb00fff8a345ca961934)"

              ],

and ignoring selectivity from the PRIMARY key, because it has assumed (incorrectly! ) that quick select on sys_class_name_2 has "taken into account" the selectivity on column sys_id. (which is not the case. quick on sys_class_name_2 has rows=49, while the condition "sys_id=8e7..." has rows=1)

The worse part starts happening during the join optimizer.
Continuing to diff the trace of the current code vs patched code:

            "considered_execution_plans": [

              {

                "plan_prefix": [],

                "table": "task2",

                "best_access_path": {

                  "considered_access_paths": [

                    {

                      "access_type": "range",

-                      "resulting_rows": 49,

-                      "cost": 2e308,

+                     "resulting_rows": 0.98,

+                     "cost": 1.2147,

                      "chosen": true

                    }

                  ],

Note the "cost": 2e308 part.

An alternative patch. I think it's more "conservative":

diff --git a/sql/opt_range.cc b/sql/opt_range.cc

index 3b23fbe6325..607e3ee74f2 100644

--- a/sql/opt_range.cc

+++ b/sql/opt_range.cc

@@ -3670,6 +3602,14 @@ bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item **cond)

     }

   }

   trace_wrapper.add("cond_selectivity", table->cond_selectivity);

+  if (quick)

+  {

+    double trivial_sel= quick->records/table_records;

+    if (table->cond_selectivity > trivial_sel)

+      table->cond_selectivity= trivial_sel;

+  }

+  trace_wrapper.add("cond_selectivity_adjusted", table->cond_selectivity);

+

   DBUG_RETURN(FALSE);

 }

Hello Sergei,

Thanks a lot for all the comments and review feedback.
Let me study your feedback and get back to you.

Thanks
Thejaka

Hi thejaka,

Yes, I would appreciate the input.

I'm also interested if the patch posted two comments above solve your issues as well (I mean, it does solve the reduced testcase from the pull request, but does it solve the full case or any other cases you're hitting ?)

Hello Sergei,

The alternate patch attached works for the specific query above and few other queries I selected. To see whether it improves overall performance of all the degrading queries under selectivity=4, I need to run some further tests.

However, I am not sure whether the proposed alternate patch addresses the root cause of the issue reported in this ticket. When a query has range conditions on the primary key and other keys, the proposed alternate patch will still not consider condition selectivity from primary key range condition. The proposed alternate patch put an upper bound on the selectivity (trivial selectivity). However, there is still a possibility that the optimizer choosing a less efficient plan, because the table condition selectivity is excluding the primary key range condition selectivity. However, I am yet to find a counter example to demonstrate above.

What is your opinion about the above comment?

Also, are you planning to merge proposed alternate patch as a fix to this issue ?

Thank you
Thejaka

... the "alternative patch" posted above
https://jira.mariadb.org/browse/MDEV-25830?focusedCommentId=194186&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-194186
was not received well on the optimizer call, "because it's not a full solution".

Sergei,

This looks like it's got legs for the other bug I found. Know you are busy.

Larry

Just to note guys, I enabled the setting:

set optimizer_switch="extended_keys=off";

And that has helped, but I periodically still get queries that hang, that should run pretty quickly. Not sure I can do any testing though, and not sure this comment helps. With the extended_keys off, I do get correct query plans though, at least the times that I have checked them.

Larry

One of the queries hung, and then an optimize came right behind it and created a meta-data lock, but since the query before the optimize did not finish on it's own, the whole server started to melt down as transactional queries stacked up behind the meta-data/optimize lock. Today I implemented a long running query control mechanism to prevent blocking of the optimize queries, but it would be good to figure out why these queries are blocking randomly. It's very frustrating. Unfortunately, in my 20+ years experience with MySQL, I've never had to dig into the InnoDB engine status. So, it's still Greek to me. So, I likely won't be of much help in the near term. I'll log a separate ticket once I come up for air.

When fixing this bug please also keep the findings in MDEV-22537 in mind.

There is several known issues with optimizer_use_condition_selectivity=4.
I have been working on fixing selectivity and other related optimizer issues for the last 2 months and it's still a couple of months before I will be completely done.

See MDEV-26974, "Improve selectivity and related costs in optimizer"

My hope is that the code will be in 10.9. Until then, don't use optimizer_use_condition_selectivity=4.

I have checked the test case from the pull request with my new optimizer code and I get the same result file.
(In other words, my tree doesn't have this issue).

The part of the code that solves this particular issue is probably that I sort the ranges to first try the range with the least rows.
This gets the code to prefer the primary key, which solves this particular issue.

I will talk with Petrunia if we can take that particular sort code and add that to 10.4.8 and see if helps a bit, until I am ready with
the optimizer selectivity fixes.

Sorry, I missed that optimizer_use_condition_selectivity=4 is now default. I agree that we should try to fix the biggest issues in selectivity in 10.4, but the real fixes has to wait for 10.9 (as there are a LOT of them and they need proper testing before we can even consider back porting any of them)

Patch given on slack

The issue was that calc_cond_selectivity_for_table preferred ranges with
many parts and when deciding on which selectivity to use.
Fixed by going through ranges according to the number of rows in the range.

This ensures that selectivity from ranges with few rows will be preferred
over ranges with many rows for indexes that uses the same columns.