Beyond Joins and Indexes
BRUCE MOMJIAN

As a follow up to the presentation, Explaining the Postgres Query Optimizer, this talkshows the non-join and non-index operations that the optimizer can choose.
https://momjian.us/presentations

Creative Commons Attribution License

Last updated: June 2024

1 / 68

Explaining the Postgres Query Optimizer

My previous talk, Explaining the Postgres Query Optimizer, covered:• Query optimization basics• Optimizer statistics• Join methods• Scan methods, including indexes• Limithttps://momjian.us/main/presentations/performance.html#optimizer
2 / 68

This Presentation Covers Everything Else

1. Result
2. Values Scan
3. Function Scan
4. Incremental Sort
5. Unique
6. Append
7. Merge Append
8. Subquery Scan
9. HashSetOp
10. SetOp
11. Materialize

12. Memoize
13. Group
14. Aggregate
15. GroupAggregate
16. HashAggregate
17. MixedAggregate
18. WindowAgg
19. Parallel Seq Scan
20. Partial Aggregate
21. Gather
22. Finalize Aggregate

23. Gather Merge
34. Foreign Scan
24. Parallel Append
35. Tid Scan
25. Parallel Hash
36. Insert
26. Parallel Hash Join 37. Update
27. CTE Scan
38. Delete
28. WorkTable Scan
39. Merge
29. Recursive Union
40. Semi Join
30. ProjectSet
41. Anti Join
31. LockRows
42. SubPlan
32. Sample Scan
33. Table Function Scan 43. Others
https://www.pgmustard.com/docs/explain
3 / 68

Controls
My previous talk covered:• enable_seqscan• enable_bitmapscan• enable_indexscan• enable_indexonlyscan• enable_nestloop• enable_hashjoin• enable_mergejoin• enable_sort
This talk will cover:• enable_incremental_sort• enable_material• enable_memoize• enable_hashagg• enable_gathermerge• enable_parallel_append• enable_parallel_hash• enable_tidscan
Not covered:*• enable_async_append• enable_partition_pruning• enable_partitionwise_join• enable_partitionwise_aggregate
https://www.postgresql.org/docs/current/runtime-config-query.html* https://momjian.us/main/presentations/performance.html#partitioning
4 / 68

1. Result-- This disables EXPLAIN cost output\set EXPLAIN ’EXPLAIN (COSTS OFF)’:EXPLAIN SELECT 1;
QUERY PLAN-----------Result

All the queries used in this presentation are available at https://momjian.us/main/writings/pgsql/
beyond.sql.
5 / 68

2. Values Scan

:EXPLAIN VALUES (1), (2);QUERY PLAN--------------------------Values Scan on "*VALUES*"

Causes are in blue, optimizer choices are in red.
6 / 68

3. Function Scan

:EXPLAIN SELECT * FROM generate_series(1,4);
QUERY PLAN---------------------------------Function Scan on generate_series

7 / 68

4. Incremental Sort
CREATE TABLE large (x) AS SELECT generate_series(1, 1000000);ANALYZE large;
CREATE INDEX i_large ON large (x);ALTER TABLE large ADD COLUMN y INTEGER;:EXPLAIN SELECT * FROM large ORDER BY x, y;
QUERY PLAN----------------------------------------Incremental Sort
Sort Key: x, y
Presorted Key: x-> Index Scan using i_large on large
8 / 68

Incremental Sort
3

6

3

2

3

3

3

3

3

2

3

4

3

4

3

5

3

6

Incremental
Sort

3

12

3

5

3

12

4

8

4

3

4

6

4

6

4

11

4

8

4

3

4

11

9 / 68

5. Unique, First Example:EXPLAIN SELECT DISTINCT * FROM generate_series(1, 10) ORDER BY 1;QUERY PLAN---------------------------------------------Unique-> Sort
Sort Key: generate_series-> Function Scan on generate_series

10 / 68

Unique, Second Example-- not UNION ALL:EXPLAIN SELECT 1 UNION SELECT 2;QUERY PLAN-------------------------Unique-> Sort
Sort Key: (1)-> Append-> Result-> Result

11 / 68

Unique

6

2

3

3

2

2

3

3

4

4

4

12

Sort

5

Unique

5

5

6

6

8

6

8

6

8

11

11

11

12

3

12

12 / 68

6. Append:EXPLAIN SELECT 1 UNION ALL SELECT 2;QUERY PLAN-------------Append-> Result-> Result

13 / 68

Append

6
6

3

3

2

2

4

4

12
Append

12
5

5
8
6
11

