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/8 -- !
, '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 19939
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..10307.17 rows=900 width=8) (actual time=0.065..132.096 rows=25001 loops=1) |
| Filter: (sub.rn = 1) |
| Rows Removed by Filter: 155060 |
| -> WindowAgg (cost=0.42..8056.40 rows=180061 width=48) (actual time=0.064..120.068 rows=180061 loops=1) |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.050..32.763 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.253 ms |
| Execution Time: 133.125 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=20622.97..26474.96 rows=900 width=8) (actual time=85.615..187.959 rows=25001 loops=1) |
| Filter: (sub.rn = 1) |
| Rows Removed by Filter: 155060 |
| -> WindowAgg (cost=20622.97..24224.19 rows=180061 width=48) (actual time=85.613..177.088 rows=180061 loops=1) |
| -> Sort (cost=20622.97..21073.13 rows=180061 width=8) (actual time=85.596..98.146 rows=180061 loops=1) |
| Sort Key: tbl.part, tbl.id DESC |
| Sort Method: quicksort Memory: 14585kB |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.012..23.667 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.154 ms |
| Execution Time: 189.128 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=20622.97..26474.96 rows=900 width=8) (actual time=77.323..160.819 rows=25001 loops=1) |
| Filter: (sub.rn = 1) |
| Rows Removed by Filter: 155060 |
| -> WindowAgg (cost=20622.97..24224.19 rows=180061 width=48) (actual time=77.320..150.019 rows=180061 loops=1) |
| -> Sort (cost=20622.97..21073.13 rows=180061 width=8) (actual time=77.307..89.603 rows=180061 loops=1) |
| Sort Key: tbl.part, tbl.id DESC |
| Sort Method: quicksort Memory: 14585kB |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.020..20.963 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.111 ms |
| Execution Time: 162.793 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..10757.32 rows=900 width=8) (actual time=0.031..133.496 rows=25001 loops=1) |
| Filter: (sub.f = 1) |
| Rows Removed by Filter: 155060 |
| -> WindowAgg (cost=0.42..8506.56 rows=180061 width=44) (actual time=0.030..122.187 rows=180061 loops=1) |
| -> Index Only Scan Backward using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.023..28.604 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.119 ms |
| Execution Time: 134.474 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..10307.17 rows=90030 width=8) (actual time=0.022..105.216 rows=25001 loops=1) |
| Filter: sub.qualified |
| Rows Removed by Filter: 155060 |
| -> WindowAgg (cost=0.42..8506.56 rows=180061 width=41) (actual time=0.017..95.701 rows=180061 loops=1) |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.012..26.378 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.104 ms |
| Execution Time: 106.082 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=20622.97..21523.28 rows=24927 width=8) (actual time=86.983..110.048 rows=25001 loops=1) |
| -> Sort (cost=20622.97..21073.13 rows=180061 width=8) (actual time=86.979..96.239 rows=180061 loops=1) |
| Sort Key: part, id DESC |
| Sort Method: quicksort Memory: 14585kB |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.015..22.661 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.091 ms |
| Execution Time: 112.002 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=20622.97..21523.28 rows=24927 width=8) (actual time=85.700..108.799 rows=25001 loops=1) |
| -> Sort (cost=20622.97..21073.13 rows=180061 width=8) (actual time=85.697..95.015 rows=180061 loops=1) |
| Sort Key: part, id DESC |
| Sort Method: quicksort Memory: 14585kB |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.020..22.511 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.092 ms |
| Execution Time: 110.744 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..5355.49 rows=24927 width=8) (actual time=0.021..32.591 rows=25001 loops=1) |
| -> Unique (cost=0.42..5355.49 rows=24927 width=8) (actual time=0.019..30.042 rows=25001 loops=1) |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.018..17.882 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.090 ms |
| Execution Time: 33.489 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.012..190.780 rows=25001 loops=1) |
| CTE cte |
| -> Recursive Union (cost=0.42..51.44 rows=101 width=8) (actual time=0.010..184.185 rows=25001 loops=1) |
| -> Limit (cost=0.42..0.45 rows=1 width=8) (actual time=0.010..0.011 rows=1 loops=1) |
| -> Index Only Scan Backward using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.009..0.009 rows=1 loops=1) |
| Heap Fetches: 0 |
| -> Nested Loop (cost=0.42..4.90 rows=10 width=8) (actual time=0.007..0.007 rows=1 loops=25001) |
| -> WorkTable Scan on cte c (cost=0.00..0.20 rows=10 width=4) (actual time=0.000..0.000 rows=1 loops=25001) |
| -> Limit (cost=0.42..0.45 rows=1 width=8) (actual time=0.006..0.006 rows=1 loops=25001) |
| -> Index Only Scan Backward using tbl_part_id_idx on tbl t (cost=0.42..1786.77 rows=60020 width=8) (actual time=0.006..0.006 rows=1 loops=25001) |
| Index Cond: (part < c.part) |
| Heap Fetches: 0 |
| Planning Time: 0.193 ms |
| Execution Time: 192.238 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=23323.89..29175.87 rows=900 width=8) (actual time=130.320..213.134 rows=25001 loops=1) |
| Filter: (sub.rn = sub.ct) |
| Rows Removed by Filter: 155060 |
| -> WindowAgg (cost=23323.89..26925.11 rows=180061 width=56) (actual time=130.312..201.651 rows=180061 loops=1) |
| -> Sort (cost=23323.89..23774.04 rows=180061 width=16) (actual time=130.299..141.547 rows=180061 loops=1) |
| Sort Key: tbl.part, tbl.id |
| Sort Method: quicksort Memory: 14585kB |
| -> WindowAgg (cost=0.42..7606.25 rows=180061 width=16) (actual time=0.020..95.633 rows=180061 loops=1) |
| -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4905.34 rows=180061 width=8) (actual time=0.012..23.447 rows=180061 loops=1) |
| Heap Fetches: 0 |
| Planning Time: 0.172 ms |
| Execution Time: 215.192 ms |
EXPLAIN