scalar: introduce Datum struct to have null-last Ord behavior

[skyzh]

No description provided.

[skyzh]

while #4263 only changes the key encoding, we should revisit all places that we store Row and Datum, so that it is consistent with the behavior of the storage. Normally this would happen in BTreeMap<Row, Row>.

[xiangjinwu]

I guess this means Datum should not have Ord, or we have to wrap them as NullsLargestDatum and NullsSmallestDatum to support nulls first and nulls last in the future. This does not take collation into account as well... (Collation is part of data type rather than order)

[skyzh]

Also sounds reasonable to me... We should rethink how we directly use Row / Datum to do comparisons...

[BugenZhao]

Datum contains the data type tag and it actually seems kind of meaningless to implement Ord on it, which allows comparing datums with different types, not to mention that we may not be able to customize that 🤣 #477.

I'm not sure whether there are many cases for comparing Row. With the new schemaless row format introduced by @yuhao-su, we'll always need the row schema to make comparisons. We may solve this issue at that time by the way.

[yuhao-su]

I'm not sure whether there are many cases for comparing Row

Ideally no. But we may be using BtreeMap as a kv index in our system somewhere (we may replace them with other data structures like HashMap).

The comparison between Rows should be avoided. If we want a order, we should encode it as memcomparable

[github-actions]

This issue has been open for 60 days with no activity. Could you please update the status? Feel free to continue discussion or close as not planned.

[stdrc]

Working on NULLS FIRST/LAST in #8485, I feel that we'd better introduce a dedicated type for Datum (either struct or enum is OK). The key point is to disallow comparing on Datums without an OrderType. If we don't, NULLS FIRST/LAST support can be easily broken by any unintentional comparison on Datums which are actually Options, and that cause a chaos in our system in regards to row ordering (which in fact is our current status🥵).

[stdrc]

I feel that we'd better introduce a dedicated type for Datum (either struct or enum is OK).

Had a try on this, the result is that there're too many changes need to be made. Then I came up with another idea.

The key point is to disallow comparing on Datums without an OrderType.

Since the key point is to avoid automatical derivation of Ord caused by Option, we can simply don't implement Ord for ScalarImpl. The idea is actually quite consistent, we don't want Datum to be ordered without an OrderType, so we may also don't want ScalarImpl to be ordered without an OrderType. The difference is that the default impl of Ord for Datum is incorrect (ascending nulls first) but the one for ScalarImpl is correct (ascending).

[stdrc]

Any thoughts? cc @BugenZhao

[BugenZhao]

so we may also don't want ScalarImpl to be ordered without an OrderType

Makes sense to me. 👍 We may introduce several thin wrappers instead for ScalarImpl, Option<ScalarImpl>, and Vec<Option<ScalarImpl>> to provide a default ASC NULLS LARGEST Ord implementation for convenience if the caller really don't care about the order.