MySQL Bugs: #33730: Full table scan instead selected partitions for query more than 10 partitions

Bug #33730	Full table scan instead selected partitions for query more than 10 partitions
Submitted:	8 Jan 2008 0:18	Modified:	12 Nov 2009 20:15
Reporter:	Jun Chen	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	5.1.22	OS:	Linux
Assigned to:		CPU Architecture:	Any
Tags:	wantin51

Description:
The table is hash partitioned, a calculation is to convert the dateKey (integer format as yyyymmdd) into sequence number that make the data of every month was stored in one single partition without duplication in 10 years (total 120 partitions).
PARTITION BY HASH (((eventDateKey div 10000 + 1)mod 10 )* 12 + (eventDateKey mod 10000 div 100  - 1)) PARTITIONS 120

If the query need 10 days or less data (can be either discrete or continuely), the only necessary partition will be involved in the query, but if more than 10 days in where condition, then it will perform a full table scan, all partitions will be involved in the query. 

It means, the partition does not work for the query with more than 10 partitions. 

How to repeat:

create table PartitionTest ( dateKey integer not null, data integer, primary key (dateKey)) PARTITION BY HASH (((dateKey div 10000 + 1)mod 10 )* 12 + (dateKey mod 10000 div 100  - 1)) PARTITIONS 120;

insert into PartitionTest values (20071101, 1), (20071102, 2),(20071103,3), (20071104,4),(20071201,5),(20071202,6), (20071203,7), (20071204,8), (20071205,9), (20080101,10), (20080102,11);

mysql> explain partitions select dateKey, count(*) from PartitionTest where dateKey between 20071101 and 20071110 group by dateKey;
+----+-------------+---------------+------------+-------+---------------+---------+---------+------+------+--------------------------+
| id | select_type | table         | partitions | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+----+-------------+---------------+------------+-------+---------------+---------+---------+------+------+--------------------------+
|  1 | SIMPLE      | PartitionTest | p106       | range | PRIMARY       | PRIMARY | 4       | NULL |    3 | Using where; Using index |
+----+-------------+---------------+------------+-------+---------------+---------+---------+------+------+--------------------------+

mysql> explain partitions select dateKey, count(*) from PartitionTest where dateKey in ( 20071101, 20071111,20071201, 20080101) group by dateKey;
+----+-------------+---------------+----------------+-------+---------------+---------+---------+------+------+--------------------------+
| id | select_type | table         | partitions     | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+----+-------------+---------------+----------------+-------+---------------+---------+---------+------+------+--------------------------+
|  1 | SIMPLE      | PartitionTest | p106,p107,p108 | range | PRIMARY       | PRIMARY | 4       | NULL |    4 | Using where; Using index |
+----+-------------+---------------+----------------+-------+---------------+---------+---------+------+------+--------------------------+
1 row in set (0.00 sec)

mysql> explain partitions select dateKey, count(*) from PartitionTest where dateKey between 20071101 and 20071111 group by dateKey;
+----+-------------+---------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------+---------------+---------+---------+------+------+--------------------------+
| id | select_type | table         | partitions                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+----+-------------+---------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------+---------------+---------+---------+------+------+--------------------------+
|  1 | SIMPLE      | PartitionTest | p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16,p17,p18,p19,p20,p21,p22,p23,p24,p25,p26,p27,p28,p29,p30,p31,p32,p33,p34,p35,p36,p37,p38,p39,p40,p41,p42,p43,p44,p45,p46,p47,p48,p49,p50,p51,p52,p53,p54,p55,p56,p57,p58,p59,p60,p61,p62,p63,p64,p65,p66,p67,p68,p69,p70,p71,p72,p73,p74,p75,p76,p77,p78,p79,p80,p81,p82,p83,p84,p85,p86,p87,p88,p89,p90,p91,p92,p93,p94,p95,p96,p97,p98,p99,p100,p101,p102,p103,p104,p105,p106,p107,p108,p109,p110,p111,p112,p113,p114,p115,p116,p117,p118,p119 | index | PRIMARY       | PRIMARY | 4       | NULL |   11 | Using where; Using index |
+----+-------------+---------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------+---------------+---------+---------+------+------+--------------------------+

It's not 10 partitions, but 10 partition key values in the re-create example.

Verified as described with bk source.

mysql> insert into PartitionTest values (20071101, 1), (20071102, 2),(20071103,3), (20071104,4),(20071201,5),(20071202,6), (20071203,7), (20071204,8), (20071205,9), (20080101,10), (20080102,11);

explain partitions select dateKey, count(*) from PartitionTest where dateKey between 20071101 and 20071110 group by dateKey\G*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: PartitionTest
   partitions: p106
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 3
        Extra: Using where; Using index
1 row in set (0.00 sec)

Here, it wonders me, that the expected rows are 3. When you look to the "INSERT", there are 4 rows, that match.

