Bug #40974 Incorrect query results when using clause evaluated using range check
Submitted: 24 Nov 2008 11:42 Modified: 28 Jan 2009 22:00
Reporter: David Heath Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.0/5.1/6.0 OS:Any
Assigned to: Sergey Petrunya
Triage: Triaged: D2 (Serious) / R2 (Low) / E2 (Low)

[24 Nov 2008 11:42] David Heath
Description:
The following SQL query gives different results depending on the presence or absence of an index on the friendship table:

select id,from_id,to_id,distance,path from friendship_shortest_path p where not exists (select * from friendship f0, friendship f1 where (f0.status in (2) AND f1.status in (2)) and ( (p.from_id = f0.befriender_id AND f0.friend_id = f1.befriender_id AND f1.friend_id = p.to_id) OR (p.from_id = f0.befriender_id AND f0.friend_id = f1.friend_id AND f1.befriender_id = p.to_id) OR (p.from_id = f0.friend_id AND f0.befriender_id = f1.befriender_id AND f1.friend_id = p.to_id) OR (p.from_id = f0.friend_id AND f0.befriender_id = f1.friend_id AND f1.befriender_id = p.to_id))) and p.distance=2;

This is clearly incorrect.

How to repeat:
Please see attached file for full steps to reproduce including data set.
[24 Nov 2008 11:43] David Heath
Steps to reproduce this bug

Attachment: mysql-bug-repro.sql (application/octet-stream, text), 15.50 KiB.

[24 Nov 2008 11:46] David Heath
Small edit for clarity

Attachment: mysql-bug-repro.sql (application/octet-stream, text), 16.14 KiB.

[24 Nov 2008 11:47] David Heath
correct grammatical error in synopsis
[24 Nov 2008 14:51] Miguel Solorzano
Thank you for the bug report. Verified as describe on 5.0/5.1/6.0 bzr source tree.
Verified with older released version 5.0.22 too.
[18 Dec 2008 18:59] Sergey Petrunya
EXPLAIN for correct result (when run without the problematic index):

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: p
         type: ref
possible_keys: friendship_shortest_path_distance
          key: friendship_shortest_path_distance
      key_len: 5
          ref: const
         rows: 9557
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: f0
         type: ALL
possible_keys: friendship_FI_2
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 329
        Extra: Using where
*************************** 3. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: f1
         type: ALL
possible_keys: friendship_FI_2
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 329
        Extra: Using where; Using join buffer
3 rows in set (0.01 sec)

EXPLAIN for incorrect results (with the index):
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: p
         type: ref
possible_keys: friendship_shortest_path_distance
          key: friendship_shortest_path_distance
      key_len: 5
          ref: const
         rows: 9557
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: f0
         type: ALL
possible_keys: friendship_FI_2,friendship_befriender_id
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 329
        Extra: Using where
*************************** 3. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: f1
         type: ALL
possible_keys: friendship_FI_2,friendship_befriender_id
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 329
        Extra: Range checked for each record (index map: 0x3)
3 rows in set (0.00 sec)
[18 Dec 2008 19:05] Sergey Petrunya
Observations

* If I use the debugger to force "range checked for each record" to always pick full table scan, the query results are correct.

* .trace shows that "Range checked for each record" will choose to do index merge:
grep -A10 ^quick /tmp/mysqld.trace  | less
quick index_merge select
merged scans {
  quick range select, key friendship_befriender_id, length: 5
    1 <= X <= 1
    508 <= X <= 508
  quick range select, key friendship_FI_2, length: 5
    1 <= X <= 1
    508 <= X <= 508
}
other_keys: 0x0:
T@3    : | | | | | | | | | | | | <print_quick
--
quick index_merge select
merged scans {
  quick range select, key friendship_befriender_id, length: 5
    1 <= X <= 1
    619 <= X <= 619
  quick range select, key friendship_FI_2, length: 5
    1 <= X <= 1
    619 <= X <= 619
}
other_keys: 0x0:
...
the same happens for roughly first 1K rows, I didn't check further.

T@3    : | | | | | | | | | | | | <print_quick

* The choice of index_merge is interesting. I investigated and see that range optimizer doesn't consider outer query references to be known when doing "Range-checked-for-each-record".  This is a gap in the optimization. Use of index_merge should not cause wrong query results, though.
[18 Dec 2008 20:48] Sergey Petrunya
Ok, the problem is as follows: if there's a query plan that uses range-checked-for-each-record which is run several times, and 

