Fast row aggregation in DataFrames.jl

[sl-solution]

As you might know DataFrame is optimised for column operations, and row operations are not efficient. There are some solutions for this and has been previously discussed (#2440, #2757, #2439, #952, ...).

Based on my knowledge, the most efficient way (similar-to-work-with-matrix performance) to do this when the problem is fitted into map and reduce, is using mapreduce, e.g.

df = DataFrame(rand(10^5, 100), :auto)
op(x, y) = x .+= y
mapreduce(identity, op, eachcol(df), init = zeros(nrow(df)))

At the beginning I thought this is very trivial and just having some documentations about mapreduce should be enough for DataFrames.jl users. However, thinking about it for a while, I guess this is not that much trivial as I thought (particularly if missings are present). Thus, I think having a bunch of common row operations inside DataFrames.jl would be helpful, particularly, the operations which take care of missing automatically. Since I know this may be controversial, at the moment, I develop a package DFRowOperation.jl to define and store a set of common row operations. The users may use, contribute and evaluate this package and if it make sense, it would be great to add its functionality into DataFrames.jl in future.

you may access the package at

https://github.com/sl-solution/DFRowOperation.jl

and currently contains the following functions one function byrow with the support of the following optimised functionalities for row-wise operations:

- sum
- prod
- cumsum
- cumsum!
- cumprod
- cumprod!
- mean
- count
- any
- all
- minimum
- maximum
- var
- std
- stdze!
- stdze
- sort!
- sort
- nunique
- mapreduce
- reduce

[bkamins]

This makes a lot of sense. However, if you allow 😄 (given you have already put a lot of work into it) in DataFrames.jl I would do the following (this is easy to do, and is more extensible). I will give an example of only sum, but this extends to other functions.

When user writes:

select(df, cols => ByRow(sum) => outcol)

or (if handling missing values is required)

select(df, cols => ByRow(sum∘skipmissing) => outcol)

then we can intercept ByRow(sum) (and other). The key benefit of our current design of ByRow (and it was intentional) is that:

julia> typeof(ByRow(sum))
ByRow{typeof(sum)}

so we can dispatch on it and provide an efficient aggregation path both for DataFrame and GroupedDataFrame (similarly to how we currently do efficient aggregations in for GroupedDataFrame).

The only consideration is that if we want to be consistent we probably should first introduce AsVector as discussed in the earlier issues so one would write:

select(df, AsVector(cols) => ByRow(sum) => outcol)

as sum expects a single positional argument that is a collection.

The benefit of this approach, over your proposal, is that we do not introduce numerous new verbs. We use what we currently have and only need to add AsVector. Actually the point will be that AsVector will just work as you want things to work, but what we will do is that if you write AsVector(cols) => ByRow(sum) => outcol a special code path would be invoked so that the source vectors would not have to be materialized but an efficient reduction would be performed.

What do you think about it?

CC @nalimilan, @pdeffebach

[sl-solution]

HandlingGroupedDataFrame in DFRowOperation shouldn't be difficult.

AsVector is a good idea, however, when I was thinking about this problem, the first thing for me was efficiency (compilation time, time, and memory allocation). mapreduce uses multi-dispatch of Julia to handle heterogeneous data type and that is the key benefit for working with DataFrame. On the other hand, at the beginning, I thought AsVector is more general, however, looking at it a little more, I found that the most desirable situations for AsVector are still the kind of problems which fit into map & reduce paradigm.

Adding more verbs, i.e. row_xxxx is not the perfect solution but it is not that much inconvenient. And always we can think about a better design approach to incorporate them into DataFrames.jl.

[bkamins]

Could you please expand on your comment where you see the conflict? What I mean is to use mapreduce approach internally, but with the only twist that we do not have to expose these row_xxxxx functions and instead hide them under a common API.

[bkamins]

I was thinking about it a bit more. Actually your package might make sense to have on its own. Essentially it could drop a dependency on DataFrames.jl and support any Tables.jl compliant source. Then it would be more general. I feel that some people might then find it useful for their workflows that do not use DataFrames.jl.

[bkamins]

In summary I would propose the following plan:

• I will implement a generic AsVector wrapper for DataFrames.jl, as we want it anyway (this will be a PR that is not intended to make things fast always but to specify the API)
• in parallel we can discuss the reduction mechanisms
• then we can decide how to incorporate them into AsVector syntax (my current thinking is that we can use special dispatch paths)

A particular comment that e.g. that:

df = DataFrame(rand(100, 10000), :auto)
select(df, AsVector(:) => sum)
select(df, AsVector(:) => mean)

will already be fast without any special handling, as sum and mean already support fast reductions in their design in Julia Base/Statistics.

[sl-solution]

... What I mean is to use mapreduce approach internally, but with the only twist that we do not have to expose these row_xxxxx functions and instead hide them under a common API.

I was thinking about this, however, this create one issue which I don't know how to avoid it:
suppose internally when user calls select(df, AsVector(:) => sum, row_sum(df) is run, but user cannot provide options to the function sum conveniently. Calling select(df, AsVector(:) => x ->sum(abs, x)) will not end up with the same path. (any idea?)

Using row_xxxx is not that much bad idea either, it is just a convenient way to use mapreduce.

[sl-solution]

df = DataFrame(rand(100, 10000), :auto)
select(df, AsVector(:) => sum)
select(df, AsVector(:) => mean)

will already be fast without any special handling, as sum and mean already support fast reductions in their design in Julia Base/Statistics.

I think that would not be that much simple (?), e.g. sum(VectorIterator(df)) needs some manual optimisation.

[bkamins]

Using row_xxxx is not that much bad idea either

Let us see what other maintainers say, but my feeling is that we will not allow for adding that many row_xxxx verbs to DataFrames.jl (they can live in a separate package though).

AsVector(:) => x ->sum(abs, x)

Yes - this will not be able to use the fast path and this would be a limitation of this approach. This is the same we have in fast aggregation.

However, if in the future Julia Base would support a nicer support for currying it would be very easy to add:

AsVector(:) => Base.Fix1(sum, abs)

just right now Base.Fix1(sum, abs) is very ugly and uses an unexported feature so I would not add support for it for now as it would be very unlikely to be used in practice.

e.g. sum(VectorIterator(df)) needs some manual optimisation.

Yes, it would not be optimal, but it would already be relatively good. As commented - we could always add a special path to it.

[bkamins]

Maybe let me add another general comment. In DataFrames.jl we try to have a different design approach than eg. Pandas has. We want to keep the body of the package as minimal as possible, but making sure that the core is flexible enough to cover user's needs. The assumption is that satellite packages (or even some simple Julia Base code) can cover for the rest. The idea is that we do not need to bake in into DataFrames.jl all the functionality because of speed (as opposed to e.g. Pandas where you have to call optimized C code to be fast, so all has to be included). This is a consideration I have in mind when discussing this issue.

This is a different situation than e.g. your #2743 proposal. In #2743 we know that the stack/unstack combo we now have is kind of lacy design that is not optimal, so some methods with a better API for reshaping data frames need to be added at some point to the core of the package. There the issue is that designing such an API is super hard and requires consideration. The key point is that the API should be immediately clear to the user how it should be applied (this is the bane of current stack/unstack - not only they are not flexible enough, but also no one ever remembers the order of their arguments and docstrings need to be constantly looked up).

In summary both this proposal and #2743 hit important things we want to focus on adding post 1.0 release. However, both issues - for different reasons - are not simple decisions to make and quickly merge new functionality.

Let me also give you the following perspective: the proposals by @pstorozenko (a new contributor) of #2726 and #2727 were easy decisions to make a PR and merge as they were both clear improvements that, however, do not affect user facing API. Everything that affects exposed API will be processed much longer. We are after 1.0 release (which we had to do although we knew that there are things to still work on). But being after 1.0 release means that we cannot loosely experiment with user-facing API any more. Whatever we add must be very well thought of so that we are 100% sure it will not change in the future.

[sl-solution]

Discussing about this issue will be eventually helpful and we can end up with a solid solution.

Let us see what other maintainers say, but my feeling is that we will not allow for adding that many row_xxxx verbs to DataFrames.jl .

I guess this wouldn't be an issue, since a suitable design can solve this (?) (although we get used to this kind of verbs in Julia Base 😄, since, sum, mean, ... are some kind of wrappers around map & reduce)

e.g. sum(VectorIterator(df)) needs some manual optimisation.

Yes, it would not be optimal, but it would already be relatively good. As commented - we could always add a special path to it.

I think VectorIterator is a nice approach, however, wouldn't scale well (unless adjusted case by case which means introducing many path internally).

[nalimilan]

I fully agree with @bkamins. We should keep the API both minimal and flexible. The strength of DataFrames.jl is that it leverages the fact that Julia allows writing custom code that is fast, so that we don't need to provide dozens of special methods. When particular optimizations are needed, they should happen under the hood, while users still use the more general syntax.

[sl-solution]

I explored the idea a little more and defined a function called byrow(f, df, cols; [by = identity, ....]), this helps to avoid many verbs, e.g.

julia> df = DataFrame(g = [1, 1, 1, 2, 2],
               x1_int = [0, 0, 1, missing, 2],
               x2_int = [3, 2, 1, 3, -2],
               x1_float = [1.2, missing, -1.0, 2.3, 10],
               x2_float = [missing, missing, 3.0, missing, missing],
           x3_float = [missing, missing, -1.4, 3.0, -100.0])
5×6 DataFrame
 Row │ g      x1_int   x2_int  x1_float   x2_float   x3_float
     │ Int64  Int64?   Int64   Float64?   Float64?   Float64?
─────┼─────────────────────────────────────────────────────────
   1 │     1        0       3        1.2  missing    missing
   2 │     1        0       2  missing    missing    missing
   3 │     1        1       1       -1.0        3.0       -1.4
   4 │     2  missing       3        2.3  missing          3.0
   5 │     2        2      -2       10.0  missing       -100.0


julia> byrow(sum, df, r"x")
5-element Vector{Union{Missing, Float64}}:
   4.2
   2.0
   2.6
   8.3
 -90.0

julia> byrow(sum, df, r"x", by = abs)
5-element Vector{Union{Missing, Float64}}:
   4.2
   2.0
   7.4
   8.3
 114.0

This can be fit in the current design by a little change. For example in select, something like cols => byrow(f; kwargs...) will be translated to byrow(f, df, cols, kwargs....), or something like f.(eachrow(df[!, cols])) when f doesn't fit into map & reduce. (by argument is following sort convention in Julia)

julia> select(df, :, r"x" => byrow(sum, by = abs) => :total)

5×7 DataFrame
 Row │ g      x1_int   x2_int  x1_float   x2_float   x3_float   total
     │ Int64  Int64?   Int64   Float64?   Float64?   Float64?   Float64?
─────┼───────────────────────────────────────────────────────────────────
   1 │     1        0       3        1.2  missing    missing         4.2
   2 │     1        0       2  missing    missing    missing         2.0
   3 │     1        1       1       -1.0        3.0       -1.4       7.4
   4 │     2  missing       3        2.3  missing          3.0       8.3
   5 │     2        2      -2       10.0  missing       -100.0     114.0

[bkamins]

Rewriting it a bit, we could - instead of adding AsVector, add something like RowReduce and RowMapReduce that would be only allowed when column selector is not AsTable. Then the syntax could be:

cols => RowReduce(op; init, skipmissing=false)

and

cols => RowMapReduce(f, op; init, skipmissing=false)

which would efficiently call reduce and mapreduce on the collection given by row selector, optionally skipping missing values.

This would be a bit less flexible than AsVector, but maybe indeed supporting only reduce and mapreduce is enough in practice.

So we have three designs on the table:

• originally planed AsVector
• your proposal with byrow
• the approach with RowReduce and RowMapReduce

Let us wait for other users/contributors to comment on what they think