maria-developers team mailing list archive
-
maria-developers team
-
Mailing list archive
-
Message #11664
Review for ANALYZE TABLE with Sampling
Hi Sergei!
Can you review that you are happy with the storage engine API changes?
I'veustructured the commit to be as small as possible to achieve the
desired outcome. In my tests, we are now twice as fast as MySQL for a
10 mil row table with 13 columns.
Vicențiu
-------- Forwarded Message --------From: vicentiu@mariadb.orgTo:
commits@mariadb.orgSubject: 53730224efd: Improve histogram collection
performance by samplingDate: Sun, 10 Feb 2019 20:09:49 +0200 (EET)
revision-id: 53730224efd987f97a6cc968ff5214ee499d84e0 (mariadb-10.4.1-
163-g53730224efd)parent(s):
3c305d3f1951f1667f84e48ddd98674c6318c39dauthor: Vicențiu
Ciorbarucommitter: Vicențiu Ciorbarutimestamp: 2019-02-10 19:54:50
+0200message:
Improve histogram collection performance by sampling
Histogram collection is done by sampling a percentage of rows from the
table,not looking at all individual ones.
The default implementation, to keep the server's Engine
IndepenentStatistics component working uses Bernoulli sampling. It does
a simpletable scan, but only accepts rows that pass a dice roll.
Thisimplementation is done as a storage engine interface method, so as
toallow faster and/or more efficient implementations for storage
enginesinternally.
The number of rows collected is capped to a minimum of 50000
andincreases logarithmically with a coffecient of 4096. The coffecient
ischosen so that we expect an error of less than 3% in our
estimationsaccording to the paper:"Random Sampling for Histogram
Construction: How much is enough?”– Surajit Chaudhuri, Rajeev Motwani,
Vivek Narasayya, ACM SIGMOD, 1998.
This interface is also a precursor to allowing SELECT ... FROM
tablewith sampling to work.
Performance wise, for a table of 10 million rows and 13 columns, 6
int,6 doubles, one string, the previous analyze table statistics took1
minute 20 seconds to collect all data. Post implementation, thetime is
less than 6 seconds. This was run on an InnoDB table, NVME SSD
withapproximately 2GB/s read speed and 500MB/s write speed.
--- mysql-test/main/selectivity.result | 8 +++---- mysql-
test/main/selectivity_innodb.result | 8 +++--
-- sql/handler.cc | 14
+++++++++++ sql/handler.h | 40
++++++++++++++++++++++++++++++- sql/sql_statistics.cc
| 32 +++++++++++++++++++------ 5 files changed, 86 insertions(+), 16
deletions(-)
diff --git a/mysql-test/main/selectivity.result b/mysql-
test/main/selectivity.resultindex 00907235ecc..6d09c1c9b62 100644---
a/mysql-test/main/selectivity.result+++ b/mysql-
test/main/selectivity.result@@ -1290,9 +1290,9 @@ explain
extended select * from t1, t2, t1 as t3 where t1.b=t2.c and t2.d=t3.a
and t3.b<5 and t1.a < 2000; id select_type table type possibl
e_keys key key_len ref rows filtered Extra-1 SIMPLE
t1 ALL NULL NULL NULL NULL 262144 100.00 Using
where+1 SIMPLE t1 ALL NULL NULL NULL NULL 262117
100.00 Using where 1 SIMPLE t2 ref c,d c 5
test.t1.b 5 100.00 -1 SIMPLE t3 ALL NULL
NULL NULL NULL 262144 100.00 Using where; Using join buffer
(flat, BNL join)+1 SIMPLE t3 ALL NULL NULL NULL
NULL 262117 100.00 Using where; Using join buffer (flat, BNL
join) Warnings: Note 1003 select `test`.`t1`.`a` AS
`a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS
`d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b` from `test`.`t1` join
`test`.`t2` join `test`.`t1` `t3` where `test`.`t2`.`c` =
`test`.`t1`.`b` and `test`.`t3`.`a` = `test`.`t2`.`d` and
`test`.`t3`.`b` < 5 and `test`.`t1`.`a` < 2000 select * from t1, t2, t1
as t3@@ -1307,9 +1307,9 @@ explain extended select * from t1, t2, t1 as
t3 where t1.b=t2.c and t2.d=t3.a and t3.b<5 and t1.a < 2000; id select_
type table type possible_keys key key_len ref rows
filtered Extra-1 SIMPLE t3 ALL NULL NULL NULL
NULL 262144 0.00 Using where+1 SIMPLE t3 ALL NULL
NULL NULL NULL 262117 0.00 Using where 1 SIMPLE t2
ref c,d d 5 test.t3.a 7 100.00 -1
SIMPLE t1 ALL NULL NULL NULL NULL 262144 2.00
Using where; Using join buffer (flat, BNL join)+1 SIMPLE t1
ALL NULL NULL NULL NULL 262117 2.00 Using where;
Using join buffer (flat, BNL join) Warnings: Note 1003 select
`test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`c` AS
`c`,`test`.`t2`.`d` AS `d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS
`b` from `test`.`t1` join `test`.`t2` join `test`.`t1` `t3` where
`test`.`t1`.`b` = `test`.`t2`.`c` and `test`.`t2`.`d` = `test`.`t3`.`a`
and `test`.`t3`.`b` < 5 and `test`.`t1`.`a` < 2000 select * from t1,
t2, t1 as t3diff --git a/mysql-test/main/selectivity_innodb.result
b/mysql-test/main/selectivity_innodb.resultindex
93917065722..0b20a40f69f 100644--- a/mysql-
test/main/selectivity_innodb.result+++ b/mysql-
test/main/selectivity_innodb.result@@ -1300,9 +1300,9 @@ explain
extended select * from t1, t2, t1 as t3 where t1.b=t2.c and t2.d=t3.a
and t3.b<5 and t1.a < 2000; id select_type table type possibl
e_keys key key_len ref rows filtered Extra-1 SIMPLE
t1 ALL NULL NULL NULL NULL 262144 100.00 Using
where+1 SIMPLE t1 ALL NULL NULL NULL NULL 262117
100.00 Using where 1 SIMPLE t2 ref c,d c 5
test.t1.b 5 100.00 -1 SIMPLE t3 ALL NULL
NULL NULL NULL 262144 100.00 Using where; Using join buffer
(flat, BNL join)+1 SIMPLE t3 ALL NULL NULL NULL
NULL 262117 100.00 Using where; Using join buffer (flat, BNL
join) Warnings: Note 1003 select `test`.`t1`.`a` AS
`a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS
`d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b` from `test`.`t1` join
`test`.`t2` join `test`.`t1` `t3` where `test`.`t2`.`c` =
`test`.`t1`.`b` and `test`.`t3`.`a` = `test`.`t2`.`d` and
`test`.`t3`.`b` < 5 and `test`.`t1`.`a` < 2000 select * from t1, t2, t1
as t3@@ -1317,9 +1317,9 @@ explain extended select * from t1, t2, t1 as
t3 where t1.b=t2.c and t2.d=t3.a and t3.b<5 and t1.a < 2000; id select_
type table type possible_keys key key_len ref rows
filtered Extra-1 SIMPLE t3 ALL NULL NULL NULL
NULL 262144 0.00 Using where+1 SIMPLE t3 ALL NULL
NULL NULL NULL 262117 0.00 Using where 1 SIMPLE t2
ref c,d d 5 test.t3.a 7 100.00 -1
SIMPLE t1 ALL NULL NULL NULL NULL 262144 2.00
Using where; Using join buffer (flat, BNL join)+1 SIMPLE t1
ALL NULL NULL NULL NULL 262117 2.00 Using where;
Using join buffer (flat, BNL join) Warnings: Note 1003 select
`test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t2`.`c` AS
`c`,`test`.`t2`.`d` AS `d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS
`b` from `test`.`t1` join `test`.`t2` join `test`.`t1` `t3` where
`test`.`t1`.`b` = `test`.`t2`.`c` and `test`.`t2`.`d` = `test`.`t3`.`a`
and `test`.`t3`.`b` < 5 and `test`.`t1`.`a` < 2000 select * from t1,
t2, t1 as t3diff --git a/sql/handler.cc b/sql/handler.ccindex
2e45b5883ea..16fb126918e 100644--- a/sql/handler.cc+++
b/sql/handler.cc@@ -7547,3 +7547,17 @@ bool
Vers_parse_info::check_sys_fields(const Lex_table_name
&table_name, "ROW END" : found_flag ? "ROW START" : "ROW
START/END"); return true; }++int handler::random_sample(uchar
*buf)+{+ int rc;+ THD *thd= ha_thd();+ do+ {+ if (table->in_use-
>check_killed(1))+ return HA_ERR_ABORTED_BY_USER;+ rc=
rnd_next(buf);+ } while (rc == HA_ERR_RECORD_DELETED || thd_rnd(thd) >
sample_fraction);++ return rc;+}diff --git a/sql/handler.h
b/sql/handler.hindex dfb2333b24e..fcdadbeb42b 100644---
a/sql/handler.h+++ b/sql/handler.h@@ -1913,6 +1913,11 @@ enum
enum_stats_auto_recalc { HA_STATS_AUTO_RECALC_DEFAULT=
0, HA_STATS_AUTO_RECALC_ON,
HA_STATS_AUTO_RECALC_OFF }; +enum sample_mode
{+ HA_SAMPLE_BERNOULLI= 0,+ HA_SAMPLE_SYSTEM+};+ /** A helper
struct for schema DDL statements: CREATE SCHEMA [IF NOT EXISTS]
name [ schema_specification... ]@@ -2947,9 +2952,11 @@ class handler
:public Sql_alloc /** Length of ref (1-8 or the clustered key length)
*/ uint ref_length; FT_INFO *ft_handler;- enum init_stat { NONE=0,
INDEX, RND };+ enum init_stat { NONE=0, INDEX, RND, SAMPLE
}; init_stat inited, pre_inited; + double sample_fraction= 0;+ enum
sample_mode sample_mode; const COND
*pushed_cond; /** next_insert_id is the next value which should
be inserted into the@@ -3112,6 +3119,31 @@ class handler :public
Sql_alloc virtual int prepare_range_scan(const key_range *start_key,
const key_range *end_key) { return 0; } + int
ha_random_sample_init(THD *thd, enum sample_mode mode, double
fraction)+ __attribute__((warn_unused_result))+ {+ DBUG_ENTER("h
a_random_sample_init");+ DBUG_ASSERT(inited==NONE);+ int
result;+ sample_mode= mode;+ sample_fraction=
fraction;+ inited= (result= random_sample_init(mode, fraction)) ?
NONE : SAMPLE;+ DBUG_RETURN(result);+ }+ int
ha_random_sample(uchar
*buf)+ __attribute__((warn_unused_result))+ {+ DBUG_ENTER("ha_ra
ndom_sample");+ DBUG_ASSERT(inited ==
SAMPLE);+ DBUG_RETURN(random_sample(buf));+ }+ int
ha_random_sample_end()+ {+ DBUG_ENTER("ha_random_sample_end");+
inited= NONE;+ DBUG_RETURN(random_sample_end());+ }+ int
ha_rnd_init(bool scan) __attribute__
((warn_unused_result)) { DBUG_EXECUTE_IF("ha_rnd_init_fail",
return HA_ERR_TABLE_DEF_CHANGED;);@@ -4425,6 +4457,12 @@ class handler
:public Sql_alloc /* Note: ha_index_read_idx_map() may bypass
index_init() */ virtual int index_init(uint idx, bool sorted) {
return 0; } virtual int index_end() { return 0; }+ virtual int
random_sample_init(enum sample_mode mode, double
fraction)+ {+ return rnd_init(TRUE);+ }+ virtual int
random_sample(uchar *buf);+ virtual int random_sample_end() { return
rnd_end(); } /** rnd_init() can be called two times without
rnd_end() in between (it only makes sense if scan=1).diff --git
a/sql/sql_statistics.cc b/sql/sql_statistics.ccindex
db214a1fe28..22a015821de 100644--- a/sql/sql_statistics.cc+++
b/sql/sql_statistics.cc@@ -2727,12 +2727,16 @@ int
collect_statistics_for_table(THD *thd, TABLE *table) Field
*table_field; ha_rows rows= 0; handler *file=table->file;+ double
sample_fraction;+ const ha_rows MIN_THRESHOLD_FOR_SAMPLING=
50000; DBUG_ENTER("collect_statistics_for_table"); table-
>collected_stats->cardinality_is_null= TRUE; table->collected_stats-
>cardinality= 0; + table->file->info(HA_STATUS_VARIABLE);+ for
(field_ptr= table->field; *field_ptr; field_ptr++) { table_field=
*field_ptr; @@ -2743,12 +2747,27 @@ int
collect_statistics_for_table(THD *thd, TABLE
*table) restore_record(table, s->default_values); - /* Perform a
full table scan to collect statistics on 'table's columns */- if
(!(rc= file->ha_rnd_init(TRUE)))- { ++ if (file->records() <
MIN_THRESHOLD_FOR_SAMPLING)+ {+ sample_fraction=
1;+ }+ else+ {+ sample_fraction=
std::fmin(+ (MIN_THRESHOLD_FOR_SAMPLING + 4096
*+ log(200 * file->records())) / file->records(),
1);+ }+++ /* Fetch samples from the table to collect statistics on
table's columns */++ if (!(rc= file->ha_random_sample_init(thd,
HA_SAMPLE_BERNOULLI,+ sample_fra
ction)))+ { DEBUG_SYNC(table->in_use,
"statistics_collection_start"); - while ((rc= file-
>ha_rnd_next(table->record[0])) != HA_ERR_END_OF_FILE)+ while ((rc=
file->ha_random_sample(table->record[0])) !=
HA_ERR_END_OF_FILE) { if (thd->killed) break;@@
-2768,10 +2787,9 @@ int collect_statistics_for_table(THD *thd, TABLE
*table) break; rows++; }- file-
>ha_rnd_end();+ file->ha_random_sample_end(); } rc= (rc ==
HA_ERR_END_OF_FILE && !thd->killed) ? 0 : 1;- /* Calculate
values for all statistical characteristics on columns and and for
each field f of 'table' save them in the write_stat structure@@ -2780,7
+2798,7 @@ int collect_statistics_for_table(THD *thd, TABLE
*table) if (!rc) { table->collected_stats->cardinality_is_null=
FALSE;- table->collected_stats->cardinality= rows;+ table-
>collected_stats->cardinality= rows /
sample_fraction; } bitmap_clear_all(table->write_set);
