Bug #42591 Valgrind warnings in ndb.ndb_index_ordered.test
Submitted: 4 Feb 2009 12:33 Modified: 13 Feb 2009 15:28
Reporter: Sergey Petrunya Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Cluster: Cluster (NDB) storage engine Severity:S3 (Non-critical)
Version:>= ndb-6.2 OS:Any
Assigned to: Jonas Oreland CPU Architecture:Any
Tags: pushbuild, test failure

[4 Feb 2009 12:33] Sergey Petrunya
Description:
ndb_index_ordered.test produces valgrind warnings in recent 6.0.

How to repeat:
I've been removing parts of ndb_index_ordered.test and got a minimal .test file that is sufficient to demonstrate the problem:

####### ndb_index_ordered.test start ###############
-- source include/have_ndb.inc
-- source include/not_embedded.inc

--disable_warnings
drop table if exists t1, test1, test2;
--enable_warnings

set autocommit=1;
show session variables like 'ndb_index_stat_%';

set ndb_index_stat_enable = off;
show session variables like 'ndb_index_stat_%';

create table t1 (a int, b int, c varchar(10) not null,
  primary key using hash (a), index(b,c)) engine=ndb;
insert into t1 values
  (1,10,'aaa'),(2,10,'bbb'),(3,10,'ccc'),
  (4,20,'aaa'),(5,20,'bbb'),(6,20,'ccc'),
  (7,30,'aaa'),(8,30,'bbb'),(9,30,'ccc');
select count(*) from t1 where b > 10;
drop table t1;
#### ndb_index_ordered.test ends #####

If one runs this, they get warnings like this:
==19146== Conditional jump or move depends on uninitialised value(s)
==19146==    at 0x89A663D: NdbSqlUtil::cmpVarchar(void const*, void const*, unsigned, void const*, unsigned, bool) (NdbSqlUtil.cpp:523)
==19146==    by 0x88C2F86: NdbIndexScanOperation::compare_ndbrecord(NdbReceiver const*, NdbReceiver const*) const (NdbScanOperation.cpp:3112)
==19146==    by 0x88C351D: NdbIndexScanOperation::ordered_insert_receiver(unsigned, NdbReceiver*) (NdbScanOperation.cpp:3207)
==19146==    by 0x88C3C00: NdbIndexScanOperation::next_result_ordered_ndbrecord(char const*&, bool, bool) (NdbScanOperation.cpp:3166)
==19146==    by 0x88C609F: NdbScanOperation::nextResultNdbRecord(char const*&, bool, bool) (NdbScanOperation.cpp:1417)
==19146==    by 0x88C69CB: NdbScanOperation::nextResult(char const**, bool, bool) (NdbScanOperation.cpp:1362)
==19146==    by 0x8592DD3: ha_ndbcluster::fetch_next(NdbScanOperation*) (ha_ndbcluster.cc:2360)
==19146==    by 0x8592FA6: ha_ndbcluster::next_result(unsigned char*) (ha_ndbcluster.cc:2419)
==19146==    by 0x8581AA4: ha_ndbcluster::ordered_index_scan(st_key_range const*, st_key_range const*, bool, bool, unsigned char*, part_id_range*) (ha_ndbcluster.cc:2655)
==19146==    by 0x8582B98: ha_ndbcluster::read_range_first_to_buf(st_key_range const*, st_key_range const*, bool, bool, unsigned char*) (ha_ndbcluster.cc:3844)
==19146==    by 0x8582C39: ha_ndbcluster::read_range_first(st_key_range const*, st_key_range const*, bool, bool) (ha_ndbcluster.cc:3854)
==19146==    by 0x8490E91: handler::multi_range_read_next(char**) (handler.cc:4326)
==19146==    by 0x85803F3: ha_ndbcluster::multi_range_read_next(char**) (ha_ndbcluster.cc:9849)
==19146==    by 0x847227C: QUICK_RANGE_SELECT::get_next() (opt_range.cc:8558)
==19146==    by 0x848A462: rr_quick(READ_RECORD*) (records.cc:322)
==19146==    by 0x83D097D: join_init_read_record(st_join_table*) (sql_select.cc:17011)
[4 Feb 2009 12:35] Sergey Petrunya
complete warnings log

Attachment: bug42591-valgrind-warnings.txt (text/plain), 10.78 KiB.

[4 Feb 2009 12:43] Sergey Petrunya
Some speculations about the cause of the bug
=============================

So we have

