Polars cross join - Filtering strategies execution run time

[rjavadi]

Here's a comparison between how different startegies are performing.

Details: I created 10 NumericalDiscreteParameters and one CategoricalParameter with 3 possible values. To change the parameter space size I tried different number of values for the numerical parameters: [5, 6, 7, 8, 10, 20, 50, 100]

When the parameters' possible values reached 8 the process was killed due to memory overflow. Using Polars' Streaming API didn't solve the problem because Streaming API doesn't support cross operation. So my results are limited to n=5,6 values for each parameter and 3 values for a categorical parameter.

Search space size for n=5 : 10 * 3 * 5 ^ 10 ~ 300M cells
Search space size for n=6 : 10 * 3 * 6 ^ 10 ~ 1.80B cells
Search space size for n=7 : 10 * 3 * 7 ^ 10 ~ 8.50B cells [Exceeded memory]

I used all types of polars-constraints (sum, product, exclusion) with these conditions:

One that could filter a large chunk of rows (more than 95%),
The effect of the second one were negligible (less than 5%),
And finally a constraint with mid-range effect (filtering ~25%)

I repeated each experiment multiple times to make sure the results are consistent. The table below shows the result of one of those experiments (they were similar):

+--------------------------------------------------+-------------------------+-------------------------+
|                      Scenario                    |           n=5           |           n=6           |
+--------------------------------------------------+-------------------------+-------------------------+
| **Runtime when filtering DURING cross operation**|                         |                         |
| Filtering < 2% of search space                   |        1.6023 seconds    |        79.9452 seconds   |
| Filtering > 95%                                  |        0.3143 seconds    |         2.8251 seconds   |
| Filtering ~25%                                   |        0.8223 seconds    |        22.0388 seconds   |
+--------------------------------------------------+-------------------------+-------------------------+
| **Runtime when filtering AFTER cross operation** |                         |                         |
| Filtering < 2% of search space                   |        1.3370 seconds    |        68.7477 seconds   |
| Filtering > 95%                                  |        1.3768 seconds    |        88.1296 seconds   |
| Filtering ~25%                                   |        2.3800 seconds    |       192.3864 seconds   |
+--------------------------------------------------+-------------------------+-------------------------+
| **Baseline runtime of Pandas**                   |                         |                         |
| Filtering < 2% of search space                   |        8.2056 seconds    |        64.0838 seconds   |
| Filtering > 95%                                  |        8.6215 seconds    |        75.2954 seconds   |
| Filtering ~25%                                   |       10.9050 seconds    |        98.3916 seconds   |
+--------------------------------------------------+-------------------------+-------------------------+

[Scienfitz]

@rjavadi

• can I just sum up the time for all three subparts or were there other things to consider? I think the overall time is what we care about, the time differences between the single steps seem to depend a lot on backend and step
• With this is seems like a clear agument for filtering DURING operation
• Can you elaborate on this Using Polars' Streaming API didn't solve the problem because Streaming API doesn't support cross operation. ? So polars cannot build a lazy dataframe for that size or what does it mean? That would somehwat defy our mian aim as imo speed is secondary importance to memory usage

@AdrianSosic please take a look

[AdrianSosic]

Hi @rjavadi, thanks for the comparison!

• I was also trying to understand what exactly is the difference between lazy execution and streaming API. Is the latter really required for our use case?
• I'm a bit surprised about the number, tbh. For once, they are not monotonic with the percentage within each group (perhaps it's not as simple as one might expect) but what completely threw me off track is the 2.8251 seconds. Is this a mistake? Or is this really just because the filter is so aggressive?

[rjavadi]

@Scienfitz @AdrianSosic

can I just sum up the time for all three subparts or were there other things to consider?

Yes, the total time is roughly = sum of three subparts

Lazy API is designed for query optimization, and Polars runs the full query end-to-end to speed up the process. Streaming API has a different purpose and it helps with data that doesn't fit into memory. At the moment, not all lazy operations are supported by Streaming API, including join (From join doc: - This is currently not supported the streaming engine. more details here and here ).

With this said, I could improve runtime of filtering AFTER cross operation by using force_parallel=True in join(). Now it can also operate for n=7 in ~15 seconds and n=6 in ~2 seconds for a single constraint (for >1 constraint it failed again for n=7). I applied the same thing to filtering DURING cross operation but there was no change to the previous result and couldn't pass n>6.