[MDEV-5950] EITS: bad estimate for very skewed distributions - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Major
Resolution: Fixed
Affects Version/s: 10.0.9
Fix Version/s: 10.0.10
Component/s: None
Labels:
- eits

Description

After fix for ~~MDEV-5926~~, we see a regression for the filtered% column for testcase from ~~MDEV-4350~~:

create table t1 (a int);

insert into t1 values (1), (1);

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 select * from t1;

insert into t1 values (0);

set use_stat_tables='preferably';

set histogram_size=127;

set histogram_type='SINGLE_PREC_HB';

analyze table t1;

flush table t1;

set optimizer_use_condition_selectivity=4;

mysql> explain extended select * from t1 where a=0;

+------+-------------+-------+------+---------------+------+---------+------+------+----------+-------------+

| id   | select_type | table | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |

+------+-------------+-------+------+---------------+------+---------+------+------+----------+-------------+

|    1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL | 1025 |    99.22 | Using where |

+------+-------------+-------+------+---------------+------+---------+------+------+----------+-------------+

filtered% used to be 50%, now it's 99.22%. Both estimates are very wrong:

mysql> select a,count(*) from  t1 group by a;

+------+----------+

| a    | count(*) |

+------+----------+

|    0 |        1 |

|    1 |     1024 |

+------+----------+

But the new one is even worse than before.

Attachments

Issue Links

relates to

MDEV-5926 EITS: Histogram estimates for column=least_possible_value are wrong

Closed

Activity

Ascending order - Click to sort in descending order

Sergei Petrunia created issue - 2014-03-25 19:35

Sergei Petrunia made changes - 2014-03-25 19:36

Field	Original Value	New Value
Labels		eits

Sergei Petrunia made changes - 2014-03-25 19:38

Description

After fix for ~~MDEV-5926~~, we see a regression for the filtered% column for testcase from ~~MDEV-4350~~:

{noformat}
create table t1 (a int);
insert into t1 values (1), (1);
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 values (0);
set use_stat_tables='preferably';
set histogram_size=127;
set histogram_type='SINGLE_PREC_HB';
analyze table t1;
flush table t1;
set optimizer_use_condition_selectivity=4;
{noformat}

{noformat}
mysql> explain extended select * from t1 where a=0;
+------+-------------+-------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+------+-------------+-------+------+---------------+------+---------+------+------+----------+-------------+
| 1 | SIMPLE | t1 | ALL | NULL | NULL | NULL | NULL | 1025 | 99.22 | Using where |
+------+-------------+-------+------+---------------+------+---------+------+------+----------+-------------+
{noformat}

Sergei Petrunia added a comment - 2014-03-25 19:41

mysql> select *, hex(histogram) from mysql.column_stats where db_name='j32'\G

*************************** 1. row ***************************

       db_name: j32

    table_name: t1

   column_name: a

     min_value: 0

     max_value: 1

   nulls_ratio: 0.0000

    avg_length: 4.0000

 avg_frequency: 512.5000

     hist_size: 127

     hist_type: SINGLE_PREC_HB

     histogram: �������������������������������������������������������������������������������������������������������������������������������

hex(histogram): FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

So, the histogram shows that all values are "1" (or very close to 1). We should be able to determine that value of 0 (which is equal to minimum) occupies zero buckets, not 99.22% of buckets.

Sergei Petrunia added a comment - 2014-03-25 19:41 mysql> select *, hex(histogram) from mysql.column_stats where db_name='j32'\G *************************** 1. row *************************** db_name: j32 table_name: t1 column_name: a min_value: 0 max_value: 1 nulls_ratio: 0.0000 avg_length: 4.0000 avg_frequency: 512.5000 hist_size: 127 hist_type: SINGLE_PREC_HB histogram: �� hex(histogram): FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF So, the histogram shows that all values are "1" (or very close to 1). We should be able to determine that value of 0 (which is equal to minimum) occupies zero buckets, not 99.22% of buckets.

Sergei Petrunia made changes - 2014-03-25 19:42

Assignee

Igor Babaev [ igor ]

Sergei Petrunia made changes - 2014-03-25 19:42

Assignee

Igor Babaev [ igor ]

Sergei Petrunia [ psergey ]

Sergei Petrunia made changes - 2014-03-25 19:42

