Bug #41660 Sort-index_merge for non-first join table may require O(#scans) memory
Submitted: 20 Dec 2008 18:29 Modified: 14 Oct 2010 13:20
Reporter: Sergey Petrunya Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.0, 5.1, etc OS:Any
Assigned to: Martin Hansson
Triage: Triaged: D3 (Medium) / R2 (Low) / E2 (Low)

[20 Dec 2008 18:29] Sergey Petrunya
Description:
Sort-index_merge code allocates a new Unique object for every re-scan. So if execution of a query requires to do N sort-index_merge scans, we will require  N*sizeof(Unique) memory. The memory will be freed when the query has finished.

Use of this amount of memory is excessive.

How to repeat:
1. Load this dataset:

create table t0 (a int);
insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
create table t1 (a int);
insert into t1 values (1),(2);
create table t3 (a int, b int, filler char(100), key(a), key(b));
insert into t3 select 1000, 1000,'filler' from t0 A, t0 B, t0 C;
insert into t3 values (1,1,'data');

2. Go into sql/opt_range.cc, locate the below code, and put a breakpoint there:

  unique= new Unique(refpos_order_cmp, (void *)head->file,
                     head->file->ref_length,
                     thd->variables.sortbuff_size);

3. Start the server under debugger
4. Issue this query:
mysql> select * from t0 left join t3 on ( t3.a < 10 or t3.b < 10); 

5. Land in debugger: 
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  Current language:  auto; currently c++

# Remember the current mem_root. This is the mem_root that the Unique object is allocated on.
(gdb) set $memroot=thd->mem_root
(gdb) p $memroot
  $11 = (MEM_ROOT *) 0x8da0fcc
# Put a conditional breakpoint to catch when this mem_root is freed 
(gdb) b free_root
  Breakpoint 5 at 0x85b2c0c: file my_alloc.c, line 334.
(gdb) cond 5 root==$memroot
(gdb) commands 2 
  Type commands for when breakpoint 2 is hit, one per line.
  End with a line saying just "end".
>p $memroot==thd->mem_root
>end
# in the end we should have this:
(gdb) info b
  Num Type           Disp Enb Address    What
  2   breakpoint     keep y   0x08338656 in QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() at opt_range.cc:6599
  	breakpoint already hit 1 time
          p $memroot==thd->mem_root
  5   breakpoint     keep y   0x085b2c0c in free_root at my_alloc.c:334
  	stop only if root == $memroot
#
# Now let it continue the execution and watch what happens
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $12 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $13 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $14 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $15 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $16 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $17 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $18 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $19 = true
(gdb) c
  Continuing.
  
  Breakpoint 2, QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x8db9a10) at opt_range.cc:6601
  $20 = true
(gdb) c
  Continuing.
  
  Breakpoint 5, free_root (root=0x8da0fcc, MyFlags=1) at my_alloc.c:334
  Current language:  auto; currently c
(gdb) 

# Apparently we've allocated 10 (that's number of records in table t0) Unique objects before we free them all at the end of the query.  For big enough queries, this amount of memory consumption is excessive.

Suggested fix:
Either
* Make QUICK_INDEX_MERGE_SELECT provide space to store the Unique object and reuse that space.  
* Create Unique object in its own MEM_ROOT (requires some tricky actions when creating/deleting it, but entirely doable).

When making choice between the above options, look at how this problem is solved by other Unique users, e.g. by COUNT(DISTINCT).
[20 Dec 2008 18:33] Sergey Petrunya
Note: the example query uses LEFT JOIN only for the sake of being able to demonstrate the issue with a very small dataset. (left join disables use of join buffering, so we get the second table re-scanned for every record in the outer table. if we used inner join, we would need to have thousands of records and/or more columns in both tables so that the join buffer is filled and re-scans are triggered).
[22 Dec 2008 7:06] Sveta Smirnova
Thank you for the report.

Verified as described.
[17 May 2010 15:27] Bugs System
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/108453

