memory-usage/performance regression on join_where in 1.19

[ypsah]

Checks

• I have checked that this issue has not already been reported.
• I have confirmed this bug exists on the latest version of Polars.

Reproducible example

import datetime

import polars as pl


def snooze(alarms: pl.DataFrame, *, over: datetime.timedelta, frequency: datetime.timedelta) -> pl.DataFrame:
    sampling = pl.datetime_range(
        alarms["start"].min(),
        alarms["start"].max() + over,
        frequency,
        eager=True,
    ).alias("sampling")
    return alarms.join_where(
        pl.DataFrame(sampling), pl.col("sampling").is_between(pl.col("start"), pl.col("start") + over)
    )


alarms = pl.DataFrame(
    {
        "start": [
            datetime.datetime.fromisoformat("2025-01-01 08:00:00"),
            datetime.datetime.fromisoformat("2026-01-01 08:00:00"),
        ]
    }
).join(
    pl.DataFrame({"users": range(1 << 12)}),
    how="cross",
)

print(
    snooze(
        alarms,
        over=datetime.timedelta(hours=1),
        frequency=datetime.timedelta(minutes=10),
    )
)

Log output

Issue description

The performance and memory usage of join_where have respectively decreased and increased dramatically in version 1.19 and remained stable after that, 1.22 being the latest version I tried. The above reproducer is ~30x slower and ~150x more memory hungry in 1.19 than it is in 1.18:

The changelog for 1.19 mentions this change: https://github.com/pola-rs/polars/pull/20525/files.
Assuming this is the change that introduced the regression, I appreciate the convenience of being able to use arbitrary expressions. Is there any chance this is compatible with the old performance?

Expected behavior

Performance of inequality joins is 1 or 2 orders of magnitude better than that of a naive cartesian product + filter.

Installed versions

--------Version info---------
Polars:              1.18.0
Index type:          UInt32
Platform:            Linux-6.13.1-arch2-1-x86_64-with-glibc2.41
Python:              3.13.1 (main, Dec  4 2024, 18:05:56) [GCC 14.2.1 20240910]
LTS CPU:             False

----Optional dependencies----
adbc_driver_manager  <not installed>
altair               <not installed>
azure.identity       <not installed>
boto3                <not installed>
cloudpickle          <not installed>
connectorx           <not installed>
deltalake            <not installed>
fastexcel            <not installed>
fsspec               <not installed>
gevent               <not installed>
google.auth          <not installed>
great_tables         <not installed>
matplotlib           <not installed>
nest_asyncio         <not installed>
numpy                <not installed>
openpyxl             <not installed>
pandas               <not installed>
pyarrow              <not installed>
pydantic             <not installed>
pyiceberg            <not installed>
sqlalchemy           <not installed>
torch                <not installed>
xlsx2csv             <not installed>
xlsxwriter           <not installed>

---

--------Version info---------
Polars:              1.19.0
Index type:          UInt32
Platform:            Linux-6.13.1-arch2-1-x86_64-with-glibc2.41
Python:              3.13.1 (main, Dec  4 2024, 18:05:56) [GCC 14.2.1 20240910]
LTS CPU:             False

----Optional dependencies----
adbc_driver_manager  <not installed>
altair               <not installed>
azure.identity       <not installed>
boto3                <not installed>
cloudpickle          <not installed>
connectorx           <not installed>
deltalake            <not installed>
fastexcel            <not installed>
fsspec               <not installed>
gevent               <not installed>
google.auth          <not installed>
great_tables         <not installed>
matplotlib           <not installed>
nest_asyncio         <not installed>
numpy                <not installed>
openpyxl             <not installed>
pandas               <not installed>
pyarrow              <not installed>
pydantic             <not installed>
pyiceberg            <not installed>
sqlalchemy           <not installed>
torch                <not installed>
xlsx2csv             <not installed>
xlsxwriter           <not installed>

[ritchie46]

@nameexhaustion can you check if it is related to the predicate_pushdown flag?

[nameexhaustion]

• I'm not sure about the flag yet, but a bisect points to feat: Support arbitrary expressions in 'join_where' #20525

Note that the reproducible example provided also runs fully in eager.

[ypsah]

Thanks, appreciate it. 👍