MySQL Bugs: #41890: Falcon: New execution plans with MRR cause slowdown for group of queries

Bug #41890	Falcon: New execution plans with MRR cause slowdown for group of queries
Submitted:	5 Jan 2009 22:53	Modified:	23 Apr 2009 1:21
Reporter:	Alexey Stroganov	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	6.0.9-release	OS:	Any
Assigned to:	Sergey Petrunya	CPU Architecture:	Any
Tags:	F_SERVER

Description:
Execution plan has changed in 6.0.9 for group of queries (see below). The only difference with 6.0.8 in execution plans is that in 6.0.9 optimizer adds 'Using MRR'. This causes 30-40% slowdown.

Table defined as following:

CREATE TABLE `bench1` (
  `id` int(11) NOT NULL,
  `id2` int(11) NOT NULL,
  `id3` int(11) NOT NULL,
  `dummy1` char(30) DEFAULT NULL,
  PRIMARY KEY (`id`,`id2`),
  KEY `ix_id3` (`id3`)
) ENGINE=Falcon;

6.0.8
-----

mysql> explain select * from  bench1 where (id3>=1 or id3 <=2) and id3<=2;
+----+-------------+--------+-------+---------------+--------+---------+------+--------+-------------+
| id | select_type | table  | type  | possible_keys | key    | key_len | ref  | rows   | Extra       |
+----+-------------+--------+-------+---------------+--------+---------+------+--------+-------------+
|  1 | SIMPLE      | bench1 | range | ix_id3        | ix_id3 | 4       | NULL | 300000 | Using where |
+----+-------------+--------+-------+---------------+--------+---------+------+--------+-------------+
1 row in set (0.00 sec)

mysql> explain select * from bench1 where id=3 or id=2 or id=1 or id=4 or id=16 or id=10;
+----+-------------+--------+-------+---------------+---------+---------+------+--------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows   | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+-------------+
|  1 | SIMPLE      | bench1 | range | PRIMARY       | PRIMARY | 4       | NULL | 180000 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+-------------+
1 row in set (0.00 sec)

6.0.9
-----
mysql> explain select * from  bench1 where (id3>=1 or id3 <=2) and id3<=2;
+----+-------------+--------+-------+---------------+--------+---------+------+--------+------------------------+
| id | select_type | table  | type  | possible_keys | key    | key_len | ref  | rows   | Extra                  |
+----+-------------+--------+-------+---------------+--------+---------+------+--------+------------------------+
|  1 | SIMPLE      | bench1 | range | ix_id3        | ix_id3 | 4       | NULL | 300000 | Using where; Using MRR |
+----+-------------+--------+-------+---------------+--------+---------+------+--------+------------------------+
1 row in set (0.00 sec)

mysql> explain select * from bench1 where id=3 or id=2 or id=1 or id=4 or id=16 or id=10;
+----+-------------+--------+-------+---------------+---------+---------+------+--------+------------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows   | Extra                  |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+------------------------+
|  1 | SIMPLE      | bench1 | range | PRIMARY       | PRIMARY | 4       | NULL | 180000 | Using where; Using MRR |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+------------------------+
1 row in set (0.00 sec)

Affected queries:

