(sequences of) mkey.bulk_rotate_xor_hash() can generate NIL from non-NIL making multi-col joins return wrong results

[monetdb-team]

Date: 2018-08-09 16:50:43 +0200
From: @drstmane
To: SQL devs <>
Version: 11.29.7 (Mar2018-SP1)

Last updated: 2018-08-31 13:23:13 +0200

Comment 26595

Date: 2018-08-09 16:50:43 +0200
From: @drstmane

mkey.bulk_rotate_xor_hash(),
respectively MKEYrotate() or GDK_ROTATE() in monetdb5/modules/mal/mkey.c,
does/do not avoid generating/returning NIL (i.e., a 64-bit integer value with only the highest/left-most/most-significant bit set).

Consequently, there are (valid, i.e., non-NIL/NULL) value constellations for which, e.g., a multi-column join fails, as (a sequence of) mkey.bulk_rotate_xor_hash() returns a NIL to MAL, which the subsequent algebra.join() does not match, resulting in a false-negative, and thus a wrong join result.

For examples see the test for this bug report.

(Indeed, the code in monetdb5/modules/mal/mkey.c says
"
/* TODO: nil handling. however; we do not want to lose time in bulk_rotate_xor_hash with that */
"
...)

Comment 26596

Date: 2018-08-09 16:57:48 +0200
From: MonetDB Mercurial Repository <>

Changeset 7eb1f93159c8 made by Stefan Manegold Stefan.Manegold@cwi.nl in the MonetDB repo, refers to this bug.

For complete details, see https//devmonetdborg/hg/MonetDB?cmd=changeset;node=7eb1f93159c8

Changeset description:

added test for bug #6638
"(sequences of) mkey.bulk_rotate_xor_hash() can generate NIL from non-NIL making multi-col joins return wrong results"

Comment 26597

Date: 2018-08-09 17:32:02 +0200
From: @drstmane

While preventing mkey.bulk_rotate_xor_hash() from returning NIL would be fix the problem
(at the expense of either checking whether the return value is NIL and then modifying it or, say, always 0-ing out the highest bit, i.e., effectively creating 63-bit instead of 64-bit hash values),
an alternative options would be to make the subsequent join match also on NILs by calling algebra.join() with argument nil_matches:bit==true (rather than false) --- I'm not sure, though, whether the result of mkey.bulk_rotate_xor_hash() is also consumed by other operations than algebra.join() (e.g, algebra.select()?) ...

Comment 26598

Date: 2018-08-09 18:00:21 +0200
From: MonetDB Mercurial Repository <>

Changeset c995f2b40b4c made by Stefan Manegold Stefan.Manegold@cwi.nl in the MonetDB repo, refers to this bug.

For complete details, see https//devmonetdborg/hg/MonetDB?cmd=changeset;node=c995f2b40b4c

Changeset description:

extended test for bug #6638:
multi-column constraint (unique, primary key) checking is also affected;
here, the result of mkey.bulk_rotate_xor_hash() is consumed by algebra.thetaselect(),
hence, also this one would need to be made to match on NILs
(in fact, the C code has this feature; IMHO not triggerable by simple
MAL command argument as with algebra.join() ...)

Comment 26601

Date: 2018-08-14 16:22:09 +0200
From: MonetDB Mercurial Repository <>

Changeset 2804f1ca791d made by Sjoerd Mullender sjoerd@acm.org in the MonetDB repo, refers to this bug.

For complete details, see https//devmonetdborg/hg/MonetDB?cmd=changeset;node=2804f1ca791d

Changeset description:

In certain cases, have join and select compare NULL as ordinary value.
This fixes bug #6638.