create table t1 (a int, b int, c varchar(10) not null,
  primary key using hash (a), index(b,c)) engine=ndb;

select count(*) from t1 where b > 10;

and  valgrind warnings in NdbSqlUtil::cmpVarchar() in a place where the SQL node merges results from data nodes.

I think the cause is as follows:

* the query only uses column b. Column a is not used (i.e. it's not in table->read_set). iirc NDB will find this out and retrieve column b only.
* on the other hand, the scan is ordered, so it tries to compare complete (a, b) index tuples.
* attempts to access the (b) part cause valgrind failures.

* the solution on NDB side is to fix ordered-merge code to compare only requested columns (they should form a prefix of the index)
* not everything is clear on the MySQL side- SQL layer is asking that NDB produces records in order while actually it's not required, we cause some extra cpu overhead this way.  That is a known limitation (can be expected to be lifted when somebody sorts out ORDER BY optimization).
[4 Feb 2009 12:50] Sergey Petrunya
Considering the above reasoning, seeking for somebody from cluster to take over.
[4 Feb 2009 13:02] Tomas Ulin
int
NdbSqlUtil::cmpVarchar(const void* info, const void* p1, unsigned n1, const void* p2, unsigned n2, bool full)
{
  const unsigned lb = 1;
  // collation does not work on prefix for some charsets
  assert(full && n1 >= lb && n2 >= lb);
  const uchar* v1 = (const uchar*)p1;
  const uchar* v2 = (const uchar*)p2;
  unsigned m1 = *v1;
  unsigned m2 = *v2;
  if (m1 <= n1 - lb && m2 <= n2 - lb) {

^ the last line is the issue
[4 Feb 2009 14:16] Jonas Oreland
Fix variant 1, returns error in scanIndex (i.e requires changes in ha_ndbcluster.cc aswell)

Attachment: bug42591.patch.v1 (application/octet-stream, text), 1.39 KiB.

[4 Feb 2009 14:17] Jonas Oreland
Fix variant 2, enables prefix order by scans...although with a bit weird semantics

Attachment: bug42591.patch.v2 (application/octet-stream, text), 2.16 KiB.

[4 Feb 2009 14:22] Jonas Oreland
Comments:
1) Code was not "originally" supposed to support order by
   wo/ requesting all columns in key.

2) Check for this was broken
   v1-patch fixes this check, so that an error is thrown
   so this patch requires changes to ha_ndbcluster to
   also fetch other key columns if order-by is requested.

3) v2-patch instead adds support for this, by API is weird.
   it checks if key columns are fetched (in key-order)
   and only compares fetched columns.

   this could be 0, in which case the order-by switch is really weird
   maybe we should add an error for that case...
   or a new scan-flag saying that we want only to compare key-prefix
   in order by.

---

Bug is also present in 6.2
Don't know if sql-layer makes such request there though...
(can be tested with patch 1)

/Jonas
[5 Feb 2009 12:38] Jonas Oreland
Fix variant 1, including handler changes

Attachment: bug42591.patch.v1.1 (application/unknown, text), 3.61 KiB.

[5 Feb 2009 12:38] Jonas Oreland
Note: patch is made against 6.0-ndb,
but should be applied to ndb-6.2
[5 Feb 2009 12:57] Jonas Oreland
Post (tomas) review fixes

Attachment: bug42591.patch.v1.2 (application/octet-stream, text), 3.59 KiB.

[9 Feb 2009 8:45] Tomas Ulin
new error code

Attachment: bug42591.patch.v1.3 (application/octet-stream, text), 4.42 KiB.

[9 Feb 2009 11:17] Frazer Clement
Fix looks ok functionally, though might be better to include the keys mask in the NdbRecord structure so you don't have to keep regenerating it (Could be useful elsewhere too).
i.e. define the keys bitmap at createRecord() time.
[9 Feb 2009 11:35] Jonas Oreland
frazer,
fully agree with improvement proposal.
but this is something I thought you (or someone in your group) could do.
[9 Feb 2009 13:28] 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/65607

2812 Tomas Ulin	2009-02-09
      bug#42591 : Valgrind warnings in ndb_index_ordered.test
[9 Feb 2009 13:31] Bugs System
Pushed into 5.1.31-ndb-6.2.17 (revid:tomas.ulin@sun.com-20090209132830-w61mvtd1a2msoqyn) (version source revid:tomas.ulin@sun.com-20090209132830-w61mvtd1a2msoqyn) (merge vers: 5.1.31-ndb-6.2.17) (pib:6)
[9 Feb 2009 19:21] 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/65649

