How do I tell Postgres to only scan the newest values in this query?

Question

I have a big table with sensor measurements that has this structure:

create table measurements (
  sensor_id    varchar(50)      not null,
  timestamp    timestamptz      not null,
  value        decimal(10, 6)   not null,
  primary key (sensor_id, timestamp)
)

It contains measurements from sensors (rain gauges, but that doesn't really matter) taken at 5 minute intervals. Sensor values can be 0 or positive, but not negative. Currently the dataset goes back a bit more than one year, but it should be able to handle years of data.

I want to retrieve the most recent measurements per sensor for further analysis, such that I get at least two weeks worth of measurements, and the set of measurements should contain at least 100 non-zero values. The query I used is this:

select *
from (
    select sensor_id, timestamp, "value",
      sum(cast("value" > 0 as INT)) over w as cum_nonzero_measurements,
      row_number() over w as cum_measurements,
      first_value(timestamp) over w - timestamp as age
    from measurements
    window w as (partition by sensor_id order by timestamp desc)
    ) windowed
where (cum_nonzero_measurements <= 100 or age < interval '2 weeks' )
  and sensor_id in ($1)
order by sensor_id, timestamp desc

This query only needs the most recent N measurements for a sensor, although N can vary. The smart way to execute such a query would be to start reading from the most recent value going backward in time. However Postgresql doesn't realize the query can be executed in that way, and insists on loading all measurements for the given sensor_ids, doing a window aggregation over all rows, and only then filtering out most of the rows to get the result.

I tried with different indices, which helps it retrieve all rows for the requested sensors more quickly, but whatever I do Postgres keeps loading all rows for the sensors in question. Currently the performance is acceptable, but that doesn't scale very well if the dataset grows.

Is there any way to convince Postgres that it doesn't need to load all the rows, only the most recent ones?

Answer 1

It's the classic "Top-N by category" problem, with a bit of a plot twist.

Fastest solution will probably be a lateral join. This allows executing a join with a dependent subquery.

If you have a separate table listing the sensor_ids, it is very simple. The idea is exactly what you wrote in your question: for each sensor_id, start reading from the most recent value going backward in time.

Here's a quick test case which gets the most recent 100 values for all sensors:

create unlogged table measurements (
  sensor_id    int       not null,
  timestamp    float       not null,
  value        decimal(10, 6)   not null,
  primary key (sensor_id, timestamp)
);

insert into measurements 
select random()*100, n, case when random()>0.5 then random() else 0 end 
from generate_series( 1, 1000000 ) n;

vacuum analyze measurements;

CREATE UNLOGGED TABLE sensors AS SELECT sensor_id FROM measurements GROUP BY sensor_id;

EXPLAIN ANALYZE SELECT *
FROM sensors s
CROSS JOIN LATERAL (SELECT * FROM measurements m WHERE m.sensor_id = s.sensor_id ORDER BY timestamp DESC LIMIT 200) top;

It does a nested loop on sensors, then index scan backwards on measurements. To get only specific sensors:

SELECT *
FROM (VALUES (1),(2),(3)) s
CROSS JOIN LATERAL (SELECT * FROM measurements m WHERE m.sensor_id = s.column1 ORDER BY timestamp DESC LIMIT 100) top;

Contrary to a regular join, the table expression in the lateral join is dependent on s.column1 from previous tables. It is re-evaluated for each row from VALUES() and the limit is applied. This is what makes it work. Without LATERAL, the table expression in the join would only be applied once, so the LIMIT would only be applied once, instead of per sensor which is what you want.

Rather than VALUES() you can also put the sensor_id's in an array and unnest() it.

However, that only gives the 100 most recent values, which is not what you want! Here's a suggestion:

SELECT *
FROM (VALUES (1),(2),(3)) s
CROSS JOIN LATERAL (SELECT * FROM measurements m WHERE m.sensor_id = s.column1 AND value>0 ORDER BY timestamp DESC LIMIT 1 OFFSET 99) first
CROSS JOIN LATERAL (SELECT * FROM measurements m WHERE m.sensor_id = s.column1 AND timestamp >= first.timestamp ORDER BY timestamp DESC LIMIT 200) top;

The first lateral join has "value>0" in the WHERE condition so it only considers these rows. Thanks to the limit/offset, it skips 99 rows going backward in time, then grabs the timestamp for this row, which is used as a starting point for the second lateral join which simply returns all rows posterior to this timestamp.

In both cases, it will use the index, so it should not read rows far into the past and therefore should not slow down as table size increases.