Postgres 15

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
CREATE TABLE foobar (
  "id" INTEGER,
  "group" INTEGER,
  "foo" INTEGER,
  "bar" INTEGER,
  "timestamp" INTEGER);
INSERT INTO foobar VALUES
  ('1', '1', '10', '20', '1'),
  ('2', '1', '11', '19', '2'),
  ('3', '1', '10', '20', '3'),
  ('4', '1', '10', '20', '4'),
  ('5', '2', '99', '99', '1'),
  ('6', '2', '99', '99', '2'),
  ('7', '2', '99', '99', '3'),
  ('8', '2', '33', '33', '4')
returning *;

CREATE TABLE

id
group
foo
bar
timestamp

1
1
10
20
1

2
1
11
19
2

3
1
10
20
3

4
1
10
20
4

5
2
99
99
1

6
2
99
99
2

7
2
99
99
3

8
2
33
33
4

INSERT 0 8

--https://stackoverflow.com/a/78448293/5298879
select distinct on("group") id,"group",foo,bar,"timestamp"
from (select *,coalesce(   foo<>lead(foo)over w1
                        or bar<>lead(bar)over w1,true) is_diff_from_prev
      from foobar
      window w1 as (partition by "group" order by "timestamp" desc))_
where is_diff_from_prev
order by "group","timestamp" desc;

id
group
foo
bar
timestamp

3
1
10
20
3

8
2
33
33
4

SELECT 2

--https://stackoverflow.com/a/78447998/5298879
select min(fb1."id"),fb1."group", fb1."foo", fb1."bar", min(fb1."timestamp") as "timestamp"
from foobar fb1
left join foobar fb2
on fb1."group" = fb2."group" and
   fb2."timestamp" > fb1."timestamp" and
   (fb2."foo" <> fb1."foo" or fb2."bar" <> fb1."bar")
left join foobar fb3
on fb1."group" = fb3."group" and
   fb3."timestamp" < fb1."timestamp" and
   fb3."foo" = fb1."foo" and
   fb3."bar" = fb1."bar"
left join foobar fb4
on fb4."group" = fb1."group" and
   fb4."timestamp" < fb1."timestamp" and fb4."timestamp" > fb3."timestamp" and
   (fb4."foo" <> fb1."foo" or fb4."bar" <> fb1."bar")
where fb2."group" is null and (fb3."group" is null or fb4."group" is not null)
group by fb1."group", fb1."foo", fb1."bar"

min
group
foo
bar
timestamp

3
1
10
20
3

8
2
33
33
4

SELECT 2

select now(),setseed(.42),version();
--generating samples
insert into foobar
select n
      ,random()*4e3
      ,random()*3
      ,random()*3
      ,n
from generate_series(9,2e5)n;

create index idx1 on foobar("group","timestamp",bar,foo)with(fillfactor=100);
create index idx2 on foobar("group","timestamp",foo,bar)with(fillfactor=100);

now
setseed
version

2024-05-08 16:38:22.81528+01

PostgreSQL 15.0 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 8.5.0 20210514 (Red Hat 8.5.0-10), 64-bit

SELECT 1

INSERT 0 199992

CREATE INDEX

CREATE INDEX

vacuum analyze foobar;

VACUUM

--inspecting samples
select "group",array_agg((foo,bar) order by "timestamp" desc) 
from (select *,row_number()over(partition by "group" order by "timestamp" desc) 
      from foobar)_
where 5>row_number
group by 1 order by 1 limit 5;

--groups with at least 3 last updates with the same (foo,bar)
select * from (
  select "group",array_agg((foo,bar) order by "timestamp" desc) 
  from (select *,row_number()over(partition by "group" order by "timestamp" desc) 
        from foobar)_
  where 5>row_number
  group by 1)_
where array_agg[1]=array_agg[2]
order by 1 limit 5;

select count(*) from (
  select "group",array_agg((foo,bar) order by "timestamp" desc) 
  from (select *,row_number()over(partition by "group" order by "timestamp" desc) 
        from foobar)_
  where 3>row_number
  group by 1)_
