Bug #59517 Incorrect detection of single row access in ha_ndbcluster::records_in_range()
Submitted: 14 Jan 2011 21:36 Modified: 31 Jan 2011 9:23
Reporter: Ole John Aske Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Cluster: Cluster (NDB) storage engine Severity:S3 (Non-critical)
Version: OS:Any
Assigned to: Ole John Aske

[14 Jan 2011 21:36] Ole John Aske
Description:
ha_ndbcluster::records_in_range() has logic for detecting when the upper / lower bounds in the range is specified such that the 'range' colapses to a single record lookup.

This logic is incorrect such that even (open) ranges may be detected as PK lookups.

How to repeat:
CREATE TABLE t10(
  K INT NOT NULL AUTO_INCREMENT,
  I INT, J INT,
  PRIMARY KEY(K),
  KEY(I,J),
  UNIQUE KEY(J,K)
) ENGINE=ndbcluster;

INSERT INTO t10(I,J) VALUES (1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(0,0);

CREATE TABLE t100 LIKE t10;
INSERT INTO t100(I,J)
  SELECT X.J, X.J+(10*Y.J) FROM t10 AS X,t10 AS Y;

CREATE TABLE t10000 LIKE t10;
INSERT INTO t10000(I,J)
  SELECT X.J, X.J+(100*Y.J) FROM t100 AS X,t100 AS Y;

ANALYZE TABLE t10,t100,t10000;

# Expect a single row (or const) when PK is excact specified
EXPLAIN 
SELECT * FROM t10000 WHERE k = 42;

# All queries below should *not* return a single row
EXPLAIN 
SELECT * FROM t10000 WHERE k >= 42 and k < 10000;
EXPLAIN 
SELECT * FROM t10000 WHERE k BETWEEN 42 AND 10000;
EXPLAIN 
SELECT * FROM t10000 WHERE k < 42;
EXPLAIN 
SELECT * FROM t10000 WHERE k > 42;

Suggested fix:
@@ -10559,8 +10611,10 @@ ha_ndbcluster::records_in_range(uint inx
   // Read from hash index with full key
   // This is a "const" table which returns only one record!      
   if ((idx_type != ORDERED_INDEX) &&
-      ((min_key && min_key->length == key_length) || 
-       (max_key && max_key->length == key_length)))
+      ((min_key && min_key->length == key_length) &&
+       (max_key && max_key->length == key_length) &&
+       (min_key->key==max_key->key ||
+        memcmp(min_key->key, max_key->key, key_length)==0)))
     DBUG_RETURN(1);
   
   if ((idx_type == PRIMARY_KEY_ORDERED_INDEX ||
[17 Jan 2011 14:47] 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/128985

4125 Ole John Aske	2011-01-17
      Fix for bug#59517: 'Incorrect detection of single row access in ha_ndbcluster::records_in_range()'
      
      The logic for detecting a range being an excact match on a single row has been corrected.
      
      Added a new MTR test 'ndb_statistics' intended for testing statistics returned 
      from ha_ndbcluster
     @ mysql-test/suite/ndb/r/ndb_index_unique.result
        The condition 'a < 9' was previously incorrectly detected as an excact match on pk(a) return 1 row.
     @ mysql-test/suite/ndb/r/ndb_read_multi_range.result
        The condition 't2.pk != 6' was previously detected as two exact ranges
        which produced the estimate '2 rows'
     @ mysql-test/suite/ndb/t/ndb_statistics.test
        Added a new MTR test which is intended for testing of 
        statistics returned from ha_ndbcluster.
[17 Jan 2011 15:10] Jonas Oreland
Did really any of those really simple ones in testcase fail prior to patch ?
[17 Jan 2011 20:45] Ole John Aske
Re: 'Did really any of those really simple ones in testcase fail prior to patch ?'

Sure, all these testcases returned 'row=1' wo/ patch.

mysql> EXPLAIN 
    -> SELECT * FROM t10000 WHERE k >= 42 and k < 10000;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra                             |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
|  1 | SIMPLE      | t10000 | range | PRIMARY       | PRIMARY | 4       | NULL |    1 | Using where with pushed condition |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN 
    -> SELECT * FROM t10000 WHERE k BETWEEN 42 AND 10000;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra                             |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
|  1 | SIMPLE      | t10000 | range | PRIMARY       | PRIMARY | 4       | NULL |    1 | Using where with pushed condition |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN 
    -> SELECT * FROM t10000 WHERE k < 42;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra                             |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
|  1 | SIMPLE      | t10000 | range | PRIMARY       | PRIMARY | 4       | NULL |    1 | Using where with pushed condition |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN 
    -> SELECT * FROM t10000 WHERE k > 42;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra                             |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
|  1 | SIMPLE      | t10000 | range | PRIMARY       | PRIMARY | 4       | NULL |    1 | Using where with pushed condition |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN  SELECT * FROM t10000 WHERE k > 42;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra                             |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
|  1 | SIMPLE      | t10000 | range | PRIMARY       | PRIMARY | 4       | NULL |    1 | Using where with pushed condition |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------------------+
1 row in set (0.00 sec)

mysql>
[18 Jan 2011 7:49] 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/129034

4131 Ole John Aske	2011-01-18
      Fix for bug#59517: 'Incorrect detection of single row access in ha_ndbcluster::records_in_range()'
      
      The logic for detecting a range being an excact match on a single row has been corrected.
      
      Added a new MTR test 'ndb_statistics' intended for testing statistics returned 
      from ha_ndbcluster
     @ mysql-test/suite/ndb/r/ndb_index_unique.result
        The condition 'a < 9' was previously incorrectly detected as an excact match on pk(a) return 1 row.
     @ mysql-test/suite/ndb/r/ndb_read_multi_range.result
        The condition 't2.pk != 6' was previously detected as two exact ranges
        which produced the estimate '2 rows'
     @ mysql-test/suite/ndb/t/ndb_statistics.test
        Added a new MTR test which is intended for testing of 
        statistics returned from ha_ndbcluster.
[18 Jan 2011 7:50] Bugs System
Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.22 (revid:ole.john.aske@oracle.com-20110118074914-s3dcmrs3ev63b1p0) (version source revid:ole.john.aske@oracle.com-20110118074914-s3dcmrs3ev63b1p0) (merge vers: 5.1.51-ndb-7.0.22) (pib:24)
[18 Jan 2011 8:15] Ole John Aske
Fix pushed to mysql-5.1-telco-7.0.
[25 Jan 2011 8:22] Jonas Oreland
pushed to 7.0.22 and 7.1.11
[26 Jan 2011 11:02] Jon Stephens
Documented fix in the NDB-7.0.22 and 7.1.11 changelogs, as follows:

        The logic used in determining whether to collapse a range to a
        simple equality was faulty. In certain cases, this could cause a
        primary key lookup to be used, thus returning only a single row,
        even though multiple records matched the range.

Closed.
[26 Jan 2011 11:41] Ole John Aske
Re 'In certain cases, this could cause a
        primary key lookup to be used, thus returning only a single row,
        even though multiple records matched the range'

This is incorrect: It is the statistic which *assumes* that a single
row will be returned - Thus possibly creating a less optimal query plan
based on incorrect 'guesses'.

However, the actual result will be correct

-> Setting back to documenting
[28 Jan 2011 19:40] Ole John Aske
See previous comment
[31 Jan 2011 9:23] Jon Stephens
Discussed with OleJohn on IRC, changelog entry updated to read as shown here:

        The logic used in determining whether to collapse a range to a
        simple equality was faulty. In certain cases, this could cause
        NDB to treat a range as if it were a primary key lookup when
        determining the query plan to be used. Although this did not
        effect the actual result returned by the query, it could in such
        cases result in inefficient execution of queries due to the use
        of an inappropriate query plan.

Closed.
[14 Apr 2011 14:57] Ahmed Medhat
This page http://dev.mysql.com/doc/refman/5.1/en/mysql-cluster-news-7-1.html says that versions 7.1.11 (including the bug fix) and 7.1.12 has been released, where to find them ? they doesn't seem to be available on the downloads page !?