Join order and nullability

Question

I am asking this question in the context of using a Postgres database, although I would imagine it would apply to most SQL databases.

When working with the results of a database query inside a statically typed application, we need to know whether a particular column could return null or not. When the underlying data is stored in a table column with a NOT NULL constraint, we can confidently type the data as non-nullable in our application. Likewise, if there is no constraint, then we type the column as nullable since it could return null.

This is simple enough to reason about, but things get more complicated when we introduce left and right joins. For example, if we have a join clause like

FROM a
LEFT JOIN b ON a.x = b.y

then all the columns on b become nullable, since the results could include rows of a where there was no matching b row. Likewise, if we do

FROM a
RIGHT JOIN b ON a.x = b.y

now all the columns on a will be nullable.

In this sense, we could say that certain joins (specifically left and right outer joins) apply a sort of "nullability modifier" to one or more of the set of tables used in the query's projection.

What I am struggling to wrap my head around is how this behavior works when there are multiple joins. For example:

FROM a
LEFT JOIN b ON a.x = b.y
LEFT JOIN c ON b.x = c.y

or

FROM a
LEFT JOIN b ON a.x = b.y
RIGHT JOIN c ON b.x = c.y

or

FROM a
LEFT JOIN b ON a.x = b.y
INNER JOIN c ON b.x = c.y
RIGHT JOIN c ON c.x = d.y

or

FROM a
LEFT JOIN (b INNER JOIN c ON b.x = c.y) ON a.x = b.y

If I iterate over the set of joins, is there a set of heuristics I could apply that would let me accurately set the "nullability modifier" for each referenced table, so that I can derive an accurate application type for the query's result? The snippets above serve to illustrate the complexity of this issue, but the idea is to have a set of heuristics that could be applied to any set of joins, regardless of length, order or composition.

Answer 1

Based on some experimentation and my understanding of how join order works in Postgres, I think the following rules can be applied:

Note: in the diagrams below, ! denotes not nullable, ∅ denotes nullable, the individual letters denote tables and the -X- denote joins where X is the type of join.

• Iterate through the joins from left to right. If there are parentheses, then the joins inside the parentheses are evaluated independently of the rest of the query first using the outlined rules.
• If the FROM clause includes multiple source tables, each additional table can be converted to a cross join for the purposes of this exercise.
• The initial source table in the FROM clause is not nullable.

A
!

• A left join makes the joined table nullable.

A -L- B
!     ∅

• A right join makes everything except the joined table nullable. Notice that A is now nullable. This is true regardless of the dependencies between the joined tables.

A -L- B -R- C
∅     ∅     !

• A full outer join makes everything nullable. This is true regardless of the dependencies between the joined tables.

A -L- B -R- C -F- D
∅     ∅     ∅     ∅

• A cross join has no impact on nullability.

A -L- B -R- C -F- D -C- E
∅     ∅     ∅     ∅     !

• An inner join is tricky because it removes the nullability from every table between itself and the source table. We have to look at the dependencies between the tables created by the join conditions themselves to determine which tables are affected.

For example, we can have two left joins to A. These are illustrated as separate lines, but they exist in the same query:

A -L- B
!     ∅
A -L- C
!     ∅

If we have add an inner join to A, the left joins are unaffected.

A -L- B
!     ∅
A -L- C
!     ∅
A -I- D
!     !

However, if we join D to one of the other two tables, it affects that tables nullability:

A -L- B
!     ∅
A -L- C -I- D
!     !     !

The same would be true for any additional tables in the "chain" between A (the source table) and D (the inner joined table).

Answer 2

When working with the results of a database query inside a statically typed application, we need to know whether a particular column could return null or not.

No, you do not. You need to know if the particular field in the current record has a value or NULL. But you do not need to do such strict static typing that whole record is nullable or not.

It is much easier to always expect that the field can have a NULL instead of value and do the check before using.

If you using ODBC to connect to the database, and SQLGetData() to read values from the recordset fields, just expect that it can return SQL_NULL_DATA for the data length. Or, if you using column binding, the pointer you provided for data length will have the SQL_NULL_DATA.

Other interfaces have similar abilities - in ADO, the field value is always returned as an object (ADODB.field), and it that would have a property .IsNull. So you write something like

rs.open "select * from tbl",con

do while not rs.eof
  f1 = rs.fields("f1")
  if not f1.IsNull then
     wscript.echo f1.value
  end if
  rs.movenext
loop

Some languages and interfaces do not have a dedicated NULL value. For example, in perl with DBI you would do something like

while (@row_ary  = $sth->fetchrow_array) {
   $f = $row_ary[1];
   if (defined($f)) {
     print $f;
   }
}

Here the SQL's NULL is replaced with perl's special undef constant. Same meaning as SQL's NULL, but different name.

The fact is, you do not really need to know before hand, will there be NULLs in the column or not. Just always expect that were would be. And each and every database interface has ability to tell you, is this particular field in the record NULL or not.

Said that, there is actually a way to ask DBMS's prediction would there be NULL or not. For example, if you use ODBC you can call SQLDescribeCol() right before the first SQLFetch() of the resultset. Which would tell you the is the column SQL_NO_NULLS, SQL_NULLABLE, SQL_NULLABLE_UNKNOWN.

Unfortunately, the SQL_NO_NULLS is known only for the straight dump from a table, and for a query, you more often would get SQL_NULLABLE_UNKNOWN. So this is not an absolutely reliable information, but it is not really needed.