ERROR: corrupt MVNDistinct entry

On 12/24/24 15:00, Richard Guo wrote:

Any thoughts?

I have a couple of notes.
1. The nulling_relids provides us sensible information about possible
nulls inside the input. We are not using it to estimate the number of
such nulls for now. Does Your idea consist of obtaining 'clear'
statistics and reusing nulling_relids knowledge somewhere later?
2. It is ok for Vars. But what about expressions? We use equal() in
distinct, MCV and dependencies modules. Do we need to remove nulls
before using extended statistics as a general rule?

--
regards, Andrei Lepikhov

On Tue, Dec 24, 2024 at 5:00 PM Richard Guo <guofenglinux@gmail.com> wrote:

It seems to me that when estimating the number of groups, we do not
need to concern ourselves with the outer joins that could null the
Vars/PHVs contained in the grouping expressions, and we should not
count the same Var more than once.

Furthermore, accounting for nullingrels in the grouping expressions
could prevent us from matching a grouping expression to expressional
index columns or to the expressions in extended statistics, as these
expressions are not decorated with any nullingrels bits. As an
example, consider

create table t (a int, b int);
insert into t select i%10, i%10 from generate_series(1,1000)i;
create statistics s (ndistinct) on (a+b), (a-b) from t;
analyze;

-- after v16
explain (costs on)
select count(*) from t t1 left join t t2 on t1.a = t2.a group by t2.a+t2.b;
QUERY PLAN
--------------------------------------------------------------------------
HashAggregate (cost=1920.00..1921.25 rows=100 width=12)
Group Key: (t2.a + t2.b)
-> Hash Left Join (cost=27.50..1420.00 rows=100000 width=4)
Hash Cond: (t1.a = t2.a)
-> Seq Scan on t t1 (cost=0.00..15.00 rows=1000 width=4)
-> Hash (cost=15.00..15.00 rows=1000 width=8)
-> Seq Scan on t t2 (cost=0.00..15.00 rows=1000 width=8)
(7 rows)

-- before v16
explain (costs on)
select count(*) from t t1 left join t t2 on t1.a = t2.a group by t2.a+t2.b;
QUERY PLAN
--------------------------------------------------------------------------
HashAggregate (cost=1920.00..1920.12 rows=10 width=12)
Group Key: (t2.a + t2.b)
-> Hash Left Join (cost=27.50..1420.00 rows=100000 width=4)
Hash Cond: (t1.a = t2.a)
-> Seq Scan on t t1 (cost=0.00..15.00 rows=1000 width=4)
-> Hash (cost=15.00..15.00 rows=1000 width=8)
-> Seq Scan on t t2 (cost=0.00..15.00 rows=1000 width=8)
(7 rows)

Attached is a more formal patch to strip out all the nullingrels from
the grouping expressions before we estimate number of groups.

Thanks
Richard

On Wed, Dec 25, 2024 at 11:34 AM Andrei Lepikhov <lepihov@gmail.com> wrote:

I have a couple of notes.
1. The nulling_relids provides us sensible information about possible
nulls inside the input. We are not using it to estimate the number of
such nulls for now. Does Your idea consist of obtaining 'clear'
statistics and reusing nulling_relids knowledge somewhere later?

Are you referring to the nullfrac estimates? A RelOptInfo's
nulling_relids records all above outer joins that can null this rel.
However, I cannot see how it helps with nullfrac.

2. It is ok for Vars. But what about expressions? We use equal() in
distinct, MCV and dependencies modules. Do we need to remove nulls
before using extended statistics as a general rule?

AFAIU, the expressions in extended statistics are not decorated with
any nullingrels bits, are they?

Thanks
Richard

On Wed, Dec 25, 2024 at 5:14 PM Richard Guo <guofenglinux@gmail.com> wrote:

On Wed, Dec 25, 2024 at 11:34 AM Andrei Lepikhov <lepihov@gmail.com> wrote:

2. It is ok for Vars. But what about expressions? We use equal() in
distinct, MCV and dependencies modules. Do we need to remove nulls
before using extended statistics as a general rule?

