MySQL Bugs: #40974: Incorrect query results when using clause evaluated using range check

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	CPU Architecture:	Any

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.

Steps to reproduce this bug

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

Small edit for clarity

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

correct grammatical error in synopsis

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.

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)

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.

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.

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.

The above fix fixes the wrong query results problem.

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.

The second problem filed as 

BUG#41659 "Range checked for each record" is not used for conditions with outer query refs

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)

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.

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)

Noted in 5.1.31 changelog.

Setting report to NDI pending push into 6.0.x.

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)

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)

Setting status back to NDI pending merge to 6.0 tree.

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)

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)

Noted in 6.0.10 changelog.

This bug fix caused crash bug #44810, which was fixed in 5.0.54, 5.1.36 and 5.4.4.