Improved Handling of Sparse Dictionaries

[tustvold]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

Sparse dictionaries, where a large number of a dictionary's values are not referenced by a corresponding key, can occur fairly frequently:

• Parquet dictionary preservation will output the same dictionary for all arrays in a row group
• Selection kernels like take or filter will not recompute a smaller dictionary

Many of the kernels, however, proceed by evaluating against the values and then "materializing" this result in the context of a dictionary.

Describe the solution you'd like

The basic primitive needed is the ability to compute a selection vector for a dictionary's values, which can then be used as a selection vector (#4095) (#3620) for further operations

Describe alternatives you've considered

Additional context

#506 tracks adding the ability to recompute a dictionary, which may share similar primitives

#4095 and #3620 track adding selection vector support.

[tustvold]

Closed by #3558