# Faster sorting of DataFrames.jl via background ordering

**URL:** <https://discourse.julialang.org/t/faster-sorting-of-dataframes-jl-via-background-ordering/45084>\
**Category:** Performance\
**Tags:** sort, dataframes\
**Created:** [August 17, 2020, 8:18am UTC](https://discourse.julialang.org/t/faster-sorting-of-dataframes-jl-via-background-ordering/45084 "2020-08-17T08:18:07Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 17, 2020, 8:18am UTC](https://discourse.julialang.org/t/faster-sorting-of-dataframes-jl-via-background-ordering/45084/1 "2020-08-17T08:18:08Z")

</div>

I have had this idea for a long time, now I finally gave it a go and the results are amazing. So here’s the idea.

Here sorting a large dataframe the algorithm roughly goes like this

1. Perform a `sortperm` on the columns to sort by. This returns an `idx` of indices.
2. Consider `colX` which his not a sort by column then `colX[idx]` would give order the `colX` in the right order.
3. Repeat number 2 for all columns.

There are room for improvement for 1 and 2 but 3 is low-hanging fruit.

Once the dataframe is sorted, most users wouldn’t start using all columns in the dataframe. For example, printing to REPL only prints the few columns. Here is our opportunity and idea

_Why not just return the dataframe and re-order the columns in the background._

If the user requests a certain column then wait for that column to be sorted and return the sorted column.

Below is a very crude implementation of that idea using [ThreadPools.jl](https://github.com/tro3/ThreadPools.jl) (which allows background threads).

But see the “performance” difference is stark!

![image](https://global.discourse-cdn.com/julialang/original/3X/3/8/3850e9b405e9f992977cbf38df06eaa8e19d6450.png)

If you did read the source you may be wondering, if someone uses the column before they have finished sorting that would cause trouble. True, but that’s I haven’t implemented the full idea which is replaced each column with a `InProgressVector` and when you access the `InProgressVector` it will be waiting for the sort to finish and return the sorted `Vector` AND it will replace itself in the DataFrame with the properly sorted vector. I haven’t implemented those yet, but you get the idea.

```julia
using ThreadPools: @bthreads
using DataFrames
using SortingLab: sorttwo!

# function barrier for assigining values
assignnew!(v, idx) = v .= v[idx]

function fsort2!(dataframe, by)
    idx = sortperm(dataframe[!, by])

    @bthreads for n in names(dataframe)
        assignnew!(dataframe[!, n], idx)
    end
    dataframe
end

# faster sort of dataframe
function fsort!(dataframe, by)
    _, idx = sorttwo!(dataframe[!, by], collect(1:nrow(dataframe)))

    all_except_by = setdiff(names(dataframe), [by])
     @bthreads for n in all_except_by
        assignnew!(dataframe[!, n], idx)
    end
    dataframe
end

# generate a dataframe with 300 columns
@time df = DataFrame([rand(Int, 1_000_000) for i = 1:300])
sort_time = @elapsed sort!(df, "x1") # takes 14 seconds

@time df = DataFrame([rand(Int, 1_000_000) for i = 1:300])
fsort2_time = @elapsed fsort2!(df, "x1") # takes 1 seconds

# sorting
@time df = DataFrame([rand(Int, 1_000_000) for i = 1:300])
fsort_time = @elapsed fsort!(df, "x1") # takes 1 seconds

using Plots
plot(
    ["DataFrames.jl sort", "New Sort", "New Sort with SortingLab.jl"], 
    [sort_time, fsort2_time, fsort_time]; title = "Sorting DataFrames", seriestype=:bar)

```