I have been working with a few customer cases and one interesting case popped up. The customer was facing a peculiar problem where the rows column in the EXPLAIN output of the query was totally off. The actual number of rows was 18 times more than the number of rows reported by MySQL in the output of EXPLAIN. Now this can be a real pain as MySQL uses “the number of rows” estimation to pick and choose indexes and it could really be picking up a wrong index simply because of the wrong estimate.

The customer reported that he changed the value of innodb_stats_sample_pages from 8 to 256 but with no effect, however I think innodb_stats_sample_pages really would have no effect on the “number of rows estimation”, because page sampling is used to generate index cardinality estimates which are then in turn used by MySQL to pick and choose indexes and hence is irrelevant to this problem.

Next, I proceeded to test using MySQL 5.1.58 and 5.5.15 vanilla releases.

Following is the definition of the table that I used for the test:

First I did a test for a SIMPLE SELECT to see the actual count of rows:

And then proceeded to run the EXPLAIN on both 5.1 and 5.5:

On 5.1:

On 5.5:

The results on 5.1 are very off, you don’t expect that much variation between the actual number of rows and the rows estimated. While the results on 5.5 are much closer and are acceptable.

Next, I decided to do a test run for a SELECT involving RANGE SCAN:

The actual count of rows is:

And the EXPLAIN result,

On 5.1:

On 5.5:

Again the row estimates on 5.1 is very off, its as much as 57 times less than the number of rows, which is not acceptable at all. While 5.5 returns an acceptable estimate.

This test proves that there is a bug in MySQL 5.1 and how it calculates the row estimates. This bug was tracked down to http://bugs.mysql.com/bug.php?id=53761 and was indeed fixed in 5.5 as my tests show.

Vasil Dimov goes on to explain the reason of the bug:
“For a given level the algo knows the number of pages in the requested range and the number of records on the leftmost and the rightmost page. Then it assumes all pages in between contain the average between the two border pages and multiplies this average number by the number of intermediate pages.”

Obviously this assumption, that all the pages in the requested range have almost similar number of records, fails when the pages between the leftmost and the rightmost page have fewer or larger number of records per page. This is not something that can happen in all cases, but there are two scenarios when this can happen:

  1. when you have a large number of records that are concentrated against a key value and that key value happens to be in the intermediate pages,
  2. when you have a large number of records that are concentrated against key values that lie in the leftmost and rightmost page and very few records concentrated against the key values that lie in the intermediate pages.

The fix that is introduced is:
“Same idea, but peek a few (10) of the intermediate pages to get a better estimate of the average number of records per page. If there are less than 10 intermediate pages then all of them will be scanned and the result will be precise, not an estimation.”

This seems to be a good fix as sampling more of the intermediate pages is going to increase the quality of the estimation, and make the estimation very precise if the index tree is not much wide.

7 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Mark Callaghan

Thanks for the notice. One consequence of the bug fix is that the optimizer can do more disk IO getting these estimates for IO-bound workloads. If that index is not selected for the query then this IO is wasted.

0
Shlomi Noach

@Mark,
Excellent point. But, would you say for sure that the IO is *not* wasted when the execution plan does indeed use said index?
Question asked is, will those pages scanned while evaluation execution plan, be cached within the buffer pool (or anywhere else other than OS cache) such that they are then quickly retrieved during query execution?

0
Jens Rantil

We’ve experienced inconsistencies in index cardinality in MySQL 5.1, too: http://bugs.mysql.com/bug.php?id=58382

0
Ovais Tariq

@Shlomi,
I ran a small test to see if the pages are actually cached within the buffer pool during query execution plan evaluation. I ran the test on a local MySQL sandbox version 5.5.15.

Before executing the explain:

[root@localhost ~]# mysqladmin –defaults-file=sandboxes/msb_vanilla_5_5_15/my.sandbox.cnf extended-status | grep -i innodb_buffer_pool_pages
| Innodb_buffer_pool_pages_data | 141 |
| Innodb_buffer_pool_pages_dirty | 0 |
| Innodb_buffer_pool_pages_flushed | 0 |
| Innodb_buffer_pool_pages_free | 10098 |
| Innodb_buffer_pool_pages_misc | 0 |
| Innodb_buffer_pool_pages_total | 10239 |

After executing the explain:

[root@localhost ~]# mysqladmin –defaults-file=sandboxes/msb_vanilla_5_5_15/my.sandbox.cnf extended-status | grep -i innodb_buffer_pool_pages
| Innodb_buffer_pool_pages_data | 224 |
| Innodb_buffer_pool_pages_dirty | 0 |
| Innodb_buffer_pool_pages_flushed | 0 |
| Innodb_buffer_pool_pages_free | 10015 |
| Innodb_buffer_pool_pages_misc | 0 |
| Innodb_buffer_pool_pages_total | 10239 |

This test clearly shows that the pages that are read during the execution plan evaluation are indeed read into the buffer pool. A total of 83 pages are read into the buffer pool, consisting of up to 10 pages being read for every level of the tree.

0
Baron Schwartz

Ovais, you are correct. InnoDB uses the buffer pool for all reads; it doesn’t have any other memory it would use for reads.

0
Ben Tremblay

Gee, that felt good! When I read the algo I thought, “Gosh, that’s not safe. Why not sample the intermediate pages?”
🙂

0
Bart

Have the same problem in mysql 5.5.20

0