where array_agg[1]=array_agg[2];

group
array_agg

0
{"(1,2)","(0,1)","(0,1)","(2,3)"}

1
{"(0,3)","(3,2)","(1,0)","(2,2)"}

2
{"(0,1)","(2,1)","(1,1)","(2,0)"}

3
{"(0,2)","(1,0)","(1,1)","(0,1)"}

4
{"(0,3)","(0,2)","(3,2)","(2,2)"}

SELECT 5

group
array_agg

15
{"(2,1)","(2,1)","(1,0)","(1,1)"}

25
{"(2,2)","(2,2)","(2,3)","(2,3)"}

45
{"(1,1)","(1,1)","(2,1)","(2,2)"}

56
{"(2,2)","(2,2)","(2,2)","(2,0)"}

64
{"(1,2)","(1,2)","(2,1)","(3,3)"}

SELECT 5

count

292

SELECT 1

--apples-to-apples, no parallel execution
set max_parallel_workers=0;
set max_parallel_workers_per_gather=0;

explain analyze verbose 
--https://stackoverflow.com/a/78448293/5298879
select distinct on("group") id,"group",foo,bar,"timestamp"
from (select *,coalesce(   foo<>lead(foo)over w1
                        or bar<>lead(bar)over w1,true) is_diff_from_prev
      from foobar
      window w1 as (partition by "group" order by "timestamp" desc))_
where is_diff_from_prev
order by "group","timestamp" desc;

SET

SET

QUERY PLAN

Result  (cost=5.48..30310.59 rows=4002 width=20) (actual time=0.166..2692.906 rows=4001 loops=1)

  Output: _.id, _."group", _.foo, _.bar, _."timestamp"

  ->  Unique  (cost=5.48..30310.59 rows=4002 width=20) (actual time=0.165..2691.773 rows=4001 loops=1)

        Output: _.id, _."group", _.foo, _.bar, _."timestamp", _.is_diff_from_prev

        ->  Subquery Scan on _  (cost=5.48..30060.59 rows=100000 width=20) (actual time=0.152..2624.103 rows=185011 loops=1)

              Output: _.id, _."group", _.foo, _.bar, _."timestamp", _.is_diff_from_prev

              Filter: _.is_diff_from_prev

              Rows Removed by Filter: 14989

              ->  WindowAgg  (cost=5.48..28060.59 rows=200000 width=21) (actual time=0.151..2494.013 rows=200000 loops=1)

                    Output: foobar.id, foobar."group", foobar.foo, foobar.bar, foobar."timestamp", COALESCE(((foobar.foo <> lead(foobar.foo) OVER (?)) OR (foobar.bar <> lead(foobar.bar) OVER (?))), true)

                    ->  Incremental Sort  (cost=5.48..23060.59 rows=200000 width=20) (actual time=0.128..1598.427 rows=200000 loops=1)

                          Output: foobar."group", foobar."timestamp", foobar.id, foobar.foo, foobar.bar

                          Sort Key: foobar."group", foobar."timestamp" DESC

                          Presorted Key: foobar."group"

                          Full-sort Groups: 3994  Sort Method: quicksort  Average Memory: 29kB  Peak Memory: 29kB

                          Pre-sorted Groups: 96  Sort Method: quicksort  Average Memory: 26kB  Peak Memory: 26kB

                          ->  Index Scan using idx2 on public.foobar  (cost=0.42..10888.41 rows=200000 width=20) (actual time=0.015..815.431 rows=200000 loops=1)

                                Output: foobar."group", foobar."timestamp", foobar.id, foobar.foo, foobar.bar

Planning Time: 0.206 ms

Execution Time: 2693.386 ms

EXPLAIN

--apples-to-apples, no parallel execution
set max_parallel_workers=0;
set max_parallel_workers_per_gather=0;

