Improve DataFrame.describe performance by sorting columns first

[braaannigan]

Problem description

With improvements to describe we now calculate multiple statistics that have fast-track paths. If we called something like this inside describe

df.select(pl.all().sort()).describe()

We could use those fast-track paths. For my test it reduced time by half. The only changes in the results were very small changes to std for some columns (which itself is possibly a bug)

[ritchie46]

Yeap, makes sense. This will make min/max/median/quantile after that free. Can you make a PR?

[braaannigan]

Sure - is this python only?

[braaannigan]

I see now it's python only

[alexander-beedie]

Wouldn't a 100 / 1,000 / 10,000 column sort be enormously expensive, counteracting the fast-paths? Or am I misunderstanding the nature of the optimisation? Or should we constrain a forced-sort to a certain maximum number of columns? 😅

[braaannigan]

@ritchie46
The string max/min are incorrect in fast-track mode when there are nulls as the code just picks the first value rather than the first non-null value. For example:

# Min should be "eur"
s = pl.Series("a",["usd","eur",None]) 
s.min()
# This gives
# "eur"
s.sort().min
# This gives NoneType
s.max()
# "usd"
s.sort().max()
# "usd" (this is correct)
# but...
s.sort(descending=True).max()
# Gives NoneType

I think this is the underlying function is Rust:

    pub(crate) fn min_str(&self) -> Option<&str> {
        match self.is_sorted_flag() {
            IsSorted::Ascending => self.get(0),
            IsSorted::Descending => self.get(self.len() - 1),
            IsSorted::Not => self
                .downcast_iter()
                .filter_map(compute::aggregate::min_string)
                .fold_first_(|acc, v| if acc < v { acc } else { v }),
        }
    }

And obviously needs a first_non_null. I've had a go with using the code from the non-string min and max, but I'm getting an error in the tests. I'll push what i've got as a draft PR

[braaannigan]

See #9400

[braaannigan]

Wouldn't a 100 / 1,000 / 10,000 column sort be enormously expensive, counteracting the fast-paths? Or am I misunderstanding the nature of the optimisation? Or should we constrain a forced-sort to a certain maximum number of columns? 😅

My understanding is that all the percentile operations do a sort first anyway. However, at present we sort before doing median and the percentiles. However, if we are only doing the median and percentile operations for numeric columns then we can limit the forced-sort to the numeric columns. How does that sound @alexander-beedie?

[ritchie46]

The quantiles do part of a sort, but will be O(1) if we pre-sort. I think that presorting is faster because we compute several quantiles and min/max aggregations. Those will all become O(1).

[alexander-beedie]

Somehow I didn't spot earlier that this referred to describe, where this all makes much more sense (as you are actively collecting related metrics on every column) 🤣

[braaannigan]

Performance isn't look good for this now I'm testing it again. In my previous examples this approach was much faster, now it's slower. I'll keep looking into it

[stinodego]

I'll accept a PR for this if there is a benchmark showing it's actually faster on realistic data.

[alexander-beedie]

I think this was closed by #13822.