MySQL Bugs: #58280: MySQL Cluster may return duplicated rows when WHERE-predicate contains 'OR'

Bug #58280	MySQL Cluster may return duplicated rows when WHERE-predicate contains 'OR'
Submitted:	18 Nov 2010 9:48	Modified:	26 Nov 2010 1:38
Reporter:	Ole John Aske	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Cluster: Cluster (NDB) storage engine	Severity:	S2 (Serious)
Version:	5.1.51-ndb-7.1.9	OS:	Any
Assigned to:	Jonas Oreland	CPU Architecture:	Any

Description:
When the where clause contains an 'OR' of multiple predicate terms, the optimizer may choose to use the 'sort_union' access method to retrieve qualifying rows. This may cause duplicates in the result set.

Further analysis:
'Sort_union' is an access method which combines usage of several indexes by reading the primary key for the qualifying rows from each index. These PKs are then temporarily stored into a 'Unique sieve' which is intended to remove any duplicated PK's.

In the next stage, (unique) PKs are read from the sieve and the rows are retrieved based on the PK values.

Using a debugger I observed that ha_ndbcluster::position() is used to retrieve the PK values from the index. If the value is a varchar type, it is retrieved based on its *max length* without any padding or normalization of the chars past its actual length.

Later the retrieved PK values are stored into TREE using tree_insert() which will use the (virtual) method handler::cmp_ref() to do the actual PK compare.

As ha_ndbcluster does not implement its own ::cmp_ref() we will end up in handler::cmp_ref() which does a plain *memcmp()* of entire PK - including any varchar garbage past its actual length! 

How to repeat:
create table t(vc varchar(16), i int
  , PRIMARY KEY(vc) USING HASH
  , KEY i1(i)
  , KEY i2(vc)
 )  ENGINE=ndbcluster;

insert into t values
  ('1',1), 
  ('2',2),
  ('3',3),
  ('4',1), 
  ('5',2),
  ('6',3),
  ('7',1), 
  ('8',2),
  ('9',3),
  ('10',1), 
  ('11',2),
  ('12',3),
  ('13',1), 
  ('14',2),
  ('15',3),
  ('16',1), 
  ('17',2),
  ('x',3),
  ('y',1), 
  ('z',2),
  ('1000',3),
  ('2000',3),
  ('10000',3)
;

analyze table t;
explain
select * from t
  where i>=1 or vc > '0';

NOTE: Make sure that your 'EXPLAIN' contains 'Using sort_union' as below
+----+-------------+-------+-------------+---------------+-------+---------+------+------+------------------------------------------------------------+
| id | select_type | table | type        | possible_keys | key   | key_len | ref  | rows | Extra                      |
+----+-------------+-------+-------------+---------------+-------+---------+------+------+------------------------------------------------------------+
|  1 | SIMPLE      | t     | index_merge | PRIMARY,i1,i2 | i1,i2 | 5,18    | NULL |   20 | Using sort_union(i1,i2); Using where with pushed condition |
+----+-------------+-------+-------------+---------------+-------+---------+------+------+------------------------------------------------------------+
1 row in set (0.01 sec)

-- The select will then (more or less randomly) return more than the 23 rows
-- contained in table 't'. The extra rows are duplicates of each other.

select * from t
  where i>=1 or vc > '0';
+-------+------+
| vc    | i    |
+-------+------+
| 1     |    1 |
| 2     |    2 |
| 3     |    3 |
| 3     |    3 |
| 4     |    1 |
| 4     |    1 |
| 5     |    2 |
| 5     |    2 |
| 6     |    3 |
| 6     |    3 |
| 7     |    1 |
| 7     |    1 |
| 8     |    2 |
| 8     |    2 |
| 9     |    3 |
| 9     |    3 |
| x     |    3 |
| y     |    1 |
| y     |    1 |
| z     |    2 |
| z     |    2 |
| 10    |    1 |
| 10    |    1 |
| 11    |    2 |
| 12    |    3 |
| 13    |    1 |
| 14    |    2 |
| 15    |    3 |
| 16    |    1 |
| 16    |    1 |
| 17    |    2 |
| 17    |    2 |
| 1000  |    3 |
| 1000  |    3 |
| 2000  |    3 |
| 10000 |    3 |
+-------+------+
36 rows in set (0.00 sec)

Suggested fix:
Either normalize/pad the varchar retrieved with ::position(), or implement ha:ndbcluster::cmp:ref() which might do a propper varchar compare ignoring the garbage past the actuall length.

NOTE: Both Innodb & partition implements ::cmp_ref().

Pushed into mysql-5.1-telco-6.3 5.1.51-ndb-6.3.40 (revid:jonas@mysql.com-20101124163758-ylwcnqce1piv1rut) (version source revid:jonas@mysql.com-20101124163758-ylwcnqce1piv1rut) (merge vers: 5.1.51-ndb-6.3.40) (pib:23)

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/124898

3347 Jonas Oreland	2010-11-24
      ndb - bug#58280 - implement ::cmp_ref which among other things is needed for "sort_union"

Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.21 (revid:jonas@mysql.com-20101124174527-2n60gu2e0wx7an60) (version source revid:jonas@mysql.com-20101124174527-2n60gu2e0wx7an60) (merge vers: 5.1.51-ndb-7.0.21) (pib:23)

pushed to 6.3.40, 7.0.21 and 7.1.10

Documented bugfix in the NDB-6.3.40, 7.0.21, and 7.1.10 changelogs as follows:

        A query having multiple predicates joined by OR in the WHERE
        clause and which used the sort_union access method (as shown
        using EXPLAIN) could return duplicate rows.

Closed.