1. the first time we pick sort-union index-merge. 
1.1. we start reading records from index-merge and stop without reaching EOF (can happen when we're within a subquery or maybe certain kinds of outer joins) 
3. the second time we pick do do full table scan.

Then:
#1.1 will not deinitialize the scan properly, causing #3 to immediately return EOF.   In this bug case, returning EOF caused NOT EXISTS subquery predicate to evaluate to TRUE when it should have been FALSE and thus the upper query returned extra records.
[19 Dec 2008 13:39] 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/62099

2717 Sergey Petrunia	2008-12-19
      BUG#40974: Incorrect query results when using clause evaluated using range check
      - QUICK_INDEX_MERGE_SELECT deinitializes its rnd_pos() scan when it reaches EOF, but we 
        need to make the deinitialization in QUICK_INDEX_MERGE_SELECT destructor also. This is because
        certain execution strategies can stop scanning without reaching EOF, then then try to do a full
        table scan on this table. Failure to deinitialize caused the full scan to use (already empty) 
        table->sort and produce zero records.
[19 Dec 2008 13:41] Sergey Petrunya
The above fix fixes the wrong query results problem.
[19 Dec 2008 13:44] Sergey Petrunya
The second problem (already mentioned) is that range-checked-for-each-record scan does not take advantage of predicates that refer to the parent query.  This only causes slowdown, and thus will be addressed in a separate bug entry.
[20 Dec 2008 16:29] Sergey Petrunya
The second problem filed as 

BUG#41659 "Range checked for each record" is not used for conditions with outer query refs
[6 Jan 2009 13:57] Bugs System
Pushed into 5.0.76 (revid:joro@sun.com-20090105160414-8q9j4bi1klkfwiup) (version source revid:azundris@mysql.com-20081230114734-nmsc37ak330zlygn) (merge vers: 5.0.76) (pib:6)
[9 Jan 2009 1:16] Paul Dubois
Noted in 5.0.76 changelog.

Some queries that used a "range checked for each record" scan could
return incorrect results. 

Setting report to NDI pending push into 5.1.x/6.0.x.
[15 Jan 2009 6:40] Bugs System
Pushed into 5.1.31 (revid:joro@sun.com-20090115053147-tx1oapthnzgvs1ro) (version source revid:azundris@mysql.com-20081230114838-cn52tu180wcrvh0h) (merge vers: 5.1.31) (pib:6)
[15 Jan 2009 16:35] Paul Dubois
Noted in 5.1.31 changelog.

Setting report to NDI pending push into 6.0.x.
[19 Jan 2009 11:29] Bugs System
Pushed into 5.1.31-ndb-6.2.17 (revid:tomas.ulin@sun.com-20090119095303-uwwvxiibtr38djii) (version source revid:tomas.ulin@sun.com-20090115073240-1wanl85vlvw2she1) (merge vers: 5.1.31-ndb-6.2.17) (pib:6)
[19 Jan 2009 13:07] Bugs System
Pushed into 5.1.31-ndb-6.3.21 (revid:tomas.ulin@sun.com-20090119104956-guxz190n2kh31fxl) (version source revid:tomas.ulin@sun.com-20090119104956-guxz190n2kh31fxl) (merge vers: 5.1.31-ndb-6.3.21) (pib:6)
[19 Jan 2009 15:11] Jon Stephens
Setting status back to NDI pending merge to 6.0 tree.
[19 Jan 2009 16:12] Bugs System
Pushed into 5.1.31-ndb-6.4.1 (revid:tomas.ulin@sun.com-20090119144033-4aylstx5czzz88i5) (version source revid:tomas.ulin@sun.com-20090119144033-4aylstx5czzz88i5) (merge vers: 5.1.31-ndb-6.4.1) (pib:6)
[20 Jan 2009 18:58] Bugs System
Pushed into 6.0.10-alpha (revid:joro@sun.com-20090119171328-2hemf2ndc1dxl0et) (version source revid:azundris@mysql.com-20081230114916-c290n83z25wkt6e4) (merge vers: 6.0.9-alpha) (pib:6)
[28 Jan 2009 22:00] Paul Dubois
Noted in 6.0.10 changelog.
[20 Jul 2009 18:44] James Day
This bug fix caused crash bug #44810, which was fixed in 5.0.54, 5.1.36 and 5.4.4.