explain analyze verbose
--https://stackoverflow.com/a/78447998/5298879
select min(fb1."id"),fb1."group", fb1."foo", fb1."bar", min(fb1."timestamp") as "timestamp"
from foobar fb1
left join foobar fb2
on fb1."group" = fb2."group" and
   fb2."timestamp" > fb1."timestamp" and
   (fb2."foo" <> fb1."foo" or fb2."bar" <> fb1."bar")
left join foobar fb3
on fb1."group" = fb3."group" and
   fb3."timestamp" < fb1."timestamp" and
   fb3."foo" = fb1."foo" and
   fb3."bar" = fb1."bar"
left join foobar fb4
on fb4."group" = fb1."group" and
   fb4."timestamp" < fb1."timestamp" and fb4."timestamp" > fb3."timestamp" and
   (fb4."foo" <> fb1."foo" or fb4."bar" <> fb1."bar")
where fb2."group" is null and (fb3."group" is null or fb4."group" is not null)
group by fb1."group", fb1."foo", fb1."bar"

SET

SET

QUERY PLAN

GroupAggregate  (cost=55002.98..191025.51 rows=20000 width=20) (actual time=2450.778..4706.277 rows=4001 loops=1)

  Output: min(fb1.id), fb1."group", fb1.foo, fb1.bar, min(fb1."timestamp")

  Group Key: fb1."group", fb1.foo, fb1.bar

  ->  Nested Loop Left Join  (cost=55002.98..179749.59 rows=886073 width=20) (actual time=2450.706..4371.575 rows=371407 loops=1)

        Output: fb1."group", fb1.foo, fb1.bar, fb1.id, fb1."timestamp"

        Filter: ((fb3."group" IS NULL) OR (fb4."group" IS NOT NULL))

        Rows Removed by Filter: 378

        ->  Merge Left Join  (cost=55002.56..68415.96 rows=171557 width=28) (actual time=2450.666..3013.242 rows=16829 loops=1)

              Output: fb1.id, fb1."group", fb1.foo, fb1.bar, fb1."timestamp", fb3."group", fb3."timestamp"

              Merge Cond: ((fb1."group" = fb3."group") AND (fb1.foo = fb3.foo) AND (fb1.bar = fb3.bar))

              Join Filter: (fb3."timestamp" < fb1."timestamp")

              Rows Removed by Join Filter: 4712

              ->  Sort  (cost=30699.42..31032.75 rows=133333 width=20) (actual time=1593.398..1649.460 rows=4334 loops=1)

                    Output: fb1.id, fb1."group", fb1.foo, fb1.bar, fb1."timestamp"

                    Sort Key: fb1."group", fb1.foo, fb1.bar

                    Sort Method: quicksort  Memory: 463kB

                    ->  Hash Anti Join  (cost=6751.00..16612.66 rows=133333 width=20) (actual time=870.759..1535.905 rows=4334 loops=1)

                          Output: fb1.id, fb1."group", fb1.foo, fb1.bar, fb1."timestamp"

                          Hash Cond: (fb1."group" = fb2."group")

                          Join Filter: ((fb2."timestamp" > fb1."timestamp") AND ((fb2.foo <> fb1.foo) OR (fb2.bar <> fb1.bar)))

                          Rows Removed by Join Filter: 232864

                          ->  Seq Scan on public.foobar fb1  (cost=0.00..3274.00 rows=200000 width=20) (actual time=0.010..72.978 rows=200000 loops=1)

                                Output: fb1.id, fb1."group", fb1.foo, fb1.bar, fb1."timestamp"

                          ->  Hash  (cost=3274.00..3274.00 rows=200000 width=16) (actual time=466.017..466.018 rows=200000 loops=1)

                                Output: fb2."group", fb2."timestamp", fb2.foo, fb2.bar

                                Buckets: 262144  Batches: 2  Memory Usage: 6772kB

                                ->  Seq Scan on public.foobar fb2  (cost=0.00..3274.00 rows=200000 width=16) (actual time=0.010..187.081 rows=200000 loops=1)

                                      Output: fb2."group", fb2."timestamp", fb2.foo, fb2.bar

              ->  Materialize  (cost=24303.14..25303.14 rows=200000 width=16) (actual time=857.249..1267.854 rows=202153 loops=1)

                    Output: fb3."group", fb3."timestamp", fb3.foo, fb3.bar

                    ->  Sort  (cost=24303.14..24803.14 rows=200000 width=16) (actual time=857.243..1126.561 rows=199979 loops=1)

                          Output: fb3."group", fb3."timestamp", fb3.foo, fb3.bar

                          Sort Key: fb3."group", fb3.foo, fb3.bar

                          Sort Method: external merge  Disk: 5096kB

                          ->  Seq Scan on public.foobar fb3  (cost=0.00..3274.00 rows=200000 width=16) (actual time=0.020..195.633 rows=200000 loops=1)

                                Output: fb3."group", fb3."timestamp", fb3.foo, fb3.bar

        ->  Index Only Scan using idx2 on public.foobar fb4  (cost=0.42..0.60 rows=5 width=16) (actual time=0.027..0.054 rows=22 loops=16829)

              Output: fb4."group", fb4."timestamp", fb4.foo, fb4.bar

              Index Cond: ((fb4."group" = fb1."group") AND (fb4."timestamp" < fb1."timestamp") AND (fb4."timestamp" > fb3."timestamp"))

              Filter: ((fb4.foo <> fb1.foo) OR (fb4.bar <> fb1.bar))

              Rows Removed by Filter: 2

              Heap Fetches: 0