Status

Open [ 1 ]

In Progress [ 3 ]

Sergei Petrunia added a comment - 2014-03-25 19:48

This looks like an edge case, but this is an edge case that I think we could (and should) handle.

Sergei Petrunia added a comment - 2014-03-25 19:48 This looks like an edge case, but this is an edge case that I think we could (and should) handle.

Sergei Petrunia added a comment - 2014-03-25 19:52

Debugging:

Histogram::point_selectivity (this=0x7fffca8829f8, pos=0, avg_sel=0.5)
(gdb) print min
$92 = 0
(gdb) print max
$93 = 126
(gdb) print used_buckets
$97 = 127
(gdb) print avg_buckets_per_value
$95 = 64

sel= avg_sel * used_buckets / avg_buckets_per_value;
(gdb) print sel
$99 = 0.9921875

Histogram::point_selectivity() is invoked with pos=0. This is correct.
Things go wrong where we look at the first bucket, see 0xFF as its upper bound, and then assume that 0xFF is close to the value we're making estimates for.
(We then see how many cells have the same value, and see that all of them have.)

Proposed solution: when we're looking at the cell, compare its left endpoint with the right endpoint. if our constant is closer to the left endpoint, assume that the cell is unoccupied.

Sergei Petrunia added a comment - 2014-03-25 19:52 Debugging: Histogram::point_selectivity (this=0x7fffca8829f8, pos=0, avg_sel=0.5) (gdb) print min $92 = 0 (gdb) print max $93 = 126 (gdb) print used_buckets $97 = 127 (gdb) print avg_buckets_per_value $95 = 64 sel= avg_sel * used_buckets / avg_buckets_per_value; (gdb) print sel $99 = 0.9921875 Histogram::point_selectivity() is invoked with pos=0. This is correct. Things go wrong where we look at the first bucket, see 0xFF as its upper bound, and then assume that 0xFF is close to the value we're making estimates for. (We then see how many cells have the same value, and see that all of them have.) Proposed solution: when we're looking at the cell, compare its left endpoint with the right endpoint. if our constant is closer to the left endpoint, assume that the cell is unoccupied.

Sergei Petrunia made changes - 2014-03-26 11:57

Fix Version/s

10.0.10 [ 14500 ]

Sergei Petrunia added a comment - 2014-03-26 16:03

The issue is fixed by the new patch for ~~MDEV-5926~~. There, we have:

-1 SIMPLE t1 ALL NULL NULL NULL NULL 1025 49.61 Using where
+1 SIMPLE t1 ALL NULL NULL NULL NULL 1025 0.39 Using where

i.e. the patch improves the estimation.

Sergei Petrunia added a comment - 2014-03-26 16:03 The issue is fixed by the new patch for MDEV-5926 . There, we have: -1 SIMPLE t1 ALL NULL NULL NULL NULL 1025 49.61 Using where +1 SIMPLE t1 ALL NULL NULL NULL NULL 1025 0.39 Using where i.e. the patch improves the estimation.

Sergei Petrunia made changes - 2014-03-26 16:03

Link

This issue relates to ~~MDEV-5926~~ [ ~~MDEV-5926~~ ]

Sergei Petrunia made changes - 2014-03-26 16:03

Resolution		Fixed [ 1 ]
Status	In Progress [ 3 ]	Closed [ 6 ]

Sergei Golubchik made changes - 2014-06-13 15:06

Workflow

defaullt [ 37401 ]

MariaDB v2 [ 42805 ]

Rasmus Johansson (Inactive) made changes - 2015-05-18 17:50

Workflow

MariaDB v2 [ 42805 ]

MariaDB v3 [ 62515 ]

Sergei Golubchik made changes - 2021-12-06 21:39

Workflow

MariaDB v3 [ 62515 ]

MariaDB v4 [ 147696 ]

People

Assignee:: Sergei Petrunia

Reporter:: Sergei Petrunia

Votes:: 0 Vote for this issue

Watchers:: 1 Start watching this issue

Dates

Created:: 2014-03-25 19:35

Updated:: 2014-03-26 16:03

Resolved:: 2014-03-26 16:03

Git Integration

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

MariaDB Server

Details

Description

Attachments

Issue Links

Activity

People

Dates

Git Integration