When we talk about databases, a very interesting aspect is understanding how the optimizer chooses the execution plan for queries.
Many readers ask me to talk about this.
In this blog, I want to demonstrate how the size of tables and the presence of indexes affect the PostgreSQL optimizer’s choice of method when joining tables. I will consider several scenarios when joining two tables in PostgreSQL. I will vary the sizes of the tables and the presence of an index, primary key, and uniqueness of records in the field used for joining the tables.
Case #1
Given two fairly large tables, each with 200,000 records.
Both tables lack a primary key and indexes.
The tables are joined on a column where the data is not unique in either the first or the second table.
drop table my_table_1;
create table my_table_1(a bigint, b varchar(1000));
drop table my_table_2;
create table my_table_2(a bigint, b varchar(1000));
INSERT INTO my_table_1 (a, b)
select
(random() * 1000)::bigint, - generates a random integer between 0 and 1000, which is cast to a bigint
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 200000);
INSERT INTO my_table_2 (a, b)
select
(random() * 1000)::bigint, - generates a random integer between 0 and 1000, which is cast to a bigint
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 200000);
select count(1) from my_table_1;
Output:
200000
select count(1) from my_table_2;
Output:
200000
select a, count(1) from my_table_1 group by 1 order by 2 desc limit 10;
Output:
832 252
275 249
594 244
952 241
530 236
55 235
569 235
891 234
173 234
444 233
select a, count(1) from my_table_2 group by 1 order by 2 desc limit 10;
Output:
427 250
358 243
234 239
169 236
744 235
627 235
150 235
324 234
960 234
493 233
analyze my_table_1;
analyze my_table_2;
explain (buffers, analyze) select t1.*, t2.*
from my_table_1 t1, my_table_2 t2
where t1.a = t2.a;
In this case, PostgreSQL chooses the Hash Join method for joining the tables.
Hash Join (cost=42665.00..614583.97 rows=39956597 width=1683) (actual time=1539.844..9508.442 rows=39989257 loops=1)
Hash Cond: (t1.a = t2.a)
Buffers: shared hit=45000, temp read=41099 written=41099
-> Seq Scan on my_table_1 t1 (cost=0.00..27000.00 rows=200000 width=965) (actual time=0.027..48.974 rows=200000 loops=1)
Buffers: shared hit=25000
-> Hash (cost=22000.00..22000.00 rows=200000 width=718) (actual time=1539.647..1539.648 rows=200000 loops=1)
Buckets: 16384 Batches: 32 Memory Usage: 6213kB
Buffers: shared hit=20000, temp written=17571
-> Seq Scan on my_table_2 t2 (cost=0.00..22000.00 rows=200000 width=718) (actual time=0.008..37.210 rows=200000 loops=1)
Buffers: shared hit=20000
Planning:
Buffers: shared hit=16
Planning Time: 0.364 ms
JIT:
Functions: 10
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 247.618 ms, Inlining 326.195 ms, Optimization 367.546 ms, Emission 367.594 ms, Total 1308.954 ms
Execution Time: 11400.245 ms
Case #2
Given two tables. One table contains 100,000 records. The other table is small, containing only 10 records. Both tables have a primary key. The tables are joined on the primary key.
drop table my_table_1;
create table my_table_1(a serial primary key, b varchar(1000));
drop table my_table_2;
create table my_table_2(a serial primary key, b varchar(1000));
INSERT INTO my_table_1 (b)
SELECT
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 100000)
on conflict do nothing;
INSERT INTO my_table_2 (b)
SELECT
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 10)
on conflict do nothing;
select count(1) from my_table_1;
Output:
100000
select count(1) from my_table_2;
Output:
10
analyze my_table_1;
analyze my_table_2;
explain (buffers, analyze) select t1.*, t2.*
from my_table_1 t1, my_table_2 t2
where t1.a = t2.a;
In this case, PostgreSQL joins the tables using the Merge Join method.
From the plan, we can see that because the my_table_2 table contains just 10 records, PostgreSQL reads 1 block (all the records fit 1 block) and sort the records. Then PostgreSQL reads the index corresponding to the primary key of the my_table_1 table. Notice that PostgreSQL reads not the entire index, but only those blocks where values are matching to the first table key, a total of 4 blocks. Finally, a Merge Join is performed.
Merge Join (cost=1.56..3.42 rows=10 width=1512) (actual time=0.029..0.039 rows=10 loops=1)
Merge Cond: (t1.a = t2.a)
Buffers: shared hit=5
-> Index Scan using my_table_1_pkey on my_table_1 t1 (cost=0.29..16893.29 rows=100000 width=999) (actual time=0.009..0.013 rows=11 loops=1)
Buffers: shared hit=4
-> Sort (cost=1.27..1.29 rows=10 width=513) (actual time=0.015..0.016 rows=10 loops=1)
Sort Key: t2.a
Sort Method: quicksort Memory: 30kB
Buffers: shared hit=1
-> Seq Scan on my_table_2 t2 (cost=0.00..1.10 rows=10 width=513) (actual time=0.005..0.006 rows=10 loops=1)
Buffers: shared hit=1
Planning:
Buffers: shared hit=10
Planning Time: 0.219 ms
Execution Time: 0.064 ms
Case #3
Given two tables. Both tables contain 100,000 records. Both tables have a primary key. The tables are joined on the primary key.
drop table my_table_1;
create table my_table_1(a serial primary key, b varchar(1000));
drop table my_table_2;
create table my_table_2(a serial primary key, b varchar(1000));
INSERT INTO my_table_1 (b)
SELECT
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 100000)
on conflict do nothing;
INSERT INTO my_table_2 (b)
SELECT
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 100000)
on conflict do nothing;
select count(1) from my_table_1;
select count(1) from my_table_2;
analyze my_table_1;
analyze my_table_2;
explain (buffers, analyze) select t1.*, t2.*
from my_table_1 t1, my_table_2 t2
where t1.a = t2.a;
PostgreSQL joins the tables using the Merge Join method, and the plan differs from the previous case.
Since both tables are large, PostgreSQL reads the indexes corresponding to the primary key of each table. Finally, a Merge Join is performed.
Merge Join (cost=0.58..18436.99 rows=100000 width=865) (actual time=0.042..86.043 rows=100000 loops=1)
Merge Cond: (t1.a = t2.a)
Buffers: shared hit=12273
-> Index Scan using my_table_1_pkey on my_table_1 t1 (cost=0.29..11698.29 rows=100000 width=683) (actual time=0.022..29.338 rows=100000 loops=1)
Buffers: shared hit=9366
-> Index Scan using my_table_2_pkey on my_table_2 t2 (cost=0.29..5239.29 rows=100000 width=182) (actual time=0.012..21.673 rows=100000 loops=1)
Buffers: shared hit=2907
Planning:
Buffers: shared hit=12
Planning Time: 0.347 ms
Execution Time: 91.104 ms
Case #4:
Given two tables. One is large, the other is small. One contains 200,000 records, the other contains 25 records. The column used for joining the tables is not unique. Indexes are defined on the column used for joining the tables.
drop table my_table_1;
create table my_table_1(a bigint, b varchar(1000));
drop table my_table_2;
create table my_table_2(a bigint, b varchar(1000));
INSERT INTO my_table_1 (a, b)
select
(random() * 1000)::bigint, - generates a random integer between 0 and 1000, which is cast to a bigint
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 200000);
INSERT INTO my_table_2 (a, b)
select
(random() * 1000)::bigint, - generates a random integer between 0 and 1000, which is cast to a bigint
ARRAY_TO_STRING(ARRAY(SELECT chr((65 + (random() * 25))::int) FROM generate_series(1, (1000*random())::int)), '') - generates a random string of characters of variable length, where each character is an uppercase letter (A-Z), and concatenates them into a single string without any delimiter.
FROM generate_series(1, 25);
select count(1) from my_table_1;
Output:
200000
select count(1) from my_table_2;
Output:
25
select a, count(1) from my_table_1 group by 1 order by 2 desc limit 10;
Output:
427 247
314 243
852 240
96 240
523 239
166 236
781 235
784 235
807 235
407 234
select a, count(1) from my_table_2 group by 1 order by 2 desc limit 10;
Output:
406 2
823 1
639 1
786 1
766 1
476 1
841 1
425 1
602 1
397 1
create index my_table_1_idx on my_table_1(a);
create index my_table_2_idx on my_table_2(a);
analyze my_table_1;
analyze my_table_2;
explain (buffers, analyze) select t1.*, t2.*
from my_table_1 t1, my_table_2 t2
where t1.a = t2.a;
PostgreSQL chooses Nested Loop as the method for joining the tables.
Nested Loop (cost=5.69..3851.45 rows=4993 width=260) (actual time=0.870..13.665 rows=4962 loops=1)
Buffers: shared hit=4366 read=28
-> Seq Scan on my_table_2 t2 (cost=0.00..1.25 rows=25 width=248) (actual time=0.024..0.047 rows=25 loops=1)
Buffers: shared hit=1
-> Memoize (cost=5.69..157.58 rows=200 width=12) (actual time=0.110..0.480 rows=198 loops=25)
Cache Key: t2.a
Cache Mode: logical
Hits: 1 Misses: 24 Evictions: 0 Overflows: 0 Memory Usage: 207kB
Buffers: shared hit=4365 read=28
-> Bitmap Heap Scan on my_table_1 t1 (cost=5.68..157.57 rows=200 width=12) (actual time=0.106..0.423 rows=198 loops=24)
Recheck Cond: (a = t2.a)
Heap Blocks: exact=4339
Buffers: shared hit=4365 read=28
-> Bitmap Index Scan on my_table_1_idx (cost=0.00..5.63 rows=200 width=0) (actual time=0.065..0.065 rows=198 loops=24)
Index Cond: (a = t2.a)
Buffers: shared hit=26 read=28
Planning:
Buffers: shared hit=21 read=3
Planning Time: 1.009 ms
Execution Time: 15.476 ms
ask_dima@yahoo.com
Top comments (0)