Postgres 15

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
Help with an interesting Postgres question: Why isn't an Index Only Scan used on a partition accessed via the parent table?.
CREATE TABLE tbl (
  id   int PRIMARY KEY
, part int NOT NULL
, ballast text
);

INSERT INTO tbl
SELECT g, g/3000  -- !
    , '0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789' -- 80 char
FROM   generate_series(1, 200000) g
ORDER  BY random();

CREATE UNIQUE INDEX tbl_part_id_idx ON tbl (part, id);

DELETE FROM tbl WHERE random() > .9;  -- some dead tuples

CREATE TABLE

INSERT 0 200000

CREATE INDEX

DELETE 20066

VACUUM ANALYZE tbl;

VACUUM

set work_mem = '384MB';

SET

-- org asc (idx only)
EXPLAIN ANALYZE
SELECT id, part
FROM  (
   SELECT *, row_number() OVER (PARTITION BY part ORDER BY id) AS rn
   FROM   tbl
   ) sub
WHERE  rn = 1;

QUERY PLAN

Subquery Scan on sub  (cost=0.42..10301.45 rows=900 width=8) (actual time=0.081..45.333 rows=67 loops=1)

  Filter: (sub.rn = 1)

  ->  WindowAgg  (cost=0.42..8052.28 rows=179934 width=48) (actual time=0.080..45.312 rows=67 loops=1)

        Run Condition: (row_number() OVER (?) <= 1)

        ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.067..34.652 rows=179934 loops=1)

              Heap Fetches: 0

Planning Time: 0.256 ms

Execution Time: 45.406 ms

EXPLAIN

-- org desc (Incremental Sort in pg 14+; additional sort step in pg 11)
EXPLAIN ANALYZE
SELECT id, part
FROM  (
   SELECT *, row_number() OVER (PARTITION BY part ORDER BY id DESC) AS rn
   FROM   tbl
   ) sub
WHERE  rn = 1;

QUERY PLAN

Subquery Scan on sub  (cost=493.11..40884.08 rows=900 width=8) (actual time=0.956..84.196 rows=67 loops=1)

  Filter: (sub.rn = 1)

  ->  WindowAgg  (cost=493.11..38634.90 rows=179934 width=48) (actual time=0.955..84.170 rows=67 loops=1)

        Run Condition: (row_number() OVER (?) <= 1)

        ->  Incremental Sort  (cost=493.11..35486.06 rows=179934 width=8) (actual time=0.949..70.223 rows=179934 loops=1)

              Sort Key: tbl.part, tbl.id DESC

              Presorted Key: tbl.part

              Full-sort Groups: 67  Sort Method: quicksort  Average Memory: 28kB  Peak Memory: 28kB

              Pre-sorted Groups: 67  Sort Method: quicksort  Average Memory: 245kB  Peak Memory: 247kB

              ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.016..25.621 rows=179934 loops=1)

                    Heap Fetches: 0

Planning Time: 0.193 ms

Execution Time: 84.259 ms

EXPLAIN

-- org desc, optmized with ROWS (Incremental Sort in pg 14+; additional sort step in pg 11)
EXPLAIN ANALYZE
SELECT id, part
FROM  (
   SELECT *, row_number() OVER (PARTITION BY part ORDER BY id DESC
                                ROWS UNBOUNDED PRECEDING) AS rn
   FROM   tbl
   ) sub
WHERE  rn = 1;

QUERY PLAN

Subquery Scan on sub  (cost=493.11..40884.08 rows=900 width=8) (actual time=0.922..84.432 rows=67 loops=1)

  Filter: (sub.rn = 1)

  ->  WindowAgg  (cost=493.11..38634.90 rows=179934 width=48) (actual time=0.921..84.404 rows=67 loops=1)

        Run Condition: (row_number() OVER (?) <= 1)

        ->  Incremental Sort  (cost=493.11..35486.06 rows=179934 width=8) (actual time=0.917..70.152 rows=179934 loops=1)

              Sort Key: tbl.part, tbl.id DESC

              Presorted Key: tbl.part

              Full-sort Groups: 67  Sort Method: quicksort  Average Memory: 28kB  Peak Memory: 28kB

              Pre-sorted Groups: 67  Sort Method: quicksort  Average Memory: 245kB  Peak Memory: 247kB

              ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.018..25.843 rows=179934 loops=1)

                    Heap Fetches: 0

