[C++] Implement arrow::Concatenate for dictionary-encoded arrays with unequal dictionaries

[asfimport]

Currently (as of ARROW-3144) if any dictionary is different, an error is returned

Reporter: Wes McKinney / @wesm
Assignee: Weston Pace / @westonpace

Related issues:

• Support Dictionary Unification with Concatenate (is duplicated by)
• [C++] Move "dictionary" member from DictionaryType to ArrayData to allow for changing dictionaries between Array chunks (depends upon)

PRs and other links:

• GitHub Pull Request #8984

_{Note: This issue was originally created as ARROW-5336. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
@bkietz

[asfimport]

Ben Kietzman / @bkietz:
@wesm would it be acceptable to require that if two dictionaries differ then one must be a prefix of the other?

[asfimport]

Wes McKinney / @wesm:
@bkietz do you plan to implement this for 1.0.0?

[asfimport]

Weston Pace / @westonpace:
@wesm @bkietz I'm planning on taking this for 3.0.0 (after discussion with Ben).  A few questions:

The I/O APIs and builder API make use of delta dictionaries.  However, these seem to not be required in the Array itself.  By the time we arrive at Array any "deltaing" has been taken care of.  So I believe I do not have to worry about delta dictionaries for this correct?

There is an existing DictionaryUnifier which seems to be unused.  There is some comment referring to Transpose but that method does not appear to make use of this.  However, it appears it is a good place to start.  Is there any reason this would not be so?

The existing DictionaryUnifierhas a check on null_count with a message Cannot yet unify dictionaries with nulls.  From what I've read null_count is only referring to the nulls in the array's buffer and not nulls in the array data's dictionary itself.  I'm not sure how these would affect unification.  These fields don't have an index in the dictionary so they can be safely ignored correct?

[asfimport]

Antoine Pitrou / @pitrou:

By the time we arrive at Array any "deltaing" has been taken care of. So I believe I do not have to worry about delta dictionaries for this correct?

This is right.

 

[asfimport]

Weston Pace / @westonpace:
So the unifier currently reassigns the index type to be as small as needed.

Pros:

• Allows unification of arrays that don't have the same index type

• Resulting dictionary will be as space efficient as possible

  Cons:

• Combining arrays could modify the type of the array

• We don't tolerate differences in other types (e.g. we can't combine int8() with int16())

  Right now I'm planning on disabling this for concatenate.  All incoming arrays must have identical value and index types and the resulting array will have the same value and index type.  I will leave the capability in the unifier but allow for an index type to be specified that will override the auto-calculate.

[asfimport]

Antoine Pitrou / @pitrou:
Issue resolved by pull request 8984
#8984