MySQL Bugs: #42591: Valgrind warnings in ndb.ndb_index

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

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)

complete warnings log

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

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

Considering the above reasoning, seeking for somebody from cluster to take over.

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

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.

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.

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

Fix variant 1, including handler changes

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

Note: patch is made against 6.0-ndb,
but should be applied to ndb-6.2

Post (tomas) review fixes

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

new error code

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

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.

frazer,
fully agree with improvement proposal.
but this is something I thought you (or someone in your group) could do.

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

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)

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

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)

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

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)

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)

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

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)

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)

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

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)

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)

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.

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

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;

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.