mysql> explain partitions select dateKey, count(*) from PartitionTest where dateKey between 20071101 and 20071111 group by dateKey\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: PartitionTest
   partitions: p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16,p17,p18,p19,p20,p21,p22,p23,p24,p25,p26,p27,p28,p29,p30,p31,p32,p33,p34,p35,p36,p37,p38,p39,p40,p41,p42,p43,p44,p45,p46,p47,p48,p49,p50,p51,p52,p53,p54,p55,p56,p57,p58,p59,p60,p61,p62,p63,p64,p65,p66,p67,p68,p69,p70,p71,p72,p73,p74,p75,p76,p77,p78,p79,p80,p81,p82,p83,p84,p85,p86,p87,p88,p89,p90,p91,p92,p93,p94,p95,p96,p97,p98,p99,p100,p101,p102,p103,p104,p105,p106,p107,p108,p109,p110,p111,p112,p113,p114,p115,p116,p117,p118,p119
         type: index
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 11
        Extra: Using where; Using index
1 row in set (0.01 sec)

When there are more then 10 steps between the numbers, it always choose all partitions.
I also tried it with other ranges.

When you expect a maximum of 10 rows, it will search only at the patitions, where the results are stored, but when you expect more then 10 rows, then it searches on all partitions.

Partitioning problem, re-assigning.

Since the range is 11 values it is just above the optimization level for partitioning pruning (MAX_RANGE_TO_WALK is defined as 10). (sql_partition.cc)

I will have a discussion with Mikael if this is the right value. Please add a comment about how you would like this to be handled.

Reassigning to Sergey P since he wrote the code and it is optimizing related too.

Single result entry with same problem

Attachment: 101.txt (text/plain), 5.54 KiB.

Glen,

I don't get what the problem is in the 101.txt file. You have

PARTITION BY HASH (messageblk_idnr)

and

WHERE physmessage_id = 1314716

Apparently the WHERE clause doesn't allow to prune away any partitions?

Jun, 

The number 10 you're hitting is an internal #define as documented here:

http://forge.mysql.com/wiki/MySQL_Internals_Optimizer#Interval_Walking

if you're comfortable with re-compiling MySQL, you can resolve the problem by these steps:

- Get MySQL source code
- Edit sql/sql_partition.cc, change

#define MAX_RANGE_TO_WALK 10

to some higher value (basically as many partitions as you need to be scanned for  such intervals. If you set the number too high then the optimizer might start working slower in certain cases).

- Recompile MySQL and use that.

At the moment we have no intent to fix this in 5.1 

We intend to fix this issue in MySQL 6.0 by 
 - introducing a tunable server parameter (most likely)
 - changing the default from 10 to some greater value (likely)
.

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/63535

2806 Sergey Petrunia	2009-01-19
      BUG#33730: Full table scan instead selected partitions for query more than 10 partitions
      For partition pruning, partition interval walking 
      - Increase MAX_RANGE_TO_WALK from 10 to 32
      - Remove "don't walk the interval if the number of values in it is greater than the number of partitions" rule.
        it could easily happen that the values fall into the same partitions so it's better to walk than not to.

See also Bug #42210

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/65386

2693 Sergey Petrunia	2009-02-05
      BUG#33730:Full table scan instead selected partitions for query more than 10 partitions
      - Be smarter when deciding whether to perform "range walking" partitioned analysis

Pushed into 6.0.10-alpha (revid:alik@sun.com-20090216180446-dl1xovi02kbd2fgn) (version source revid:igor@mysql.com-20090212210233-90wt5smvdd3orrcd) (merge vers: 6.0.10-alpha) (pib:6)

Noted in 6.0.10 changelog.

For partitioned tables with more than ten partitions, a full table
scan was used in some cases when only a subset of the partitions were
needed.

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/85798

2887 Guilhem Bichot	2009-10-05
      Backport of the fix for BUG#33730 "Full table scan instead selected partitions for query more than 10 partitions"
      from 6.0, made in sergefp@mysql.com-20090205190644-q8632sniogedhtsu

Pushed into 6.0.14-alpha (revid:alik@ibmvm-20091009083208-0o0f0i9w1sq3c1kn) (version source revid:guilhem@mysql.com-20091005210234-vjlm0uj8y41x4jh8) (merge vers: 6.0.14-alpha) (pib:12)

Already noted in 6.0.10 changelog.

as I have back-ported this to next-mr-bugfixing, it should be documented at some point.

Noted in 5.5.0 changelog.

Pushed into 5.5.0-beta (revid:alik@sun.com-20091110093229-0bh5hix780cyeicl) (version source revid:alik@ibmvm-20091009130916-0ijstmmz3efzx20g) (merge vers: 5.5.0-beta) (pib:13)

CentOS 5.7
MySQL 5.5.16

I see that the only change for this in 5.5.x seems to be MAX_RANGE_TO_WALK=32 ...

Considering the following:

PARTITION BY RANGE ((record_id div 2000000) mod 1024)
(
PARTITION p0 VALUES LESS THAN (1),
PARTITION p1 VALUES LESS THAN (2),
....
PARTITION p1022 VALUES LESS THAN (1023),
PARTITION p1023 VALUES LESS THAN (1024)
);

I have a table with 2 billion records, and I partitioned it into 1024 partitions with each partition containing chunks of 2 million consecutive record_id values.  I need this because our data processing system pulls data in chunks of 500K, 1M, and 2M.  With the current tests used in get_part_iter_for_interval_via_walking, I'm stuck with a full table scan, instead of ONE partition being checked.  I imagine that my case isn't too rare.  A worthwhile additional test might be to check the first value in the range and the last value in the range.  That would give you an idea of how many partitions will be scanned.  At the very least, if both fall within a single partition, the actual size of the range should be irrelevant.