SQL plan compilation and truth tables

Question

If I have NOT ( 1 <> 1 AND NULL <> 1 )

I can see SQL turning this into in the execution plan XML: ( 1 = 1 OR NULL = 1)

If you would literally evaluate the former expression, the True AND Null would be Null and would eliminate the row. However, the compiled expression can return a row due to the OR.

Can I assume that this type of compilation is guaranteed to always happen? SQL Server would never attempt to bring the convoluted logic forward into the compiled plan? Is there some documentation on this?

This article was pretty helpful, but I am just missing a piece of the puzzle: https://www.simple-talk.com/sql/learn-sql-server/sql-and-the-snare-of-three-valued-logic/

Here is a SQL example

SELECT 1
FROM T T
    LEFT JOIN T2 T2 --t2 has zero rows
        ON T.id = t2.t_id
WHERE NOT ( T.id <> 99 AND T2.id <> 99 )

From my experience with SQL, I know that under normal circumstances (without short circuit evaluation) T2.id <> 99 effectively turns the left join into an inner join. That was the behavior I was initially expecting. I was surprised when this filter actually worked.

Answer 1

TL;DR The "compiled result" is not a helpful concept. What matters is the "specified result"--specified by the language definition. A DBMS must make the statement act the way you wrote it.

The truth [sic] table for AND in your link is wrong. AND with False is always False and OR with True is always True in SQL.

---

Comparisons in SQL return True, False or Unknown. Unknown can arise from a comparison to NULL or a 3VL logic connective (AND/OR/NOT etc) on Unknown. "NULL" is not a literal. True, False & Unknown are values with (assorted) literals in the SQL standard, but not in most DBMSs. (And Unknown can be returned as NULL.) IS is not a comparison; IS NULL and IS NOT NULL are unary 3Vl logic connectives and so are the similar ones named with TRUE, FALSE & UNKNOWN. They always return True or False.

True AND Null would be Null and would eliminate the row. However, the compiled expression can return a row due to the OR.

No. The truth [sic] table for AND in your link is wrong. AND with False is always False and OR with True is always True in SQL. So your AND is always False from the NOT of False from the AND of False from 1 <> 1 and your OR is always True from 1 = 1. No matter what the other comparisons return (True, False or Unknown). If you work through these two expressions using the (correct) SQL truth tables), they both always give the same result, True.

One has to be very careful about rewriting conditions in SQL. One can interchange NOT (E1 *comparison* E2) by E1 *NOT-comparison* E2 or NOT (E IS ?) and E IS NOT ?. One can safely rewrite an expression using standard logic identities/rules if no value ever IS NULL. One can also safely apply rewrite rules to

    (E1 *comparison* E2)
AND E1 IS NOT NULL AND E2 IS NOT NULL

Also beware that you must properly use an Unknown final result, which includes not matching for a WHERE but not failing for a constraint.

SELECT 1
FROM T T
    LEFT JOIN T2 T2 --t2 has zero rows
        ON T.id = t2.t_id
WHERE NOT ( T.id <> 99 AND T2.id <> 99 )

LEFT JOIN returns the rows of INNER JOIN plus unmatched rows of T extended by T2 columns NULL. (With T2 empty, the INNER JOIN is empty and all rows of T are unmatched.) All the extended rows have T2.id <> 99 Unknown since T2.id is NULL. For T.id = 99 the AND is False and the NOT is True; the WHERE returns all rows. For T1.id any other integer or NULL, the AND will be Unknown, the NOT will be Unknown; the WHERE returns no rows.

(There is no "short ciruit" evaluation of conditions in SQL. Every argument of a connective must be defined.)

Answer 2

If you would literally evaluate the former expression, the True AND Null would be Null and would eliminate the row.

No. You are evaluating the expression. NOT ( 1 <> 1 AND NULL <> 1 ) is NOT (FALSE AND UNKNOWN) is NOT FALSE is TRUE.

( 1 = 1 OR NULL = 1) is TRUE OR UNKNOWN is TRUE. They are both equivalent.

---

NOT ( 1 <> 1 AND NULL <> 1 ) can be rewritten as NOT ((NOT (1=1)) AND (NOT (NULL = 1))). In regular two value logic, by De Morgan's Laws that can be rewritten as NOT (NOT ((1 = 1) OR (NULL = 1))) and then (1=1) OR (NULL = 1). As it turns out De Morgan's Laws also hold in the three value logic of SQL. This can be demonstrated by creating exhaustive truth tables for the two laws.

The truth table showing that one of De Morgan's Laws, (NOT A) OR (NOT B) is equivalent to NOT (A AND B), holds in SQL's three value logic:

A  B | (NOT A)  OR  (NOT B) | equiv? | NOT (A  AND  B)
========================================================
T  T |   F  T   F     F  T  |   T    |  F   T   T   T
T  F |   F  T   T     T  F  |   T    |  T   T   F   F
T  U |   F  T   U     U  U  |   T    |  U   T   U   U
-------------------------------------------------------
F  T |   T  F   T     F  T  |   T    |  T   F   F   T
F  F |   T  F   T     T  F  |   T    |  T   F   F   F
F  U |   T  F   T     U  U  |   T    |  T   F   F   U
-------------------------------------------------------
U  T |   U  U   U     F  T  |   T    |  U   U   U   T
U  F |   U  U   T     T  F  |   T    |  T   U   F   F
U  U |   U  U   U     U  U  |   T    |  U   U   U   U

The other law, (NOT A) AND (NOT B) is equivalent to NOT (A OR B) can similarly be demonstrated.

---

Can I assume that this type of compilation is guaranteed to always happen?

No, specific compilations are never (hardly ever) guaranteed. Barring bugs in SQL Server, the query plans chosen, the transformations applied, will return the results specified by a query.

---

Edited to add: Let T.id be 99 and T2.id be NULL. Then:

• WHERE NOT ( T.id <> 99 AND T2.id <> 99 )
• WHERE NOT (99 <> 99 AND NULL <> 99)
• WHERE NOT (FALSE AND UNKNOWN)
• WHERE NOT (FALSE)
• WHERE TRUE