window performance

[dxe4]

What happens?

window functions seem to be slow, there was a previous issue here #1367
i thought i should re-raise because this may help fix the issue.
pandas takes 1 sec, duckdb takes 30, maybe its worth checking the logic in pandas and see if you can do the same? i think its here https://github.com/pandas-dev/pandas/blob/main/pandas/_libs/window/aggregations.pyx

To Reproduce

file:
https://d37ci6vzurychx.cloudfront.net/trip-data/fhvhv_tripdata_2021-04.parquet

duckdb:

select
    sum(driver_pay) over _win,
    dropoff_datetime
from read_parquet("~/dev/data/taxi3/fhvhv_tripdata_2021-04.parquet")
WINDOW _win as (
        order by dropoff_datetime asc
        range between
        interval 3 days preceding and
        interval 0 days following
    )
)

pandas:

    df = pd.read_parquet(
        file1,
        columns=["driver_pay", "dropoff_datetime"],
    )
    df.index = pd.DatetimeIndex(df["dropoff_datetime"])
    df = df.sort_index()
    df = df.drop("dropoff_datetime", axis=1)
    df = df.rolling("3d").sum()

OS:

linux

DuckDB Version:

0.8

DuckDB Client:

latest

Full Name:

harry

Affiliation:

harry

Have you tried this on the latest master branch?

• I agree

Have you tried the steps to reproduce? Do they include all relevant data and configuration? Does the issue you report still appear there?

• I agree

[hkpeaks]

In a Windows 11, I used DuckDB 0.8.0 to convert 300 million rows csv to parquet file. Then run a python script, DuckDB 0.8.0 took less than 4 seconds to get the Filter2GroupBy results from the parquet file. If you want to compare your setting with mine, you can check out this video: https://youtu.be/gnIh6r7Gwh4. I have expereince using Polars to convert 1 billion rows csv to parquet, then Polars is able to use GroupBy to process the file, but fail in using Filter - no output. So you can use Pandas to convert the Parquet file to csv, then use DuckDB 0.8.0 to convert it back to parquet. You can compare the performance of 2 different version Parquet file. I believe CSV is the best file format to store data. It is very risky if meta data of Parquet file be corrupted. Keep CSV as a backup is mostly recommended.

[l1t1]

how many rows in the parquet file?
sum(driver_pay) over will return them all

[cmdlineluser]

@l1t1 There's 14,111,371 rows.

┌──────────────┐
│ count_star() │
│    int64     │
├──────────────┤
│     14111371 │
└──────────────┘

[l1t1]

how long it takes when run

select
    driver_pay,
    dropoff_datetime
from read_parquet("~/dev/data/taxi3/fhvhv_tripdata_2021-04.parquet")

[paultiq]

There's a discussion in discord #sql:

The issue is not related to the parquet load; the parquet read is under 2 seconds, and loading to a table first didn't help.

[hawkfish]

There are a number of obvious hot spots here:

• In WindowSegmentTree::WindowSegmentValue we construct two Vectors each time we compute a level of the tree. These can be preallocated.
• In the same function, the loop to generate the pointers has unnecessary multiplication
• Probably not important for this case but if the aggregate has a simple_update function, we should use it because we are only aggregating one value
• Because there is only one partition, the computations are single threaded. It may be possible to relax this with the current sorting code if the data is all fixed length.
• Finding RANGE frame boundaries may benefit from using the previous value as the start of the search instead of the midpoint of the frame as the common case uses fixed length offsets (as in this example).

[hawkfish]

Fixing the first two issues drops the run time on my laptop from 34s to 21s.

Another issue is that the data (driver_pay) appears to have NULLs and this triggers calls to ValidityMask::SliceInPlace, which is not optimised for the case where the target_offset is 0 (or at least aligned).

[hawkfish]

BTW I had a look at what pandas does and it is just a standard add/remove. Our segment trees are theoretically faster, but our internals seem to be creating roadblocks...