MySQL Bugs: #59517: Incorrect detection of single row access in ha_ndbcluster::records_in

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

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

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.

Did really any of those really simple ones in testcase fail prior to patch ?

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>

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.

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)

Fix pushed to mysql-5.1-telco-7.0.

pushed to 7.0.22 and 7.1.11

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.

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

See previous comment

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.

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 !?