8
6
11
3

3

14 / 68

7. Merge Append:EXPLAIN (VALUES (1), (2) ORDER BY 1)
UNION ALL(VALUES (3), (4) ORDER BY 1)
ORDER BY 1;QUERY PLAN----------------------------------------Merge Append
Sort Key: "*VALUES*".column1-> Sort
Sort Key: "*VALUES*".column1-> Values Scan on "*VALUES*"-> Sort
Sort Key: "*VALUES*_1".column1-> Values Scan on "*VALUES*_1"
15 / 68

Merge Append

6

2

3

3

2

Sort

2
3

4

4

6

12

12

3
4
5
Merge Append
6

5

3

8

5

6

Sort

6

11

8

3

11

6
8
11
12

16 / 68

8, 9. Subquery Scan, HashSetOp
CREATE TABLE small (x) AS
SELECT generate_series(1, 1000);ANALYZE small;:EXPLAIN SELECT * FROM small EXCEPT SELECT * FROM small;
QUERY PLAN--------------------------------------------HashSetOp Except-> Append-> Subquery Scan on "*SELECT* 1"-> Seq Scan on small-> Subquery Scan on "*SELECT* 2"-> Seq Scan on small small_1
17 / 68

HashSetOp
Count
7,1

1

3,1

2

3,2

1

3,1

6,1

1

12,1

6,2

1

7
3
6

7,1
Append with
"1" Label

3,1
6,1

3
12

Hash with CountHashSetOp
with EXCEPT

5,2
5
8
6
11
3

12,1

1

5,2

1

8,2

1

11,2

1

7
12

8,2
Append with
"2" Label

6,2
11,2
3,2

The count is useful for efficiently
processing duplicates when
ALL is used.

Logically UNION, EXCEPT, and INTERSECT without ALL remove duplicates in joined queries and results. For example. thequery VALUES (1), (1), (2), (2) EXCEPT VALUES (1) returning 2 shows joined query removal, while UNION shows result removal.

18 / 6810. SetOp-- table has to be too large to hash
:EXPLAIN SELECT * FROM large INTERSECT SELECT * FROM large;
QUERY PLAN--------------------------------------------------SetOp Intersect-> Sort
Sort Key: "*SELECT* 1".x, "*SELECT* 1".y-> Append-> Subquery Scan on "*SELECT* 1"-> Seq Scan on large-> Subquery Scan on "*SELECT* 2"-> Seq Scan on large large_1

19 / 68

SetOp

7
3
6

Count
7,1
Append with
"1" Label

3,1

2

3,2

1

5,2

1

6,1

1

6,2

1

7,1

1

3,1
6,1

3

3,1

12

12,1

Sort

8
6
11

3
6

5,2
5

SetOp with
INTERSECT

8,2
Append with
"2" Label

8,2

1

11,2

1

12,1

1

6,2
11,2
3,2

3

20 / 6811. Materialize:EXPLAIN SELECT * FROM small s1, small s2 WHERE s1.x != s2.x;
QUERY PLAN---------------------------------Nested Loop
Join Filter: (s1.x <> s2.x)-> Seq Scan on small s1-> Materialize-> Seq Scan on small s2

21 / 68

Materialize
Inner
Outer

Local
MemorySharedBuffers

aag

aai

aai

aay

aag

aag

aar

aas

aai

aar

aar

aay

aay

aaa

aaa

aag

aag

Materializeaas

22 / 6812. Memoize, Setup-- needs duplicates and too small for a hash join
CREATE TABLE small_with_dups (x) AS
SELECT generate_series(1, 1000)
FROM generate_series(1, 10);-- unique and too big for a hash join
CREATE TABLE medium (x) AS
SELECT generate_series(1, 100000);-- index required for this memoize example
CREATE INDEX i_medium ON medium (x);ANALYZE;

23 / 68

Memoize:EXPLAIN SELECT * FROM small_with_dups JOIN medium USING (x);QUERY PLAN-----------------------------------------------------Nested Loop-> Seq Scan on small_with_dups-> Memoize
Cache Key: small_with_dups.x
Cache Mode: logical-> Index Only Scan using i_medium on medium
Index Cond: (x = small_with_dups.x)
Only happens in nested loops; supported in Postgres 14 and later.
https://blog.jooq.org/postgresql-14s-enable_memoize-for-improved-performance-of-nested-loop-joins/
24 / 68

Memoize
Inner
Local

SharedOuter

Memory

aag

Hash

aai

aak

Cache

aag

aay

aag

aag

aay

Buffers

LRU

Memoize

