[jira] [Commented] (ARROW-14314) [C++] Sorting dictionary array not implemented

["Antoine Pitrou (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/ARROW-14314?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17445377#comment-17445377 ] 

Antoine Pitrou commented on ARROW-14314:
----------------------------------------

It should be possible to do this efficiently:

* generate an array of ordinals from the dictionary values: for example {{["c", "a", "b"]}} would generate {{[2, 0, 1]}}, while {{["c", "a", "b", "b"]}} would generate {{[3, 0, 1, 1]}} (notice that equal values should give the same ordinal, for stability)
* generate a dense array by indexing the computed ordinals with the generated indices
* sort the dense array

One complication is to deal with nulls inside the dictionary values, so that stability is enforced for them as well.


> [C++] Sorting dictionary array not implemented
> ----------------------------------------------
>
>                 Key: ARROW-14314
>                 URL: https://issues.apache.org/jira/browse/ARROW-14314
>             Project: Apache Arrow
>          Issue Type: Improvement
>          Components: C++
>            Reporter: Neal Richardson
>            Priority: Major
>              Labels: kernel
>             Fix For: 7.0.0
>
>
> From R, taking the stock {{mtcars}} dataset and giving it a dictionary type column:
> {code}
> mtcars %>% 
>   mutate(cyl = as.factor(cyl)) %>% 
>   Table$create() %>% 
>   arrange(cyl) %>% 
>   collect()
> Error: Type error: Sorting not supported for type dictionary<values=string, indices=int8, ordered=0>
> ../src/arrow/compute/kernels/vector_array_sort.cc:427  VisitTypeInline(type, this)
> ../src/arrow/compute/kernels/vector_sort.cc:148  GetArraySorter(*physical_type_)
> ../src/arrow/compute/kernels/vector_sort.cc:1206  sorter.Sort()
> ../src/arrow/compute/api_vector.cc:259  CallFunction("sort_indices", {datum}, &options, ctx)
> ../src/arrow/compute/exec/order_by_impl.cc:53  SortIndices(table, options_, ctx_)
> ../src/arrow/compute/exec/sink_node.cc:292  impl_->DoFinish()
> ../src/arrow/compute/exec/exec_plan.cc:297  iterator_.Next()
> ../src/arrow/record_batch.cc:318  ReadNext(&batch)
> ../src/arrow/record_batch.cc:329  ReadAll(&batches)
> {code}



--
This message was sent by Atlassian Jira
(v8.20.1#820001)