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

Query with: Cross join, Non-indexed column comparison, Column with histogram: speed varies 20x depending on histogram type

Details

    • Bug
    • Status: Closed (View Workflow)
    • Critical
    • Resolution: Not a Bug
    • N/A
    • N/A
    • Optimizer
    • None

    Description

      CREATE OR REPLACE TABLE t (
        f1 text,
        f2 int,
        f3 varchar(16),
        f4 text,
        f5 blob,
        f6 blob,
        f7 text,
        f8 blob,
        f9 text
      ) ENGINE=MyISAM;
       
      CREATE OR REPLACE ALGORITHM=TEMPTABLE VIEW v AS SELECT * FROM t;
       
      INSERT INTO t SELECT
        REPEAT('a',900),
        seq%8+1,
        CONCAT('s',seq%8+1),
        NULL,
        REPEAT('b',900),
        REPEAT('c',100*(seq%8+1)),
        NULL,
        REPEAT('d',700),
        REPEAT('e',800)
      FROM seq_1_to_128;
       
      ANALYZE TABLE t PERSISTENT FOR ALL;
       
      SELECT v.f2 FROM
        v, t AS t_outer
        LEFT JOIN
          v AS v_inner
          JOIN
          t AS t_inner
          ON (t_inner.f3 = v_inner.f3)
        ON (t_outer.f2 = v_inner.f2)
      GROUP BY v.f2
      HAVING v.f2 != 5;
      

      On a non-debug build on my machine, with SINGLE_PREC_HB the query takes less than a second. With JSON_HB it takes over 20 seconds.

      SINGLE_PREC_HB

      +------+
      | f2   |
      +------+
      |    1 |
      |    2 |
      |    3 |
      |    4 |
      |    6 |
      |    7 |
      |    8 |
      +------+
      7 rows in set (0.893 sec)
      

      JSON_HB

      | f2   |
      +------+
      |    1 |
      |    2 |
      |    3 |
      |    4 |
      |    6 |
      |    7 |
      |    8 |
      +------+
      7 rows in set (20.850 sec)
      

      The effect seems to be deterministic.

      Analyze output:

      SINGLE_PREC_HB

      ANALYZE: {
        "query_block": {
          "select_id": 1,
          "r_loops": 1,
          "r_total_time_ms": 877.7945293,
          "filesort": {
            "sort_key": "v.f2",
            "r_loops": 1,
            "r_total_time_ms": 0.006179985,
            "r_used_priority_queue": false,
            "r_output_rows": 7,
            "r_buffer_size": "360",
            "r_sort_mode": "sort_key,rowid",
            "temporary_table": {
              "table": {
                "table_name": "t_outer",
                "access_type": "ALL",
                "r_loops": 1,
                "rows": 128,
                "r_rows": 128,
                "r_table_time_ms": 0.088546344,
                "r_other_time_ms": 0.222168455,
                "filtered": 100,
                "r_filtered": 100
              },
              "table": {
                "table_name": "<derived3>",
                "access_type": "ref",
                "possible_keys": ["key0"],
                "key": "key0",
                "key_length": "5",
                "used_key_parts": ["f2"],
                "ref": ["test.t_outer.f2"],
                "r_loops": 128,
                "rows": 18,
                "r_rows": 16,
                "r_table_time_ms": 2.18024053,
                "r_other_time_ms": 0.398318093,
                "filtered": 100,
                "r_filtered": 100,
                "attached_condition": "trigcond(trigcond(t_outer.f2 is not null))",
                "materialized": {
                  "query_block": {
                    "select_id": 3,
                    "r_loops": 1,
                    "r_total_time_ms": 0.838371151,
                    "table": {
                      "table_name": "t",
                      "access_type": "ALL",
                      "r_loops": 1,
                      "rows": 128,
                      "r_rows": 128,
                      "r_table_time_ms": 0.139922486,
                      "r_other_time_ms": 0.16433142,
                      "filtered": 100,
                      "r_filtered": 100
                    }
                  }
                }
              },
              "table": {
                "table_name": "t_inner",
                "access_type": "ALL",
                "r_loops": 2048,
                "rows": 128,
                "r_rows": 128,
                "r_table_time_ms": 174.9042608,
                "r_other_time_ms": 17.27683035,
                "filtered": 100,
                "r_filtered": 12.5,
                "attached_condition": "trigcond(t_inner.f3 = v_inner.f3)"
              },
              "block-nl-join": {
                "table": {
                  "table_name": "<derived2>",
                  "access_type": "ALL",
                  "r_loops": 470,
                  "rows": 128,
                  "r_rows": 112,
                  "r_table_time_ms": 18.4123725,
                  "r_other_time_ms": 663.6949674,
                  "filtered": 100,
                  "r_filtered": 100,
                  "attached_condition": "v.f2 <> 5"
                },
                "buffer_type": "flat",
                "buffer_size": "256Kb",
                "join_type": "BNL",
                "r_filtered": 100,
                "materialized": {
                  "query_block": {
                    "select_id": 2,
                    "r_loops": 1,
                    "r_total_time_ms": 0.476350437,
                    "table": {
                      "table_name": "t",
                      "access_type": "ALL",
                      "r_loops": 1,
                      "rows": 128,
                      "r_rows": 128,
                      "r_table_time_ms": 0.14055453,
                      "r_other_time_ms": 0.140725081,
                      "filtered": 100,
                      "r_filtered": 87.5,
                      "attached_condition": "t.f2 <> 5"
                    }
                  }
                }
              }
            }
          }
        }
      }
      

      JSON_HB

      ANALYZE: {
        "query_block": {
          "select_id": 1,
          "r_loops": 1,
          "r_total_time_ms": 21109.07323,
          "filesort": {
            "sort_key": "v.f2",
            "r_loops": 1,
            "r_total_time_ms": 0.008015922,
            "r_used_priority_queue": false,
            "r_output_rows": 7,
            "r_buffer_size": "360",
            "r_sort_mode": "sort_key,rowid",
            "temporary_table": {
              "table": {
                "table_name": "<derived2>",
                "access_type": "ALL",
                "r_loops": 1,
                "rows": 112,
                "r_rows": 112,
                "r_table_time_ms": 0.309109608,
                "r_other_time_ms": 0.066946494,
                "filtered": 100,
                "r_filtered": 100,
                "attached_condition": "v.f2 <> 5",
                "materialized": {
                  "query_block": {
                    "select_id": 2,
                    "r_loops": 1,
                    "r_total_time_ms": 0.475056252,
                    "table": {
                      "table_name": "t",
                      "access_type": "ALL",
                      "r_loops": 1,
                      "rows": 128,
                      "r_rows": 128,
                      "r_table_time_ms": 0.130221113,
                      "r_other_time_ms": 0.148690841,
                      "filtered": 87.5,
                      "r_filtered": 87.5,
                      "attached_condition": "t.f2 <> 5"
                    }
                  }
                }
              },
              "block-nl-join": {
                "table": {
                  "table_name": "t_outer",
                  "access_type": "ALL",
                  "r_loops": 27,
                  "rows": 128,
                  "r_rows": 128,
                  "r_table_time_ms": 2.909438633,
                  "r_other_time_ms": 1.070110557,
                  "filtered": 100,
                  "r_filtered": 100
                },
                "buffer_type": "flat",
                "buffer_size": "14Kb",
                "join_type": "BNL",
                "r_filtered": 100
              },
              "table": {
                "table_name": "<derived3>",
                "access_type": "ref",
                "possible_keys": ["key0"],
                "key": "key0",
                "key_length": "5",
                "used_key_parts": ["f2"],
                "ref": ["test.t_outer.f2"],
                "r_loops": 14336,
                "rows": 18,
                "r_rows": 16,
                "r_table_time_ms": 174.6954054,
                "r_other_time_ms": 42.59518564,
                "filtered": 100,
                "r_filtered": 100,
                "attached_condition": "trigcond(trigcond(t_outer.f2 is not null))",
                "materialized": {
                  "query_block": {
                    "select_id": 3,
                    "r_loops": 1,
                    "r_total_time_ms": 0.81681143,
                    "table": {
                      "table_name": "t",
                      "access_type": "ALL",
                      "r_loops": 1,
                      "rows": 128,
                      "r_rows": 128,
                      "r_table_time_ms": 0.111641028,
                      "r_other_time_ms": 0.161612628,
                      "filtered": 100,
                      "r_filtered": 100
                    }
                  }
                }
              },
              "table": {
                "table_name": "t_inner",
                "access_type": "ALL",
                "r_loops": 229376,
                "rows": 128,
                "r_rows": 128,
                "r_table_time_ms": 19197.38184,
                "r_other_time_ms": 1689.314608,
                "filtered": 100,
                "r_filtered": 12.5,
                "attached_condition": "trigcond(t_inner.f3 = v_inner.f3)"
              }
            }
          }
        }
      }
      

      Attachments

        Issue Links

          Activity

            Ok, the difference between query plans is explained by binary histogram producing wrong selectivity data.
            But why there's such a slowdown?

            psergei Sergei Petrunia added a comment - Ok, the difference between query plans is explained by binary histogram producing wrong selectivity data. But why there's such a slowdown?

            EXPLAIN outputs. I've added:

            • "OJ" for tables that are inner for the outer join
            • r_time_ms column with data from analyze format=json.

            Old histogram: r_total_time_ms=877 ms.

            +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+-------------------------------------------------+
            | id   | select_type | table      | type | r_time_ms | possible_keys | key  | key_len | ref           | rows | Extra                                           |
            +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+-------------------------------------------------+
            |    1 | PRIMARY     | t_outer    | ALL  |     0.3   | NULL          | NULL | NULL    | NULL          | 128  | Using temporary; Using filesort                 |
            | OJ 1 | PRIMARY     | <derived3> | ref  |     2.4   | key0          | key0 | 5       | j1.t_outer.f2 | 18   | Using where                                     |
            | OJ 1 | PRIMARY     | t_inner    | ALL  |     200   | NULL          | NULL | NULL    | NULL          | 128  | Using where                                     |
            |    1 | PRIMARY     | <derived2> | ALL  |     600   | NULL          | NULL | NULL    | NULL          | 128  | Using where; Using join buffer (flat, BNL join) |
                                                     |           
            |    3 | DERIVED     | t          | ALL  |           | NULL          | NULL | NULL    | NULL          | 128  |                                                 |
            |    2 | DERIVED     | t          | ALL  |           | NULL          | NULL | NULL    | NULL          | 128  | Using where                                     |
            +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+-------------------------------------------------+
            

            New histogram: r_total_time_ms=21109 ms.

            +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+----------------------------------------------+
            | id   | select_type | table      | type | r_time_ms | possible_keys | key  | key_len | ref           | rows | Extra                                        |
            +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+----------------------------------------------+
            |    1 | PRIMARY     | <derived2> | ALL  |       0.4 | NULL          | NULL | NULL    | NULL          | 112  | Using where; Using temporary; Using filesort |
            |    1 | PRIMARY     | t_outer    | ALL  |       3.9 | NULL          | NULL | NULL    | NULL          | 128  | Using join buffer (flat, BNL join)           |
            | OJ 1 | PRIMARY     | <derived3> | ref  |       200 | key0          | key0 | 5       | j5.t_outer.f2 | 18   | Using where                                  |
            | OJ 1 | PRIMARY     | t_inner    | ALL  |     19100 | NULL          | NULL | NULL    | NULL          | 128  | Using where                                  |
                                                                  
            |    3 | DERIVED     | t          | ALL  |           | NULL          | NULL | NULL    | NULL          | 128  |                                              |
            |    2 | DERIVED     | t          | ALL  |           | NULL          | NULL | NULL    | NULL          | 128  | Using where                                  |
            +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+----------------------------------------------+
            

            for new histogram, the join order is different. The outer join nest table is at the very end. The tables inside outer join nest are not using join buffering, and the last t_inner totally dominates the query execution time.

            psergei Sergei Petrunia added a comment - EXPLAIN outputs. I've added: "OJ" for tables that are inner for the outer join r_time_ms column with data from analyze format=json. Old histogram: r_total_time_ms=877 ms. +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+-------------------------------------------------+ | id | select_type | table | type | r_time_ms | possible_keys | key | key_len | ref | rows | Extra | +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+-------------------------------------------------+ | 1 | PRIMARY | t_outer | ALL | 0.3 | NULL | NULL | NULL | NULL | 128 | Using temporary; Using filesort | | OJ 1 | PRIMARY | <derived3> | ref | 2.4 | key0 | key0 | 5 | j1.t_outer.f2 | 18 | Using where | | OJ 1 | PRIMARY | t_inner | ALL | 200 | NULL | NULL | NULL | NULL | 128 | Using where | | 1 | PRIMARY | <derived2> | ALL | 600 | NULL | NULL | NULL | NULL | 128 | Using where; Using join buffer (flat, BNL join) | | | 3 | DERIVED | t | ALL | | NULL | NULL | NULL | NULL | 128 | | | 2 | DERIVED | t | ALL | | NULL | NULL | NULL | NULL | 128 | Using where | +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+-------------------------------------------------+ New histogram: r_total_time_ms=21109 ms. +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+----------------------------------------------+ | id | select_type | table | type | r_time_ms | possible_keys | key | key_len | ref | rows | Extra | +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+----------------------------------------------+ | 1 | PRIMARY | <derived2> | ALL | 0.4 | NULL | NULL | NULL | NULL | 112 | Using where; Using temporary; Using filesort | | 1 | PRIMARY | t_outer | ALL | 3.9 | NULL | NULL | NULL | NULL | 128 | Using join buffer (flat, BNL join) | | OJ 1 | PRIMARY | <derived3> | ref | 200 | key0 | key0 | 5 | j5.t_outer.f2 | 18 | Using where | | OJ 1 | PRIMARY | t_inner | ALL | 19100 | NULL | NULL | NULL | NULL | 128 | Using where | | 3 | DERIVED | t | ALL | | NULL | NULL | NULL | NULL | 128 | | | 2 | DERIVED | t | ALL | | NULL | NULL | NULL | NULL | 128 | Using where | +------+-------------+------------+------+-----------+---------------+------+---------+---------------+------+----------------------------------------------+ for new histogram, the join order is different. The outer join nest table is at the very end. The tables inside outer join nest are not using join buffering, and the last t_inner totally dominates the query execution time.

            Note: if I set join_cache_level=0 and disable join buffering, I get the same join order for both histogram types, and similar query time (~80 sec).

            psergei Sergei Petrunia added a comment - Note: if I set join_cache_level=0 and disable join buffering, I get the same join order for both histogram types, and similar query time (~80 sec).
            psergei Sergei Petrunia added a comment - - edited

            A rough explanation of where most of the slowdown comes:

            Old histograms, ("r_total_time_ms": 6062.363311),

            id select_type table type possible_keys key key_len ref rows r_rows filtered r_filtered Extra
            1 PRIMARY t_outer ALL NULL NULL NULL NULL 128 128.00 100.00 100.00 Using temporary; Using filesort
            1 PRIMARY <derived3> ref key0 key0 5 j10.t_outer.f2 18 16.00 100.00 100.00 Using where
            1 PRIMARY t_inner ALL NULL NULL NULL NULL 128 128.00 100.00 12.50 Using where
            1 PRIMARY <derived2> ALL NULL NULL NULL NULL 128 112.00 100.00 100.00 Using where; Using join buffer (flat, BNL join)

            ..
            Note the filtered/r_filtered discrepancy in table #3 100/12.5=8x.

            New histograms ( "r_total_time_ms": 89848.70511) produce a different join order:

            id select_type table type possible_keys key key_len ref rows r_rows filtered r_filtered Extra
            1 PRIMARY <derived2> ALL NULL NULL NULL NULL 112 112.00 100.00 100.00 Using where; Using temporary; Using filesort
            1 PRIMARY t_outer ALL NULL NULL NULL NULL 128 128.00 100.00 100.00 Using join buffer (flat, BNL join)
            1 PRIMARY <derived3> ref key0 key0 5 j11.t_outer.f2 18 16.00 100.00 100.00 Using where
            1 PRIMARY t_inner ALL NULL NULL NULL NULL 128 128.00 100.00 12.50 Using where

            ..

            We don't get the 8x win, because it happens on the last table.

            I suspect this is not the sole reason but this is where the most of it comes from.

            psergei Sergei Petrunia added a comment - - edited A rough explanation of where most of the slowdown comes: Old histograms, ("r_total_time_ms": 6062.363311), id select_type table type possible_keys key key_len ref rows r_rows filtered r_filtered Extra 1 PRIMARY t_outer ALL NULL NULL NULL NULL 128 128.00 100.00 100.00 Using temporary; Using filesort 1 PRIMARY <derived3> ref key0 key0 5 j10.t_outer.f2 18 16.00 100.00 100.00 Using where 1 PRIMARY t_inner ALL NULL NULL NULL NULL 128 128.00 100.00 12.50 Using where 1 PRIMARY <derived2> ALL NULL NULL NULL NULL 128 112.00 100.00 100.00 Using where; Using join buffer (flat, BNL join) .. Note the filtered/r_filtered discrepancy in table #3 100/12.5=8x. New histograms ( "r_total_time_ms": 89848.70511) produce a different join order: id select_type table type possible_keys key key_len ref rows r_rows filtered r_filtered Extra 1 PRIMARY <derived2> ALL NULL NULL NULL NULL 112 112.00 100.00 100.00 Using where; Using temporary; Using filesort 1 PRIMARY t_outer ALL NULL NULL NULL NULL 128 128.00 100.00 100.00 Using join buffer (flat, BNL join) 1 PRIMARY <derived3> ref key0 key0 5 j11.t_outer.f2 18 16.00 100.00 100.00 Using where 1 PRIMARY t_inner ALL NULL NULL NULL NULL 128 128.00 100.00 12.50 Using where .. We don't get the 8x win, because it happens on the last table. I suspect this is not the sole reason but this is where the most of it comes from.

            Closing as Not-a-bug, because I don't see anything that the current optimizer could do but is not doing that would let to fix this.

            psergei Sergei Petrunia added a comment - Closing as Not-a-bug, because I don't see anything that the current optimizer could do but is not doing that would let to fix this.

            People

              psergei Sergei Petrunia
              elenst Elena Stepanova
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Git Integration

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