AW: Wrong rows estimations with joins of CTEs slows queries by more than factor 500

Hello Tomas,

Thank you for looking at.

First, I miscalculated the factor which should be about 50, not 500. Sorry.

Then I want to show you the table definitions (simple, very similar, ommited child_tables and additional indexes, here using always "ONLY"):

cpsdb_matcol=# \d sa_upper;
Tabelle ╗public.sa_upper½
Spalte | Typ | Sortierfolge | NULL erlaubt? | Vorgabewert
--------------+-----------------------+--------------+---------------+----------------------------------
id_sup | integer | | not null | generated by default as identity
sup_season | smallint | | |
sup_sa_code | character varying(10) | C | |
sup_mat_code | character varying(4) | C | |
sup_clr_code | character varying(3) | C | |
Indexe:
"sa_upper_active_pkey" PRIMARY KEY, btree (id_sup)

cpsdb_matcol=# \d sa_lining+;
Tabelle ╗public.sa_lining½
Spalte | Typ | Sortierfolge | NULL erlaubt? | Vorgabewert
--------------+-----------------------+--------------+---------------+----------------------------------
id_sli | integer | | not null | generated by default as identity
sli_season | smallint | | |
sli_sa_code | character varying(10) | C | |
sli_mat_code | character varying(4) | C | |
sli_clr_code | character varying(3) | C | |
Indexe:
"sa_lining_active_pkey" PRIMARY KEY, btree (id_sli)

cpsdb_matcol=# \d sa_insole;
Tabelle ╗public.sa_insole½
Spalte | Typ | Sortierfolge | NULL erlaubt? | Vorgabewert
--------------+-----------------------+--------------+---------------+----------------------------------
id_sin | integer | | not null | generated by default as identity
sin_season | smallint | | |
sin_sa_code | character varying(10) | C | |
sin_mat_code | character varying(4) | C | |
sin_clr_code | character varying(3) | C | |
Indexe:
"sa_insole_active_pkey" PRIMARY KEY, btree (id_sin)

cpsdb_matcol=# \d sa_outsole;
Tabelle ╗public.sa_outsole½
Spalte | Typ | Sortierfolge | NULL erlaubt? | Vorgabewert
--------------+-----------------------+--------------+---------------+----------------------------------
id_sou | integer | | not null | generated by default as identity
sou_season | smallint | | |
sou_sa_code | character varying(10) | C | |
sou_mat_code | character varying(4) | C | |
sou_clr_code | character varying(3) | C | |
Indexe:
"sa_outsole_active_pkey" PRIMARY KEY, btree (id_sou)

The xxx_target tables are very similiar, here the upper one as an example:
They are count_aggregates of the whole dataset, where up_mat_code=sup_mat_code etc.

cpsdb_matcol=# \d upper_target
Tabelle ╗admin.upper_target½
Spalte | Typ | Sortierfolge | NULL erlaubt? | Vorgabewert
-------------+----------+--------------+---------------+-------------
id_up | smallint | | |
nup | integer | | |
up_mat_code | text | C | |

I have reworked the two queries to show their complete explain plans:

1. query with left join in the qupd CTE:

\set only 'ONLY'

