Query optimization. Basics of EXPLAIN in PostgreSQL (part 3)

I keep publishing the author's rework Understanding EXPLAIN from Guillaume Lelarge.
Once again I will note that some of the information is omitted for brevity, so I strongly recommend that you familiarize yourself with the original.

Previous parts:

Part 1
Part 2

ORDER BY

DROP INDEX foo_c1_idx; EXPLAIN (ANALYZE) SELECT * FROM foo ORDER BY c1; 

QUERY PLAN
- Sort (cost = 117993.01..120493.04 rows = 1000010 width = 37) (actual time = 571.591..651.524 rows = 1000010 loops = 1)
Short key: c1
Sort Method: external merge Disk: 45952kB
-> Seq Scan on foo (cost = 0.00..18334.10 rows = 1000010 width = 37) (actual time = 0.007..62.041 rows = 1000010 loops = 1)
Total runtime: 690.984 ms
(5 rows)

First produced by Seq Scan table foo . Then sort Sort . In the output of the EXPLAIN command, the sign -> indicates a hierarchy of actions ( node ). The sooner an action is performed, the more indented it is displayed.
Sort Key - sorting condition.
Sort Method: external merge Disk - when sorting, a temporary file on a disk with a volume of 45952kB .

I ask those who understand the topic to explain the differences between external merge and external sort .

Check with the BUFFERS option:

 EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM foo ORDER BY c1; 

QUERY PLAN
- Sort (cost = 117993.01..120493.04 rows = 1000010 width = 37) (actual time = 568.412..652.308 rows = 1000010 loops = 1)
Short key: c1
Sort Method: external merge Disk: 45952kB
Buffers: shared hit = 8334, temp read = 5745 written = 5745
-> Seq Scan on foo (cost = 0.00..18334.10 rows = 1000010 width = 37) (actual time = 0.010..68.203 rows = 1000010 loops = 1)
Buffers: shared hit = 8334
Total runtime: 698.032 ms
(7 rows)

Indeed, temp read=5745 written=5745 - 5745 blocks of 8Kb = 45960Kb were written and read into a temporary file. Operations with 8334 blocks were made in the cache.
')
File system operations are slower than RAM operations.
Let's try to increase the amount of used memory work_mem :

 SET work_mem TO '200MB'; EXPLAIN (ANALYZE) SELECT * FROM foo ORDER BY c1; 

QUERY PLAN
- Sort (cost = 117993.01..120493.04 rows = 1000010 width = 37) (actual time = 265.301..296.777 rows = 1000010 loops = 1)
Short key: c1
Sort Method: quicksort Memory: 102702kB
-> Seq Scan on foo (cost = 0.00..18334.10 rows = 1000010 width = 37) (actual time = 0.006..57.836 rows = 1000010 loops = 1)
Total runtime: 328.746 ms
(5 rows)

Sort Method: quicksort Memory: 102702kB - the entire sorting is done in RAM.

Index:

 CREATE INDEX ON foo(c1); EXPLAIN (ANALYZE) SELECT * FROM foo ORDER BY c1; 

QUERY PLAN
- Index Scan using foo_c1_idx on foo (cost = 0.42..34327.57 rows = 1000010 width = 37) (actual time = 0.023..126.076 rows = 1000010 loops = 1)
Total runtime: 153.452 ms
(2 rows)

Of the actions left only Index Scan , which markedly affected the speed of the query.

LIMIT

Delete the previously created index.

 DROP INDEX foo_c2_idx1; EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM foo WHERE c2 LIKE 'ab%'; 

QUERY PLAN
- Seq Scan on foo (cost = 0.00..20834.12 rows = 100 width = 37) (actual time = 0.033..94.757 rows = 3824 loops = 1)
Filter: (c2 ~ ab '%' :: text)
Rows Removed by Filter: 996186
Buffers: shared hit = 8334
Total runtime: 94.924 ms
(5 rows)

Expectedly, Seq Scan and Filter .

 EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM foo WHERE c2 LIKE 'ab%' LIMIT 10; 

