What does this function return when there are two datapoints (x, y0) and (x, y1) and you need a fill for (x, NULL)? One of the two y values (doesn't matter which one because their order isn't well defined anyway), or the midpoint, or NaN, or user's choice of one?

Hi DuckDB Team!

I started this original discussion on Discord and wanted to chime in to clarify this functionality, and why it'll be a very important and valuable addition to DuckDB.

Importance

Code Simplicity

Currently, the fill and transformation functionality is implemented through SQL, rather than natively with DuckDB. This makes queries complex.

For example, this is a linear fill implementation in DuckDB: https://stackoverflow.com/a/77588520. Pairing a transformation function with a fill would be even more complicated. Adding these features would make queries much easier to write.

The current core DuckDB implementation uses C++, and various extensions are made with Rust. Could implementing these features in core DuckDB or as an extension result in speed, memory, or I/O performance improvements?

If these features were to be implemented as code, then new features (e.g., Cubic Spline Interpolation) can be added in the future. Could these features make a good usecase for a core extension?

Feature Support

DuckDB is used for time-series data analysis, see blog: https://motherduck.com/glossary/time-series and time-series forecasting with DuckDB: https://github.com/evidence-dev/sql-prophet.

There are a number of time-series datases such as InfluxDB, QuestDB, TimescaleDB, and Amazon Time Stream that support fill and transformation functionality. Other columnar databases such as ClickHouse have implemented fill functionality.

InfluxDB

• Fill: https://docs.influxdata.com/influxdb/v2/query-data/influxql/explore-data/group-by/#group-by-time-intervals-and-fill

• Transformations: https://docs.influxdata.com/influxdb/v2/query-data/influxql/functions/transformations/

• Example Query (fill = linear, transformation = derivative)

SELECT 
    time,
    DERIVATIVE(last(field), 1h) AS field 
FROM table
WHERE id = 'id' 
AND time >= start_time AND time <= end_time 
GROUP BY time(1h) fill(linear)

QuestDB

• Fill: https://questdb.com/docs/reference/sql/sample-by/#fill-options

• Example Query (fill = linear, transformation = derivative)

SELECT
    time,
    DERIVATIVE(last(field)) AS field
FROM table
SAMPLE BY 1h
FILL(LINEAR)

TimescaleDB

• Fill: https://www.timescale.com/blog/sql-functions-for-time-series-analysis

• Example Query (fill = linear, transformation = derivative)

WITH sampled AS (
    SELECT
        time_bucket('1 hour', time) AS bucket,
        interpolate(last(field, time)) AS field
    FROM table
    GROUP BY bucket
),
with_derivative AS (
    SELECT
        bucket,
        field,
        (field - LAG(field) OVER (ORDER BY bucket)) / extract(epoch FROM (bucket - LAG(bucket) OVER (ORDER BY bucket))) AS field_derivative
    FROM sampled
)
SELECT bucket AS time, field_derivative
FROM with_derivative;

Amazon Time Stream

• Fill: https://docs.aws.amazon.com/timestream/latest/developerguide/timeseries-specific-constructs.functions.interpolation.html

• Example Query (fill = linear)

...
SELECT hostname,
    INTERPOLATE_LINEAR(
        CREATE_TIME_SERIES(binned_timestamp, avg_cpu_utilization),
            SEQUENCE(min(binned_timestamp), max(binned_timestamp), 15s)) AS interpolated_avg_cpu_utilization
FROM binned_timeseries
GROUP BY hostname
...

ClickHouse

• Fill: https://clickhouse.com/docs/guides/developer/time-series-filling-gaps

• Issue shows how difficult implementing this functionality is: ClickHouse Upsampling Time Series ClickHouse/ClickHouse#38206

• Complicated Example Query (fill = linear)

WITH
    toDateTime('{start}') AS start_time,
    toDateTime('{end}') AS end_time
SELECT
    bucket,
    if(
        field IS NULL AND prev_field IS NOT NULL AND next_field IS NOT NULL,
        prev_field + (next_field - prev_field) * dateDiff('second', prev_time, bucket) / nullIf(dateDiff('second', prev_time, next_time), 0),
        field
    ) AS filled_field
FROM (
    SELECT
        bucket,
        field,
        lag(bucket) OVER (ORDER BY bucket) AS prev_time,
        lag(field) OVER (ORDER BY bucket) AS prev_field,
        lead(bucket) OVER (ORDER BY bucket) AS next_time,
        lead(field) OVER (ORDER BY bucket) AS next_field
    FROM (
        SELECT
            toStartOfInterval(timestamp, INTERVAL 1 HOUR) AS bucket,
            anyLast(field) AS field
        FROM your_table
        WHERE timestamp BETWEEN start_time AND end_time
        GROUP BY bucket
        ORDER BY bucket
        WITH FILL
        FROM start_time
        TO end_time
        STEP INTERVAL 1 HOUR
    )
)

Fill Behaviors

Reading up on documentation from the primary time-series database providers' implementations is recommended.

LINEAR Fill

• Behavior: Performs linear interpolation between existing data points.
• We can only look 1 row forward, and 1 row backwards.
• This means we can look before the defined start time and past the end time to interpolate a NULL value if it occurs on the boundary.

let x = current time
let x1 = next time
let x0 = previous time

let y = current value (this is what we are linearly interpolating)
let y1 = next value
let y0 = previous value

Formula: y = y0 + (y1 - y0) * (x - x0) / (x1 - x0)

PREVIOUS Fill

• Behavior: Looks back to find the previous non-NULL value for a column.
• Cannot look beyond the time boundaries, if they are set.
• Should implement PARTITION BY functionality to ensure we are not just selecting an arbitrary non-NULL value.
• Edge case: If we are selecting multiple columns, we might run into the case where we look back an unequal number of rows for different columns.
  • Example: Column A we look back 1 row, Column B we look back 5 rows to fill the NULL value using previous fill.

NULL Fill

• Behavior: Bins that are otherwise completely missing will be returned with NULLs.
• Useful when downstream processes need to know exact gap positions.

NONE Fill

• Behavior: Bins with NULL are omitted entirely from the final result.
• Useful when only actual measurements matter.

Transformation Functions

DIFFERENCE Transformation

• Behavior: Calculates difference between consecutive values (current - previous), if the difference is negative, returns 0.

DERIVATIVE Transformation

• Behavior: Calculates rate of change between consecutive values.
• Similar to linear fill, except that we normalize the value by the period.

let x = current time
let x1 = next time
let x0 = previous time

let y = current value (this is what we are linearly interpolating)
let y1 = next value
let y0 = previous value

let p = period

Formula: y = (y0 + (y1 - y0) * (x - x0) / (x1 - x0)) / period

NON-NEGATIVE Variants

• Both the difference and derivative transformation functions contain non-negative variants.
• Behaviour: When using the non-negative variant, if the result of the transformation function is negative, return 0.

Compatibility with Aggregate Functions

The fill window function, and transformation functions should work seamlessly with existing aggregate functions such as:

• LAST
• FIRST
• MIN
• MAX
• AVG
• SUM

Just wanted to say thank you @hawkfish for both of the PRs #17686 and #17821!

I will test my queries against your implementation of linear interpolation fill, and report back here.

Hey @hawkfish (Richard), we tested your feature -- works great and as expected! Thank you again!