Polars Sorts Floats the Way Nobody Wants Them Sorted
Polars gives floats a total order where NaN is the largest value and -0.0 equals 0.0, then picks a comparator per dtype and flattens chunks to sort them.
TL;DR: Rust floats have no total order, so Polars defines one:
TotalOrd. Every NaN compares equal to every other NaN, and NaN is the largest value in the order, which meanssort(descending=True)puts NaN first.-0.0and0.0compare equal, so the sign of zero is not recoverable from a sorted column. The sort then picks a comparator per dtype, keeps nulls out of the comparator entirely, and flattens the chunks of a chunked array into one vector before sorting it.
Sorting floats is one of those places where a dataframe engine has to pick a behaviour and then live with it forever. The obvious behaviour — the one every language gives you by default — is “NaN compares equal to nothing, so it goes wherever the comparator happens to put it”. That is not a behaviour you can implement with a sort, because a comparator that is not a total order makes the result depend on the algorithm, the input order and the pivot choices of the sort. Polars refuses to have that property, so it invents an order. The question worth asking is not whether that order is correct, but which unconvenient truths it bakes in.
Why Rust cannot sort floats
f64 implements PartialOrd, not Ord, because IEEE 754 says NaN compares
false against everything, including itself. Ord requires a total order, so
the standard library simply does not offer one. A sort algorithm that needs
Ord cannot be written for f64.
Polars solves this with a parallel trait hierarchy in
crates/polars-utils/src/total_ord.rs. The TotalOrd trait is a drop-in
replacement for Ord with a tot_cmp method:
/// Alternative trait for Ord. By consistently using this we can still be
/// generic w.r.t Ord while getting a total ordering for floats.
pub trait TotalOrd: TotalEq {
fn tot_cmp(&self, other: &Self) -> Ordering;
#[inline]
fn tot_lt(&self, other: &Self) -> bool {
self.tot_cmp(other) == Ordering::Less
}
#[inline]
fn tot_gt(&self, other: &Self) -> bool {
self.tot_cmp(other) == Ordering::Greater
}
#[inline]
fn tot_le(&self, other: &Self) -> bool {
self.tot_cmp(other) != Ordering::Greater
}
#[inline]
fn tot_ge(&self, other: &Self) -> bool {
self.tot_cmp(other) != Ordering::Less
}
}crates/polars-utils/src/total_ord.rs:64
The point of the trait is not the comparison itself but the plumbing: the
same generic code can then sort i32, String and f64 with one
implementation, because the trait is implemented for all of them.
What the float order actually says
Here is the entire float implementation. It is a macro because f16, f32
and f64 all want it:
macro_rules! impl_float_eq_ord {
($T:ty) => {
impl TotalEq for $T {
#[inline]
fn tot_eq(&self, other: &Self) -> bool {
if self.is_nan() {
other.is_nan()
} else {
self == other
}
}
}
impl TotalOrd for $T {
#[inline(always)]
fn tot_cmp(&self, other: &Self) -> Ordering {
if self.tot_lt(other) {
Ordering::Less
} else if self.tot_gt(other) {
Ordering::Greater
} else {
Ordering::Equal
}
}
#[inline(always)]
fn tot_lt(&self, other: &Self) -> bool {
!self.tot_ge(other)
}
#[inline(always)]
fn tot_gt(&self, other: &Self) -> bool {
other.tot_lt(self)
}
#[inline(always)]
fn tot_le(&self, other: &Self) -> bool {
other.tot_ge(self)
}
#[inline(always)]
fn tot_ge(&self, other: &Self) -> bool {
// We consider all NaNs equal, and NaN is the largest possible
// value. Thus if self is NaN we always return true. Otherwise
// self >= other is correct. If other is not NaN it is trivially
// correct, and if it is we note that nothing can be greater or
// equal to NaN except NaN itself, which we already handled earlier.
self.is_nan() | (self >= other)
}
}
};
}
impl_float_eq_ord!(pf16);
impl_float_eq_ord!(f32);
impl_float_eq_ord!(f64);crates/polars-utils/src/total_ord.rs:259
Everything interesting is in tot_ge. Because tot_lt is defined as
!tot_ge, the whole order is decided by one expression:
self.is_nan()short-circuits to true. A NaN is greater than or equal to everything, including another NaN.- Otherwise
self >= otheris plain IEEE comparison, and it is false for every comparison against a NaN.
So NaN is the maximum of the order, every NaN is equal to every other NaN, and
nothing is greater than a NaN. That is a genuine total order: tot_cmp is
antisymmetric, transitive and total. The consequences are the inconvenient ones
nobody asked for:
- NaN sorts last ascending and first descending. The descending branch of
the sort swaps the comparator’s arguments, which turns “NaN is the largest”
into “NaN comes first”. A
sort(descending=True)that puts NaN at the top of the column is not a bug, it is the order you asked for. -0.0and0.0are equal. IEEE says-0.0 >= 0.0is true (they compare equal), so neither istot_ltthe other andtot_cmpreturnsEqual. The sign of a zero is destroyed by a sort. If you need it, keep it in another column.NaN == NaNunderTotalEq. Two NaNs are the same key forunique,group_byand hash joins. That is a choice, and it is the choice that makes NaN usable as a group key at all.
Equality and ordering have to agree, or a HashMap keyed by floats would
break. Rust’s Hash for f64 hashes the bit pattern, so 0.0 and -0.0
would hash differently while comparing equal. Polars solves this by
canonicalising before hashing:
/// Converts an f64 into a canonical form, where -0 == 0 and all NaNs map to
/// the same value.
#[inline]
pub fn canonical_f64(x: f64) -> f64 {
// -0.0 + 0.0 becomes 0.0.
let convert_zero = x + 0.0;
if convert_zero.is_nan() {
f64::from_bits(0x7ff8000000000000) // Canonical quiet NaN.
} else {
convert_zero
}
}crates/polars-utils/src/total_ord.rs:44
x + 0.0 is the cheapest possible way to strip a sign bit: IEEE addition
gives +0.0 for -0.0 + +0.0. The same helper is used for f32 and f16,
and the hashed value is canonical_f64(x).to_bits(), so -0.0 and 0.0
hash identically and every NaN hashes identically.
To use these floats in code that wants Eq + Hash + Ord — a HashMap key, a
BTreeMap key — Polars wraps them in TotalOrdWrap, which is #[repr(transparent)]
over the value and forwards Ord to tot_cmp. Integers do not need the
wrapper; the ToTotalOrd trait exists precisely so the wrapper can be
elided for types that are already totally ordered.
Picking a comparator per dtype
With an order in hand, the sort machinery is small. The comparator is a
generic closure, and the dtype decides which one gets instantiated:
TotalOrd::tot_cmp for the numeric types, a byte comparison for binary
views, a row encoding for the nested ones. The descending flag is applied by
swapping the arguments:
pub(crate) fn sort_by_branch<T, C>(slice: &mut [T], descending: bool, cmp: C, parallel: bool)
where
T: Send,
C: Send + Sync + Fn(&T, &T) -> Ordering,
{
if parallel {
RAYON.install(|| match descending {
true => slice.par_sort_by(|a, b| cmp(b, a)),
false => slice.par_sort_by(cmp),
})
} else {
match descending {
true => slice.sort_by(|a, b| cmp(b, a)),
false => slice.sort_by(cmp),
}
}
}
fn sort_unstable_by_branch<T, C>(slice: &mut [T], options: SortOptions, cmp: C)
where
T: Send,
C: Send + Sync + Fn(&T, &T) -> Ordering,
{
if options.multithreaded {
RAYON.install(|| match options.descending {
true => slice.par_sort_unstable_by(|a, b| cmp(b, a)),
false => slice.par_sort_unstable_by(cmp),
})
} else {
match options.descending {
true => slice.sort_unstable_by(|a, b| cmp(b, a)),
false => slice.sort_unstable_by(cmp),
}
}
}
// Reduce monomorphisation.
fn sort_impl_unstable<T>(vals: &mut [T], options: SortOptions)
where
T: TotalOrd + Send + Sync,
{
sort_unstable_by_branch(vals, options, TotalOrd::tot_cmp);
}crates/polars-core/src/chunked_array/ops/sort/mod.rs:73
Note sort_by_branch is stable and sort_unstable_by_branch is not; both
are used, and the choice is deliberate per call site. A stable sort allocates
a scratch buffer of half the slice length, so the unstable variant exists to
avoid that allocation when the caller does not care about tie order.
Not every dtype reaches a comparator at all:
- Boolean is sorted by counting. The number of
truevalues is known from the bitmask, so the sorted column is written as a run oftruefollowed by a run offalse. There is no sort, no comparator and no allocation beyond the output bitmap. - BinaryView sorts the views, not the bytes. The 16-byte view structs are permuted in place and the data buffers are left untouched.
- Struct and List have no natural order, so they are row-encoded first and the encoded bytes are sorted.
Nulls never reach a comparator. They are partitioned out of the values before the sort and re-attached afterwards:
fn partition_nulls<T: Copy>(
values: &mut [T],
mut validity: Option<Bitmap>,
options: SortOptions,
) -> (&mut [T], Option<Bitmap>) {
let partitioned = if let Some(bitmap) = &validity {
// Partition null last first
let mut out_len = 0;
for idx in bitmap.true_idx_iter() {
unsafe { *values.get_unchecked_mut(out_len) = *values.get_unchecked(idx) };
out_len += 1;
}
let valid_count = out_len;
let null_count = values.len() - valid_count;
validity = Some(create_validity(
bitmap.len(),
bitmap.unset_bits(),
options.nulls_last,
));
// Views are correctly partitioned.
if options.nulls_last {
&mut values[..valid_count]
}
// We need to swap the ends.
else {
// swap nulls with end
let mut end = values.len() - 1;
for i in 0..null_count {
unsafe { *values.get_unchecked_mut(end) = *values.get_unchecked(i) };
end = end.saturating_sub(1);
}
&mut values[null_count..]
}
} else {
values
};
(partitioned, validity)
}crates/polars-core/src/chunked_array/ops/sort/mod.rs:41
The null mask is turned into a run of valid values at the front, the values are
sorted, and a new validity bitmap is written to match where the nulls ended
up. nulls_last is not a comparator flag; it is a partition decision made
before the sort starts. This is why the float order can be as weird as it is:
nulls are not part of it.
The same philosophy shows up in crates/polars-utils/src/sort.rs, where the
comparison helper that the multi-key sort uses keeps nulls out of the value
comparison as well:
/// Compare two values with support for sort direction and nulls position.
///
/// # Panics
///
/// Panics if `T::partial_cmp(lhs, rhs)` returns `None`.
#[inline]
pub fn reorder_cmp<T: PartialOrd + IsNull>(
lhs: &T,
rhs: &T,
descending: bool,
nulls_last: bool,
) -> Ordering {
match PartialOrd::partial_cmp(lhs, rhs).expect("expected total ordering") {
Ordering::Equal => Ordering::Equal,
_ if lhs.is_null() && nulls_last => Ordering::Greater,
_ if rhs.is_null() && nulls_last => Ordering::Less,
_ if lhs.is_null() => Ordering::Less,
_ if rhs.is_null() => Ordering::Greater,
ord if descending => ord.reverse(),
ord => ord,
}
}crates/polars-utils/src/sort.rs:119
Note the order of the arms: the null rules are applied before the
descending reversal, so nulls_last and descending do not interact. A
null is either smaller than everything or larger than everything, never
“reversed”.
That file also holds the one place where Polars sorts a scratch buffer of
(value, index) pairs by hand, which is a neat trick worth reading: the
pairs are sorted, and then the value half of the memory is overwritten with
the index half, in place, because the index is smaller than the value:
pub fn arg_sort_ascending<'a, T: TotalOrd + Copy + 'a, Idx, I: IntoIterator<Item = T>>(
v: I,
scratch: &'a mut Vec<u8>,
n: usize,
) -> &'a mut [Idx]
where
Idx: FromPrimitive + Copy,
{
let upper_bound = size_of::<(T, Idx)>() * n + align_of::<(T, Idx)>();
scratch.reserve(upper_bound);
let scratch_slice = unsafe {
let cap_slice = scratch.spare_capacity_mut();
let (_, scratch_slice, _) = cap_slice.align_to_mut::<MaybeUninit<(T, Idx)>>();
&mut scratch_slice[..n]
};
for ((i, v), dst) in v.into_iter().enumerate().zip_eq(scratch_slice.iter_mut()) {
*dst = MaybeUninit::new((v, Idx::from_usize(i).unwrap()));
}
let scratch_slice = unsafe { assume_init_mut(scratch_slice) };
scratch_slice.sort_by(|key1, key2| key1.0.tot_cmp(&key2.0));
// Now we write the indexes in the same array. So from (T, Idxsize) to just IdxSize.
unsafe {
let src = scratch_slice.as_ptr();
let (_, scratch_slice_aligned_to_idx, _) = scratch_slice.align_to_mut::<Idx>();
let dst = scratch_slice_aligned_to_idx.as_mut_ptr();
for i in 0..n {
dst.add(i).write((*src.add(i)).1);
}
&mut scratch_slice_aligned_to_idx[..n]
}
}crates/polars-utils/src/sort.rs:15
The scratch buffer is a Vec<u8> that is reused across calls, and the
alignment dance is what lets the same allocation hold (T, Idx) pairs on the
way in and bare Idx values on the way out.
What a chunked sort actually costs
Here is the part that surprised me. A ChunkedArray is a list of chunks, but
the numeric sort does not sort the chunks and merge them. It flattens
everything into one vector:
fn sort_with_numeric<T>(ca: &ChunkedArray<T>, options: SortOptions) -> ChunkedArray<T>
where
T: PolarsNumericType,
{
sort_with_fast_path!(ca, options);
if ca.null_count() == 0 {
let mut vals = ca.to_vec_null_aware().left().unwrap();
sort_impl_unstable(vals.as_mut_slice(), options);
let mut ca = ChunkedArray::from_vec(ca.name().clone(), vals);
let s = if options.descending {
IsSorted::Descending
} else {
IsSorted::Ascending
};
ca.set_sorted_flag(s);
ca
} else {
let null_count = ca.null_count();
let len = ca.len();
let mut vals = Vec::with_capacity(ca.len());
if !options.nulls_last {
let iter = std::iter::repeat_n(T::Native::default(), null_count);
vals.extend(iter);
}
ca.downcast_iter().for_each(|arr| {
let iter = arr.iter().filter_map(|v| v.copied());
vals.extend(iter);
});
let mut_slice = if options.nulls_last {
&mut vals[..len - null_count]
} else {
&mut vals[null_count..]
};
sort_impl_unstable(mut_slice, options);
if options.nulls_last {
vals.extend(std::iter::repeat_n(T::Native::default(), ca.null_count()));
}
let arr = PrimitiveArray::new(
T::get_static_dtype().to_arrow(CompatLevel::newest()),
vals.into(),
Some(create_validity(len, null_count, options.nulls_last)),
);
let mut new_ca = ChunkedArray::with_chunk(ca.name().clone(), arr);
let s = if options.descending {
IsSorted::Descending
} else {
IsSorted::Ascending
};
new_ca.set_sorted_flag(s);
new_ca
}
}crates/polars-core/src/chunked_array/ops/sort/mod.rs:189
So sorting an f64 column of n rows copies 8n bytes out of the chunk
buffers into a fresh Vec, sorts that vector in place, and hands the vector
to a new Buffer — the buffer takes ownership, so there is no second copy,
but the first one is unavoidable: the sort works on a contiguous array, and a
chunked array is not contiguous. The chunk boundaries are irrelevant to the
result; they only matter for how the data was laid out in memory.
The arg_sort path is more expensive, because it has to carry the index along
with the value:
let mut vals = Vec::with_capacity(len - null_count);
let mut nulls_idx = Vec::with_capacity(null_cap);
let mut count: IdxSize = 0;
for arr_iter in iters {
let iter = arr_iter.into_iter().filter_map(|v| {
let i = count;
count += 1;
match v {
Some(v) => Some((i, v)),
None => {
// SAFETY: we allocated enough.
unsafe { nulls_idx.push_unchecked(i) };
None
},
}
});
vals.extend(iter);
}
let vals = if let Some(limit) = options.limit {
// Overwrite output len.
len = std::cmp::min(limit as usize, len);
sort_limit_impl(&mut vals, len, options)
} else {
sort_impl(vals.as_mut_slice(), options);
vals.as_slice()
};crates/polars-core/src/chunked_array/ops/sort/arg_sort.rs:150
A (IdxSize, f64) pair is 16 bytes with alignment 8, so an argsort of an
f64 column materialises 16n bytes before the first comparison happens.
And because sort_impl uses the stable sort_by, Rust’s stable sort adds
another n/2 elements of scratch space — about 8n more bytes. The
unstable variant is used for the values-only sort precisely because it does not
need that scratch buffer.
That is the real price of “sort the chunks and merge them” being avoided: a
single global sort of a flattened vector, with one big allocation. A k-way
merge of per-chunk sorts would have cost O(n log c) comparisons instead of
O(n log n), but it would also have needed the chunks to stay alive and the
merge to run over c cursors. Polars does not do that, and the reason shows up
in the streaming engine.
The streaming engine sorts by partitioning, not by merging
When the sort cannot fit in memory, the streaming engine takes a different route. Instead of one sort over everything, it samples the key column, picks split keys from the sample, and routes every row into a bucket:
/// Computes the `b - 1` split keys separating `b` equally sized buckets.
///
/// The result is sorted in the order the buckets are laid out, so descending
/// when `descending` is set, and contains no nulls. Equal neighbours are kept:
/// they are what marks a key value that holds a whole bucket by itself.
pub fn split_keys(
samples: Vec<Series>,
dtype: &DataType,
descending: bool,
b: usize,
) -> PolarsResult<Series> {
let samples: Vec<Series> = samples.into_iter().filter(|s| !s.is_empty()).collect();
if samples.is_empty() || b <= 1 {
return Ok(Series::new_empty(PlSmallStr::EMPTY, dtype));
}
let s = concat(samples).drop_nulls().sort_with(SortOptions {
descending,
nulls_last: false,
multithreaded: true,
maintain_order: false,
limit: None,
})?;
let n = s.len();
if n == 0 {
return Ok(Series::new_empty(PlSmallStr::EMPTY, dtype));
}
let idxs: Vec<IdxSize> = (1..b).map(|j| (j * n / b) as IdxSize).collect();
s.take_slice(&idxs)
}crates/polars-stream/src/nodes/sort/sample.rs:135
Each bucket is then sorted on its own, and the buckets are emitted in key
order. There is no merge step at all, because the buckets hold disjoint key
ranges: the output is a concatenation of sorted runs, not a merge of them. The
classifier is a branchless search tree over the split keys in Eytzinger layout,
so classifying a row is log2(b) comparisons with no branch mispredictions.
A bucket bounded by two equal split keys holds a single key value and is
already sorted, so it is emitted without sorting at all.
This is the answer to “how do you avoid materialising the whole column”: you do not sort it as one thing, you cut it into key ranges first. The cost is that the split keys come from a sample, so the buckets are only roughly equal-sized; a heavy-tailed key column can put most of the rows in one bucket, which is exactly the case the “single key value” fast path covers.
Where a real merge does happen
One place Polars merges two sorted streams is the sort-merge join. If both sides of a join are already sorted, the hash table can be replaced by a linear scan of the two sorted runs:
let no_nulls = s_left.null_count() == 0 && s_right.null_count() == 0;
match (s_left.is_sorted_flag(), s_right.is_sorted_flag(), no_nulls) {
(IsSorted::Ascending, IsSorted::Ascending, true) if is_numeric => {
if verbose {
eprintln!("inner join: keys are sorted: use sorted merge join");
}
Ok((par_sorted_merge_inner_no_nulls(s_left, s_right), true))
},crates/polars-ops/src/frame/join/hash_join/sort_merge.rs:235
The merge itself is O(n + m) comparisons, which is far cheaper than a hash
join’s random memory access pattern — but only if the sortedness is already
there. If one side is not sorted, Polars sorts it (paying O(n log n) plus a
full copy of the values) and then undoes the permutation on the resulting
indices. The engine only takes that route when the size ratio between the two
sides makes the extra sort worth it, which is a decision made with a float
comparison of lengths and an environment variable override.
The bottom line
The float order in Polars is not the IEEE order, and it is not the “NaN goes last, whatever that means” order either. It is a deliberate total order with three properties worth memorising:
- NaN is the maximum.
sort(descending=True)puts NaN first. -0.0and0.0are the same value, in sorting and in hashing.- Every NaN is the same value, so
uniquecollapses them andgroup_bytreats them as one group.
The sort machinery around that order is unremarkable and worth knowing anyway:
nulls are partitioned out before sorting rather than handled in the
comparator, descending is implemented by swapping comparator arguments, the
numeric sort flattens the chunks into one vector (one full copy of the
values), an argsort materialises 16 bytes per row for the (index, value)
pairs plus the stable sort’s scratch buffer, booleans are sorted by counting,
and the streaming engine avoids the global sort altogether by partitioning the
key range and emitting sorted buckets back to back.
If you want to see the order for yourself:
import polars as pl
df = pl.DataFrame({"x": [1.0, float("nan"), -0.0, 0.0, float("nan")]})
print(df.sort("x")) # [1.0, -0.0, 0.0, nan, nan]
print(df.sort("x", descending=True)) # [nan, nan, 1.0, 0.0, -0.0]Those two lines are the whole article. The two NaNs are adjacent and
indistinguishable, the two zeros are adjacent because Polars considers them
equal, and in the descending sort the NaNs are first — the largest value
under the order that sort actually implements. The relative order of the two
zeros is not guaranteed, incidentally: a values-only sort is an unstable sort,
so the tie is broken arbitrarily.