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 12:42	Modified:	28 Jan 2009 23:00
Reporter:	David Heath
Status:	Closed
Category:	Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0/5.1/6.0	OS:	Any
Assigned to:	Bugs System	Target Version:	5.0+
Triage:	Triaged: D2 (Serious) / R2 (Low) / E2 (Low)

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.