2813 Jonas Oreland	2009-02-09
      ndb - bug#42591 - bug in bugfix
[9 Feb 2009 19:26] Bugs System
Pushed into 5.1.31-ndb-6.2.17 (revid:jonas@mysql.com-20090209192142-8eqy87knjumx0w2v) (version source revid:jonas@mysql.com-20090209192142-8eqy87knjumx0w2v) (merge vers: 5.1.31-ndb-6.2.17) (pib:6)
[9 Feb 2009 19:59] 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/65655

2814 Jonas Oreland	2009-02-09
      ndb - bug#42591 - yet another typo
[9 Feb 2009 19:59] Bugs System
Pushed into 5.1.31-ndb-6.2.17 (revid:jonas@mysql.com-20090209195921-1p1awm7gst0k69ib) (version source revid:jonas@mysql.com-20090209195921-1p1awm7gst0k69ib) (merge vers: 5.1.31-ndb-6.2.17) (pib:6)
[10 Feb 2009 6:56] Bugs System
Pushed into 5.1.31-ndb-6.3.23 (revid:jonas@mysql.com-20090210065305-s4i2e8obj0rhwfaq) (version source revid:jonas@mysql.com-20090210065305-s4i2e8obj0rhwfaq) (merge vers: 5.1.31-ndb-6.3.23) (pib:6)
[10 Feb 2009 8:05] 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/65690

2815 Jonas Oreland	2009-02-10
      ndb - bug#42591 - another case...puh
[10 Feb 2009 8:05] Bugs System
Pushed into 5.1.31-ndb-6.2.17 (revid:jonas@mysql.com-20090210080516-o1688qh29psz8o04) (version source revid:jonas@mysql.com-20090210080516-o1688qh29psz8o04) (merge vers: 5.1.31-ndb-6.2.17) (pib:6)
[10 Feb 2009 9:08] Bugs System
Pushed into 5.1.31-ndb-6.3.23 (revid:jonas@mysql.com-20090210090659-3lnm0svcbw24he7m) (version source revid:jonas@mysql.com-20090210090659-3lnm0svcbw24he7m) (merge vers: 5.1.31-ndb-6.3.23) (pib:6)
[10 Feb 2009 16:23] 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/65774

2814 Martin Skold	2009-02-10 [merge]
      Merge
[10 Feb 2009 20:13] Bugs System
Pushed into 6.0.10-alpha (revid:alik@sun.com-20090210194937-s7xshv5l3m1v7wi9) (version source revid:tomas.ulin@sun.com-20090210082437-gq3x2ls9zggdxdz5) (merge vers: 6.0.10-alpha) (pib:6)
[11 Feb 2009 12:34] Bugs System
Pushed into 5.1.31-ndb-6.4.3 (revid:jonas@mysql.com-20090211123309-bda03zblogm4r2eu) (version source revid:jonas@mysql.com-20090211123309-bda03zblogm4r2eu) (merge vers: 5.1.31-ndb-6.4.3) (pib:6)
[11 Feb 2009 15:14] Jonas Oreland
Documentation for < mysql-6.0:
If using ndbapi ordered index scan, and not putting all key columns
in read-mask, ndbapi would fail to detect this invalid use of ndbapi
and use uninitialized memory.

Documentation for >= 6.0
mysql could use uninitialized memory for some queries involving order by.
[11 Feb 2009 15:17] 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/65920

3252 Martin Skold	2009-02-11 [merge]
      Merge
[11 Feb 2009 19:10] Jon Stephens
Bugfix documented in the NDB-6.2.17, 6.3.23, and 6.4.3 changelogs as follows:

        Scans on NDBCLUSTER tables that used prefixes of non-primary-key 
        columns were not always handled correctly (they sometimes used
        unitialized memory). An example of such a query is:
        
        SELECT COUNT(*) FROM t1 WHERE b > 10;
        
        where table t1 is defined as shown here:
        
        CREATE TABLE t1 (
            a INT, 
            b INT, 
            c VARCHAR(10) NOT NULL,
            PRIMARY KEY USING HASH (a), 
            KEY(b,c)
        ) ENGINE=NDBCLUSTER;
[13 Feb 2009 15:28] Jon Stephens
Discussed with Jonas, updated changelog entry to read:

        When using an ordered index scan without putting all key columns
        in the read mask, this invalid use of the NDB API went
        undetected, which resulted in the use of uninitialized memory.