Hi, hackers mergejoinscansel() calls get_variable_range() for both inner and outer relations to retrieve the minimum and maximum values of values[].
In the following code snippet inside get_variable_range(), when
STATISTIC_KIND_MCV_VALUE_SORTED
is present, we can avoid the O(n) comparisons on the MCV value[] performed by
get_stats_slot_range().
**This optimization eliminates all N comparisons entirely.**
```C
/*
* Like STATISTIC_KIND_HISTOGRAM: if the MCV slot is
* STATISTIC_KIND_MCV_VALUE_SORTED, it has the ordering
we want,
* grab the last and first values.
*/
if (sslot.stacoll == collation && sslot.nvalues > 0 &&
statskind == STATISTIC_KIND_MCV_VALUE_SORTED)
{
tmin = datumCopy(sslot.values[0], typByVal,
typLen);
tmax = datumCopy(sslot.values[sslot.nvalues -
1], typByVal, typLen);
have_data = true;
}
else
get_stats_slot_range(&sslot, opfuncoid, &opproc,
collation, typLen, typByVal,
&tmin,
&tmax, &have_data);
```C
Below are the test SQL statements and their results:
```SQL
drop table if exists t1;
create table t1(id int);
drop table if exists t2;
create table t2(id int);
insert into t1 select oid from pg_catalog.pg_class limit 20;
insert into t1 select oid from pg_catalog.pg_class limit 20;
insert into t2 select oid from pg_catalog.pg_class limit 20;
insert into t2 select oid from pg_catalog.pg_class limit 20;
create index idx_t1 on t1(id);
create index idx_t2 on t2(id);
analyze t1, t2;
select
attname,null_frac,n_distinct,most_common_vals,most_common_freqs,correlation
from pg_catalog.pg_stats where tablename in ('t1', 't2')\gx
xman7=# select
attname,null_frac,n_distinct,most_common_vals,most_common_freqs,correlation
from pg_catalog.pg_stats where tablename in ('t1', 't2')\gx
-[ RECORD 1
]-----+---------------------------------------------------------------------------------------------------------
attname | id
null_frac | 0
n_distinct | -0.5
most_common_vals |
{1247,2619,2830,2831,2832,2833,2836,2837,2840,4157,4158,4159,4160,4171,4172,6351,6352,16385,16399,16402}
most_common_freqs |
{0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05}
correlation | 0.05403377
-[ RECORD 2
]-----+---------------------------------------------------------------------------------------------------------
attname | id
null_frac | 0
n_distinct | -0.5
most_common_vals |
{1247,2619,2830,2831,2832,2833,2836,2837,2840,4157,4158,4159,4160,4171,4172,6351,6352,16385,16399,16402}
most_common_freqs |
{0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05}
correlation | 0.05403377
xman7=#
select * from pg_catalog.pg_statistic where starelid in (select oid from
pg_catalog.pg_class where relname in ('t1', 't2')) and staattnum = 1\gx
xman7=# select * from pg_catalog.pg_statistic where starelid in (select oid
from pg_catalog.pg_class where relname in ('t1', 't2')) and staattnum = 1\gx
-[ RECORD 1
]---------------------------------------------------------------------------------------------------------
starelid | 16399
staattnum | 1
stainherit | f
stanullfrac | 0
stawidth | 4
stadistinct | -0.5
stakind1 | 8
stakind2 | 3
stakind3 | 0
stakind4 | 0
stakind5 | 0
staop1 | 96
staop2 | 97
staop3 | 0
staop4 | 0
staop5 | 0
stacoll1 | 0
stacoll2 | 0
stacoll3 | 0
stacoll4 | 0
stacoll5 | 0
stanumbers1 |
{0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05}
stanumbers2 | {0.05403377}
stanumbers3 |
stanumbers4 |
stanumbers5 |
stavalues1 |
{1247,2619,2830,2831,2832,2833,2836,2837,2840,4157,4158,4159,4160,4171,4172,6351,6352,16385,16399,16402}
stavalues2 |
stavalues3 |
stavalues4 |
stavalues5 |
-[ RECORD 2
]---------------------------------------------------------------------------------------------------------
starelid | 16402
staattnum | 1
stainherit | f
stanullfrac | 0
stawidth | 4
stadistinct | -0.5
stakind1 | 8
stakind2 | 3
stakind3 | 0
stakind4 | 0
stakind5 | 0
staop1 | 96
staop2 | 97
staop3 | 0
staop4 | 0
staop5 | 0
stacoll1 | 0
stacoll2 | 0
stacoll3 | 0
stacoll4 | 0
stacoll5 | 0
stanumbers1 |
{0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05}
stanumbers2 | {0.05403377}
stanumbers3 |
stanumbers4 |
stanumbers5 |
stavalues1 |
{1247,2619,2830,2831,2832,2833,2836,2837,2840,4157,4158,4159,4160,4171,4172,6351,6352,16385,16399,16402}
stavalues2 |
stavalues3 |
stavalues4 |
stavalues5 |
xman7=#
set enable_hashjoin=off;
explain select * from t1 , t2 where t1.id = t2.id;
xman7=# explain select * from t1 , t2 where t1.id = t2.id;
QUERY PLAN
---------------------------------------------------------------
Merge Join (cost=4.93..6.33 rows=80 width=8)
Merge Cond: (t1.id = t2.id)
-> Sort (cost=2.46..2.56 rows=40 width=4)
Sort Key: t1.id
-> Seq Scan on t1 (cost=0.00..1.40 rows=40 width=4)
-> Sort (cost=2.46..2.56 rows=40 width=4)
Sort Key: t2.id
-> Seq Scan on t2 (cost=0.00..1.40 rows=40 width=4)
(8 rows)
xman7=#
```debug
bt
#0 get_variable_range (root=0x7fffecdb6178, vardata=0x7ffff3fa7d40, sortop=97,
collation=0, min=0x7ffff3fa7d00, max=0x7ffff3fa7d08) at
../7_patch/src/backend/utils/adt/selfuncs.c:7541
p sslot.values[0]
$1 = 1247
p sslot.values[sslot.nvalues - 1]
$2 = 16402
验证80 rows 的SQL:
xman7=# select * from t1 , t2 where t1.id = t2.id;
id | id
-------+-------
1247 | 1247
1247 | 1247
1247 | 1247
1247 | 1247
2619 | 2619
2619 | 2619
2619 | 2619
2619 | 2619
2830 | 2830
2830 | 2830
2830 | 2830
2830 | 2830
2831 | 2831
2831 | 2831
2831 | 2831
2831 | 2831
2832 | 2832
2832 | 2832
2832 | 2832
2832 | 2832
2833 | 2833
2833 | 2833
2833 | 2833
2833 | 2833
2836 | 2836
2836 | 2836
2836 | 2836
2836 | 2836
2837 | 2837
2837 | 2837
2837 | 2837
2837 | 2837
2840 | 2840
2840 | 2840
2840 | 2840
2840 | 2840
4157 | 4157
4157 | 4157
4157 | 4157
4157 | 4157
4158 | 4158
4158 | 4158
4158 | 4158
4158 | 4158
4159 | 4159
4159 | 4159
4159 | 4159
4159 | 4159
4160 | 4160
4160 | 4160
4160 | 4160
4160 | 4160
4171 | 4171
4171 | 4171
4171 | 4171
4171 | 4171
4172 | 4172
4172 | 4172
4172 | 4172
4172 | 4172
6351 | 6351
6351 | 6351
6351 | 6351
6351 | 6351
6352 | 6352
6352 | 6352
6352 | 6352
6352 | 6352
16385 | 16385
16385 | 16385
16385 | 16385
16385 | 16385
16399 | 16399
16399 | 16399
16399 | 16399
16399 | 16399
16402 | 16402
16402 | 16402
16402 | 16402
16402 | 16402
(80 rows)
xman7=#
regards,
--
ZizhuanLiu (X-MAN)
[email protected]
v4-0001-Optimize-MCV-statistics-for-sortable-types-by-lev.patch
Description: Binary data