select * from bench1 where id=3 or id=2 or id=1 or id=4 or id=16 or id=10;
select * from bench1 where id>=299999 or id<1;
select * from bench1 where id>=1 and id<=2;
select * from bench1 where (id>=1 and id<=2) or (id>=1 and id<=2);
select * from bench1 where id>=1 and id<=10 and id<=5;
select * from bench1 where (id>0 and id<2) or id>=299999;
select * from bench1 where (id>0 and id<2) or (id>= 50000 and id <= 50002) or id = 49999;
select * from bench1 where (id>=5 and id<=10) or (id>=1 and id<=4);
select * from bench1 where (id=1 or id=5 or id=20 or id=40) and (id=1 or id>=20 or id=4);
select * from bench1 where ((id=1 or id=3) or (id>1 and id<3)) and id<=2;
select * from bench1 where (id >= 0 and id < 4) or (id >=4 and id < 6);
select * from bench1 where id <= -1 or (id >= 0 and id <= 5) or (id >=4 and id<6) or (id>=6 and id<=7) or (id>7 and id <=8);
select * from bench1 where (id>=1 and id<=2 or id>=4 and id<=5) or (id>=0 and id <=10);
select * from bench1 where (id>=1 and id<=2 or id>=4 and id<=5) or (id>2 and id <=10);
select * from bench1 where (id>1 or id <1) and id<=2;
select * from bench1 where id <= 2 and (id>1 or id <=1);
select * from bench1 where (id>=1 or id <1) and id<=2;
select * from bench1 where (id>=1 or id <=2) and id<=2;
select * from bench1 where id3=3 or id3=2 or id3=1 or id3=4 or id3=16 or id3=10;
select * from bench1 where id3>=299999 or id3<1;
select * from bench1 where id3>=1 and id3<=2;
select * from bench1 where (id3>=1 and id3<=2) or (id3>=1 and id3<=2);
select * from bench1 where id3>=1 and id3<=10 and id3<=5;
select * from bench1 where (id3>0 and id3<2) or id3>=299999;
select * from bench1 where (id3>0 and id3<2) or (id3>= 50000 and id3 <= 50002) or id3 = 49999;
select * from bench1 where (id3>=5 and id3<=10) or (id3>=1 and id3<=4);
select * from bench1 where (id3=1 or id3=5 or id3=20 or id3=40) and (id3=1 or id3>=20 or id3=4);
select * from bench1 where ((id3=1 or id3=3) or (id3>1 and id3<3)) and id3<=2;
select * from bench1 where (id3 >= 0 and id3 < 4) or (id3 >=4 and id3 < 6);
select * from bench1 where id3<=-1 or (id3>=0 and id3<=5) or (id3>=4 and id3<6) or (id3>=6 and id3<=7) or (id3>7 and id3<=8);
select * from bench1 where (id3>=1 and id3<=2 or id3>=4 and id3<=5) or (id3>=0 and id3 <=10);
select * from bench1 where (id3>=1 and id3<=2 or id3>=4 and id3<=5) or (id3>2 and id3 <=10);
select * from bench1 where (id3>1 or id3 <1) and id3<=2;
select * from bench1 where id3 <= 2 and (id3>1 or id3 <=1);
select * from bench1 where (id3>=1 or id3 <1) and id3<=2;
select * from bench1 where (id3>=1 or id3 <=2) and id3<=2;

How to repeat:
- Create tables in 6.0.8 and 6.0.9 and compare explain output for any of provided queries.

- I've attached script that will help to create/populate table with data

Helper script for the issue

Attachment: bug-falcon_mrr.pl (application/octet-stream, text), 1.61 KiB.

Found one more query that became slower on 40% due to using MRR in the execution plan:

query: select bench1.* from bench1 where id in (1,2,3,4,5,6,7,8,9,10);

table definition: the same as and for issues above

6.0.8
-----
mysql> explain select bench1.* from bench1 where id in (1,2,3,4,5,6,7,8,9,10);
+----+-------------+--------+-------+---------------+---------+---------+------+--------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows   | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+-------------+
|  1 | SIMPLE      | bench1 | range | PRIMARY       | PRIMARY | 4       | NULL | 300000 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+-------------+
1 row in set (0.00 sec)

6.0.9
-----
mysql> explain select bench1.* from bench1 where id in (1,2,3,4,5,6,7,8,9,10);
+----+-------------+--------+-------+---------------+---------+---------+------+--------+------------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows   | Extra                  |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+------------------------+
|  1 | SIMPLE      | bench1 | range | PRIMARY       | PRIMARY | 4       | NULL | 300000 | Using where; Using MRR |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+------------------------+

Kevin,

It looks that despite the fact execution plan has changed in 6.0.9(explain displays 'Using MRR' now) switching on/off MRR feature itself has no impact on performance for Falcon so I think you should re-evaluate this issue:

'MySQL 6.0.8 alpha/'
Time for select_range_prefix (1000:3000): 33.072 wallclock secs

'MySQL 6.0.9 alpha/'
Time for select_range_prefix (1000:3000): 47.118 wallclock secs

'MySQL 6.0.9 alpha/' with @optimizer_use_mrr='disable'
Time for select_range_prefix (1000:3000): 47.234 wallclock secs

I will provide simplified test case that should to debug/profile issue.

Ranger, if MRR isn't the problem, could you please change the bug synopsis then?

Kevin,

I have to apologize for confusion. Due to silly mistake in the test script optimizer_use_mrr option was handled incorrectly so this leaded to wrong conclusion. 

I've rerun test for the last query mentioned in this bug report and found out that mrr affects performance and number of Handler_read_next is significantly differs between cases when mrr is enabled  and disabled.

with mrr:    time: 106.662   Handler_read_next: 131072000
without mrr: time: 85.2591   Handler_read_next: 30000

