perf: the IVF shuffle sorts a key tuple per row when partition ids are already bucketable

Description

sort_to_interleave_indices in rust/lance-index/src/vector/v3/shuffler.rs decides the row order for a shuffle flush group by building one (part_id, batch_idx, row_idx) tuple per row and sorting them:

let mut keys: Vec<(u32, u32, u32)> = Vec::with_capacity(total_rows);
// ... one push per row ...
keys.sort_unstable_by_key(|k| k.0);

The sort key is a partition id, which is already known to live in [0, num_partitions) because the very next loop rejects anything outside that range. Bounded keys do not need a comparison sort: counting the rows per partition, turning the counts into prefix sums, and scattering each row into its partition's run gives the same grouping in two linear passes and needs no 12-byte tuple per row.

The function runs once per flush group inside spawn_cpu, and a group is up to shuffle_partition_batches batches, 10240 by default, so n reaches millions of rows per call on a real build.

Measured in release, alternating both implementations in one process on uniformly distributed partition ids:

About 7x, and the gap grows with n rather than staying constant.

Expected behavior

Bucket the rows by partition id in O(n + num_partitions) instead of sorting n keys, keeping the null and out-of-range rejections the current code performs.

Lance version

13.0.0-beta.4 (main)

Language binding

Rust

Start in rust/lance-index/src/vector/v3/shuffler.rs at sort_to_interleave_indices, and read how it validates partition ids and handles nulls. Reproduce the release measurements if possible, then verify that the resulting rows remain grouped by partition while both rejection behaviors are preserved and the implementation avoids sorting one tuple per row.