Planning Time: 0.756 ms

Execution Time: 4707.440 ms

EXPLAIN

--unlocking parallel execution achieves matching performance, at CPU cost
set max_parallel_workers=8;
set max_parallel_workers_per_gather=8;

explain analyze verbose
--https://stackoverflow.com/a/78447998/5298879
select min(fb1."id"),fb1."group", fb1."foo", fb1."bar", min(fb1."timestamp") as "timestamp"
from foobar fb1
left join foobar fb2
on fb1."group" = fb2."group" and
   fb2."timestamp" > fb1."timestamp" and
   (fb2."foo" <> fb1."foo" or fb2."bar" <> fb1."bar")
left join foobar fb3
on fb1."group" = fb3."group" and
   fb3."timestamp" < fb1."timestamp" and
   fb3."foo" = fb1."foo" and
   fb3."bar" = fb1."bar"
left join foobar fb4
on fb4."group" = fb1."group" and
   fb4."timestamp" < fb1."timestamp" and fb4."timestamp" > fb3."timestamp" and
   (fb4."foo" <> fb1."foo" or fb4."bar" <> fb1."bar")
where fb2."group" is null and (fb3."group" is null or fb4."group" is not null)
group by fb1."group", fb1."foo", fb1."bar"

SET

SET

QUERY PLAN

