Duckdb: A predicate NOT(NULL OR TRUE) unexpectedly evaluates to TRUE

[mrigger]

Consider the following statements:

CREATE TABLE t0(c0 INT);
INSERT INTO t0(c0) VALUES (0);
SELECT * FROM t0 WHERE NOT(NULL OR TRUE); -- expected: {}, actual: {0}

Unexpectedly, the SELECT fetches a row in the table. The predicate NOT(NULL OR TRUE) should evaluate to false, since NULL OR TRUE evaluates to true:

SELECT NULL OR TRUE; -- true

A simpler test case that demonstrates the underlying issue is the following:

SELECT NOT(NULL OR TRUE); -- expected: false, actual: true

I found this bug based on commit bc9f086b9fcffb058763a6d1723da01127cd9100.

[Mytherin]

Thanks for all the bug reports! Please keep them coming :) I will have a look at solving them when I am done with my current task.

[hannesmuehleisen]

Could also not reproduce this one in the current version, but added a test.

[mrigger]

Okay, that's strange. I can still reproduce it on the latest version:

duckdb/build/release$ ./duckdb_cli 
SQLite version DuckDB f11d74a0
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> CREATE TABLE t0(c0 INT);
sqlite> INSERT INTO t0(c0) VALUES (0);
sqlite> SELECT * FROM t0 WHERE NOT(NULL OR TRUE); -- expected: {}, actual: {0}
0
sqlite> SELECT NULL OR TRUE; -- true
true
sqlite> SELECT NOT(NULL OR TRUE); -- expected: false, actual: true
true

[Mytherin]

I got this to reproduce on an optimized build with GCC, but not on a debug build. This is likely related to an uninitialized variable or uninitialized memory. I will investigate more.

[mrigger]

I just built the debug build and cannot reproduce the issue there:

duckdb/build/debug$ ./duckdb_cli
SQLite version DuckDB f11d74a0
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> CREATE TABLE t0(c0 INT);
sqlite> INSERT INTO t0(c0) VALUES (0);
sqlite> SELECT * FROM t0 WHERE NOT(NULL OR TRUE); -- expected: {}, actual: {0}
sqlite> SELECT NULL OR TRUE; -- true
true
sqlite> SELECT NOT(NULL OR TRUE); -- expected: false, actual: true
false

It really seems likely that some undefined or unspecified behavior is biting us, as you suggested.

[Mytherin]

Alright, this was a very strange bug. I am still not sure what the exact problem was and I'm thinking this could be a compiler bug, but I think I have fixed it now by rewriting the manner in which AND/OR are computed. Previously, this was computed as follows:

void OR(bool left, bool right, bool left_null, bool right_null,
               bool &result_data, bool &is_null) {
  result_data = left || right;
  is_null = (left_null && (right_null || !right)) || (right_null && !left);
}

In the test case, the input to this is (left=[undefined], right=true, left_null=true, right_null=false), hence I would expect the results to be as follows:

result_data = [undefined] || true; // true
is_null = (true && (false || !true)) || (false && ![undefined]);
// simplify:
//  (true && (false || false)) || (false && !undefined)
// (true && false) || (false && undefined)
// false || false
// false

So I would expect the result here to be correct (TRUE and not null). And indeed printing the intermediate created by the OR gave the correct result. However, for some reason in the next step in the NOT the generated value would result in weird behavior. Essentially, in the NOT we would have the following operation:

result_data = !input_data;

Now input_data would be true, but result_data (somehow) would also contain true after the negation. Now my suspicion was that the OR with the undefined data somehow created a weird bit pattern that was still "truthy", but did not give a correct result when negated. So I printed the actual bytes in the boolean and this is what I found

sqlite> SELECT NOT(NULL or TRUE);
AS INT8: 1
AS BOOL: TRUE
false
sqlite> SELECT NOT(NULL or TRUE);
AS INT8: -15
AS BOOL: TRUE
true
sqlite> SELECT NOT(NULL or TRUE);
AS INT8: -31
AS BOOL: TRUE
true

Now you can see the value is always truthy (i.e. as a boolean it represents TRUE), but the actual bytes underneath are different. However, NEGATING the value gives the wrong result!

AS INT8: 1
AS BOOL: TRUE
NEGATED AS INT8: 0
NEGATED AS BOOL: FALSE

AS INT8: -15
AS BOOL: TRUE
NEGATED AS INT8: -16
NEGATED AS BOOL: TRUE

AS INT8: -31
AS BOOL: TRUE
NEGATED AS INT8: -32
NEGATED AS BOOL: TRUE

This feels like a compiler bug, but unfortunately I could not make a small reproducible example that exhibits the same behavior.

To fix it, I reworked the OR/AND operators so that if the left or right side is NULL, the actual boolean value (the bytes within it) are not touched. This seems to have fixed the bug for me at least. Could you have a look and see if it works now for you as well?

[mrigger]

Thanks a lot for the explanation and the PR! The test case seems to execute as expected with the proposed fix:

duckdb/build/release$ ./duckdb_cli 
SQLite version DuckDB ef2286fa
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> CREATE TABLE t0(c0 INT);
sqlite> INSERT INTO t0(c0) VALUES (0);
sqlite> SELECT * FROM t0 WHERE NOT(NULL OR TRUE); -- expected: {}, actual: {0}
sqlite> SELECT NULL OR TRUE; -- true
true
sqlite> SELECT NOT(NULL OR TRUE); -- expected: false, actual: true
false

[Mytherin]

Great :) And thanks again for finding this bug!

[mrigger]

Since I'm keeping track of fixes that are associated with the bug reports: I assume this bug was fixed by commits b838c589e26c47c342dd29b890438f5fb9dce4d4 and ef2286faef94a75d1ed02de0e86b804610da281e? Or only ef2286faef94a75d1ed02de0e86b804610da281e?

[hannesmuehleisen]

I think both commits.