DISC/PERF: Laziness

[jbrockmendel]

Motivation: profiling https://github.com/pola-rs/tpch/tree/main/pandas_queries I saw a ton of time spent in frame[mask] but what is actually used is more like frame[mask][small_subset_of_columns]. If we did the frame[mask] part lazily, we'd get a huge performance improvement in cases like this.

Discussion Question 1: How common are cases like this? What other cases could benefit from laziness?

Discussion Question 2: What would it take to implement laziness? Would this be worth it?

Most of this is brainstorming on these topics. No strong opinion yet.

---

Cases that benefit

1. df[mask] mentioned above
2. operator fusing on arithmetic (a + b*c - d) / e can likely be optimized similar to how numexpr optimizes in pd.eval.
3. ... [fill in as they are suggested]

Implementation (triple tentative)
Could make Block.values a cache_readonly instead of an ArrayLike so it only gets evaluated when needed. Oftentimes we need .shape or .dtype before we need the actual values, and in some cases we can determine those ahead of time in O(1) time. This reminds me of issues/PRs I frequently see on the modin tracker, maybe @YarShev or @anmyachev can comment on the tradeoffs here?

Alternatively could add a new layer either between DataFrame/Manager or between Manager/Block. Extra layers can hurt perf-wise, but this might be the right move w/r/t separation of concerns.

One potential footgun would be something like df.where(mask, other) if other is mutable, we could get incorrect behavior if we delayed the evaluation and then other was mutated.

cc @TomAugspurger any insights?

[mroeschke]

I think this would be more compelling for examples like (a + b*c - d) / e as opposed to frame[mask][small_subset_of_columns] where there is no obvious user way to write the operation in a more performant way. "Fixing" user inefficient code treads on the "too magic" side IMO.

Here's pyarrow's API start to an execution plan: https://arrow.apache.org/docs/dev/python/api/acero.html

[jbrockmendel]

Two thoughts about potential parallelism.

1. A mechanism like in the OP where Block.values is a cache_readonly that can be delayed could also have those values be set by a callback from a parallel dispatch.

2. Laziness may expand the set of cases where parallelizing is worth the dispatch overhead. Consider e.g. df[mask].groupby("A").sum() and suppose (bear with me...) we had a mechanism for doing each Block's operation in its own process at the cost of some dispatch overhead. Doing just block[mask] might not be worth it, nor the grouped-reduce. But doing them together might me.

[datapythonista]

With the scale of pandas I guess this can be complex to implement in a way that doesn't require a decent amount of work and doesn't cause a decent amount of problems. But it's clear to me that significant performance gains in data frames will come from out-of-core algorithms and lazy execution, so surely worth to give it a try.

I think Vaex has a really nice approach to laziness. The return of dataframe operations would in general be a lazy object, but __str__ and __repr__ values will materialize the first rows and return the data, so a user in a Jupyter notebook shouldn't notice if things are lazy or not. For example:

>>> df
   a  b
0  1  3
1  2  4

>>> df + 1  # `df + 1` is lazy, but since python will call `DataFrame.__repr__`, we materialize the rows we want to show to the user
   a  b
0  2  4
1  3  5

>>> (df + 1).query('a >= 3')  # since `df + 1` is lazy, we could potentially filter results before it
   a  b
0  2  4
1  3  5

Am I understanding correctly what you're proposing @jbrockmendel, is this more or less it?

If it is, I guess it could make sense to find a very expensive operation, and give a try to make it lazy and see. If it works well (both for performance and user experience), even that single operation would be a win. What do you think?

[jbrockmendel]

Am I understanding correctly what you're proposing @jbrockmendel, is this more or less it?

Yes

[jbrockmendel]

Giving some more thought to how this might be implemented...

The upside of making Block.values lazy is it seems like it would be amenable to introducing laziness incrementally, which is otherwise pretty daunting.

Some problems with that approach are 1) we don't know what Block subclass we need until we know the values dtype. 2) in some Block methods we return a list of Blocks and don't know how many Blocks will be returned up-front (though PDEP-6 or something like it may change that eventually).

This suggests that doing this at the Manager level (or a level between DataFrame and manager, though as in the OP im not wild about adding layers) may be more robust.

[YarShev]

As the first step to implementing laziness in pandas, I think we should start with df[mask], df.shape, df.dtypes. This is kind of related to metadata management, which exists in Modin. I encourage you to read this paper (link), or, at least, "dataframe metadata management" section to get more insight on the matter. As far as I am aware of pandas internals, I think it would be good to implement laziness at the BlockManager layer, but I believe you know better where it could be placed more properly.

[datapythonista]

@YarShev I don't see how making df.shape lazy can be useful. Can you please explain what would be the advantages for users, and provide an example? Thanks!

[anmyachev]

Could make Block.values a cache_readonly instead of an ArrayLike so it only gets evaluated when needed. Oftentimes we need .shape or .dtype before we need the actual values, and in some cases we can determine those ahead of time in O(1) time. This reminds me of issues/PRs I frequently see on the modin tracker, maybe @YarShev or @anmyachev can comment on the tradeoffs here?

The number of lazy operations is very small in Modin (except for one of the backends - HDK), the main emphasis is on performing operations asynchronously.
One of the main problems is to get the type of the object that should be obtained after performing the operation, without performing it. Sometimes this is almost impossible to do (in the case of groupby().apply(udf)). However, if laziness is introduced in stages and not everywhere, then this case can be left as is.

One potential footgun would be something like df.where(mask, other) if other is mutable, we could get incorrect behavior if we delayed the evaluation and then other was mutated.

Almost all Modin objects are immutable (this is a limitation of the storages in which these objects are placed), so we do not encounter this problem. Can CoW semantics helps Pandas here?

Cases that benefit

I think one such common case where laziness should help is loops. A simple example is a loop where one column is removed at each iteration. Drop operations can be folded into one and thus save on copy operations.

This suggests that doing this at the Manager level (or a level between DataFrame and manager, though as in the OP im not wild about adding layers) may be more robust.

To the criterion for choosing the level at which to introduce laziness, the available amount of information necessary for lazy calculations can be added (try to maximize it). This information may be dtypes, indices, any other internal meta-information.