Finalize HashAggregate  (cost=113033.06..113233.06 rows=20000 width=20) (actual time=2680.045..2686.195 rows=4001 loops=1)

  Output: min(fb1.id), fb1."group", fb1.foo, fb1.bar, min(fb1."timestamp")

  Group Key: fb1."group", fb1.foo, fb1.bar

  Batches: 1  Memory Usage: 1297kB

  ->  Gather  (cost=110583.06..112783.06 rows=20000 width=20) (actual time=2594.684..2683.308 rows=4154 loops=1)

        Output: fb1."group", fb1.foo, fb1.bar, (PARTIAL min(fb1.id)), (PARTIAL min(fb1."timestamp"))

        Workers Planned: 1

        Workers Launched: 1

        ->  Partial HashAggregate  (cost=109583.06..109783.06 rows=20000 width=20) (actual time=2539.970..2540.630 rows=2077 loops=2)

              Output: fb1."group", fb1.foo, fb1.bar, PARTIAL min(fb1.id), PARTIAL min(fb1."timestamp")

              Group Key: fb1."group", fb1.foo, fb1.bar

              Batches: 1  Memory Usage: 1041kB

              Worker 0:  actual time=2485.710..2486.352 rows=1990 loops=1

                Batches: 1  Memory Usage: 1041kB

              ->  Nested Loop Left Join  (cost=8430.77..103067.82 rows=521219 width=20) (actual time=934.875..1970.568 rows=185704 loops=2)

                    Output: fb1."group", fb1.foo, fb1.bar, fb1.id, fb1."timestamp"

                    Filter: ((fb3."group" IS NULL) OR (fb4."group" IS NOT NULL))

                    Rows Removed by Filter: 189

                    Worker 0:  actual time=878.144..1847.449 rows=178562 loops=1

                    ->  Parallel Hash Left Join  (cost=8430.35..37577.37 rows=100916 width=28) (actual time=934.784..1298.209 rows=8414 loops=2)

                          Output: fb1.id, fb1."group", fb1.foo, fb1.bar, fb1."timestamp", fb3."group", fb3."timestamp"

                          Hash Cond: ((fb1."group" = fb3."group") AND (fb1.foo = fb3.foo) AND (fb1.bar = fb3.bar))

                          Join Filter: (fb3."timestamp" < fb1."timestamp")

                          Rows Removed by Join Filter: 2356

                          Worker 0:  actual time=877.991..1205.300 rows=8111 loops=1

                          ->  Parallel Hash Anti Join  (cost=3921.06..8195.05 rows=78431 width=20) (actual time=539.107..858.264 rows=2167 loops=2)

                                Output: fb1.id, fb1."group", fb1.foo, fb1.bar, fb1."timestamp"

                                Hash Cond: (fb1."group" = fb2."group")

                                Join Filter: ((fb2."timestamp" > fb1."timestamp") AND ((fb2.foo <> fb1.foo) OR (fb2.bar <> fb1.bar)))

                                Rows Removed by Join Filter: 116725

                                Worker 0:  actual time=535.799..782.033 rows=2071 loops=1

                                ->  Parallel Seq Scan on public.foobar fb1  (cost=0.00..2450.47 rows=117647 width=20) (actual time=0.007..70.120 rows=100000 loops=2)

                                      Output: fb1.id, fb1."group", fb1.foo, fb1.bar, fb1."timestamp"

                                      Worker 0:  actual time=0.007..131.986 rows=105818 loops=1

                                ->  Parallel Hash  (cost=2450.47..2450.47 rows=117647 width=16) (actual time=301.301..301.302 rows=100000 loops=2)

                                      Output: fb2."group", fb2."timestamp", fb2.foo, fb2.bar

                                      Buckets: 262144  Batches: 1  Memory Usage: 11456kB

                                      Worker 0:  actual time=305.480..305.481 rows=94496 loops=1

                                      ->  Parallel Seq Scan on public.foobar fb2  (cost=0.00..2450.47 rows=117647 width=16) (actual time=0.013..83.702 rows=100000 loops=2)

                                            Output: fb2."group", fb2."timestamp", fb2.foo, fb2.bar

                                            Worker 0:  actual time=0.017..148.702 rows=94496 loops=1

                          ->  Parallel Hash  (cost=2450.47..2450.47 rows=117647 width=16) (actual time=389.351..389.352 rows=100000 loops=2)

                                Output: fb3."group", fb3."timestamp", fb3.foo, fb3.bar

                                Buckets: 262144  Batches: 1  Memory Usage: 11456kB

                                Worker 0:  actual time=342.163..342.164 rows=71574 loops=1

                                ->  Parallel Seq Scan on public.foobar fb3  (cost=0.00..2450.47 rows=117647 width=16) (actual time=0.012..171.250 rows=100000 loops=2)

                                      Output: fb3."group", fb3."timestamp", fb3.foo, fb3.bar

                                      Worker 0:  actual time=0.015..78.474 rows=71574 loops=1

                    ->  Index Only Scan using idx2 on public.foobar fb4  (cost=0.42..0.60 rows=5 width=16) (actual time=0.013..0.048 rows=22 loops=16829)

                          Output: fb4."group", fb4."timestamp", fb4.foo, fb4.bar

                          Index Cond: ((fb4."group" = fb1."group") AND (fb4."timestamp" < fb1."timestamp") AND (fb4."timestamp" > fb3."timestamp"))

                          Filter: ((fb4.foo <> fb1.foo) OR (fb4.bar <> fb1.bar))

                          Rows Removed by Filter: 2

                          Heap Fetches: 0

                          Worker 0:  actual time=0.005..0.038 rows=22 loops=8111