See details below:

#WITH MRR
perl  bug_select_mrr.pl --db-socket=/tmp/609.sock --select_in --db-engine="FALCON"  --mrr_mode=force
MySQL 6.0.9 alpha, ENGINE: FALCON
Inner table size: 10
SET mode=force
optimizer_use_mrr=force

QUERY:SELECT bench1.* FROM bench1 WHERE id IN (1,2,3,4,5,6,7,8,9,10)
init values:
Testing SELECT ... WHERE id in (10 values)
end values:
Handler_read_next: 131072000
Time for select_in (1000:10000): 106.662 wallclock secs 

#WITHOUT MRR
perl  bug_select_mrr.pl --db-socket=/tmp/609.sock --select_in  --db-engine="FALCON" --mrr_mode=disable
MySQL 6.0.9 alpha, ENGINE: FALCON
Inner table size: 10
SET mode=disable
optimizer_use_mrr=disable

QUERY:SELECT bench1.* FROM bench1 WHERE id IN (1,2,3,4,5,6,7,8,9,10)
init values:
Testing SELECT ... WHERE id in (10 values)
end values:
Handler_read_next: 30000
Time for select_in (1000:10000): 85.2591 wallclock secs 

I will attach updated script that will help to simplify process of preparing data and running affected queries. 

#to load initial data run script with --create option
perl  bug_select_mrr.pl --db-socket=/tmp/609.sock --db-engine="FALCON" --create 

#to run select_in query 
perl  bug_select_mrr.pl --db-socket=/tmp/609.sock --db-engine="FALCON" --select_in 

#to enable/disable mrr use --mode_mrr=(disable|force)
perl  bug_select_mrr.pl --db-socket=/tmp/609.sock --db-engine="FALCON" --select_in  --mode_mrr=disable

#to get handler stat for query use --db-stat option
perl  bug_select_mrr.pl --db-socket=/tmp/609.sock --db-engine="FALCON" --select_in  --mode_mrr=disable --db-stat

Updated test case for the issue

Attachment: bug_select_mrr_41980.pl (application/octet-stream, text), 9.42 KiB.

I'm experimenting with this query:
mysql> SELECT bench1.* FROM bench1 WHERE id IN (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999,1000);

Handler_% counter increments 

with MRR:

| Handler_commit             | 1      |
| Handler_read_next          | 131072 |

without MRR:  
| Handler_commit             | 1     |
| Handler_read_next          | 3000  |

neither of the values seems to be correct.

For non-MRR case, wrong counter values (3K increments while retrieving 1K ranges with 1K records each) is caused by the following:

ha_falcon::index_next_same() calls ha_falcon::index_next(). 
Both of them have the

  ha_statistic_increment(&SSV::ha_read_next_count);

line at the start which causes counter to be incremented twice for index_next_same() calls.

For MRR case: 

On the second entry into IndexRootPage::scanIndex(), it puts 131K record number bits into the bitmap (while the query can't have >1K results). This is the cause of wrong counter values and most likely the cause of the slowdown.

Checking if MRR ships correct index bounds down into IndexRootPage::scanIndex: examining the first two ranges in MRR and non-MRR scans:

==== Without MRR ===
  Breakpoint 4, IndexRootPage::scanIndex (dbb=0xb6889818, indexId=10, rootPage=220, lowKey=0xb6becc54, highKey=0xb6bef6a4, searchFlags=1, transId=0, bitmap=0xb6885308) at IndexRootPage.cpp:371

(gdb) p *start_key
  $66 = {key = 0x9f83a30 "\001", length = 4, keypart_map = 1, flag = HA_READ_KEY_EXACT}
(gdb) p *end_key
  $67 = {key = 0x9f83a38 "\001", length = 4, keypart_map = 1, flag = HA_READ_AFTER_KEY}

  $59 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 3, recordNumber = 0, key = "\002¿ð@", 'Ì' <repeats 10805 times>}
(gdb) p *highKey
  $60 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 3, recordNumber = 0, key = "\002¿ð@", 'Ì' <repeats 10805 times>}
(gdb) x/4c lowKey.key
  0xb6becc64:	2 '\002'	-65 '¿'	-16 'ð'	64 '@'
(gdb) x/4c highKey.key
  0xb6bef6b4:	2 '\002'	-65 '¿'	-16 'ð'	64 '@'

  Breakpoint 4, IndexRootPage::scanIndex (dbb=0xb6889818, indexId=10, rootPage=220, lowKey=0xb6becc54, highKey=0xb6bef6a4, searchFlags=1, transId=0, bitmap=0xb6885308) at IndexRootPage.cpp:371