cpsdb_matcol=# explain analyze -- explain analyze verbose -- explain -- select * from ( -- select count(*) from ( -- select length(sel) from (
cpsdb_matcol-# with
cpsdb_matcol-# qup as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season -- all xxx_seasosn are always smallint
cpsdb_matcol(# ,curr_code-- all xx_code are always varchar(10)
cpsdb_matcol(# ,array_agg(id_up order by id_up)||array_fill(0::smallint,array[10]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_up) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sup_season as curr_season
cpsdb_matcol(# ,sup_sa_code as curr_code
cpsdb_matcol(# ,sup_mat_code as curr_mat_code
cpsdb_matcol(# ,sup_clr_code as curr_clr_code
cpsdb_matcol(# ,id_up
cpsdb_matcol(# ,coalesce(id_up,-1) as imask
cpsdb_matcol(# from :only sa_upper
cpsdb_matcol(# left join upper_target on up_mat_code=sup_mat_code and id_up <= (512-1-16)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qli as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season
cpsdb_matcol(# ,curr_code
cpsdb_matcol(# ,array_agg(id_li order by id_li)||array_fill(0::smallint,array[4]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_li) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sli_season as curr_season
cpsdb_matcol(# ,sli_sa_code as curr_code
cpsdb_matcol(# ,sli_mat_code as curr_mat_code
cpsdb_matcol(# ,sli_clr_code as curr_clr_code
cpsdb_matcol(# ,id_li
cpsdb_matcol(# ,coalesce(id_li,-1) as imask
cpsdb_matcol(# from :only sa_lining
cpsdb_matcol(# left join lining_target on li_mat_code=sli_mat_code and id_li <= (128-1-8)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qin as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season
cpsdb_matcol(# ,curr_code
cpsdb_matcol(# ,array_agg(id_in order by id_in)||array_fill(0::smallint,array[4]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_in) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sin_season as curr_season
cpsdb_matcol(# ,sin_sa_code as curr_code
cpsdb_matcol(# ,sin_mat_code as curr_mat_code
cpsdb_matcol(# ,sin_clr_code as curr_clr_code
cpsdb_matcol(# ,id_in
cpsdb_matcol(# ,coalesce(id_in,-1) as imask
cpsdb_matcol(# from :only sa_insole
cpsdb_matcol(# left join insole_target on in_mat_code=sin_mat_code and id_in <= (128-1-8)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qou as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season
cpsdb_matcol(# ,curr_code
cpsdb_matcol(# ,array_agg(id_ou order by id_ou)||array_fill(0::smallint,array[6]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_ou) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sou_season as curr_season
cpsdb_matcol(# ,sou_sa_code as curr_code
cpsdb_matcol(# ,sou_mat_code as curr_mat_code
cpsdb_matcol(# ,sou_clr_code as curr_clr_code
cpsdb_matcol(# ,id_ou
cpsdb_matcol(# ,coalesce(id_ou,-1) as imask
cpsdb_matcol(# from :only sa_outsole
cpsdb_matcol(# left join outsole_target on ou_mat_code=sou_mat_code and id_ou <= (32-1-2)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qupd as (
cpsdb_matcol(# select * from (
cpsdb_matcol(# select
cpsdb_matcol(# qup.curr_season
cpsdb_matcol(# ,qup.curr_code
cpsdb_matcol(# ,qup.ibitmask|qin.ibitmask|qli.ibitmask|qou.ibitmask as ibitmask
cpsdb_matcol(# -- the calculations of new_mat_x are simplified here
cpsdb_matcol(# -- in the production version they are a more complex combination of bit masks, bit shifts and bit or of different elements of the arrays
cpsdb_matcol(# ,(qup.mat_arr[1]|qli.mat_arr[1]|qin.mat_arr[1]|qou.mat_arr[1])::bigint as new_mat_1
cpsdb_matcol(#
cpsdb_matcol(# ,(qup.mat_arr[2]|qli.mat_arr[2]|qin.mat_arr[2]|qou.mat_arr[2])::bigint as new_mat_2
cpsdb_matcol(#
cpsdb_matcol(# ,(qup.mat_arr[3]|qli.mat_arr[3]|qin.mat_arr[3]|qou.mat_arr[3])::bigint as new_mat_3
cpsdb_matcol(#
cpsdb_matcol(# from qup
cpsdb_matcol(# left join qli on (qli.curr_season=qup.curr_season and qli.curr_code=qup.curr_code and qli.ibitmask>0 and cardinality(qli.mat_arr) <=8)
cpsdb_matcol(# left join qin on (qin.curr_season=qup.curr_season and qin.curr_code=qup.curr_code and qin.ibitmask>0 and cardinality(qin.mat_arr) <=8)
cpsdb_matcol(# left join qou on (qou.curr_season=qup.curr_season and qou.curr_code=qup.curr_code and qou.ibitmask>0 and cardinality(qou.mat_arr) <=11)
cpsdb_matcol(# where qup.ibitmask>0 and cardinality(qup.mat_arr) <=21
cpsdb_matcol(# )qj
cpsdb_matcol(# where ibitmask is not null
cpsdb_matcol(# )
cpsdb_matcol-# ,qupda as (
cpsdb_matcol(# select
cpsdb_matcol(# qup.curr_season
cpsdb_matcol(# ,qup.curr_code
cpsdb_matcol(# ,repeat('0',64)||
cpsdb_matcol(# repeat('11',coalesce(cardinality(qou.matcode_arr),0))||repeat('10',coalesce(cardinality(qin.matcode_arr),0))||
cpsdb_matcol(# repeat('01',coalesce(cardinality(qou.matcode_arr),0))||repeat('00',coalesce(cardinality(qup.matcode_arr),0))||
cpsdb_matcol(# '00' as curr_mattype_bitmask
cpsdb_matcol(# ,qup.matcode_arr||qli.matcode_arr||qin.matcode_arr||qou.matcode_arr as curr_matcode_arr
cpsdb_matcol(# from qup
cpsdb_matcol(# left join qli on qli.curr_season=qup.curr_season and qli.curr_code=qup.curr_code and (qli.ibitmask<0 or cardinality(qli.mat_arr) >8)
cpsdb_matcol(# left join qin on qin.curr_season=qup.curr_season and qin.curr_code=qup.curr_code and (qin.ibitmask<0 or cardinality(qin.mat_arr) >8)
cpsdb_matcol(# left join qou on qou.curr_season=qup.curr_season and qou.curr_code=qup.curr_code and (qou.ibitmask<0 or cardinality(qou.mat_arr) >11)
cpsdb_matcol(# where qup.ibitmask<0 or cardinality(qup.mat_arr) >21
cpsdb_matcol(# )
cpsdb_matcol-# select
cpsdb_matcol-# curr_season
cpsdb_matcol-# ,curr_code
cpsdb_matcol-# ,new_mat_1
cpsdb_matcol-# ,new_mat_2
cpsdb_matcol-# ,new_mat_3
cpsdb_matcol-# ,NULL::bigint as new_mattype_bitmask
cpsdb_matcol-# ,NULL as new_mat_codes
cpsdb_matcol-# from qupd
cpsdb_matcol-# union all
cpsdb_matcol-# select
cpsdb_matcol-# curr_season
cpsdb_matcol-# ,curr_code
cpsdb_matcol-# ,NULL::bigint as new_mat_1
cpsdb_matcol-# ,NULL::bigint as new_mat_2
cpsdb_matcol-# ,NULL::bigint as new_mat_3
cpsdb_matcol-# ,substr(curr_mattype_bitmask,length(curr_mattype_bitmask)-63)::bit(64)::bigint as new_mattype_bitmask
cpsdb_matcol-# ,curr_matcode_arr as new_mat_codes
cpsdb_matcol-# from qupda
cpsdb_matcol-# ;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
Append (cost=13673.81..17462.84 rows=5734 width=104) (actual time=169.382..210.799 rows=9963 loops=1)
CTE qup
-> GroupAggregate (cost=5231.22..6303.78 rows=10320 width=80) (actual time=35.064..68.308 rows=10735 loops=1)
Group Key: sa_upper.sup_season, sa_upper.sup_sa_code
-> Sort (cost=5231.22..5358.64 rows=50969 width=18) (actual time=35.053..36.412 rows=50969 loops=1)
Sort Key: sa_upper.sup_season, sa_upper.sup_sa_code COLLATE "C"
Sort Method: quicksort Memory: 4722kB
-> Hash Left Join (cost=41.71..1246.13 rows=50969 width=18) (actual time=0.165..10.562 rows=50969 loops=1)
Hash Cond: ((sa_upper.sup_mat_code)::text = upper_target.up_mat_code)
-> Seq Scan on sa_upper (cost=0.00..884.69 rows=50969 width=16) (actual time=0.006..1.990 rows=50969 loops=1)
-> Hash (cost=35.53..35.53 rows=495 width=6) (actual time=0.157..0.157 rows=495 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 27kB
-> Seq Scan on upper_target (cost=0.00..35.53 rows=495 width=6) (actual time=0.006..0.115 rows=495 loops=1)
Filter: (id_up <= 495)
Rows Removed by Filter: 1467
CTE qli
-> GroupAggregate (cost=1097.31..1486.56 rows=10469 width=80) (actual time=9.354..28.199 rows=10469 loops=1)
Group Key: sa_lining.sli_season, sa_lining.sli_sa_code
-> Sort (cost=1097.31..1126.74 rows=11774 width=18) (actual time=9.347..9.711 rows=11774 loops=1)
Sort Key: sa_lining.sli_season, sa_lining.sli_sa_code COLLATE "C"
Sort Method: quicksort Memory: 1120kB
-> Hash Left Join (cost=7.34..301.19 rows=11774 width=18) (actual time=0.049..2.397 rows=11774 loops=1)
Hash Cond: ((sa_lining.sli_mat_code)::text = lining_target.li_mat_code)
-> Seq Scan on sa_lining (cost=0.00..204.74 rows=11774 width=16) (actual time=0.009..0.469 rows=11774 loops=1)
-> Hash (cost=5.86..5.86 rows=118 width=6) (actual time=0.037..0.037 rows=119 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 13kB
-> Seq Scan on lining_target (cost=0.00..5.86 rows=118 width=6) (actual time=0.008..0.025 rows=119 loops=1)
Filter: (id_li <= 119)
Rows Removed by Filter: 190
CTE qin
-> GroupAggregate (cost=1427.34..1880.73 rows=10678 width=80) (actual time=11.453..32.317 rows=10678 loops=1)
Group Key: sa_insole.sin_season, sa_insole.sin_sa_code
-> Sort (cost=1427.34..1465.41 rows=15230 width=18) (actual time=11.444..11.943 rows=15230 loops=1)
Sort Key: sa_insole.sin_season, sa_insole.sin_sa_code COLLATE "C"
Sort Method: quicksort Memory: 1336kB
-> Hash Left Join (cost=10.49..369.26 rows=15230 width=18) (actual time=0.051..3.098 rows=15230 loops=1)
Hash Cond: ((sa_insole.sin_mat_code)::text = insole_target.in_mat_code)
-> Seq Scan on sa_insole (cost=0.00..264.30 rows=15230 width=16) (actual time=0.007..0.608 rows=15230 loops=1)
-> Hash (cost=9.01..9.01 rows=118 width=6) (actual time=0.041..0.041 rows=119 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 13kB
-> Seq Scan on insole_target (cost=0.00..9.01 rows=118 width=6) (actual time=0.007..0.031 rows=119 loops=1)
Filter: (id_in <= 119)
Rows Removed by Filter: 362
CTE qou
-> GroupAggregate (cost=2366.22..2986.89 rows=10699 width=80) (actual time=18.055..42.079 rows=10699 loops=1)
Group Key: sa_outsole.sou_season, sa_outsole.sou_sa_code
-> Sort (cost=2366.22..2428.14 rows=24768 width=18) (actual time=18.043..18.798 rows=24768 loops=1)
Sort Key: sa_outsole.sou_season, sa_outsole.sou_sa_code COLLATE "C"
Sort Method: quicksort Memory: 2317kB
-> Hash Left Join (cost=5.39..558.63 rows=24768 width=18) (actual time=0.037..5.017 rows=24768 loops=1)
Hash Cond: ((sa_outsole.sou_mat_code)::text = outsole_target.ou_mat_code)
-> Seq Scan on sa_outsole (cost=0.00..430.68 rows=24768 width=16) (actual time=0.008..0.998 rows=24768 loops=1)
-> Hash (cost=5.03..5.03 rows=29 width=6) (actual time=0.025..0.025 rows=29 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 10kB
-> Seq Scan on outsole_target (cost=0.00..5.03 rows=29 width=6) (actual time=0.009..0.020 rows=29 loops=1)
Filter: (id_ou <= 29)
Rows Removed by Filter: 213
-> Hash Join (cost=1015.85..1319.04 rows=1 width=104) (actual time=169.382..203.707 rows=8548 loops=1)
Hash Cond: ((qou.curr_season = qli.curr_season) AND ((qou.curr_code)::text = (qli.curr_code)::text))
Join Filter: ((((qup.ibitmask | qin.ibitmask) | qli.ibitmask) | qou.ibitmask) IS NOT NULL)
-> CTE Scan on qou (cost=0.00..294.22 rows=1189 width=76) (actual time=18.057..45.448 rows=10275 loops=1)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 11))
Rows Removed by Filter: 424
-> Hash (cost=1015.83..1015.83 rows=1 width=228) (actual time=151.316..151.317 rows=8845 loops=1)
Buckets: 16384 (originally 1024) Batches: 1 (originally 1) Memory Usage: 1899kB
-> Hash Join (cost=707.35..1015.83 rows=1 width=228) (actual time=122.483..149.030 rows=8845 loops=1)
Hash Cond: ((qin.curr_season = qli.curr_season) AND ((qin.curr_code)::text = (qli.curr_code)::text))
-> CTE Scan on qin (cost=0.00..293.65 rows=1186 width=76) (actual time=11.454..35.456 rows=10197 loops=1)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 8))
Rows Removed by Filter: 481
-> Hash (cost=706.86..706.86 rows=33 width=152) (actual time=111.026..111.027 rows=9007 loops=1)
Buckets: 16384 (originally 1024) Batches: 1 (originally 1) Memory Usage: 1473kB
-> Merge Join (cost=689.20..706.86 rows=33 width=152) (actual time=106.441..109.505 rows=9007 loops=1)
Merge Cond: ((qup.curr_season = qli.curr_season) AND ((qup.curr_code)::text = (qli.curr_code)::text))
-> Sort (cost=342.09..344.96 rows=1147 width=76) (actual time=73.200..73.429 rows=9320 loops=1)
Sort Key: qup.curr_season, qup.curr_code COLLATE "C"
Sort Method: quicksort Memory: 1391kB
-> CTE Scan on qup (cost=0.00..283.80 rows=1147 width=76) (actual time=35.067..71.872 rows=9320 loops=1)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 21))
Rows Removed by Filter: 1415
-> Sort (cost=347.12..350.02 rows=1163 width=76) (actual time=33.239..33.490 rows=10289 loops=1)
Sort Key: qli.curr_season, qli.curr_code COLLATE "C"
Sort Method: quicksort Memory: 1349kB
-> CTE Scan on qli (cost=0.00..287.90 rows=1163 width=76) (actual time=9.355..31.457 rows=10289 loops=1)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 8))
Rows Removed by Filter: 180
-> Merge Left Join (cost=2625.49..3399.84 rows=5733 width=104) (actual time=4.529..6.645 rows=1415 loops=1)
Merge Cond: ((qup_1.curr_season = qou_1.curr_season) AND ((qup_1.curr_code)::text = (qou_1.curr_code)::text))
-> Merge Left Join (cost=1958.66..2135.28 rows=5733 width=136) (actual time=3.388..3.833 rows=1415 loops=1)
Merge Cond: ((qup_1.curr_season = qin_1.curr_season) AND ((qup_1.curr_code)::text = (qin_1.curr_code)::text))
-> Merge Left Join (cost=1293.25..1388.21 rows=5733 width=104) (actual time=2.297..2.534 rows=1415 loops=1)
Merge Cond: ((qup_1.curr_season = qli_1.curr_season) AND ((qup_1.curr_code)::text = (qli_1.curr_code)::text))
-> Sort (cost=641.68..656.02 rows=5733 width=72) (actual time=1.278..1.315 rows=1415 loops=1)
Sort Key: qup_1.curr_season, qup_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 204kB
-> CTE Scan on qup qup_1 (cost=0.00..283.80 rows=5733 width=72) (actual time=0.009..1.081 rows=1415 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 21))
Rows Removed by Filter: 9320
-> Sort (cost=651.57..666.11 rows=5816 width=72) (actual time=1.017..1.022 rows=180 loops=1)
Sort Key: qli_1.curr_season, qli_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 41kB
-> CTE Scan on qli qli_1 (cost=0.00..287.90 rows=5816 width=72) (actual time=0.054..0.994 rows=180 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 8))
Rows Removed by Filter: 10289
-> Sort (cost=665.41..680.24 rows=5932 width=72) (actual time=1.089..1.103 rows=481 loops=1)
Sort Key: qin_1.curr_season, qin_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 68kB
-> CTE Scan on qin qin_1 (cost=0.00..293.65 rows=5932 width=72) (actual time=0.016..1.022 rows=481 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 8))
Rows Removed by Filter: 10197
-> Sort (cost=666.83..681.69 rows=5944 width=72) (actual time=1.134..1.145 rows=417 loops=1)
Sort Key: qou_1.curr_season, qou_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 68kB
-> CTE Scan on qou qou_1 (cost=0.00..294.22 rows=5944 width=72) (actual time=0.029..1.038 rows=424 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 11))
Rows Removed by Filter: 10275
Planning Time: 1.055 ms
Execution Time: 212.800 ms
(118 Zeilen)

As seen in the line of the qupd CTE

-> Merge Join (cost=689.20..706.86 rows=33 width=152) (actual time=106.441..109.505 rows=9007 loops=1)

the row count of the second join round drops to 33 and for the third round it drops to 1

-> Hash Join (cost=707.35..1015.83 rows=1 width=228) (actual time=122.483..149.030 rows=8845 loops=1)

BTW, I don't know, why the second join group (part of qupda) gets a complete different plan.

--------------------------------------------

Here is the second question, different from the first only by replacing the left join to inner join in the join group of qupd:

\set only 'ONLY'

cpsdb_matcol=# explain analyze -- explain analyze verbose -- explain -- select * from ( -- select count(*) from ( -- select length(sel) from (
cpsdb_matcol-# with
cpsdb_matcol-# qup as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season -- all xxx_seasosn are always smallint
cpsdb_matcol(# ,curr_code-- all xx_code are always varchar(10)
cpsdb_matcol(# ,array_agg(id_up order by id_up)||array_fill(0::smallint,array[10]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_up) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sup_season as curr_season
cpsdb_matcol(# ,sup_sa_code as curr_code
cpsdb_matcol(# ,sup_mat_code as curr_mat_code
cpsdb_matcol(# ,sup_clr_code as curr_clr_code
cpsdb_matcol(# ,id_up
cpsdb_matcol(# ,coalesce(id_up,-1) as imask
cpsdb_matcol(# from :only sa_upper
cpsdb_matcol(# left join upper_target on up_mat_code=sup_mat_code and id_up <= (512-1-16)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qli as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season
cpsdb_matcol(# ,curr_code
cpsdb_matcol(# ,array_agg(id_li order by id_li)||array_fill(0::smallint,array[4]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_li) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sli_season as curr_season
cpsdb_matcol(# ,sli_sa_code as curr_code
cpsdb_matcol(# ,sli_mat_code as curr_mat_code
cpsdb_matcol(# ,sli_clr_code as curr_clr_code
cpsdb_matcol(# ,id_li
cpsdb_matcol(# ,coalesce(id_li,-1) as imask
cpsdb_matcol(# from :only sa_lining
cpsdb_matcol(# left join lining_target on li_mat_code=sli_mat_code and id_li <= (128-1-8)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qin as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season
cpsdb_matcol(# ,curr_code
cpsdb_matcol(# ,array_agg(id_in order by id_in)||array_fill(0::smallint,array[4]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_in) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sin_season as curr_season
cpsdb_matcol(# ,sin_sa_code as curr_code
cpsdb_matcol(# ,sin_mat_code as curr_mat_code
cpsdb_matcol(# ,sin_clr_code as curr_clr_code
cpsdb_matcol(# ,id_in
cpsdb_matcol(# ,coalesce(id_in,-1) as imask
cpsdb_matcol(# from :only sa_insole
cpsdb_matcol(# left join insole_target on in_mat_code=sin_mat_code and id_in <= (128-1-8)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qou as (
cpsdb_matcol(# select
cpsdb_matcol(# curr_season
cpsdb_matcol(# ,curr_code
cpsdb_matcol(# ,array_agg(id_ou order by id_ou)||array_fill(0::smallint,array[6]) as mat_arr
cpsdb_matcol(# ,array_agg(curr_mat_code order by id_ou) as matcode_arr
cpsdb_matcol(# ,bit_or(imask) as ibitmask
cpsdb_matcol(# from(
cpsdb_matcol(# select
cpsdb_matcol(# sou_season as curr_season
cpsdb_matcol(# ,sou_sa_code as curr_code
cpsdb_matcol(# ,sou_mat_code as curr_mat_code
cpsdb_matcol(# ,sou_clr_code as curr_clr_code
cpsdb_matcol(# ,id_ou
cpsdb_matcol(# ,coalesce(id_ou,-1) as imask
cpsdb_matcol(# from :only sa_outsole
cpsdb_matcol(# left join outsole_target on ou_mat_code=sou_mat_code and id_ou <= (32-1-2)
cpsdb_matcol(# )qr
cpsdb_matcol(# group by 1,2
cpsdb_matcol(# )
cpsdb_matcol-# ,qupd as (
cpsdb_matcol(# select
cpsdb_matcol(# qup.curr_season
cpsdb_matcol(# ,qup.curr_code
cpsdb_matcol(# ,qup.ibitmask|qin.ibitmask|qli.ibitmask|qou.ibitmask as ibitmask
cpsdb_matcol(# -- the calculations of new_mat_x are simplified here
cpsdb_matcol(# -- in the production version they are a more complex combination of bit masks, bit shifts and bit or of different elements of the arrays
cpsdb_matcol(# ,(qup.mat_arr[1]|qli.mat_arr[1]|qin.mat_arr[1]|qou.mat_arr[1])::bigint as new_mat_1
cpsdb_matcol(#
cpsdb_matcol(# ,(qup.mat_arr[2]|qli.mat_arr[2]|qin.mat_arr[2]|qou.mat_arr[2])::bigint as new_mat_2
cpsdb_matcol(#
cpsdb_matcol(# ,(qup.mat_arr[3]|qli.mat_arr[3]|qin.mat_arr[3]|qou.mat_arr[3])::bigint as new_mat_3
cpsdb_matcol(#
cpsdb_matcol(# from qup
cpsdb_matcol(# join qli on (qli.curr_season=qup.curr_season and qli.curr_code=qup.curr_code and qli.ibitmask>0 and cardinality(qli.mat_arr) <=8)
cpsdb_matcol(# join qin on (qin.curr_season=qup.curr_season and qin.curr_code=qup.curr_code and qin.ibitmask>0 and cardinality(qin.mat_arr) <=8)
cpsdb_matcol(# join qou on (qou.curr_season=qup.curr_season and qou.curr_code=qup.curr_code and qou.ibitmask>0 and cardinality(qou.mat_arr) <=11)
cpsdb_matcol(# where qup.ibitmask>0 and cardinality(qup.mat_arr) <=21
cpsdb_matcol(# )
cpsdb_matcol-# ,qupda as (
cpsdb_matcol(# select
cpsdb_matcol(# qup.curr_season
cpsdb_matcol(# ,qup.curr_code
cpsdb_matcol(# ,repeat('0',64)||
cpsdb_matcol(# repeat('11',coalesce(cardinality(qou.matcode_arr),0))||repeat('10',coalesce(cardinality(qin.matcode_arr),0))||
cpsdb_matcol(# repeat('01',coalesce(cardinality(qou.matcode_arr),0))||repeat('00',coalesce(cardinality(qup.matcode_arr),0))||
cpsdb_matcol(# '00' as curr_mattype_bitmask
cpsdb_matcol(# ,qup.matcode_arr||qli.matcode_arr||qin.matcode_arr||qou.matcode_arr as curr_matcode_arr
cpsdb_matcol(# from qup
cpsdb_matcol(# left join qli on qli.curr_season=qup.curr_season and qli.curr_code=qup.curr_code and (qli.ibitmask<0 or cardinality(qli.mat_arr) >8)
cpsdb_matcol(# left join qin on qin.curr_season=qup.curr_season and qin.curr_code=qup.curr_code and (qin.ibitmask<0 or cardinality(qin.mat_arr) >8)
cpsdb_matcol(# left join qou on qou.curr_season=qup.curr_season and qou.curr_code=qup.curr_code and (qou.ibitmask<0 or cardinality(qou.mat_arr) >11)
cpsdb_matcol(# where qup.ibitmask<0 or cardinality(qup.mat_arr) >21
cpsdb_matcol(# )
cpsdb_matcol-# select
cpsdb_matcol-# curr_season
cpsdb_matcol-# ,curr_code
cpsdb_matcol-# ,new_mat_1
cpsdb_matcol-# ,new_mat_2
cpsdb_matcol-# ,new_mat_3
cpsdb_matcol-# ,NULL::bigint as new_mattype_bitmask
cpsdb_matcol-# ,NULL as new_mat_codes
cpsdb_matcol-# from qupd
cpsdb_matcol-# union all
cpsdb_matcol-# select
cpsdb_matcol-# curr_season
cpsdb_matcol-# ,curr_code
cpsdb_matcol-# ,NULL::bigint as new_mat_1
cpsdb_matcol-# ,NULL::bigint as new_mat_2
cpsdb_matcol-# ,NULL::bigint as new_mat_3
cpsdb_matcol-# ,substr(curr_mattype_bitmask,length(curr_mattype_bitmask)-63)::bit(64)::bigint as new_mattype_bitmask
cpsdb_matcol-# ,curr_matcode_arr as new_mat_codes
cpsdb_matcol-# from qupda
cpsdb_matcol-# ;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------
Append (cost=13365.31..17471.72 rows=5734 width=104) (actual time=139.730..13430.641 rows=9963 loops=1)
CTE qup
-> GroupAggregate (cost=5231.22..6303.78 rows=10320 width=80) (actual time=35.337..67.779 rows=10735 loops=1)
Group Key: sa_upper.sup_season, sa_upper.sup_sa_code
-> Sort (cost=5231.22..5358.64 rows=50969 width=18) (actual time=35.326..36.704 rows=50969 loops=1)
Sort Key: sa_upper.sup_season, sa_upper.sup_sa_code COLLATE "C"
Sort Method: quicksort Memory: 4722kB
-> Hash Left Join (cost=41.71..1246.13 rows=50969 width=18) (actual time=0.179..10.787 rows=50969 loops=1)
Hash Cond: ((sa_upper.sup_mat_code)::text = upper_target.up_mat_code)
-> Seq Scan on sa_upper (cost=0.00..884.69 rows=50969 width=16) (actual time=0.009..1.990 rows=50969 loops=1)
-> Hash (cost=35.53..35.53 rows=495 width=6) (actual time=0.164..0.164 rows=495 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 27kB
-> Seq Scan on upper_target (cost=0.00..35.53 rows=495 width=6) (actual time=0.006..0.128 rows=495 loops=1)
Filter: (id_up <= 495)
Rows Removed by Filter: 1467
CTE qli
-> GroupAggregate (cost=1097.31..1486.56 rows=10469 width=80) (actual time=9.434..27.620 rows=10469 loops=1)
Group Key: sa_lining.sli_season, sa_lining.sli_sa_code
-> Sort (cost=1097.31..1126.74 rows=11774 width=18) (actual time=9.424..9.796 rows=11774 loops=1)
Sort Key: sa_lining.sli_season, sa_lining.sli_sa_code COLLATE "C"
Sort Method: quicksort Memory: 1120kB
-> Hash Left Join (cost=7.34..301.19 rows=11774 width=18) (actual time=0.049..2.444 rows=11774 loops=1)
Hash Cond: ((sa_lining.sli_mat_code)::text = lining_target.li_mat_code)
-> Seq Scan on sa_lining (cost=0.00..204.74 rows=11774 width=16) (actual time=0.009..0.476 rows=11774 loops=1)
-> Hash (cost=5.86..5.86 rows=118 width=6) (actual time=0.036..0.036 rows=119 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 13kB
-> Seq Scan on lining_target (cost=0.00..5.86 rows=118 width=6) (actual time=0.008..0.026 rows=119 loops=1)
Filter: (id_li <= 119)
Rows Removed by Filter: 190
CTE qin
-> GroupAggregate (cost=1427.34..1880.73 rows=10678 width=80) (actual time=11.578..31.510 rows=10678 loops=1)
Group Key: sa_insole.sin_season, sa_insole.sin_sa_code
-> Sort (cost=1427.34..1465.41 rows=15230 width=18) (actual time=11.572..12.044 rows=15230 loops=1)
Sort Key: sa_insole.sin_season, sa_insole.sin_sa_code COLLATE "C"
Sort Method: quicksort Memory: 1336kB
-> Hash Left Join (cost=10.49..369.26 rows=15230 width=18) (actual time=0.056..3.120 rows=15230 loops=1)
Hash Cond: ((sa_insole.sin_mat_code)::text = insole_target.in_mat_code)
-> Seq Scan on sa_insole (cost=0.00..264.30 rows=15230 width=16) (actual time=0.008..0.609 rows=15230 loops=1)
-> Hash (cost=9.01..9.01 rows=118 width=6) (actual time=0.044..0.045 rows=119 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 13kB
-> Seq Scan on insole_target (cost=0.00..9.01 rows=118 width=6) (actual time=0.008..0.033 rows=119 loops=1)
Filter: (id_in <= 119)
Rows Removed by Filter: 362
CTE qou
-> GroupAggregate (cost=2366.22..2986.89 rows=10699 width=80) (actual time=18.295..51.236 rows=10699 loops=1)
Group Key: sa_outsole.sou_season, sa_outsole.sou_sa_code
-> Sort (cost=2366.22..2428.14 rows=24768 width=18) (actual time=18.281..20.157 rows=24768 loops=1)
Sort Key: sa_outsole.sou_season, sa_outsole.sou_sa_code COLLATE "C"
Sort Method: quicksort Memory: 2317kB
-> Hash Left Join (cost=5.39..558.63 rows=24768 width=18) (actual time=0.036..5.080 rows=24768 loops=1)
Hash Cond: ((sa_outsole.sou_mat_code)::text = outsole_target.ou_mat_code)
-> Seq Scan on sa_outsole (cost=0.00..430.68 rows=24768 width=16) (actual time=0.009..1.017 rows=24768 loops=1)
-> Hash (cost=5.03..5.03 rows=29 width=6) (actual time=0.024..0.025 rows=29 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 10kB
-> Seq Scan on outsole_target (cost=0.00..5.03 rows=29 width=6) (actual time=0.007..0.018 rows=29 loops=1)
Filter: (id_ou <= 29)
Rows Removed by Filter: 213
-> Nested Loop (cost=707.35..1327.91 rows=1 width=104) (actual time=139.729..13423.084 rows=8548 loops=1)
Join Filter: ((qli.curr_season = qin.curr_season) AND ((qli.curr_code)::text = (qin.curr_code)::text))
Rows Removed by Join Filter: 88552397
-> Hash Join (cost=707.35..1016.45 rows=1 width=216) (actual time=128.145..169.287 rows=8685 loops=1)
Hash Cond: ((qou.curr_season = qli.curr_season) AND ((qou.curr_code)::text = (qli.curr_code)::text))
-> CTE Scan on qou (cost=0.00..294.22 rows=1189 width=72) (actual time=18.297..55.085 rows=10275 loops=1)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 11))
Rows Removed by Filter: 424
-> Hash (cost=706.86..706.86 rows=33 width=144) (actual time=109.843..109.845 rows=9007 loops=1)
Buckets: 16384 (originally 1024) Batches: 1 (originally 1) Memory Usage: 1369kB
-> Merge Join (cost=689.20..706.86 rows=33 width=144) (actual time=105.294..108.377 rows=9007 loops=1)
Merge Cond: ((qup.curr_season = qli.curr_season) AND ((qup.curr_code)::text = (qli.curr_code)::text))
-> Sort (cost=342.09..344.96 rows=1147 width=72) (actual time=72.693..72.923 rows=9320 loops=1)
Sort Key: qup.curr_season, qup.curr_code COLLATE "C"
Sort Method: quicksort Memory: 1357kB
-> CTE Scan on qup (cost=0.00..283.80 rows=1147 width=72) (actual time=35.339..71.419 rows=9320 loops=1)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 21))
Rows Removed by Filter: 1415
-> Sort (cost=347.12..350.02 rows=1163 width=72) (actual time=32.598..32.861 rows=10289 loops=1)
Sort Key: qli.curr_season, qli.curr_code COLLATE "C"
Sort Method: quicksort Memory: 1269kB
-> CTE Scan on qli (cost=0.00..287.90 rows=1163 width=72) (actual time=9.436..30.852 rows=10289 loops=1)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 8))
Rows Removed by Filter: 180
-> CTE Scan on qin (cost=0.00..293.65 rows=1186 width=72) (actual time=0.001..1.163 rows=10197 loops=8685)
Filter: ((ibitmask > 0) AND (cardinality(mat_arr) <= 8))
Rows Removed by Filter: 481
-> Merge Left Join (cost=2625.49..3399.84 rows=5733 width=104) (actual time=4.622..6.715 rows=1415 loops=1)
Merge Cond: ((qup_1.curr_season = qou_1.curr_season) AND ((qup_1.curr_code)::text = (qou_1.curr_code)::text))
-> Merge Left Join (cost=1958.66..2135.28 rows=5733 width=136) (actual time=3.489..3.937 rows=1415 loops=1)
Merge Cond: ((qup_1.curr_season = qin_1.curr_season) AND ((qup_1.curr_code)::text = (qin_1.curr_code)::text))
-> Merge Left Join (cost=1293.25..1388.21 rows=5733 width=104) (actual time=2.376..2.614 rows=1415 loops=1)
Merge Cond: ((qup_1.curr_season = qli_1.curr_season) AND ((qup_1.curr_code)::text = (qli_1.curr_code)::text))
-> Sort (cost=641.68..656.02 rows=5733 width=72) (actual time=1.300..1.337 rows=1415 loops=1)
Sort Key: qup_1.curr_season, qup_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 204kB
-> CTE Scan on qup qup_1 (cost=0.00..283.80 rows=5733 width=72) (actual time=0.010..1.119 rows=1415 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 21))
Rows Removed by Filter: 9320
-> Sort (cost=651.57..666.11 rows=5816 width=72) (actual time=1.073..1.078 rows=180 loops=1)
Sort Key: qli_1.curr_season, qli_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 41kB
-> CTE Scan on qli qli_1 (cost=0.00..287.90 rows=5816 width=72) (actual time=0.057..1.029 rows=180 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 8))
Rows Removed by Filter: 10289
-> Sort (cost=665.41..680.24 rows=5932 width=72) (actual time=1.111..1.124 rows=481 loops=1)
Sort Key: qin_1.curr_season, qin_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 68kB
-> CTE Scan on qin qin_1 (cost=0.00..293.65 rows=5932 width=72) (actual time=0.016..1.045 rows=481 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 8))
Rows Removed by Filter: 10197
-> Sort (cost=666.83..681.69 rows=5944 width=72) (actual time=1.125..1.135 rows=417 loops=1)
Sort Key: qou_1.curr_season, qou_1.curr_code COLLATE "C"
Sort Method: quicksort Memory: 68kB
-> CTE Scan on qou qou_1 (cost=0.00..294.22 rows=5944 width=72) (actual time=0.029..1.063 rows=424 loops=1)
Filter: ((ibitmask < 0) OR (cardinality(mat_arr) > 11))
Rows Removed by Filter: 10275
Planning Time: 0.969 ms
Execution Time: 13432.726 ms
(116 Zeilen)

(All plans are unchanged, cut/pasted from psql window)

In qupd we find the same rows estimations as above, as shown in the lines

-> Hash (cost=706.86..706.86 rows=33 width=144) (actual time=109.843..109.845 rows=9007 loops=1)

-> Nested Loop (cost=707.35..1327.91 rows=1 width=104) (actual time=139.729..13423.084 rows=8548 loops=1)

---------

In both queries I haven't used materialized CTEs explicitely, but the first 4 CTE's are used in 2 different subsequent CTE's.

This query is not fully optimized for frequent use, it is only used for refactoring old data, but finally it will use a 10fold bigger dataset.
(Optimizing could eleminate the cardinality function in join conditions, eliminate materialized CTEs etc).

I only encountered the long execution time in the second query (with inner joins), which let me analyze and dig to the root cause.
The use of the nested loop in the third inner join round took very long and eliminated about 9 million rows (on a quad join with 4 datasets of about 10000 tuples).

I wanted to draw attention on my accidently findings, but I am not able to fully understand or investigate in the source code :-(.

I conclude that the row estimation in this example seems wrong ((left) outer join case) or too strict (inner join case, only 1/33 estimated from the previous step!)

I Hope this updated information may help you

Hans Buschmann

________________________________
Von: Tomas Vondra <tomas(dot)vondra(at)enterprisedb(dot)com>
Gesendet: Mittwoch, 8. Februar 2023 22:27
An: Hans Buschmann; pgsql-hackers(at)lists(dot)postgresql(dot)org
Betreff: Re: Wrong rows estimations with joins of CTEs slows queries by more than factor 500

On 2/8/23 14:55, Hans Buschmann wrote:
> During data refactoring of our Application I encountered $subject when
> joining 4 CTEs with left join or inner join.
>
>
> 1. Background
>
> PG 15.1 on Windows x64 (OS seems no to have no meening here)
>
>
> I try to collect data from 4 (analyzed) tables (up,li,in,ou) by grouping
> certain data (4 CTEs qup,qli,qin,qou)
>
> The grouping of the data in the CTEs gives estimated row counts of about
> 1000 (1 tenth of the real value) This is OK for estimation.
>
>
> These 4 CTEs are then used to combine the data by joining them.
>
>
> 2. Problem
>
> The 4 CTEs are joined by left joins as shown below:
>
...
>
> This case really brought me to detect the problem!
>
> The original query and data are not shown here, but the principle should
> be clear from the execution plans.
>
> I think the planner shouldn't change the row estimations on further
> steps after left joins at all, and be a bit more conservative on inner
> joins.

But the code should alredy do exactly that, see:

https://github.com/postgres/postgres/blob/dbe8a1726cfd5a09cf1ef99e76f5f89e2efada71/src/backend/optimizer/path/costsize.c#L5212

And in fact, the second part of the plains shows it's doing the trick:

-> Merge Left Join (cost=1293.25..1388.21 rows=5733 width=104)
(actual time=2.321..2.556 rows=1415 loops=1)
Merge Cond: ((qup_1.curr_season = qli_1.curr_season) AND
((qup_1.curr_code)::text = (qli_1.curr_code)::text))
-> Sort (cost=641.68..656.02 rows=5733 width=72)
-> Sort (cost=651.57..666.11 rows=5816 width=72)

But notice the first join (with rows=33) doesn't say "Left". And I see
there's Append on top, so presumably the query is much more complex, and
there's a regular join of these CTEs in some other part.

We'll need to se the whole query, not just one chunk of it.

FWIW it seems you're using materialized CTEs - that's likely pretty bad
for the estimates, because we don't propagate statistics from the CTE.
So a join on CTEs can't see statistics from the underlying tables, and
that can easily produce really bad estimates.

I'm assuming you're not using AS MATERIALIZED explicitly, so I'd bet
this happens because the "cardinality" function is marked as volatile.
Perhaps it can be redefined as stable/immutable.

> This may be related to the fact that this case has 2 join-conditions
> (xx_season an xx_code).

That shouldn't affect outer join estimates this way (but as I explained
above, the join does not seem to be "left" per the explain).
Multi-column joins can cause issues, no doubt about it - but CTEs make
it worse because we can't e.g. see foreign keys.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company