aas
aar

aay

aay

aaf

aaa
aag

Inner-side lookups that return no rows are also recorded in the cache.

25 / 6813. Group-- must be small enough not to trigger HashAggregate-- removing WHERE and adding ORDER BY x does the same
:EXPLAIN SELECT x FROM large WHERE x < 0 GROUP BY x;
QUERY PLAN---------------------------------------------Group
Group Key: x-> Index Only Scan using i_large on large
Index Cond: (x < 0)

26 / 68

Group, All Columns
1,1

Sorted

1,2

1,1

1,2

1,2

1,4

1,4

2,1

Group, All Columns

2,1

2,5

2,5

3,2

3,2

3,2

3,4

3,2
3,4
GROUP BY without aggregates is similar to SELECT DISTINCT, except duplicate
detection can consider more columns than those selected for output.

27 / 68

Group, Single Columns
1,1
1,2
1,2
1,4
Sorted2,12,51Group, Single Column

2
3

3,2
3,2
3,2
3,4

28 / 6814. Aggregate:EXPLAIN SELECT COUNT(*) FROM medium;QUERY PLAN-------------------------Aggregate-> Seq Scan on medium

29 / 6815. GroupAggregate:EXPLAIN SELECT x, COUNT(*) FROM medium GROUP BY x ORDER BY x;
QUERY PLAN-----------------------------------------------GroupAggregate
Group Key: x-> Index Only Scan using i_medium on medium

30 / 68

GroupAggregate

1,1
1,2
1,2
1,4
Sorted

2,1
2,5

1,Agg
GroupAggregate

2,Agg
3,Agg

3,2
3,2
3,2
3,4

31 / 6816. HashAggregate:EXPLAIN SELECT DISTINCT x FROM medium;QUERY PLAN-------------------------HashAggregate
Group Key: x-> Seq Scan on medium

32 / 68

HashAggregate

8.4
3,2
6,2

8

3,1
11,5
6,7

3
HashAggregate
6

8,9
6,2

11

11,4
3,1

33 / 6817. MixedAggregate:EXPLAIN SELECT x FROM medium GROUP BY ROLLUP(x);QUERY PLAN-------------------------MixedAggregate
Hash Key: xGroup Key: ()-> Seq Scan on medium

34 / 68

MixedAggregate

8,4
3,2
6,2

3,Agg

3,1
11,5
6,7

6,Agg
MixedAggregate

Sorted
8,Agg

8,9
6,2

11,Agg11,43,135 / 68

18. WindowAgg:EXPLAIN SELECT x, SUM(x) OVER ()FROM generate_series(1, 10) AS f(x);QUERY PLAN-----------------------------------------WindowAgg-> Function Scan on generate_series f

https://momjian.us/main/presentations/sql.html#window
36 / 68

WindowAgg

Sorted1,1

1,1,Agg

1,2

1,2,Agg

1,2

1,2,Agg

1,4

1,4,Agg

2,1

WindowAgg

2,1,Agg

2,5

2,5,Agg

3,2

3,2,Agg

3,2

3,2,Agg

3,2

3,2,Agg

3,4

3,4,Agg

Window functions allow aggregates across rows while the individual rows remain.

37 / 6819-22. Parallel Seq Scan, Partial Aggregate,
Gather, Finalize Aggregate:EXPLAIN SELECT SUM(x) FROM large;
QUERY PLAN---------------------------------------------Finalize Aggregate-> Gather
Workers Planned: 2-> Partial Aggregate-> Parallel Seq Scan on large

https://www.postgresql.org/docs/current/parallel-plans.html
38 / 68

Parallel Seq Scan, Partial Aggregate,
Gather, Finalize Aggregate
Background Worker
63
Parallel
Seq Scan2

Background Worker
Partial Aggregate27

412GatherBackground Worker

27

Finalize Aggregate
60

33

5
8
Parallel
Seq Scan6

Background Worker

Gather collects results from background workers.

Partial Aggregate
33

11
3

Parallel Seq Scan uses background workers to scan different parts of a table in parallel.

39 / 6823. Gather Merge

CREATE TABLE huge (x) AS SELECT generate_series(1, 100000000);ANALYZE huge;:EXPLAIN SELECT * FROM huge ORDER BY 1;QUERY PLAN--------------------------------------Gather Merge
Workers Planned: 2-> Sort
Sort Key: x-> Parallel Seq Scan on huge

40 / 68

Gather Merge

Parallel
Seq ScanBackground Worker

Background Worker

6

2

3

3

2

Sort

2
3

4

4

6

12

12

