Implement `array_union` function

[izveigor]

Is your feature request related to a problem or challenge?

Summary

Characteristic	Description
Function name:	array_union
Aliases:	list_union
Original function?:	No
Function Description:	Azure DataBricks: Returns an array of the elements in the union of array1 and array2 without duplicates. Spark SQL: Returns an array of elements that are present in both arrays (all elements from both arrays) with out duplicates.
Sources:	Concept Azure Spark

Examples:

select array_union([1, 2, 3, 4], [5, 6, 3, 4]);
----
[1, 2, 3, 4, 5, 6]

select array_union([1, 2, 3, 4], [5, 6, 7, 8]);
----
[1, 2, 3, 4, 5, 6, 7, 8]

Describe the solution you'd like

No response

Describe alternatives you've considered

No response

Additional context

No response

[Weijun-H]

The example is not correct. It should be

select array_union([1, 2, 3, 4], [5, 6, 3, 4]);
----
[1, 2, 3, 4, 5, 6]

select array_union([1, 2, 3, 4], [5, 6, 7, 8]);
----
[1, 2, 3, 4, 5, 6, 7, 8]

[izveigor]

Thank you, @Weijun-H! Corrected now.

[Weijun-H]

Could I pick this ticket?

[izveigor]

Could I pick this ticket?

@Weijun-H Yes, you can implement. Thanks for your initiative!

[edmondop]

I started doing some work on this @izveigor but I am stucked in handling the non trivial case:

main...edmondop:arrow-datafusion:issue-6981?#diff-48cc9cf1bf

I have the following newbie questions:

• Which types I need to match against ? (data_type, data_type) ?
• Should I implement a deduplication post a concat_internal or should I find a way to rewrite concat_internal that minimize allocations and keep a set to avoid adding element twice?
• What when the type is not DataType::List ?

[jayzhan211]

Which types I need to match against ? (data_type, data_type) ?
What when the type is not DataType::List ?

I think union with Null is not defined, so you could just match the List type, i.e. (List,List).

Should I implement a deduplication post a concat_internal or should I find a way to rewrite concat_internal that minimize allocations and keep a set to avoid adding element twice?

It sounds like the latter is better, but if you fail to find the way, the first approach is also fine.

[edmondop]

@jayzhan211 I looked deeper in the code, it seems that:

• performing deduplication after would require to pattern match the internal type of the array
• performing deduplication upon creation would require modifying the MutableArrayData

The latter is here: https://github.com/apache/arrow-rs/blob/03d0505fc864c09e6dcd208d3cdddeecefb90345/arrow-select/src/concat.rs#L111 and would require a separate release of arrow-rs to extend concatenation to use an HashSet internally. On the other side, in the current arrow-datafusion, I can't find any sign of deduplication.

I created a draft PR here https://github.com/apache/arrow-datafusion/pull/7897/files but I am stuck at the moment

[jayzhan211]

@edmondop

performing deduplication after would require to pattern match the internal type of the array

We may not need pattern matching for Internal type of array. Type coercion should had been done in https://github.com/apache/arrow-datafusion/blob/9fde5c4282fd9f0e3332fb40998bf1562c17fcda/datafusion/optimizer/src/analyzer/type_coercion.rs#L582-L601
Therefore after concatenation for each arrays, they have the same data type and just add them to HashSet and construct back from it.

performing deduplication upon creation would require modifying the MutableArrayData

I think we can maintain HashSet for each row, convert array to primitives e.g.Vec<i32> or scalars e.g.Vec<ScalarValue>, extend all the values on the same row to the same HashSet then construct the final array back from the HashSets. No need concat_internal or arrow::compute::concat.

would require a separate release of arrow-rs to extend concatenation to use an HashSet internally

I'm not sure how can we benefit from having HashSet inside arrow-rs. It seems to me easier to have that in DF

[edmondop]

Initial implementation of array union without deduplication #7897

Thanks a lot for your help. So you recommend here to avoid concat_internal. I was looking at array_concat as a starting point for an implementaiton, but it looks like I might be wrong?

[jayzhan211]

I would prefer performing deduplication after , since this seems much more straightforward to me.

1. Concat N arrays with array_concat or concat_internal
2. Extends array into HashSet per row then build them back from final HashSet

But you can also try performing dedup upon without concat, if this is more efficient or readable, we can go with it.

[edmondop]

I would prefer performing deduplication after , since this seems much more straightforward to me.

1. Concat N arrays with array_concat or concat_internal
2. Extends array into HashSet per row then build them back from final HashSet

But you can also try performing dedup upon without concat, if this is more efficient or readable, we can go with it.

Hello @jayzhan211, can you help me move my next steps from https://github.com/apache/arrow-datafusion/pull/7897/files#r1369465094 ? I am still learning the internal API so the answer might be obvious :)