AFAIU, the expressions in extended statistics are not decorated with
any nullingrels bits, are they?

I've just realized that there may be other places with similar issues,
not just in estimate_num_groups. For instance,

-- after v16
explain (costs on)
select * from t t1 left join t t2 on true where (t2.a+t2.b) is null;
QUERY PLAN
--------------------------------------------------------------------
Nested Loop Left Join (cost=0.00..15032.50 rows=5000 width=16)
Filter: ((t2.a + t2.b) IS NULL)
-> Seq Scan on t t1 (cost=0.00..15.00 rows=1000 width=8)
-> Materialize (cost=0.00..20.00 rows=1000 width=8)
-> Seq Scan on t t2 (cost=0.00..15.00 rows=1000 width=8)
(5 rows)

-- before v16
explain (costs on)
select * from t t1 left join t t2 on true where (t2.a+t2.b) is null;
QUERY PLAN
--------------------------------------------------------------------
Nested Loop Left Join (cost=0.00..15032.50 rows=1 width=16)
Filter: ((t2.a + t2.b) IS NULL)
-> Seq Scan on t t1 (cost=0.00..15.00 rows=1000 width=8)
-> Materialize (cost=0.00..20.00 rows=1000 width=8)
-> Seq Scan on t t2 (cost=0.00..15.00 rows=1000 width=8)
(5 rows)

In v16 and later, the nullingrels within the expression "t2.a + t2.b"
prevent it from being matched to the corresponding expression in
extended statistics, forcing us to use DEFAULT_UNK_SEL(0.005).

It seems that we need to strip out the nullingrels bits from
expressions before matching them to extended statistics or
expressional index columns in more places.

Thanks
Richard

On 25/12/2024 16:36, Richard Guo wrote:

On Wed, Dec 25, 2024 at 5:14 PM Richard Guo <guofenglinux@gmail.com> wrote:

On Wed, Dec 25, 2024 at 11:34 AM Andrei Lepikhov <lepihov@gmail.com> wrote:

2. It is ok for Vars. But what about expressions? We use equal() in
distinct, MCV and dependencies modules. Do we need to remove nulls
before using extended statistics as a general rule?

AFAIU, the expressions in extended statistics are not decorated with
any nullingrels bits, are they?

I've just realized that there may be other places with similar issues,
not just in estimate_num_groups. For instance,

I'm pleased to see that you've grasped my initially unclear idea. Yeah,
it seems that all types of statistics may be lost because of varnullingrels.

In v16 and later, the nullingrels within the expression "t2.a + t2.b"
prevent it from being matched to the corresponding expression in
extended statistics, forcing us to use DEFAULT_UNK_SEL(0.005).

It seems that we need to strip out the nullingrels bits from
expressions before matching them to extended statistics or
expressional index columns in more places.

I think Tomas Vondra may have a decisive opinion in this place: we have
already discussed some approaches to calculate NULLs generated by RHS of
Left Join shortly.
Maybe we can commit a quick cure like the one provided in your patch,
but we should remember this example - it is not apparent to me how to
estimate a group of clauses in the case when part of Vars has
varnullingrels and part of them - doesn't.

Also, I think this is a good example that an explain analyse summary
could have some sort of extended statistics usage report. It can help to
clearly identify cases when extended statistics don't work, but should.
- something like already implemented in SQL Server.

--
regards, Andrei Lepikhov

On Wed, Dec 25, 2024 at 6:36 PM Richard Guo <guofenglinux@gmail.com> wrote:

In v16 and later, the nullingrels within the expression "t2.a + t2.b"
prevent it from being matched to the corresponding expression in
extended statistics, forcing us to use DEFAULT_UNK_SEL(0.005).

Furthermore, even without extended statistics or expressional index
columns, the nullingrels can still cause issues with selectivity
estimates. They may cause examine_variable to fail in identifying a
valid RelOptInfo for an expression, making the relation size not
available, which is required in many cases. For instance,

create table t (a int, b int);
insert into t select i, i from generate_series(1,10)i;
analyze t;