Background Worker

Background Worker

5

3

8

5

3
4
5

Parallel
Seq Scan6

Sort

Gather Merge

6

11

8

3

11

6
6
8
11
12

Gather Merge collects ordered results from background workers, retaining their ordering.

41 / 6824. Parallel Append:EXPLAIN SELECT * FROM huge UNION ALL SELECT * FROM huge ORDER BY 1;QUERY PLAN---------------------------------------------------Gather Merge
Workers Planned: 2-> Sort
Sort Key: huge.x-> Parallel Append-> Parallel Seq Scan on huge-> Parallel Seq Scan on huge huge_1

42 / 68

Parallel Append
Two Tables

One Result

Background Worker
6
Parallel
Seq ScanBackground Worker

Background Worker

6

2

3
2
3
Background Worker

Parallel
Seq ScanParallel Append

2

2

3
Sort

3

4

4

4

6

12

12

12

Background Worker

Background Worker

Background Worker

5

5

3

8

8

5

3
4
5

Parallel
Seq Scan6

Parallel Append

6

Sort

6

11

8

3

11

Background Worker
Parallel
Seq ScanGather Merge
6
6
8
11
12

11
3

43 / 6825, 26. Parallel Hash, Parallel Hash Join

:EXPLAIN SELECT * FROM huge h1 JOIN huge h2 USING (x);QUERY PLAN-----------------------------------------------Gather
Workers Planned: 2-> Parallel Hash Join
Hash Cond: (h1.x = h2.x)-> Parallel Seq Scan on huge h1-> Parallel Hash-> Parallel Seq Scan on huge h2

44 / 68

Parallel Hash, Parallel Hash Join
Inner

Outer

Background Worker

Background Worker
Shared Hash

5

6
5

3
Parallel
Seq Scan883Parallel Hash Join

3

4
3

6

Background Worker
812Gather

9

Background Worker

Parallel Hash

5

6

9
Parallel
Seq Scan

11
8
4

2

8
11

4

Parallel Hash Join

6
11
3

45 / 6827. CTE Scan

:EXPLAIN WITH source AS MATERIALIZED (SELECT 1)
SELECT * FROM source;
QUERY PLAN-------------------CTE Scan on source
CTE source-> Resulthttps://momjian.us/main/presentations/sql.html#cte
46 / 68

CTE Scan
CTE Source
6324
Materialized
Common Table
Expressions

12

CTE Scan

5
8
6
11
3

47 / 6828, 29. WorkTable Scan, Recursive Union:EXPLAIN WITH RECURSIVE source (counter) AS (SELECT 1
UNION ALL
SELECT counter + 1
FROM source
WHERE counter < 10)
SELECT * FROM source;
QUERY PLAN------------------------------------------------CTE Scan on source
CTE source-> Recursive Union-> Result-> WorkTable Scan on source source_1
Filter: (counter < 10)

48 / 68

CTE Query Flow

WITH RECURSIVE source AS (SELECT 1
UNION ALL

1
3

2

SELECT 1 FROM source)
SELECT * FROM source;
49 / 68

WorkTable Scan, Recursive Union
CTE Source
6
3

Non−Recursive
Common Table
Expressions

2
4
Recursive Union

WorkTable

12

CTE Scan5
8Recursive
Common Table
Expression

6
11
3

WorkTable is cleared before every iteration. Recursion stops when the recursive CTE returns no rows.

50 / 6830. ProjectSet:EXPLAIN SELECT generate_series(1,4);
QUERY PLAN-------------ProjectSet-> Result

51 / 6831. LockRows:EXPLAIN SELECT * FROM small FOR UPDATE;QUERY PLAN------------------------LockRows-> Seq Scan on small

52 / 6832. Sample Scan

:EXPLAIN SELECT * FROM small TABLESAMPLE SYSTEM(50);QUERY PLAN--------------------------------Sample Scan on small
Sampling: system (’50’::real)

53 / 6833. Table Function Scan
:EXPLAIN SELECT *FROM XMLTABLE(’/ROWS/ROW’PASSING$$<ROWS><ROW id="1"><COUNTRY_ID>US</COUNTRY_ID></ROW></ROWS>$$COLUMNS id int PATH ’@id’,_id FOR ORDINALITY);QUERY PLAN----------------------------------Table Function Scan on "xmltable"
54 / 6834. Foreign Scan
CREATE EXTENSION postgres_fdw;
CREATE SERVER postgres_fdw_test
FOREIGN DATA WRAPPER postgres_fdw
OPTIONS (host ’localhost’, dbname ’fdw_test’);
CREATE USER MAPPING FOR PUBLICSERVER postgres_fdw_test
OPTIONS (password ’’);
CREATE FOREIGN TABLE other_world (greeting TEXT)SERVER postgres_fdw_test
OPTIONS (table_name ’world’);:EXPLAIN SELECT * FROM other_world;
QUERY PLAN----------------------------Foreign Scan on other_world

