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

[MDEV-26718] Query with: Cross join, Non-indexed column comparison, Column with histogram: speed varies 20x depending on histogram type Created: 2021-09-29 Updated: 2021-10-12 Resolved: 2021-10-08
Status:	Closed
Project:	MariaDB Server
Component/s:	Optimizer
Affects Version/s:	N/A
Fix Version/s:	N/A

Type:

Bug

Priority:

Critical

Reporter:

Elena Stepanova

Assignee:

Sergei Petrunia

Resolution:

Not a Bug

Votes:

Labels:

None

Issue Links:

Problem/Incident
is caused by	~~MDEV-21130~~	Histograms: use JSON as on-disk format	Closed
is caused by	~~MDEV-26519~~	JSON Histograms: improve histogram co...	Closed
Relates
relates to	MDEV-26728	Histogram may return selectivity > 1.0	Open

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)"
}
}
}
}
}

Comments

Comment by Sergei Petrunia [ 2021-09-29 ]

Diff'ing the optimizer trace:

--- /tmp/trace-old

+++ /tmp/trace-new

@@ -133,10 +133,10 @@

                           "column_name": "f2",

                           "ranges": ["NULL < f2 < 5", "5 < f2"],

-                          "selectivity_from_histogram": 1.1171875

+                          "selectivity_from_histogram": 0.875

],

-                      "cond_selectivity": 1

+                      "cond_selectivity": 0.875

},

                       "table": "t",

@@ -156,21 +156,21 @@

                         "considered_access_paths": [

Comment by Sergei Petrunia [ 2021-09-29 ]

Note the selectivity_from_histogram": 1.1171875 ! More than 1!

With histogram_type=DOUBLE_PREC_HB:

mysql> analyze format=json select * from t where f2<>5;

| {

  "query_block": {

    "select_id": 1,

    "r_loops": 1,

    "r_total_time_ms": 0.431759949,

    "table": {

      "table_name": "t",

      "access_type": "ALL",

      "r_loops": 1,

      "rows": 128,

      "r_rows": 128,

      "r_table_time_ms": 0.234841603,

      "r_other_time_ms": 0.166091629,

      "filtered": 100,

      "r_filtered": 87.5,

      "attached_condition": "t.f2 <> 5"

On histogram_type=JSON_HB:

mysql> analyze format=json select * from t where f2<>5;

| {

  "query_block": {

    "select_id": 1,

    "r_loops": 1,

    "r_total_time_ms": 1.110254728,

    "table": {

      "table_name": "t",

      "access_type": "ALL",

      "r_loops": 1,

      "rows": 128,

      "r_rows": 128,

      "r_table_time_ms": 0.587855218,

      "r_other_time_ms": 0.439884064,

      "filtered": 87.5,

      "r_filtered": 87.5,

      "attached_condition": "t.f2 <> 5"

} |

Comment by Sergei Petrunia [ 2021-09-29 ]

That is, JSON_HB histogram provides a more precise estimate.

Comment by Sergei Petrunia [ 2021-09-30 ]

Filed MDEV-26728 for the "selectivity > 1.0" part.

Comment by Sergei Petrunia [ 2021-10-01 ]

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

Comment by Sergei Petrunia [ 2021-10-05 ]

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.

Comment by Sergei Petrunia [ 2021-10-05 ]

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).

Comment by Sergei Petrunia [ 2021-10-08 ]

A rough explanation of where most of the slowdown comes:

Old histograms, ("r_total_time_ms": 6062.363311),

select_type

table

type

possible_keys

key

key_len

ref

rows

r_rows

filtered

r_filtered

Extra

PRIMARY

t_outer

ALL

NULL

128

128.00

100.00

Using temporary; Using filesort

PRIMARY

ref

key0

j10.t_outer.f2

16.00

100.00

Using where

PRIMARY

t_inner

ALL

NULL

128

128.00

100.00

12.50

Using where

PRIMARY

ALL

NULL

128

112.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:

select_type

table

type

possible_keys

key

key_len

ref

rows

r_rows

filtered

r_filtered

Extra

PRIMARY

ALL

NULL

112

112.00

100.00

Using where; Using temporary; Using filesort

PRIMARY

t_outer

ALL

NULL

128

128.00

100.00

Using join buffer (flat, BNL join)

PRIMARY

ref

key0

j11.t_outer.f2

16.00

100.00

Using where

PRIMARY

t_inner

ALL

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.

Comment by Sergei Petrunia [ 2021-10-08 ]

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.

Generated at Thu Feb 08 09:47:25 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.

[MDEV-26718] Query with: Cross join, Non-indexed column comparison, Column with histogram: speed varies 20x depending on histogram type Created: 2021-09-29 Updated: 2021-10-12 Resolved: 2021-10-08