| 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: | |
| Category: | MySQL Server: Optimizer | Severity: | S3 (Non-critical) |
| Version: | 5.0, 5.1, etc | OS: | Any |
| Assigned to: | Martin Hansson | CPU Architecture: | Any |
[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.
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).