(gdb) p *start_key
  $64 = {key = 0x9f83a58 "\002", length = 4, keypart_map = 1, flag = HA_READ_KEY_EXACT}
(gdb) p *end_key
  $65 = {key = 0x9f83a60 "\002", length = 4, keypart_map = 1, flag = HA_READ_AFTER_KEY}

(gdb) p *highKey
  $62 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 2, recordNumber = 0, key = "\002Àð@", 'Ì' <repeats 10805 times>}
(gdb) p *lowKey
  $63 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 2, recordNumber = 0, key = "\002Àð@", 'Ì' <repeats 10805 times>}
(gdb) x/4c lowKey.key
  0xb6becc64:	2 '\002'	-64 'À'	-16 'ð'	64 '@'
(gdb) x/4c highKey.key
  0xb6bef6b4:	2 '\002'	-64 'À'	-16 'ð'	64 '@'

=== With MRR ===

(gdb) p * startKey
  $70 = {key = 0x9f83a30 "\001", length = 4, keypart_map = 1, flag = HA_READ_KEY_EXACT}
(gdb) p * endKey
  $71 = {key = 0x9f83a38 "\001", length = 4, keypart_map = 1, flag = HA_READ_AFTER_KEY}

  Breakpoint 4, IndexRootPage::scanIndex (dbb=0xb6889818, indexId=10, rootPage=220, lowKey=0xb6becc54, highKey=0xb6bef6a4, searchFlags=1, transId=0, bitmap=0xb6885308) at IndexRootPage.cpp:371
(gdb) p *lowKey
  $72 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 3, recordNumber = 0, key = "\002¿ð@", 'Ì' <repeats 10805 times>}
(gdb) p *highKey
  $73 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 3, recordNumber = 0, key = "\002¿ð@", 'Ì' <repeats 10805 times>}
(gdb) x/4c lowKey.key
  0xb6becc64:	2 '\002'	-65 '¿'	-16 'ð'	64 '@'
(gdb) x/4c highKey.key
  0xb6bef6b4:	2 '\002'	-65 '¿'	-16 'ð'	64 '@'
(gdb) c

  Breakpoint 4, IndexRootPage::scanIndex (dbb=0xb6889818, indexId=10, rootPage=220, lowKey=0xb6becc54, highKey=0xb6bef6a4, searchFlags=1, transId=0, bitmap=0xb6885308) at IndexRootPage.cpp:371

(gdb) p *lowKey
  $74 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 2, recordNumber = 0, key = "\002Àð@", 'Ì' <repeats 10805 times>}
(gdb) p *highKey
  $75 = {_vptr.IndexKey = 0x8b69e40, index = 0xb68a0780, keyLength = 2, recordNumber = 0, key = "\002Àð@", 'Ì' <repeats 10805 times>}
(gdb) x/4c lowKey.key
  0xb6becc64:	2 '\002'	-64 'À'	-16 'ð'	64 '@'
(gdb) x/4c highKey.key
  0xb6bef6b4:	2 '\002'	-64 'À'	-16 'ð'	64 '@'

The parameters seem to be the same. Nevertheless, in MRR case, second invocation of IndexRootPage::scanIndex puts 131K bits into the bitmap.  in non-MRR it puts, as expected, only one.

Perhaps MRR isn't cleaning something after one range scan before the other but I don't understand what it is.

Discovered an odd thing in Falcon w/o MRR, reported it as BUG#42136. Waiting for that to be resolved before we can proceed with this bug.

With regards to why do we have (see previous comments):

without MRR:  
| Handler_commit             | 1     |
| Handler_read_next          | 3000  |

it's another issue, reported it as BUG#43293.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/67939

2726 Sergey Petrunia	2009-03-01
      BUG#41890: Falcon: New execution plans with MRR cause slowdown for group of queries
      - Testcase

With the fix for BUG#42136, this issue is resolved. Committed a patch with testcase.

With the fix for BUG#42136, this problem doesn't occur anymore. Committed a patch with a testcase.

Pushed into 6.0.11-alpha (revid:sergefp@mysql.com-20090417211236-fy28y9o1w8p4ic9m) (version source revid:sergefp@mysql.com-20090301182607-xglayyk67lwson93) (merge vers: 6.0.11-alpha) (pib:6)

Noted in 6.0.10 changelog.

For Falcon tables, range queries using an index prefix were slow when
Multi-Range Read index scans were disabled.