QUERY PLAN
- Limit (cost = 0.00..2083.41 rows = 10 width = 37) (actual time = 0.037..0.607 rows = 10 loops = 1)
Buffers: shared hit = 26
-> Seq Scan on foo (cost = 0.00..20834.12 rows = 100 width = 37) (actual time = 0.031..0.599 rows = 10 loops = 1)
Filter: (c2 ~ ab '%' :: text)
Rows Removed by Filter: 3053
Buffers: shared hit = 26
Total runtime: 0.628 ms
(7 rows)

Seq Scan table rows and compares them to the condition. As soon as there are 10 entries that satisfy the condition, the scan will end. In our case, in order to get 10 rows of the result, we had to read not the entire table, but only 3063 records, of which 3053 were rejected ( Rows Removed by Filter ).
The same thing happens with Index Scan .

JOIN

Let's create a new table, collect statistics for it.

 CREATE TABLE bar (c1 integer, c2 boolean); INSERT INTO bar SELECT i, i%2=1 FROM generate_series(1, 500000) AS i; ANALYZE bar; 

Query on two tables

 EXPLAIN (ANALYZE) SELECT * FROM foo JOIN bar ON foo.c1=bar.c1; 

QUERY PLAN
- Hash Join (cost = 13463.00..49297.22 rows = 500000 width = 42) (actual time = 87.441..907.555 rows = 500010 loops = 1)
Hash Cond: (foo.c1 = bar.c1)
-> Seq Scan on foo (cost = 0.00..18334.10 rows = 1000010 width = 37) (actual time = 0.008..67.951 rows = 1000010 loops = 1)
-> Hash (cost = 7213.00..7213.00 rows = 500000 width = 5) (actual time = 87.352..87.352 rows = 500000 loops = 1)
Buckets: 65536 Batches: 1 Memory Usage: 18067kB
-> Seq Scan on bar (cost = 0.00 ..7213.00 rows = 500000 width = 5) (actual time = 0.007..33.233 rows = 500000 loops = 1)
Total runtime: 920.967 ms
(7 rows)

First viewed ( Seq Scan ) table bar . For each of its lines, a hash is computed.
Then, the Seq Scan table foo scanned, and for each row of this table a hash is computed, which is compared ( Hash Join ) with the hash of the bar table by the Hash Cond condition. If a match is found, the resulting string is output, otherwise the string will be skipped.
Used 18067kB in memory to accommodate the hash table bar .

Add an index

 CREATE INDEX ON bar(c1); EXPLAIN (ANALYZE) SELECT * FROM foo JOIN bar ON foo.c1=bar.c1; 

QUERY PLAN
- Merge Join (cost = 1.69..39879.71 rows = 500000 width = 42) (actual time = 0.037..263.357 rows = 500010 loops = 1)
Merge Cond: (foo.c1 = bar.c1)
-> Index Scan using foo_c1_idx on foo (cost = 0.42..34327.57 rows = 1000010 width = 37) (actual time = 0.019..58.920 rows = 500011 loops = 1)
-> Index Scan using bar_c1_idx on bar (cost = 0.42..15212.42 rows = 500000 width = 5) (actual time = 0.008..71.719 rows = 500010 loops = 1)
Total runtime: 283.549 ms
(5 rows)

Hash no longer in use. Merge Join and Index Scan indices of both tables provide an impressive performance boost.

LEFT JOIN:

 EXPLAIN (ANALYZE) SELECT * FROM foo LEFT JOIN bar ON foo.c1=bar.c1; 

QUERY PLAN
- Hash Left Join (cost = 13463.00..49297.22 rows = 1000010 width = 42) (actual time = 82.682..926.331 rows = 1000010 loops = 1)
Hash Cond: (foo.c1 = bar.c1)
-> Seq Scan on foo (cost = 0.00..18334.10 rows = 1000010 width = 37) (actual time = 0.004..68.763 rows = 1000010 loops = 1)
-> Hash (cost = 7213.00..7213.00 rows = 500000 width = 5) (actual time = 82.625..82.625 rows = 500000 loops = 1)
Buckets: 65536 Batches: 1 Memory Usage: 18067kB
-> Seq Scan on bar (cost = 0.00..7213.00 rows = 500000 width = 5) (actual time = 0.003..31.890 rows = 500000 loops = 1)
Total runtime: 950.625 ms
(7 rows)