Planning Time: 0.927 ms

Execution Time: 2686.625 ms

EXPLAIN

--unlocking parallel execution achieves matching performance, at CPU cost
set max_parallel_workers=8;
set max_parallel_workers_per_gather=8;

explain analyze verbose 
--https://stackoverflow.com/a/78448293/5298879
select distinct on("group") id,"group",foo,bar,"timestamp"
from (select *,coalesce(   foo<>lead(foo)over w1
                        or bar<>lead(bar)over w1,true) is_diff_from_prev
      from foobar
      window w1 as (partition by "group" order by "timestamp" desc))_
where is_diff_from_prev
order by "group","timestamp" desc;

SET

SET

QUERY PLAN

Result  (cost=5.48..30310.59 rows=4002 width=20) (actual time=0.145..2867.102 rows=4001 loops=1)

  Output: _.id, _."group", _.foo, _.bar, _."timestamp"

  ->  Unique  (cost=5.48..30310.59 rows=4002 width=20) (actual time=0.144..2866.016 rows=4001 loops=1)

        Output: _.id, _."group", _.foo, _.bar, _."timestamp", _.is_diff_from_prev

        ->  Subquery Scan on _  (cost=5.48..30060.59 rows=100000 width=20) (actual time=0.144..2743.175 rows=185011 loops=1)

              Output: _.id, _."group", _.foo, _.bar, _."timestamp", _.is_diff_from_prev

              Filter: _.is_diff_from_prev

              Rows Removed by Filter: 14989

              ->  WindowAgg  (cost=5.48..28060.59 rows=200000 width=21) (actual time=0.143..2722.778 rows=200000 loops=1)

                    Output: foobar.id, foobar."group", foobar.foo, foobar.bar, foobar."timestamp", COALESCE(((foobar.foo <> lead(foobar.foo) OVER (?)) OR (foobar.bar <> lead(foobar.bar) OVER (?))), true)

                    ->  Incremental Sort  (cost=5.48..23060.59 rows=200000 width=20) (actual time=0.135..1522.621 rows=200000 loops=1)

                          Output: foobar."group", foobar."timestamp", foobar.id, foobar.foo, foobar.bar

                          Sort Key: foobar."group", foobar."timestamp" DESC

                          Presorted Key: foobar."group"

                          Full-sort Groups: 3994  Sort Method: quicksort  Average Memory: 29kB  Peak Memory: 29kB

                          Pre-sorted Groups: 96  Sort Method: quicksort  Average Memory: 26kB  Peak Memory: 26kB

                          ->  Index Scan using idx2 on public.foobar  (cost=0.42..10888.41 rows=200000 width=20) (actual time=0.021..957.022 rows=200000 loops=1)

                                Output: foobar."group", foobar."timestamp", foobar.id, foobar.foo, foobar.bar

Planning Time: 0.175 ms

Execution Time: 2867.676 ms

EXPLAIN
group	array_agg
0	{"(1,2)","(0,1)","(0,1)","(2,3)"}
1	{"(0,3)","(3,2)","(1,0)","(2,2)"}
2	{"(0,1)","(2,1)","(1,1)","(2,0)"}
3	{"(0,2)","(1,0)","(1,1)","(0,1)"}
4	{"(0,3)","(0,2)","(3,2)","(2,2)"}
group	array_agg
15	{"(2,1)","(2,1)","(1,0)","(1,1)"}
25	{"(2,2)","(2,2)","(2,3)","(2,3)"}
45	{"(1,1)","(1,1)","(2,1)","(2,2)"}
56	{"(2,2)","(2,2)","(2,2)","(2,0)"}
64	{"(1,2)","(1,2)","(2,1)","(3,3)"}