[ARROW-13969] [C++][Compute] Implement SelectKStable

• Type: Improvement
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Component/s: C++
• Labels: analytics kernel query-engine
• External issue URL: https://github.com/apache/arrow/issues/29573

Language

C++

• Assignee: Unassigned
• Reporter: Alexander Ocsa
• Created: 10/Sep/21 02:09
• Updated: 11/Jan/23 08:36

Description

PR https://github.com/apache/arrow/pull/11019 implements SelectKUnstable.

 

Some previous result of SelectKUnstable using StableHeap is shown here: https://github.com/apache/arrow/pull/11019#issuecomment-913977337 

 

So, implementation of SelectKStable   should explore how to implement this algorithm using StablePartition + stable_sorting.

 

Final note: As mentioned here: https://github.com/apache/arrow/pull/11019#discussion_r706231044 

.e. instead of select_k_options.is_top_k() have 1) a check that there are sort keys and then 2) check select_k_options.sort_keys[0].order == Descending instead, inside the function definition.
1