You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "tustvold (via GitHub)" <gi...@apache.org> on 2024/02/24 03:29:20 UTC
[I] Dyn Comparison of Nested Arrays [arrow-rs]
tustvold opened a new issue, #5426:
URL: https://github.com/apache/arrow-rs/issues/5426
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
<!--
A clear and concise description of what the problem is. Ex. I'm always frustrated when [...]
(This section helps Arrow developers understand the context and *why* for this feature, in addition to the *what*)
-->
Currently `build_compare` can be used to construct a `DynComparator` that can be used to establish an ordering between two different array indices. It is up to the caller to inspect the null masks, and apply ordering as appropriate. This works well for arrays non-nested arrays, but runs into issues when arrays have children.
The introduction of logical nullability worked around this limitation for DictionaryArray and RunArray, but it is unclear how best to handle types such as StructArray and ListArray.
Part of the challenge is there isn't one way users may wish to handle nulls:
* When sorting nulls are ordered based on the `SortOptions::nulls_first` parameter
* When used in a comparison operator, the behaviour of nulls depends on the operator
Also correctly using `DynComparator` requires understanding the distinction between logical and physical nullability, see #4691, which is confusing (#4840)
**Describe the solution you'd like**
<!--
A clear and concise description of what you want to happen.
-->
In order to support arbitrarily nested ListArray in comparison kernels, we need a mechanism similar to DynComparator but which is able to handle nulls.
I would like something similar to the below
```
pub enum Compare {
LeftNull,
RightNull,
BothNull,
Less,
Equal,
Greater,
}
impl Compare {
pub fn ordering(&self, nulls_first: bool) -> Ordering {
...
}
#[inline]
pub fn is_null(&self) -> bool {
matches!(self, Self::LeftNull | Self::RightNull | Self::BothNull)
}
}
pub type Comparator = Box<dyn Fn(usize, usize) -> Compare + Send + Sync>;
pub fn build_comparator(left: &dyn Array, right: &dyn Array) -> Result<Comparator> {
...
}
```
We could then deprecate and eventually remove `build_compare` and `DynComparator`.
**Describe alternatives you've considered**
<!--
A clear and concise description of any alternative solutions or features you've considered.
-->
**Additional context**
<!--
Add any other context or screenshots about the feature request here.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Support Nested Arrays in Comparison Kernels [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2122483056
I think we should follow Postgres and Duckdb conventions for now and not worry about SQL standards. We can always extend support for SQL standard in the future if anyone needs it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Support Nested Arrays in Comparison Kernels [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2122433645
> Which is incorrect, as the result for the non-distinct case should be null
Can you explain more on this, I may miss something
I check the result in postgres and find the result is what I expected
```
postgres=# select array[null, 1] < array[null, 2];
?column?
----------
t
(1 row)
```
I think whether null is first or last if we got both nulls, it could be considered the same, so we can skip to the next element.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2068038015
Yeah, I can't remember why I decided this didn't work :sweat_smile:
I guess the proof will be to wire up a draft implementation showing it working, and then we'll know for sure :laughing:
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-1962366498
I think I can apply Comparator to List first and Struct second, then replace other after Comparator is certain
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-1962788101
For List, we iterate the pair of elements and get the `Compare` for each of them.
How do we determine the final single `Compare` based on them without `null_first`?
In this case, we may need to collect the list of `Compare` until we know what `null_first` is, which is when ``ordering(null_first)` is called after collecting all the sub-`Compare` for the nested list. For a higher dimension list, we need to collect more.
It seems to be more memory efficient to have the `null_first` info in the first place, so we can evaluate the actual ordering early, instead of collecting them and evaluate at the end.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-1962819790
This is not urgent, we can work on this after coming out a good solution
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-1962795400
> How do we determine the final single Compare based on them without null_first?
You return the appropriate variant for the case, e.g. `Compare::LeftNull`, `Compare::RightNull` or `Compare::BothNull`
> It seems to be more memory efficient to have the null_first info in the first place, so we can evaluate the actual ordering early
The problem is that for comparison operations we don't establish an ordering for NULLS, but instead have special logic to handle nulls based on the operator being used.
Unfortunately I realise this formulation won't work for `DISTINCT` and so we may need something else :thinking:
Perhaps we just need to implement a dyn dispatch version of compare_op, not sure.
I'll continue to have a play time permitting
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Support Nested Arrays in Comparison Kernels [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2121407992
> so we return Less here
Which is incorrect, as the result for the non-distinct case should be null 😅
Ultimately I can't see a way to avoid introducing a type-erased compare_op_dyn, SQL null semantics are annoying. We should be able to keep this an implementation detail though, I intend to have a play tomorrow
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2042677042
I think I would need to support nulls for non-nested types like primitive first.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Support Nested Arrays in Comparison Kernels [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2122452166
Typically ternary logic would state that comparing a null value with anything else yields a NULL, although it is interesting that postgres does not appear to be following this in your example... It would certainly make things simpler, even if it is wildly inconsistent :sweat_smile:
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-1962779260
> I think I can apply Comparator to List first and Struct second, then replace other after Comparator is certain
It seems null handling for non-list should be done first than list and struct
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Support Nested Arrays in Comparison Kernels [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2122533085
So I did some experiments:
Presto/Trino simply doesn't support comparison with nested nulls, instead returning a not supported error.
BigQuery doesn't support comparison of nested types at all.
Spark appears to follow the postgres behaviour.
In which case I think I agree that we can just follow postgres and define a total order, I will polish up my implementation of Compare.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Support Nested Arrays in Comparison Kernels [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold closed issue #5426: Support Nested Arrays in Comparison Kernels
URL: https://github.com/apache/arrow-rs/issues/5426
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-1962779581
How do we pass the `null_first` parameter? Should we extend `compare_op` or introduce a new one?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold closed issue #5426: Dyn Comparison of Nested Arrays
URL: https://github.com/apache/arrow-rs/issues/5426
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-1962779787
> How do we pass the null_first parameter? Should we extend compare_op or introduce a new one?
The idea is you wouldn't, this would instead be a property of how the users choose to interpret the returned `Compare`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2068012133
> As stated on the ticket, this needs more thought as it won't work for distinct, it is on my list to work out a way to support this but I haven't had time recently
I forgot what is the issue for `distinct` case, can you explain more?
My understanding is that `a is not distinct from b` if every element is exactly the same or say every element is either Eq or BothNull.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dyn Comparison of Nested Arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2120832436
I've remembered why the `Compare` formulation doesn't work.
Take the example of comparing two ListArray elements of `[null, 1]` and `[null, 1]`. In the distinct case the result should be equality, but in the equality case the result should be null. Now you could just return `Compare::BothNull` in this case, but what should you return for `[null, 1]` vs `[null, 2]`, returning `Compare::BothNull` would be incorrect, but as would `Compare::Less`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Support Nested Arrays in Comparison Kernels [arrow-rs]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #5426:
URL: https://github.com/apache/arrow-rs/issues/5426#issuecomment-2121393337
> in the equality case the result should be null
Can we return `true` for the equality case for `[null, 1]` and `[null, 1]`? Why should not we consider `null` equal to `null`?
For `[null, 1]` and `[null, 2]`, I think it is reasonable to return Compare::Less for `<` op, true for `distinct`, and false for `eq`.
Why should we return `BothNull` for [null, 1] vs [null, 2].
I think the calculation is like
* [null,1] < [null, 2], compare elementwise, got `BothNull`, and `Less`. Iterate left to right, skip `BothNull` or `Eq`, so we return Less here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org