55 / 6835. Tid Scan

:EXPLAIN SELECT * FROM small WHERE ctid = ’(0,1)’;QUERY PLAN----------------------------------Tid Scan on small
TID Cond: (ctid = ’(0,1)’::tid)

56 / 68

Tid Scan
Postgres/data/base /16385/24692
8k

8k

8k

8k

Postgres
Page Header

Item

Item

Item

Postgres
8K
Tuple
Tuple

Tuple

SpecialTuple

57 / 6836. Insert:EXPLAIN INSERT INTO small VALUES (0);QUERY PLAN----------------Insert on small-> Result

58 / 6837. Update:EXPLAIN UPDATE small SET x = 1 WHERE x = 0;
QUERY PLAN------------------------Update on small-> Seq Scan on small
Filter: (x = 0)

59 / 6838. Delete:EXPLAIN DELETE FROM small;
QUERY PLAN------------------------Delete on small-> Seq Scan on small-- You cannot run EXPLAIN on utility commands like TRUNCATE.
:EXPLAIN TRUNCATE small;
ERROR: syntax error at or near "TRUNCATE"
LINE 1: EXPLAIN (COSTS OFF) TRUNCATE small;^

60 / 6839. Merge
CREATE TABLE mergetest (x, y) AS VALUES (1, NULL), (3, NULL), (5, NULL);:EXPLAIN MERGE INTO mergetest
USING (VALUES (1), (2), (3), (4), (5), (6)) m (x)ON mergetest.x = m.x
WHEN NOT MATCHED THEN
INSERT (x) VALUES (m.x)
WHEN MATCHED THENUPDATE SET y = TRUE;QUERY PLAN------------------------------------------------------Merge on mergetest-> Hash Right Join
Hash Cond: (mergetest.x = "*VALUES*".column1)-> Seq Scan on mergetest-> Hash-> Values Scan on "*VALUES*"
61 / 6840. Semi Join, First Example:EXPLAIN SELECT *FROM small
WHERE EXISTS (SELECT * FROM medium WHERE medium.x = small.x);
QUERY PLAN----------------------------------Hash Semi Join
Hash Cond: (small.x = medium.x)-> Seq Scan on small-> Hash-> Seq Scan on medium
Stop scan after first inner match.

62 / 68

Semi Join, Second Example:EXPLAIN SELECT *FROM small
WHERE small.x IN (SELECT medium.x FROM medium);QUERY PLAN----------------------------------Hash Semi Join
Hash Cond: (small.x = medium.x)-> Seq Scan on small-> Hash-> Seq Scan on medium
EXISTS and IN are equivalent in handling of NULLs because EXISTS only checks for row
existence while IN logically does OR comparisons that can ignore non-true results from
NULL comparisons.
63 / 6841. Anti Join
:EXPLAIN SELECT *FROM medium
WHERE NOT EXISTS (SELECT * FROM small WHERE small.x = medium.x);
QUERY PLAN----------------------------------Hash Anti Join
Hash Cond: (medium.x = small.x)-> Seq Scan on medium-> Hash-> Seq Scan on small
Stop scan after first inner match; negate result.

64 / 6842. SubPlan:EXPLAIN SELECT *FROM small
WHERE small.x NOT IN (SELECT medium.x FROM medium);QUERY PLAN-----------------------------------Seq Scan on small
Filter: (NOT (hashed SubPlan 1))
SubPlan 1-> Seq Scan on medium
NOT IN and NOT EXISTS are not equivalent for NULLs because NOT IN logically does
repeated not-equal AND comparisons which must all be true to return true; NULL affects
this.
65 / 6843. Others: Outer Join Removal-- UNIQUE index guarantees at most one right row match
CREATE UNIQUE INDEX i_small ON small (x);-- LEFT JOIN guarantees every left row is returned:EXPLAIN SELECT medium.x FROM medium LEFT JOIN small USING (x);QUERY PLAN-------------------Seq Scan on medium

66 / 68

Not Covered• Named Tuplestore Scan: after triggers• Custom Scan: custom scan providers

67 / 68

Conclusion

https://momjian.us/presentations

https://www.flickr.com/photos/glassholic/
68 / 68