Description:
btr_estimate_n_rows_in_range and btr_estimate_n_rows_in_range_on_level produces
1 row less than actual numbers even though all the pages are used for sampling.
and is_n_rows_exact is set true.
How to repeat:
CREATE TABLE `t1` (
c1 int NOT NULL,
c2 int NOT NULL,
c3 int NOT NULL,
PRIMARY KEY (c1,c2),
KEY (c3)
) ENGINE=InnoDB, STATS_PERSISTENT=1;
# populate with data
INSERT INTO t1 VALUES (5,2,1246276747);
INSERT INTO t1 VALUES (2,1,1246281721);
INSERT INTO t1 VALUES (7,3,1246281756);
INSERT INTO t1 VALUES (4,2,1246282139);
INSERT INTO t1 VALUES (3,1,1246282230);
INSERT INTO t1 VALUES (1,0,1246282712);
INSERT INTO t1 VALUES (8,3,1246282765);
INSERT INTO t1 SELECT c1+10,c2+10,c3+10 FROM t1;
INSERT INTO t1 SELECT c1+100,c2+100,c3+100 from t1;
INSERT INTO t1 SELECT c1+1000,c2+1000,c3+1000 from t1;
INSERT INTO t1 SELECT c1+10000,c2+10000,c3+10000 from t1;
INSERT INTO t1 SELECT c1+100000,c2+100000,c3+100000 from t1;
INSERT INTO t1 SELECT c1+1000000,c2+1000000,c3+1000000 from t1;
ANALYZE TABLE t1;
EXPLAIN SELECT * FROM t1 WHERE c1 = 99999999 AND c3 > 1 ORDER BY c3;
id select_type table partitions type possible_keys key key_len ref rows filtered Extra
-1 SIMPLE t1 NULL ref PRIMARY,c3 PRIMARY 4 const 1 100.00 Using where; Using filesort
+1 SIMPLE t1 NULL ref PRIMARY,c3 PRIMARY 4 const 1 99.78 Using where; Using filesort
condition c3> 1 should produce all the rows in index c3 but it produces 1 row less.
Here in above case total rows is 448, estimates is 447,
What I see from debugging. btr_estimate_n_rows_in_range_on_level there are 3 pages to scan and all are used in sampling
but still estimates are less by 1 row.
so instead of getting 100% we get 99.78% for filtered column.
This can be repeated only when we set innodb_page_size id 4k or less.
For 8K+ plus page all rows are in single page and it get resolved as non diverged case btr_estimate_n_rows_in_range.
So not repeatable with above case. May be we can insert more rows to repeat the same with 8k+ pages.
Suggested fix:
By reviewing I found following things.
In btr_estimate_n_rows_in_range_on_level
When calculating number rows from first page/slot.
/* add records from slot1->page_no which are to the right of
the record which serves as a left border of the range, if any */
if (slot1->nth_rec < slot1->n_recs) {
n_rows += slot1->n_recs - slot1->nth_rec;
}
n_recs is total user records in page (only user records).
nth_rec is position of record in page.
-- nth_rec is calculated as number of records before this records, this count also includes meta records (INF, SUP).
CODE:
slot->nth_rec = page_rec_get_n_recs_before(rec); in btr_cur_add_path_info
Consider
a page with following records
INF a, b SUP
slot->nth_rec for record "a" will be 1 (records before it INF here)
slot->nth_rec for record "b" will be 2 (records a, INF before b)
slot->nth_rec for record SUP will be 3 (records b, a, INF)
So when calculating number of user rows from given slot in page.
we do "n_rows += slot1->n_recs - slot1->nth_rec;"
Here nth_rec also counts INF.
Subtracting INF with actual user records will produce 1 count less.
So I think it should be "n_rows += slot1->n_recs - (slot1->nth_rec - 1);" // remove INF from the count while subtracting.
OR "n_rows += slot1->n_recs - slot1->nth_rec + 1;"
Appears similar issue exists in btr_estimate_n_rows_in_range, have not verified.
Description: btr_estimate_n_rows_in_range and btr_estimate_n_rows_in_range_on_level produces 1 row less than actual numbers even though all the pages are used for sampling. and is_n_rows_exact is set true. How to repeat: CREATE TABLE `t1` ( c1 int NOT NULL, c2 int NOT NULL, c3 int NOT NULL, PRIMARY KEY (c1,c2), KEY (c3) ) ENGINE=InnoDB, STATS_PERSISTENT=1; # populate with data INSERT INTO t1 VALUES (5,2,1246276747); INSERT INTO t1 VALUES (2,1,1246281721); INSERT INTO t1 VALUES (7,3,1246281756); INSERT INTO t1 VALUES (4,2,1246282139); INSERT INTO t1 VALUES (3,1,1246282230); INSERT INTO t1 VALUES (1,0,1246282712); INSERT INTO t1 VALUES (8,3,1246282765); INSERT INTO t1 SELECT c1+10,c2+10,c3+10 FROM t1; INSERT INTO t1 SELECT c1+100,c2+100,c3+100 from t1; INSERT INTO t1 SELECT c1+1000,c2+1000,c3+1000 from t1; INSERT INTO t1 SELECT c1+10000,c2+10000,c3+10000 from t1; INSERT INTO t1 SELECT c1+100000,c2+100000,c3+100000 from t1; INSERT INTO t1 SELECT c1+1000000,c2+1000000,c3+1000000 from t1; ANALYZE TABLE t1; EXPLAIN SELECT * FROM t1 WHERE c1 = 99999999 AND c3 > 1 ORDER BY c3; id select_type table partitions type possible_keys key key_len ref rows filtered Extra -1 SIMPLE t1 NULL ref PRIMARY,c3 PRIMARY 4 const 1 100.00 Using where; Using filesort +1 SIMPLE t1 NULL ref PRIMARY,c3 PRIMARY 4 const 1 99.78 Using where; Using filesort condition c3> 1 should produce all the rows in index c3 but it produces 1 row less. Here in above case total rows is 448, estimates is 447, What I see from debugging. btr_estimate_n_rows_in_range_on_level there are 3 pages to scan and all are used in sampling but still estimates are less by 1 row. so instead of getting 100% we get 99.78% for filtered column. This can be repeated only when we set innodb_page_size id 4k or less. For 8K+ plus page all rows are in single page and it get resolved as non diverged case btr_estimate_n_rows_in_range. So not repeatable with above case. May be we can insert more rows to repeat the same with 8k+ pages. Suggested fix: By reviewing I found following things. In btr_estimate_n_rows_in_range_on_level When calculating number rows from first page/slot. /* add records from slot1->page_no which are to the right of the record which serves as a left border of the range, if any */ if (slot1->nth_rec < slot1->n_recs) { n_rows += slot1->n_recs - slot1->nth_rec; } n_recs is total user records in page (only user records). nth_rec is position of record in page. -- nth_rec is calculated as number of records before this records, this count also includes meta records (INF, SUP). CODE: slot->nth_rec = page_rec_get_n_recs_before(rec); in btr_cur_add_path_info Consider a page with following records INF a, b SUP slot->nth_rec for record "a" will be 1 (records before it INF here) slot->nth_rec for record "b" will be 2 (records a, INF before b) slot->nth_rec for record SUP will be 3 (records b, a, INF) So when calculating number of user rows from given slot in page. we do "n_rows += slot1->n_recs - slot1->nth_rec;" Here nth_rec also counts INF. Subtracting INF with actual user records will produce 1 count less. So I think it should be "n_rows += slot1->n_recs - (slot1->nth_rec - 1);" // remove INF from the count while subtracting. OR "n_rows += slot1->n_recs - slot1->nth_rec + 1;" Appears similar issue exists in btr_estimate_n_rows_in_range, have not verified.