3378 Martin Hansson	2010-05-17
      Bug#41660: Sort-index_merge for non-first join table may
      require O(#scans) memory
      
      When an index merge operation was restarted, it would
      re-allocate the Unique object controlling the duplicate row
      ID elimination. Fixed by making the Unique object a member
      of QUICK_INDEX_MERGE_SELECT and thus reusing it throughout
      the lifetime of this object.
[19 May 2010 14:18] Bugs System
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/108642

3378 Martin Hansson	2010-05-19
      Bug#41660: Sort-index_merge for non-first join table may
      require O(#scans) memory
      
      When an index merge operation was restarted, it would
      re-allocate the Unique object controlling the duplicate row
      ID elimination. Fixed by making the Unique object a member
      of QUICK_INDEX_MERGE_SELECT and thus reusing it throughout
      the lifetime of this object.
[4 Jun 2010 15:04] Bugs System
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/110251

3387 Martin Hansson	2010-06-04
      Bug#41660: Sort-index_merge for non-first join table may
      require O(#scans) memory
      
      When an index merge operation was restarted, it would
      re-allocate the Unique object controlling the duplicate row
      ID elimination. Fixed by making the Unique object a member
      of QUICK_INDEX_MERGE_SELECT and thus reusing it throughout
      the lifetime of this object.
[24 Jun 2010 13:21] Bugs System
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/112086

3441 Martin Hansson	2010-06-24
      Bug#41660: Sort-index_merge for non-first join table may
      require O(#scans) memory
      
      When an index merge operation was restarted, it would
      re-allocate the Unique object controlling the duplicate row
      ID elimination. Fixed by making the Unique object a member
      of QUICK_INDEX_MERGE_SELECT and thus reusing it throughout
      the lifetime of this object.
[24 Jun 2010 14:00] Bugs System
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/112095

3077 Martin Hansson	2010-06-24 [merge]
      Bug#41660: Sort-index_merge for non-first join table may
      require O(#scans) memory
      
      When an index merge operation was restarted, it would
      re-allocate the Unique object controlling the duplicate row
      ID elimination. Fixed by making the Unique object a member
      of QUICK_INDEX_MERGE_SELECT and thus reusing it throughout
      the lifetime of this object.
[24 Jun 2010 14:01] Bugs System
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/112096

3077 Martin Hansson	2010-06-24 [merge]
      Merge of fix for Bug#41660.
[29 Jun 2010 8:28] Bugs System
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/112418

3452 Martin Hansson	2010-06-29
      Fix of bad merge of test case for Bug#41660 (test case moved).
[19 Jul 2010 14:34] Bugs System
Pushed into 5.1.49 (revid:build@mysql.com-20100719143034-omcma40sblwmay3x) (version source revid:martin.hansson@sun.com-20100629082817-4f8vthqk8wq050zn) (merge vers: 5.1.48) (pib:16)
[20 Jul 2010 2:33] Paul Dubois
Noted in 5.1.49 changelog.

Sort-index_merge for join tables other than the first table used
excessive memory. 

Setting report to Need Merge pending further pushes.
[23 Jul 2010 12:22] Bugs System
Pushed into mysql-trunk 5.5.6-m3 (revid:alik@sun.com-20100723121820-jryu2fuw3pc53q9w) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:18)
[23 Jul 2010 12:29] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100723121929-90e9zemk3jkr2ocy) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (pib:18)
[26 Jul 2010 15:23] Paul Dubois
Noted in 5.5.6 changelog.
[14 Oct 2010 8:26] Bugs System
Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.20 (revid:martin.skold@mysql.com-20101014082627-jrmy9xbfbtrebw3c) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 8:41] Bugs System
Pushed into mysql-5.1-telco-6.3 5.1.51-ndb-6.3.39 (revid:martin.skold@mysql.com-20101014083757-5qo48b86d69zjvzj) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 8:56] Bugs System
Pushed into mysql-5.1-telco-6.2 5.1.51-ndb-6.2.19 (revid:martin.skold@mysql.com-20101014084420-y54ecj85j5we27oa) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 13:20] Jon Stephens
Already documented in the 5.1.49 changelog; no additional changelog entries required. Set back to Closed state.