Planning Time: 0.136 ms

Execution Time: 84.496 ms

EXPLAIN

-- Paul's query, adapted to get greatest id per group
EXPLAIN ANALYZE
SELECT id, part
FROM  (
   SELECT *
        , CASE WHEN part = lag(part) OVER (ORDER BY part DESC, id DESC)
               THEN 0
               ELSE 1
          END AS f
   FROM   tbl
   ) sub
WHERE  sub.f = 1;

QUERY PLAN

Subquery Scan on sub  (cost=0.42..10751.28 rows=900 width=8) (actual time=0.278..131.801 rows=67 loops=1)

  Filter: (sub.f = 1)

  Rows Removed by Filter: 179867

  ->  WindowAgg  (cost=0.42..8502.11 rows=179934 width=44) (actual time=0.278..122.405 rows=179934 loops=1)

        ->  Index Only Scan Backward using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.269..28.261 rows=179934 loops=1)

              Heap Fetches: 0

Planning Time: 0.145 ms

Execution Time: 131.856 ms

EXPLAIN

-- Paul's query, optimized (without index scan backward)
EXPLAIN ANALYZE
SELECT id, part
FROM  (
   SELECT *
        , CASE WHEN part = lead(part) OVER (ORDER BY part, id ROWS UNBOUNDED PRECEDING)
               THEN false 
               ELSE true END AS qualified
   FROM   tbl
   ) sub
WHERE  qualified;

QUERY PLAN

Subquery Scan on sub  (cost=0.42..10301.45 rows=89967 width=8) (actual time=1.696..108.786 rows=67 loops=1)

  Filter: sub.qualified

  Rows Removed by Filter: 179867

  ->  WindowAgg  (cost=0.42..8502.11 rows=179934 width=41) (actual time=0.021..100.138 rows=179934 loops=1)

        ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.016..27.431 rows=179934 loops=1)

              Heap Fetches: 0

Planning Time: 0.120 ms

Execution Time: 108.837 ms

EXPLAIN

-- DISTINCT ON is faster for few rows per group (seq scan)
EXPLAIN ANALYZE
SELECT DISTINCT ON (part) id, part
FROM   tbl
ORDER  BY part, id DESC

QUERY PLAN

Unique  (cost=31021.21..31920.88 rows=67 width=8) (actual time=100.285..124.092 rows=67 loops=1)

  ->  Sort  (cost=31021.21..31471.04 rows=179934 width=8) (actual time=100.282..110.770 rows=179934 loops=1)

        Sort Key: part, id DESC

        Sort Method: quicksort  Memory: 15985kB

        ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.018..27.361 rows=179934 loops=1)

              Heap Fetches: 0

Planning Time: 0.096 ms

Execution Time: 126.410 ms

EXPLAIN

-- DISTINCT ON is faster for few rows per group (seq scan)
EXPLAIN ANALYZE
SELECT DISTINCT ON (part) id, part
FROM   tbl
ORDER  BY part, id DESC;

QUERY PLAN

Unique  (cost=31021.21..31920.88 rows=67 width=8) (actual time=100.025..123.556 rows=67 loops=1)

  ->  Sort  (cost=31021.21..31471.04 rows=179934 width=8) (actual time=100.022..110.252 rows=179934 loops=1)

        Sort Key: part, id DESC

        Sort Method: quicksort  Memory: 15985kB

        ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.026..27.319 rows=179934 loops=1)

              Heap Fetches: 0

Planning Time: 0.104 ms

Execution Time: 125.755 ms

EXPLAIN

