Dictionary comparator ignores value cardinality #11413

arrow_cmp::make_comparator on a DictionaryArray returns a closure that runs the full value-level comparator on every slot call (str::cmp for Utf8, byte compare for Binary, nested compare for structs, and so on), ignoring the fact that the dictionary values are a small bounded set of size K. Sort and rank over N rows pay O(N log N) of those compares regardless of K, so the dictionary encoding gives no help on the hot path.

Precomputing a shared u32 rank per dictionary value inside make_comparator would reduce each slot call to two indexed loads and a u32::cmp. The rank storage is always u32 regardless of the dictionary key type (Int{8,16,32,64} / UInt{8,16,32,64}), since the rank space is bounded by K, not by the key width.

went with a different idea but perf wins are still nice to have