[CALCITE-4446] Implement three-valued logic for SEARCH operator

• Type: Bug
• Status: Closed
• Priority: Blocker
• Resolution: Fixed
• Fix Version/s: 1.27.0
• Labels: pull-request-available
• Assignee: Unassigned
• Reporter: Julian Hyde
• Created: 23/Dec/20 21:27
• Updated: 03/Jun/21 22:32
• Resolved: 03/Mar/21 01:39

Description

Implement three-valued logic for SEARCH operator.

Consider the expression x IN (10, 20), which we might represent as SEARCH(x, Sarg(10, 20)). Suppose we invoke this with a value of NULL for x. Do we want it to return UNKNOWN, FALSE or TRUE? The answer is: all of the above.

Here are the 3 variants:

• Sarg(10, 20; NULL AS TRUE) returns TRUE if x is NULL, and is equivalent to SQL x IS NULL OR x IN (10, 20)
• Sarg(10, 20) returns UNKNOWN if x is NULL, and is equivalent to SQL x IN (10, 20)
• Sarg(10, 20; NULL AS FALSE) returns FALSE if x is NULL, and is equivalent to SQL x IS NOT NULL AND (x IN (10, 20))

Currently class Sarg has a field boolean containsNull which deals with the first two cases. Changing boolean containsNull to RexUnknownAs nullAs (which has 3 values) will allow us to represent the third. The new representation is symmetrical under negation, which de Morgan's law suggests is a good thing.

We also introduce internal constant Sarg values to deal with the 6 combinations of empty and full ranges (3 truth values multiplied by {all, none}):

• FALSE returns FALSE for all null and not-null values;
• IS_NOT_NULL returns TRUE for all not-null values, FALSE for null;
• IS_NULL returns FALSE for all not-null values, TRUE for null;
• TRUE returns TRUE for all null and not-null values;
• NOT_EQUAL returns FALSE for all not-null values, UNKNOWN for null;
• EQUAL returns TRUE for all not-null values, UNKNOWN for null.

Issue Links

• is duplicated by: CALCITE-4405 SEARCH operator (with Sarg literal) handles UNKNOWN incorrectly
• is duplicated by: CALCITE-4507 'a = 0 or a is null' should not be rewrite to a sarg 'a in (0, null)'
• is duplicated by: CALCITE-4487 Add fuzzy tests for SEARCH operator
• relates to: CALCITE-4508 Related to FLINK-21162,SQL optimization in OR syntax
• relates to: CALCITE-4405 SEARCH operator (with Sarg literal) handles UNKNOWN incorrectly
• links to: GitHub Pull Request #2357