-- in v16 and later
explain (costs on)
select * from t t1
left join t t2 on true
left join t t3 on t1.a = t3.a and t3.a < 8
where t1.a = coalesce(t2.a);
QUERY PLAN
-----------------------------------------------------------------------
Nested Loop Left Join (cost=0.00..4.94 rows=1 width=24)
Join Filter: (t1.a = t3.a)
-> Nested Loop Left Join (cost=0.00..3.73 rows=1 width=16)
Filter: (t1.a = COALESCE(t2.a))
-> Seq Scan on t t1 (cost=0.00..1.10 rows=10 width=8)
-> Materialize (cost=0.00..1.15 rows=10 width=8)
-> Seq Scan on t t2 (cost=0.00..1.10 rows=10 width=8)
-> Seq Scan on t t3 (cost=0.00..1.12 rows=7 width=8)
Filter: (a < 8)
(9 rows)

-- in v15 and before
explain (costs on)
select * from t t1
left join t t2 on true
left join t t3 on t1.a = t3.a and t3.a < 8
where t1.a = coalesce(t2.a);
QUERY PLAN
-----------------------------------------------------------------------
Hash Left Join (cost=1.21..5.04 rows=10 width=24)
Hash Cond: (t1.a = t3.a)
-> Nested Loop Left Join (cost=0.00..3.73 rows=10 width=16)
Filter: (t1.a = COALESCE(t2.a))
-> Seq Scan on t t1 (cost=0.00..1.10 rows=10 width=8)
-> Materialize (cost=0.00..1.15 rows=10 width=8)
-> Seq Scan on t t2 (cost=0.00..1.10 rows=10 width=8)
-> Hash (cost=1.12..1.12 rows=7 width=8)
-> Seq Scan on t t3 (cost=0.00..1.12 rows=7 width=8)
Filter: (a < 8)
(10 rows)

In v16 and later, when calculating the join selectivity for "t1.a =
coalesce(t2.a)", eqjoinsel sets nd2 — the number of distinct values of
coalesce(t2.a) — to DEFAULT_NUM_DISTINCT (200) because the
corresponding RelOptInfo is not identifiable. This results in very
inaccurate join selectivity.

I'm wondering if we also need to strip out the nullingrels from the
expression in examine_variable(). I tried doing so and noticed a plan
diff in regression test join.sql.

@@ -2573,10 +2573,11 @@
                ->  Materialize
                      ->  Seq Scan on int4_tbl t2
                            Filter: (f1 > 1)
-         ->  Seq Scan on int4_tbl t3
+         ->  Materialize
+               ->  Seq Scan on int4_tbl t3
    ->  Materialize
          ->  Seq Scan on int4_tbl t4
-(13 rows)
+(14 rows)

Thanks
Richard

On Fri, Dec 27, 2024 at 1:16 PM Richard Guo <guofenglinux@gmail.com> wrote:

I'm wondering if we also need to strip out the nullingrels from the
expression in examine_variable(). I tried doing so and noticed a plan
diff in regression test join.sql.

Here is an updated patch that implements this change, and also moves
the removal of the nullingrels within grouping expressions from
estimate_num_groups to add_unique_group_var.

I'm not quite sure how this change affects the exprs_known_equal call
in add_unique_group_var, possibly making it even less precise (it is
alreay somewhat fuzzy, as we do not provide a valid opfamily).
However, I think it should be fine for estimation purposes. Moreover,
in many cases, such as with groupClause, distinctClause, and
WindowClause's PARTITION BY clauses, we have already removed any items
that can be proven redundant.

Regarding the back-patch, this patch is a bug fix, which suggests it
should be back-patched. However, it also changes some plans by fixing
the cost estimation. Does anyone know what our usual approach is in
this situation?

Thanks
Richard

On Tue, Dec 31, 2024 at 5:40 PM Richard Guo <guofenglinux@gmail.com> wrote:

Regarding the back-patch, this patch is a bug fix, which suggests it
should be back-patched. However, it also changes some plans by fixing
the cost estimation. Does anyone know what our usual approach is in
this situation?

Although this patch could result in plan changes, it fixes an actual
bug, so I've back-patched it to v16.

Thanks
Richard