-- DISTINCT ON with matching index (your first query to get min id per group)
EXPLAIN ANALYZE
SELECT DISTINCT ON (part) id, part
FROM   tbl
ORDER  BY part, id;

QUERY PLAN

Result  (cost=0.42..5353.27 rows=67 width=8) (actual time=0.028..32.121 rows=67 loops=1)

  ->  Unique  (cost=0.42..5353.27 rows=67 width=8) (actual time=0.026..32.099 rows=67 loops=1)

        ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.025..21.971 rows=179934 loops=1)

              Heap Fetches: 0

Planning Time: 0.096 ms

Execution Time: 32.160 ms

EXPLAIN

-- rCTE is faster for more than a few rows per group (idx scan)
EXPLAIN ANALYZE
WITH RECURSIVE cte AS (
   (                                           -- parentheses required
   SELECT part, id
   FROM   tbl
   ORDER  BY part DESC, id DESC
   LIMIT  1
   )
   
   UNION ALL
   SELECT l.*
   FROM   cte c
   CROSS  JOIN LATERAL (
      SELECT t.part, t.id
      FROM   tbl t
      WHERE  t.part < c.part        -- lateral reference
      ORDER  BY t.part DESC, t.id DESC
      LIMIT  1
      ) l
   )
TABLE  cte;

QUERY PLAN

CTE Scan on cte  (cost=51.44..53.46 rows=101 width=8) (actual time=0.014..0.822 rows=67 loops=1)

  CTE cte

    ->  Recursive Union  (cost=0.42..51.44 rows=101 width=8) (actual time=0.013..0.800 rows=67 loops=1)

          ->  Limit  (cost=0.42..0.45 rows=1 width=8) (actual time=0.012..0.012 rows=1 loops=1)

                ->  Index Only Scan Backward using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.011..0.011 rows=1 loops=1)

                      Heap Fetches: 0

          ->  Nested Loop  (cost=0.42..4.90 rows=10 width=8) (actual time=0.010..0.010 rows=1 loops=67)

                ->  WorkTable Scan on cte c  (cost=0.00..0.20 rows=10 width=4) (actual time=0.000..0.000 rows=1 loops=67)

                ->  Limit  (cost=0.42..0.45 rows=1 width=8) (actual time=0.010..0.010 rows=1 loops=67)

                      ->  Index Only Scan Backward using tbl_part_id_idx on tbl t  (cost=0.42..1786.04 rows=59978 width=8) (actual time=0.009..0.009 rows=1 loops=67)

                            Index Cond: (part < c.part)

                            Heap Fetches: 0

Planning Time: 0.212 ms

Execution Time: 0.874 ms

EXPLAIN

-- original woraround, inferior to the new query, but now with more work_mem.
EXPLAIN ANALYZE
SELECT id, part
FROM  (
   SELECT *, count(*)  OVER w AS ct
        , row_number() OVER (w ORDER BY id ROWS UNBOUNDED PRECEDING) AS rn
   FROM   tbl
   WINDOW  w AS (PARTITION BY part)
   ) sub
WHERE  rn = ct;

QUERY PLAN

Subquery Scan on sub  (cost=0.42..13000.46 rows=900 width=8) (actual time=2.587..168.026 rows=67 loops=1)

  Filter: (sub.rn = sub.ct)

  Rows Removed by Filter: 179867

  ->  WindowAgg  (cost=0.42..10751.28 rows=179934 width=56) (actual time=1.964..158.216 rows=179934 loops=1)

        ->  WindowAgg  (cost=0.42..8052.28 rows=179934 width=16) (actual time=0.018..87.123 rows=179934 loops=1)

              ->  Index Only Scan using tbl_part_id_idx on tbl  (cost=0.42..4903.43 rows=179934 width=8) (actual time=0.014..27.902 rows=179934 loops=1)

                    Heap Fetches: 0

Planning Time: 0.112 ms

Execution Time: 168.135 ms

EXPLAIN