Nullable discussions

[sundy-li]

Is Expression nullable or not?
Should we make nullable as a special & separated datatype or just a constraint property?
Nullable is annoyment but we must take into consideration.

Some kind of ways to handle the nullable:

A. Nullable is property, every expression can be nullable, if a column is declared as not null constraint, we should use a validator to check the values

B. Similiar to A, Nullable is property but every expression can be nullable and not nullable, Scalar Functions can produce Nullable results only if the argument's DataType is nullable.

C. Nullable is not a property, it's a special datatype, like Nullable(UInt8) in ClickHouse style. Scalar Functions can produce Nullable results only if the argument's DataType is nullable. In this way, queries can work most efficiently.

ClickHouse takes NotNull datatype as default, yet MySQL takes Nullable as default constraint.

[xudong963]

Thanks for @sundy-li starting the discussion. It's very meaningful to determine how to define and process Null, I'll continue to follow this discussion.

[leiysky]

Maybe we can list pros & cons of the schemes here?

Personally, I prefer C. Making nullability a part of type can avoid passing an extra boolean variable nullable everywhere. And if we have nested or recursive data type in the future, a Nullable data type can be very useful.

The disadvantage of Nullable data type is that we should deal with compatibility between types with same kind and the relationship between data type and column type more carefully.

[junli1026]

For option C, "In this way, queries can work most efficiently."

Could you please be more specific ? I can imagine Arrow may benefit from Non-nullable column and be more efficient in computing. Besides that, any thing else we can get ?

[sundy-li]

	Nullable Kind	Example	Expression is Nullable or not
A	Column Constraint property	a bigint [not null]	expr(args) is nullable only if args have any nullable value.eg: pow(3, null ) => null, for dirty values, throws exception
B	Column Constraint property	a bigint [not null]	Same as A, but For dirty values, defaults to null. Behavior more like MySQL.
C	DataType	a Nullable(bigint) / bigint	Same as A, behavior more like ClickHouse

A:

Pros:
Much more efficient, eg: DataBlock::choose_hash_method since nullable will only be produced by nullable args, so if we define column as not null we can ensure that group by keys are not nullable.

We don't have to worried about dirty values in expression/functions. In expression(args), we know the result will always be not nullable if args are all not nullable. If any args is nullable, we can unwrap it to be not nullable and then call expression(args_not_nullable), and then wrap the result back to nullable using validity bitmap combination.

Cons:

1. It's not a DataType but it works more like a DataType, we should use DataField to replace DataType everywhere to be aware of Nullable sign. Such as scalar/aggr functions, , expressions, serialization/deserialization.

2. Not compatible with MySQL behavior.

B:

Pros:

Be compatible with MySQL behavior.

Cons:

In expression(args), the result may be nullable if any args is nullable or some dirty values in args. The nullable is infectious so most of the expression result may be nullable, it's hard to decide it is nullable or not just by the schema because data values can be the reason of nullable.

C:

Pros:

Much more efficient as C.

It's a DataType, we can use it in expression like A did. We can know the result is nullable or not just by the schema.
We don't have to add another field inside the DataField struct to store the nullable sign which will make the code much easier to reafctor.

Cons:
Not compatible with MySQL behavior.

[leiysky]

IMO, compatibility with MySQL isn't a big deal.

If someone depends on the behavior that returns NULL for invalid values, we can provide a sql mode for them(a slow path, make return type of expressions default to nullable and do extra error handling). We achieved compatibility with MySQL successfully in my previous project, which is based on ClickHouse's system.

[jiangzhe]

Cons of C should include one more thing: Increasing complexity of type inference.
If nullable is associated to data type, the type inference must take care of not only expression but also operator.
Join and subquery may change the nullable property of its output:
e.g.
A full join may convert all its input to nullable output.
A semi join may convert the join key as not null in join result.
Scalar subquery on non-null column may return null if the result set is empty.
IMO, maybe to identify nullable property at runtime in an efficient way is another option.

[sundy-li]

Thanks for the suggestions, but we are starting to use Nullable(Box<DataType>)now. #3664

A full join may convert all its input to nullable output.
A semi join may convert the join key as not null in join result.

I think we can also achieve these by converting non-null column into null column in a light transformer, just need to add an extra bitmap instead.

It is useful to create deserd by datatypes in https://github.com/datafuselabs/databend/blob/1947c2282e5c62d083328492267d9223a250d328/common/datavalues/src/types/deserializations/mod.rs

If the datatype is non-null, we should never care about the bitmap and this will reduce much branch prediction miss.

[jiangzhe]

Thank you for your response.
I totally agree computation on non-null values will benefit.
I'm curious about the case of computation on a vector or a pair of vectors with very few nulls. Will this suffer a lot by additional check on nulls?
In my opinion, for most vectorized arithmetic calculation, the computation on bitmap and values are executed separately. That mean no matter the value is null or not, we do calculations on all values, then merge the bitmap.
The additional cost is the cost of merge of two bitmaps. I think that should be small compared to the real computation.
For some operations that require to do different things based on nullable, a fast scan and partition on bitmap could be performed
before the real loop of computation happens, which will also reduce a lot of branch prediction misses.
e.g. in an extreme case that the bitmap contains all valid flag, a fast scan will indicate a full range to compute, and no null check will be performed in real computation loop.
Will the performance degrade a lot due to the single scan?
By the way, my point is not to treat nullable property as not important, actually I think it is very important in a query engine.
Query optimizations like expression simplification and join conversion(left join to inner join) require this feature.

[sundy-li]

You are right, bitmap and values are executed separately, so it always has a faster path for non-null computations(both bitmap are none, no need bitmap merge cost) and bitmap merge is not the main cost.

Current we use DataField to store nullable property, but we found that lots of codes need this nullable property even in DataType field. So we should pass DataField to all functions to judge if it is nullable.

My thought is why not make it embedded into DataType since we mostly carry this property?

Eg:

1. We can have a faster limit sort if it's not nullable in: https://github.com/jorgecarleitao/arrow2/blob/main/src/compute/sort/mod.rs#L74-L82

No need to partition the values and nulls using take/memcpy.
No need to care about nulls_first.

2. Memory efficient in group by.

https://github.com/datafuselabs/databend/blob/f36b0a348c5c3c9ad1ca8cd9de800c5ae732d9ba/common/datablocks/src/kernels/data_block_group_by_hash.rs

If group key u32 not null, the hash map can use key u32.
If group key is u32 nullable, the hash map should use key u32 + 1 bit which may align to u64.

3. others ...

I admit that A and B and C can also achieve this, but C comes more naturally.