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

LATERAL DERIVED refills the temp. table too many times

    XMLWordPrintable

    Details

      Description

      Short

      LATERAL DERIVED optimization refills the temp. table every time the derived table is accessed, regardless of whether the inputs have changed or not.

      LATERAL DERIVED's cost calculations match the execution and also assume the temp.table is refilled every time.
      The join optimizer typically over-estimates join output cardinality, so the optimizer considers LATERAL DERIVED optimization to be even more expensive.

      Taken together, these two properties cause the optimizer to miss using LATERAL DERIVED optimization where it is very advantageous.

      Long

      (This is based on a real-world case but the dataset I am using is totally artificial)

      Tables that will make a prefix before the lateral:

      # 5 values
      create table t1(a int, b int);
      insert into t1 select seq,seq from seq_1_to_5;
       
      # 5 value groups of size 2 each
      create table t2(a int, b int, key(a));
      insert into t2
      select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B;
       
      # 5 value groups of size 3 each
      create table t3(a int, b int, key(a));
      insert into t3
      select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B;
       
      analyze table t1,t2,t3 persistent for all;
      

      explain
      select * from
        (t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b;
      

      +------+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
      | id   | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra       |
      +------+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
      |    1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      | 5    |             |
      |    1 | SIMPLE      | t2    | ref  | a             | a    | 5       | test.t1.b | 2    | Using where |
      |    1 | SIMPLE      | t3    | ref  | a             | a    | 5       | test.t1.b | 3    | Using where |
      +------+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
      

      Now, tables for the LATERAL DERIVED:

      create table t10 (
        grp_id int,
        col1 int,
        key(grp_id)
      );
       
      # 100 groups of 100 values each
      insert into t10
      select
        A.seq,
        B.seq
      from
        seq_1_to_100 A,
        seq_1_to_100 B;
       
      # and X10 multiplier
      create table t11 (
        col1 int,
        col2 int
      );
      insert into t11
      select A.seq, A.seq from seq_1_to_10 A;
       
      analyze table t10,t11 persistent for all;
      

      Now, the query:

      explain
      select * from
        (
          (t1 left join t2 on t2.a=t1.b)
          left join t3 on t3.a=t1.b
        ) left join (select grp_id, count(*)
                     from t10 left join t11 on t11.col1=t10.col1
                     group by grp_id) T on T.grp_id=t1.b;
      

      Note that the join is between T and t1, the first table. t1 has 5 rows. However, the optimizer assumes that the table is refilled t1xt2xt3: 30 times.
      Because of that, it doesn't pick LATERAL DERIVED:

      +------+-------------+------------+------+---------------+------+---------+-----------+-------+-------------------------------------------------+
      | id   | select_type | table      | type | possible_keys | key  | key_len | ref       | rows  | Extra                                           |
      +------+-------------+------------+------+---------------+------+---------+-----------+-------+-------------------------------------------------+
      |    1 | PRIMARY     | t1         | ALL  | NULL          | NULL | NULL    | NULL      | 5     |                                                 |
      |    1 | PRIMARY     | t2         | ref  | a             | a    | 5       | test.t1.b | 2     | Using where                                     |
      |    1 | PRIMARY     | t3         | ref  | a             | a    | 5       | test.t1.b | 3     | Using where                                     |
      |    1 | PRIMARY     | <derived2> | ref  | key0          | key0 | 5       | test.t1.b | 1000  | Using where                                     |
      |    2 | DERIVED     | t10        | ALL  | grp_id        | NULL | NULL    | NULL      | 10000 | Using temporary; Using filesort                 |
      |    2 | DERIVED     | t11        | ALL  | NULL          | NULL | NULL    | NULL      | 10    | Using where; Using join buffer (flat, BNL join) |
      +------+-------------+------------+------+---------------+------+---------+-----------+-------+-------------------------------------------------+
      

        Attachments

          Activity

            People

            Assignee:
            psergei Sergei Petrunia
            Reporter:
            psergei Sergei Petrunia
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Dates

              Created:
              Updated:

                Git Integration