Seq Scan ?
Let's see what the results will be if you disable Seq Scan.

 SET enable_seqscan TO off; EXPLAIN (ANALYZE) SELECT * FROM foo LEFT JOIN bar ON foo.c1=bar.c1; 

QUERY PLAN
- Merge Left Join (cost = 0.85..58290.02 rows = 1000010 width = 42) (actual time = 0.024..353.819 rows = 1000010 loops = 1)
Merge Cond: (foo.c1 = bar.c1)
-> Index Scan using foo_c1_idx on foo (cost = 0.42..34327.57 rows = 1000010 width = 37) (actual time = 0.011..112.095 rows = 1000010 loops = 1)
-> Index Scan using bar_c1_idx on bar (cost = 0.42..15212.42 rows = 500000 width = 5) (actual time = 0.008..63.125 rows = 500010 loops = 1)
Total runtime: 378.603 ms
(5 rows)

According to the planner, using indexes is more expensive than using hashes. This is possible with a sufficiently large amount of allocated memory. Remember we increased work_mem ?
But, if memory is in short supply, the scheduler will behave differently:

 SET work_mem TO '15MB'; SET enable_seqscan TO ON; EXPLAIN (ANALYZE) SELECT * FROM foo LEFT JOIN bar ON foo.c1=bar.c1; 

QUERY PLAN
- Merge Left Join (cost = 0.85..58290.02 rows = 1000010 width = 42) (actual time = 0.014..376.395 rows = 1000010 loops = 1)
Merge Cond: (foo.c1 = bar.c1)
-> Index Scan using foo_c1_idx1 on foo (cost = 0.42..34327.57 rows = 1000010 width = 37) (actual time = 0.005..124.698 rows = 1000010 loops = 1)
-> Index Scan using bar_c1_idx on bar (cost = 0.42..15212.42 rows = 500000 width = 5) (actual time = 0.006..66.813 rows = 500010 loops = 1)
Total runtime: 401.990 ms
(5 rows)

And what will the output of EXPLAIN look like when Index Scan ?

 SET work_mem TO '15MB'; SET enable_indexscan TO off; EXPLAIN (ANALYZE) SELECT * FROM foo LEFT JOIN bar ON foo.c1=bar.c1; 

QUERY PLAN
- Hash Left Join (cost = 15417.00..63831.18 rows = 1000010 width = 42) (actual time = 93.440..712.056 rows = 1000010 loops = 1)
Hash Cond: (foo.c1 = bar.c1)
-> Seq Scan on foo (cost = 0.00..18334.10 rows = 1000010 width = 37) (actual time = 0.008..65.901 rows = 1000010 loops = 1)
-> Hash (cost = 7213.00..7213.00 rows = 500000 width = 5) (actual time = 93.308..93.308 rows = 500000 loops = 1)
Buckets: 65536 Batches: 2 Memory Usage: 9045kB
-> Seq Scan on bar (cost = 0.00..7213.00 rows = 500000 width = 5) (actual time = 0.007..33.718 rows = 500000 loops = 1)
Total runtime: 736.726 ms
(7 rows)

cost clearly increased. The reason for the Batches: 2 . The whole hash did not fit in memory, it had to be broken into 2 packages of 9045kB.

Here again I ask for the help of the guru. Explain why with LEFT JOIN and sufficient work_mem , using Merge Left Join more expensive than Hash Left Join ?

I’ll stop on this today.

UPD.
Oleg Bartunov and Alexander Korotkov told a lot about PostgreSQL indexes.

I will bring here a link to the latest articles from PostgreSQL Indices in PostgreSQL , part 2 , part 3 . There much is clarified.