Re: Optimize MCV stats for sortable types and utilize sorted-order properties

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) 
44973863(at)qq(dot)com