Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-20129

Equality propagation for ORDER BY items do not work with expressions

Details

    • Bug
    • Status: Stalled (View Workflow)
    • Major
    • Resolution: Unresolved
    • 10.2(EOL), 10.3(EOL), 10.4(EOL), 10.5, 10.6, 10.9(EOL), 10.10(EOL), 10.11, 11.0(EOL), 11.1(EOL), 11.2(EOL)
    • 10.6, 10.11
    • Optimizer
    • None

    Description

      Test data

      create table ten(a int);
      		 
      insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
      		 
       
      		 
      create table one_k(a int);
      		 
      insert into one_k select A.a + B.a* 10 + C.a * 100 from ten A, ten B, ten C;
      		 
       
      		 
      create table t1(a int, b int);
      		 
      insert into t1 select A.a + B.a* 10, A.a + B.a* 10 from ten A, ten B;
      		 
      create table t2(a int, b int, key(a));
      		 
      insert into t2 select A.a + B.a* 10, A.a+B.a*10 from ten A, ten B;
      		 
      create table t3(a int, b int);
      		 
      insert into t3 select A.a + B.a* 10 + C.a * 100, A.a + B.a* 10 + C.a * 100 from ten A, ten B, ten C


      MariaDB [test]>  explain select * from t1,t2 where t1.a > 95  and t1.a=t2.a order by t2.a;
      		 
      +------+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------------+
      		 
      | id   | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra                       |
      		 
      +------+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------------+
      		 
      |    1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      | 100  | Using where; Using filesort |
      		 
      |    1 | SIMPLE      | t2    | ref  | a             | a    | 5       | test.t1.a | 1    |                             |
      		 
      +------+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------------+
      		 
      2 rows in set (0.008 sec)
      		 
       
      		 
      MariaDB [test]>  explain select * from t1,t2 where t1.a > 95  and t1.a=t2.a order by t2.a+1;
      		 
      +------+-------------+-------+------+---------------+------+---------+-----------+------+----------------------------------------------+
      		 
      | id   | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra                                        |
      		 
      +------+-------------+-------+------+---------------+------+---------+-----------+------+----------------------------------------------+
      		 
      |    1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      | 100  | Using where; Using temporary; Using filesort |
      		 
      |    1 | SIMPLE      | t2    | ref  | a             | a    | 5       | test.t1.a | 1    |                                              |
      		 
      +------+-------------+-------+------+---------------+------+---------+-----------+------+----------------------------------------------+
      		 
      2 rows in set (0.004 sec)

      So for expressions we don't propagate equal fields and so we are not able to use the optimization where we can sort by the first table

      Attachments

        Issue Links

          relates to

          New Feature - A new feature of the product, which has yet to be developed. MDEV-8306 Complete cost-based optimization for ORDER BY with LIMIT

          • Major - Major loss of function.
          • Stalled

          Activity

            Ascending order - Click to sort in descending order
            varun Varun Gupta (Inactive) added a comment -

            Patch
            http://lists.askmonty.org/pipermail/commits/2019-July/013914.html

            varun Varun Gupta (Inactive) added a comment - Patch http://lists.askmonty.org/pipermail/commits/2019-July/013914.html
            psergei Sergei Petrunia added a comment -

            Review notes:

            The idea behind the new function equality_propagation_for_order_items doesn't look good to me.

            The effect of the function is similar (but exactly the same) as propagate_equal_fields call followed by substitute_for_best_equal_field call.

            Here is an alternative variant of the fix that uses those two calls: https://gist.github.com/spetrunia/f48251cc87f07cc8e4a8fa9910bbe6c7

            psergei Sergei Petrunia added a comment - Review notes: The idea behind the new function equality_propagation_for_order_items doesn't look good to me. The effect of the function is similar (but exactly the same) as propagate_equal_fields call followed by substitute_for_best_equal_field call. Here is an alternative variant of the fix that uses those two calls: https://gist.github.com/spetrunia/f48251cc87f07cc8e4a8fa9910bbe6c7
            psergei Sergei Petrunia added a comment -

            Another interesting observation:

            Before the patch, the optimizer only handles "ORDER BY table.col".

            The code in remove_const() checks if it can be substituted with other_table.col, and whether that will allow to get rid of "Using temporary". No substitution is performed here. The substitution is done in Filesort::make_sortorder():

                  /*
            		 
                    It is possible that the query plan is to read table t1, while the
            		 
                    sort criteria actually has "ORDER BY t2.col" and the WHERE clause has
            		 
                    a multi-equality(t1.col, t2.col, ...).
            		 
                    The optimizer detects such cases (grep for
            		 
                    UseMultipleEqualitiesToRemoveTempTable to see where), but doesn't
            		 
                    perform equality substitution in the order->item. We need to do the
            		 
                    substitution here ourselves.
            		 
                  */
            		 
            9     table_map item_map= first->used_tables();                                                                                     
                  if (join && (item_map & ~join->const_table_map) &&
            		 
                      !(item_map & first_table_bit) && join->cond_equal &&
            		 
                       first->get_item_equal())
            		 
                  {

            (item->get_item_equal() returns non-NULL only for Item_field and Item_direct_view_ref. )
            Let's call the above "Late substitution".

            The patch for this MDEv adds "early substitution": if the Item_field that we need to replace is not at the top level of the ORDER BY clause, it will be replaced in remove_const().

            Can we switch the code to do the substitution in only one place and do it "early"?

            I've tried to do that and got an assertion failure in create_tmp_table, not sure why.

            psergei Sergei Petrunia added a comment - Another interesting observation: Before the patch, the optimizer only handles "ORDER BY table.col". The code in remove_const() checks if it can be substituted with other_table.col, and whether that will allow to get rid of "Using temporary". No substitution is performed here. The substitution is done in Filesort::make_sortorder(): /* It is possible that the query plan is to read table t1, while the sort criteria actually has "ORDER BY t2.col" and the WHERE clause has a multi-equality(t1.col, t2.col, ...). The optimizer detects such cases (grep for UseMultipleEqualitiesToRemoveTempTable to see where), but doesn't perform equality substitution in the order->item. We need to do the substitution here ourselves. */ 9 table_map item_map= first->used_tables(); if (join && (item_map & ~join->const_table_map) && !(item_map & first_table_bit) && join->cond_equal && first->get_item_equal()) { (item->get_item_equal() returns non-NULL only for Item_field and Item_direct_view_ref. ) Let's call the above "Late substitution". The patch for this MDEv adds "early substitution": if the Item_field that we need to replace is not at the top level of the ORDER BY clause, it will be replaced in remove_const() . Can we switch the code to do the substitution in only one place and do it "early"? I've tried to do that and got an assertion failure in create_tmp_table, not sure why.

            People

              psergei Sergei Petrunia
              varun Varun Gupta (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

                Created:
                Updated:

                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.